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''] 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 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
:
ight|}{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.

Contents

Pseudo-code

See also

Reference

External links

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 (abs(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

See also

★ Binary search algorithm

★ Lehmer-Schur algorithm, generalization of the bisection method in the complex plane

Reference

★ Richard L. Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0-534-38216-9.

External links

★ Bisection Method on Mathcad Application Server.

★ Bisection Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica

★ Module for the Bisection Method by John H. Mathews

★ True example of using bisection method in computer programming free program to isoelectric point calculation