Bisection Method

11 Key excerpts on "Bisection Method"

• 

  eBook - PDF

  An Introduction to Numerical Methods and Analysis

  • James F. Epperson(Author)
  • 2014(Publication Date)
  • Wiley

    (Publisher)

  An Introduction to Numerical Methods and Analysis, Second Edition. By James F. Epperson 89 Copyright © 2013 John Wiley & Sons, Inc. 90 ROOT-FINDING 3.1 THE Bisection Method Bisection is a marvelously simple idea that is based on little more than the continuity of the function /. Suppose we know that f(a)f(b) < 0. This means that / is negative at one point and positive at the other. If we assume that / is continuous, then it follows (by the Intermediate Value Theorem) that there must be some value between a and b at which / is zero. In other words, we know that there is a root a between a and b. (Note: There may be more than one root in the interval.) Now let's try to use these ideas to find a. Let c be the midpoint of the interval [a, b], i.e., c=\(a + b) and consider the product /(a)/(c). There are three possibilities: 1. f(a)f(c) < 0; this means that a root (there might be more than one) is between a and c, i.e., a G [a,c\. 2. f(a)f(c) = 0; if we assume that we already know /(α) 0, this means that /(c) = 0, thus a = c and we have found a root. 3. f{a)f(c) > 0; this means that a root must lie in the other half of the interval, i.e., a e [c,b\. At first glance, this is helpful only if we get the second case and land right on top of a root, and this does not seem very likely. However, a second look reveals that if (1) or (3) hold, we now have a root localized to an interval ([a, c] or [c, b]) that is half the length of the original interval [a, b]. If we now repeat the process, the interval of uncertainty is again decreased in half, and so on, until we have the root localized to within any tolerance we desire.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Numerical Methods in Engineering with MATLAB®

  • Jaan Kiusalaas(Author)
  • 2015(Publication Date)
  • Cambridge University Press

    (Publisher)

  The method of bisection accomplishes this by successively halving the interval until it becomes sufficiently small. This technique is also known as the interval halving method . Bisection is not the fastest method available for computing roots, but it is the most reliable. Once a root has been bracketed, bisection will always close in on it. The method of bisection uses the same principle as incremental search: if there is a root in the interval ( x 1 , x 2 ) , then f ( x 1 ) · f ( x 2 ) < 0. To halve the interval, we compute f ( x 3 ) , where x 3 = 1 2 ( x 1 + x 2 ) is the midpoint of the interval. If f ( x 2 ) · f ( x 3 ) < 0, then the root must be in ( x 2 , x 3 ) and we record this by replacing the original bound x 1 by x 3 . Otherwise, the root lies in ( x 1 , x 3 ) , in which case x 2 is replaced by x 3 . In either case, the new interval ( x 1 , x 2 ) is half the size of the original interval. The bisection is repeated until the interval has been reduced to a small value ε , so that x 2 − x 1 ≤ ε It is easy to compute the number of bisections required to reach a prescribed ε. The original interval x is reduced to x / 2 after one bisection, x / 2 2 after two bisections, 4.3 Method of Bisection 143 and after n bisections it is x / 2 n . Setting x / 2 n = ε and solving for n , we get n = ln ( | x | /ε) ln 2 (4.1) Clearly the method of bisection converges linearly, because the error behaves as E k + 1 = E k / 2. bisect This function uses the method of bisection to compute the root of f ( x ) = 0 that is known to lie in the interval ( x1,x2 ). The number of bisections n required to reduce the interval to tol is computed from Eq. ( 4.2 ). The input argument filter controls the filtering of suspected singularities. By setting filter = 1 , we force the routine to check whether the magnitude of f ( x ) decreases with each interval halving. If it does not, the “root” may not be a root at all, but a singularity, in which case root = NaN is returned.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Numerical and Statistical Methods for Bioengineering

  Applications in MATLAB

  • Michael R. King, Nipa A. Mody(Authors)
  • 2010(Publication Date)
  • Cambridge University Press

    (Publisher)

  The Bisection Method searches for the root by depleting the size of the bracketing interval by half so that the location of the root is known with an accuracy that doubles with every iteration. If our initial interval is [ a , b ], then we proceed as follows ( Figure 5.3 illustrates these steps). (1) Bisect the interval such that the midpoint of the interval is x 1 ¼ð a þ b Þ = 2 : Unless x 1 is precisely the root, i.e. unless f ( x 1 ) = 0, the root must lie either in the interval [ a , x 1 ] or in [ x 1 , b ]. (2) To determine which interval contains the root, f ( x 1 ) is calculated and then compared with f ( a ) and f ( b ). Figure 5.2 Plot of a function that contains a double root. At the double root, the function does not cross the x -axis, but is tangent to the axis. -1 0 1 2 3 4 5 -20 -10 0 10 20 f ( x ) = x 3 -6 x 2 + 9 x -4 x f ( x ) Double root at x = 1 Single root at x = 4 313 5.2 Bisection Method (a) If f ð a Þ f ð x 1 Þ 5 0, then the root is located in the interval [ a , x 1 ], and the current value of b is replaced by x 1 , i.e. b = x 1 . The new interval is half the size of the previous starting interval. (b) If f ð a Þ f ð x 1 Þ 4 0, the root lies within [ x 1 , b ], and a is set equal to x 1 . (3) The bisection step is repeated to find the midpoint, x 2 , of the new bracketing interval, which is either [ a , x 1 ] or [ x 1 , b ]. Then, the next smaller interval that encloses the root is selected. In Figure 5.3 , the interval [ x 2 , x 1 ] is found to bracket the root. This new interval is one-quarter the size of the original interval [ a , b ]. (4) The iterative process is stopped when the algorithm has converged upon a solution. The criteria for attaining convergence are discussed below. We must specify certain criteria that establish whether we have arrived at a solution. After every iteration, the solution should be tested for convergence to determine whether to continue the Bisection Method or terminate the process.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Theory and Applications of Numerical Analysis

  • G. M. Phillips, Peter J. Taylor(Authors)
  • 1996(Publication Date)
  • Academic Press

    (Publisher)

  n → ∞ so that in principle we may compute the root as accurately as we wish.

  8.2 The Bisection Method

  Suppose that f is continuous on some interval [x 0 , x 1 ] and that f(x 1 ) and f(x 1 ) have opposite signs, as in Fig. 8.2 . There is at least one root of f(x) = 0 in the interval [x 0 , x 1 ], which we shall denote by I 0 . We now bisect I 0 , writing x 2 = (x 0 + x 1 )/2, and let I 1 , denote the sub-interval [x 0 , x 2 ] or [x 2 , x 1 ] at whose endpoints f takes opposite signs. Similarly I 1 is bisected to give an interval I 2 (half the width of I 1 ) at whose endpoints f still has opposite signs, and so on (see Fig. 8.2 ). This bracketing method is called the bisection method.

  Fig. 8.2 The bisction method.

  Algorithm 8.1

  (Bisection Method) We begin with x 0 < x 1 , and y 0 = f(x 0 ), y 1 = f(x 1 ) with y 0 y 1 < 0.

  repeat

  (8.4)

    y 2 := f(x 2 )

    if y 1 y 2 < 0 then x o := x 2  y 0 := y 2

          else x 1 := x 2  y 1 := y 2

  until x 1 − x 0 l0−6

  The algorithm terminates when the root is pinned down in an interval of at most 10−6 . We may select the midpoint of this last interval to approximate the root, with an error not greater than (The number 10−6 which we have chosen in our stopping criterion, can be adjusted. However, we need to avoid making this number so small that the operation of the algorithm is confused by rounding error.) Advantages of the Bisection Method are its simplicity and the fact that we may predict, in advance, how many iterations of the main ‘loop’ of calculations will be required since the interval is halved during each iteration. For example, if initially x 1 − x 0 = 1, the number of iterations or bisections necessary will be 20, since 2−20 < 10−6 < 2−19

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Numerical Methods with Python

  for the Sciences

  • William Miles(Author)
  • 2023(Publication Date)
  • De Gruyter

    (Publisher)

  5 Iteration While solving linear systems is probably the most common task in applied mathematics, another often-used concept for solving problems algorithmically is iteration. We use iteration primarily for two functions: – to advance in time; – to improve upon a previous approximation. To introduce iteration as a process, we begin by showing a powerful but simple method to find the roots of a function. 5.1 Finding roots: the Bisection Method Suppose we have a continuous function f (x), as shown below, and we wish to find the roots (or zeros) of the function, indicated by black dots. That is, we wish to solve f (x) = 0. If we can find numbers a and b such that f (a) and f (b) have opposite signs, then the intermediate value theorem assures us that there is a value c, between a and b, such that f (c) = 0. From the graph, we can see that f (−3) < 0 and f (−2) > 0. Therefore, there is a root between x = −3 (playing the role of a) and x = −2 (playing the role of b). Thus, we could take the midpoint between a and b as our first approximation of the root. Taking the midpoint is equivalent to bisecting the interval [a, b]. So, let x 1 = a+b 2 . In our example, we have x 1 = −3+−2 2 = −2.5 as can be seen in the next graph. https://doi.org/10.1515/9783110776645-005 72 � 5 Iteration Now, if f (x 1 ) = 0, then we are done, and x 1 is a root. Otherwise, either: (a) f (x 1 ) and f (a) have different signs or (b) f (x 1 ) and f (b) have different signs. If (a) is true, then we know the root lies between a and x 1 . If (b) is true, then the root lies between b and x 1 . In the function shown, we see that f (−2.5) is negative. Thus, there must be a root between x = −2.5 and x = −2. The function value at x 1 = −2.5 is approximately f (−2.5) = −0.08534. Now we can reassign a to be −2.5 and leave b as it was. We can zoom in on the graph for the new interval. Notice that the interval [−2.5, −2] is half as wide as the original interval [−3, −2].

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  An Introduction to Numerical Methods Using MATLAB

  • K. Akbar Ansari Ph.D., P.E., Bonni Dichone Ph.D.(Authors)
  • 2019(Publication Date)
  • SDC Publications

    (Publisher)

  3.1: Bisection Method Procedure for Finding Roots 1. Choose starting and ending points xstart and xend . 2. Compute: f ( xstart ) and f ( xend ) . 3. Compute: f ( xstart ) times f ( xend ) . 4. If the above product is negative, then the root lies between xstart and xend . If this product is positive, reselect xstart and xend . 5. If f ( xstart ) * f ( xend ) < 0, compute the mid-point of the xstart - xend range. Call it “ xmid 1 ” and repeat above steps, i.e. compute f ( xstart ) * f ( xmid 1 ) and f ( xmid 1 ) * f ( xend ) . 3.3 Bisection Method 31 6. If f ( xstart ) * f ( xmid 1 ) < 0, the root lies between xstart and xmid 1 . If f ( xmid 1 ) * f ( xend ) < 0, then the root lies between xmid 1 and xend . 7. Repeat the above procedure until convergence at a root value occurs. Computation of Error and Convergence Criterion A convergence criterion has to be followed in order to determine if a root has indeed been found. This is expressed in terms of the error ε or the percentage relative error ε rel which are defined as ε = | xmid i +1 - xmid i | , (3.1) ε rel = xmid i +1 - xmid 1 xmid i +1 * 100 percent , (3.2) where xmid i +1 and xmid i are the midpoints in the current and previous iterations. While, in general, the relative error should not be greater than 5%, an error of 0.01% is the largest that is tolerable for some classes of problems that require immense precision. The true error, ε True , is an indicator of the real accuracy of a solution and can be evaluated only if the true solution, x True , is known. It is defined as ε True = x True - xmid i x True * 100. (3.3) Calculation of the true error clearly requires knowledge of the true solution, which, in general, will not be known to us. Therefore, the quantity ε rel may have to be mostly used to determine the error associated with a solution process.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introduction to Numerical Analysis and Scientific Computing

  • Nabil Nassif, Dolly Khuwayri Fayyad(Authors)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  st was needed to meet the termination condition.
