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
- <math> \frac{b-a}{2^{n+1}} <math>
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.
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
References
Richard L. Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0534382169de:Bisektion zh:二分法