Bisection method working principle

The bisection method is a bracketing method based on the Intermediate Value Theorem: if f(x) is continuous on [a, b] and f(a)·f(b) < 0, then f(x) = 0 has at least one real root between a and b.

Working principle

1. Choose a and b such that f(a) and f(b) have opposite signs.
2. Find the midpoint c = (a + b)/2.
3. Test the sign of f(c):
   • if f(c) = 0, c is the root;
   • if f(a)·f(c) < 0, the root lies in [a, c], so set b = c;
   • otherwise the root lies in [c, b], so set a = c.
4. The new interval is exactly half as long as the old one and still contains the root. Repeat from step 2.
5. Stop when the interval length (b − a) is less than the tolerance, or |f(c)| is very small. The last midpoint is the root.

 a                  c                  b
 |------------------|------------------|
 f(a)<0           f(c)>0             f(b)>0
 root is in [a, c]  ->  set b = c

Error and iterations

After n steps the interval length is (b − a)/2ⁿ, so the error is at most (b − a)/2ⁿ. For tolerance e the number of iterations needed is

n ≥ [log(b − a) − log(e)] / log 2

Example: for f(x) = x² − 2 on [1, 2], c = 1.5 gives f(c) = 0.25 > 0 and f(1) < 0, so the root is in [1, 1.5]; next c = 1.25, and so on toward √2 = 1.4142.

Features

• Always converges (if the initial interval is valid), but slowly (linear convergence).
• Needs only function values, not derivatives.
• Cannot find roots where the curve touches the axis without crossing (even multiplicity).