Bisection method

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

The absolute error for the bisection method is at most

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

after n steps when f is continuous on an interval [a, b] and f(a)f(b) < 0. 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.

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(xL) 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

Reference

Richard L. Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0534382169