Bisection method

From Wikipedia, the free encyclopedia

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 works by repeatedly dividing an interval in half and then selecting the subinterval in which the 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. 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 to the sub-interval where the sign change occurs, meaning that the bisection algorithm is inherently recursive.

The bisection method is less efficient than Newton's method but it is much less prone to 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 for the bisection method is at most

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

after n steps. In other words, the error is halved at every step, so 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 sign.

1 Pseudo-code
2 See also
3 External links
4 Reference

[edit] Pseudo-code

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

'Bisection Method

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