Bisection method

From Wikipedia, the free encyclopedia

A few steps of the bisection method applied over the starting range [a1;b1]. The bigger red dot is the root of the function.
A few steps of the bisection method applied over the starting range [a1;b1]. 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.

Suppose we want to solve the equation f(x) = 0. Given two points a and b such that f(a) and f(b) have opposite signs, we know by the intermediate value theorem that f must have at least one root in the interval [a, b] as long as f is continuous on this interval. The bisection method 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.

The bisection method is less efficient than Newton's method but is not prone to the same odd behavior.

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. After n steps, the maximum absolute error is

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

if the midpoint of the approximation error is used as the estimate for the root. If one endpoint (either a or b) is used, then the maximum absolute error is

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

the entire length of the interval. This inconsistency arises because the bisection method gives only a range where the root exists, rather than a single estimate for the root's location.

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.

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 (Corliss 1977).

Contents

[edit] 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

[edit] See also

[edit] 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 .

[edit] External links