Bisection method

A few steps of the bisection method applied over the starting range [a₁;b₁]. The bigger red dot is the root of the function.

In mathematics, the bisection method is a root-finding algorithm which repeatedly divides an interval in half and then selects the subinterval in which a root exists. It is a very simple and robust method, but it is also rather slow.

The method

Suppose we want to solve the equation

$f(x)=0,\,$

where f is a continuous function.

The bisection method starts with two points a and b such that f(a) and f(b) have opposite signs. The intermediate value theorem says that f must have at least one root in the interval [a, b]. The method now divides the interval in two by computing c = (a+b) / 2. There are now two possibilities: either f(a) and f(c) have opposite signs, or f(c) and f(b) have opposite signs. The bisection algorithm is then applied recursively to the sub-interval where the sign change occurs.

Explicitly, if f(a) f(c) < 0, then the method sets b equal to c, and if f(b) f(c) < 0, then the method sets a equal to c. In both cases, f(a) and f(b) have again opposite signs, so the method can start again with the points a and b which now lie closer to each other.

Analysis

If f is a continuous function on the interval [a, b] and f(a)f(b) < 0, then the bisection method converges to a root of f. In fact, the absolute error is halved at each step. Thus, the method converges linearly, which is quite slow. On the positive side, the method is guaranteed to converge if f(a) and f(b) have different signs.

The bisection method gives only a range where the root exists, rather than a single estimate for the root's location. Without using any other information, the best estimate for the location of the root is the midpoint of the range. In that case, the absolute error after n steps is at most

${\frac {\left|b-a\right|}{2^{n+1}}}$

If either endpoint of the interval is used, then the maximum absolute error is

${\frac {\left|b-a\right|}{2^{n}}},$

the entire length of the interval.

These formulas can be used to find the number of iterations that the bisection method needs to converge to a root within a certain tolerance. For instance, using the second formula for the error, the number of iterations n has to satisfy

$n>{\frac {\log(b-a)-\log \varepsilon }{\log 2}}$

to make sure that the error is smaller than the tolerance ε.

If f has several roots in the interval [a, b], then the bisection method finds the odd-numbered roots with equal, non-zero probability and the even-numbered roots with zero probability. More precisely, suppose that f has 2k + 1 simple roots x₁ < x₂ < … < x_2k+1 in the interval [a, b] (the number of roots is odd because f(a) and f(b) have opposite signs). Assume that the roots are distributed independently and uniformly in this interval. Then, the probability that the bisection method converges to the root x_i with i = 1, 2, …, 2k + 1 is zero if i is even and 1 / (k + 1) if i is odd (Corliss 1977).

Pseudo-code

Here is a representation of the bisection method in Visual Basic code. The variables left and right correspond to a and b above. The initial left and right must be chosen so that f(left) and f(right) are of opposite sign (they 'bracket' a root). The variable epsilon specifies how precise the result will be.

 'Bisection Method
 
 'Start loop
 Do While (abs(right - left) > 2*epsilon)
   
   'Calculate midpoint of domain
   midpoint = (right + left) / 2
   
   'Find f(midpoint)
   If ((f(left) * f(midpoint)) > 0) Then
     'Throw away left half
     left = midpoint
   Else
     'Throw away right half
     right = midpoint
   End If
 Loop
 Return (right + left) / 2

See also

• Binary search algorithm
• Lehmer-Schur algorithm, generalization of the bisection method in the complex plane
• Nested intervals

References

• Burden, Richard L.; Faires, J. Douglas (2000), Numerical Analysis (7th ed.), Brooks/Cole, ISBN 978-0-534-38216-2.
• Corliss, George (1977), "Which root does the bisection algorithm find?", SIAM Review, 19 (2): 325–327, doi:10.1137/1019044, ISSN 1095-7200.
• Kaw, Autar; Kalu, Egwu (2008), Numerical Methods with Applications (1st ed.). http://numericalmethods.eng.usf.edu/topics/textbook_index.html

External links

• Bisection Method on Mathcad Application Server.
• Bisection Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica from Holistic Numerical Methods Institute
• Module for the Bisection Method by John H. Mathews
• Java Code for Bisection Method by Behzad Torkian
• True example of using bisection method in computer programming free program to isoelectric point calculation