• Let f (x ) = x 4 − x 3 − x − 1. Search for the root of f in the interval [0, 3] with ϵ = 0.5 × 10 − 4 (5 significant figures rounded). The results of the bisection iterates are given in Table 2.3 .
Table 2.4 illustrates the convergence of the sequence of intervals {(
an
,
bn
)|n = 1, 2, 10}, generated by the Bisection Method for the function
f ( x ) = ln ( 1 + x ) −
1
1 + x
, as proved in Theorem 2.1. Computations are carried out up to 3 significant figures. To conclude, the bisection is a multistep method that, although conceptually clear and simple, has significant drawbacks since, as theory and practice indicate, it is a slowly convergent method. However it globally converges to the searched solution and can be used as a starter to more efficient locally convergent methods, notably both the Newton’s and secant methods.

2.4 Newton’s Method

Newton’s (or Newton-Raphson’s ) method is one of the most powerful numerical methods for solving non-linear equations. It is also referred to as the tangent method , as it consists in constructing a sequence of numbers {

rn

|

rn

∈ (a , b )∀n ≥ 1}, obtained by intersecting tangents to the curve y = f (x ) at the sequence of points {(r

n − 1

, f (r

n − 1

))|n ≥ 1} with the x-Axis. Constructing such tangents and such sequences requires additional assumptions to 2.2 − 2.5 as derived hereafter.

To start, let r 0 ∈ (a , b ) in which the root is located, and let M 0 = (r 0 , f (r 0 )) be the point on the curve

{ ( C ) | y = f ( x ) , a ≤ x ≤ b } .

Let also (𝒯0 ) be the tangent to (𝒞) at M 0 with equation given by:

y =

f '

(

r 0

) ( x −

r 0

) + f (

r 0

)

The intersection of (𝒯0 ) with the x-Axis is obtained for y = 0 and is given by:

r 1

=

r 0

−

f (

r 0

)

f ’ (

r 0

)

(2.19)

To insure that r

1 ∈ (

a , b ) , r 0 should be chosen “close enough” to r . Specifically, since f (r ) = 0, 2.19