Bisection method

The bisection method is a technique for locating real roots of a continuous function.

Process

Applying the bisection method to a function $f(x)$ begins by selecting a lower bound $a$ and an upper bound $b$. The values $f(a)$ and $f(b)$ should have opposite signs, guaranteeing that a root of $f(x)$ lies in the interval $(a,b)$ by the Intermediate Value Theorem.

The method proceeds by considering $c = \frac{a + b}{2}$, the midpoint of the interval. If by chance $f(c) = 0$, then $c$ is the desired root. Otherwise, $f(c)$ has the same sign as either $f(a)$ or $f(b)$, so the process can be repeated with $c$ replacing $a$ or $b$ respectively.

Performance

Bisection halves the width of the interval containing the root at each step. In binary, this corresponds to gaining one digit of precision per iteration. While finding a root exactly at the midpoint of any step is rare, the endpoints of the intervals produced are guaranteed to converge to a root.

The bisection method will not find roots of even multiplicity because $f(x)$ does not change sign at such roots. One way to correct the omission is to use the bisection method on the derivative $f'(x)$, since a root of multiplicity $n$ of $f(x)$ is a root of multiplicity $n - 1$ of $f'(x)$.

See also