Welcome to the MedLibrary.org Wikipedia Supplement on Bisection method -- Please Click to Return to Front Page

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

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.

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

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

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

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

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).

See also

The Wikibook Numerical Methods has a page on the topic of Equation Solving

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

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, ISSN 1095-7200 .

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

Wikipedia content modification information:

• This page was last modified on 29 November 2008, at 14:27.

Wikipedia Authorship and Review

Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.

Wikipedia Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Bisection method".

The URL for this specific entry is:

• http://medlibrary.org/medwiki/Bisection_method

All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.