Find roots by bisection

A common computational job is to find the root(s) of a function. That is, for some function $f(x)$, find all the values of $x$ that make $f(x) = 0$. If $f(x)$ $=$ $x^7 - 2$, the root would be $sqrt[7]{2}$, a bit of a job to find before hand-held calculators.

The first step is to make a guess, or two. If you're lucky and guess two numbers $x_1 < x_2$ with $f(x_1) < 0$ and $f(x_2) >0$, then you can make the following conclusion: so long as $f$ is continuous, the interval $[x_1, x_2]$ contains at least one root. ``Proof'' is a picture: the graph of $f$ is above the axis at $x_1$ and below the axis at $x_2$, so somewhere in between it must cross the axis (this ``proof'' of the Intermediate Value Theorem wouldn't get you through Calculus, but it will help you find a root).

The same conclusion holds if $f(x_1) > 0$ and $f(x_2) < 0$. One way to combine the two conditions is: $f(x_1)\times f(x_2) < 0$.

So, we cut the interval in half. Let $x_3$ be $(x_1 + x_2)/2$. There must be a root in either $[x_1, x_3]$ or $[x_3, x_2]$, so we can repeat our test: if $x_3 \not= 0$ (in which case we'd be done), then either $f(x_1)\times f(x_3) < 0$ or $f(x_3) \times f(x_2) < 0$. We can now restrict our search to half the original interval. Keep doing this until the interval is ``small enough.'' If we decide in advance that we want to be within some tolerance factor $t$ of the root $r$, then we keep cutting our interval in half until it is smaller than $t$. Notice that, even if $t$ is small (for example $t=0.00001$), the fact that $f(r) == 0$, doesn't guarantee that $f(r+t)$ is small -- $f$ may have a large slope near $r$.

If you took the approach that you would keep bisecting until the mid-point (call it $m$) of your interval had $f(m) < \epsilon$, then you might have an infinite loop. For example, consider finding the root of $x^2 - 2$ on a computer that could represent 5 decimal digits. If you bisected until you had the interval $[1.4142, 1.4143]$, then the mid-point (in 5-digit precision) would be 1.4143...With this approach, you must specify the maximum number of iterations (loops).

If you repeat this process $i$ times, getting an interval $[x_i, y_i]$, and you return $m_i = (x_i+y_i)/2)$ as your best approximation of the root $r$, you can be assured that $\vert r - m_i\vert$ $\leq$ $(y_i - x_i)/2$. If we denote the length of $k$th interval by $e_k$, then $e_{k+1}$ $=$ $(1/2)e_k^1$, and we say that the bisection method converges linearly (due to the exponent 1).

There are root finding methods that converge with a higher exponent than 1, but they are not guaranteed to converge, whereas bisection always converges once we've made two appropriate initial guesses.