2. The Bisection Method

When we want to find a root of a function, we have to know something about it; a general (not necessarily continuous) function could have a root anywhere. So we postulate that our function $f$ is continuous; this is reasonable, because $f$ is often derived from some physical model. Suppose now that we have an interval $[a,b]$, with $f(a)$ and $f(b)$ having different signs, or in other words:

$$f(a) f(b) < 0.$$

It follows then from elementary analysis that the interval $[a,b]$ will contain at least one root of the function $f$. Suppose now that we have in some way got an approximation to this root, say $c$, with $a < c < b$. We can then evaluate $f$ in $c$. There are now 3 possibilities:

1. $f(c) = 0$; we have found the root, but this is "infinitely unlikely" to occur
2. $f(a) f(c) < 0$; we know the root lies in the interval $[a,c]$
3. $f(b) f(c) < 0$; we know the root lies in the interval $[c,b]$

So if $c$ isn't the real root, we can at least update our interval and get a smaller one, that still contains the root. If we repeat this often enough, we can make the interval $[a,b]$ smaller and smaller, and we hope that in this way, we can get a sufficient accurate approximation to the root.

Now, how do we determine $c$? The simplest solution is to take $c$ to be the middle of the interval $[a,b]$. We then effectually cut the interval in half at each iteration. So we call this method the Bisection Method.

Enough theory; time for some practice. When you scroll a little down, you will find an applet with which you can see the process in action. Click on Leontine, and see what happens. Then, try other functions, and see how it works, but make sure that your function has different signs in the start and ending point of your interval! If you are using the Numerical Toolbench for the first time, here are some hints for using these applets:

1. You can center the graph at the position of the mouse cursor by clicking the mouse while holding the SHIFT-button down.
2. When you want to try a different starting interval, you can drag the triangular markers with the mouse to the new starting points.
3. You can start again by pressing Clear.
4. When you are "lost" somewhere in the graph, you can press Home to get back at your starting point.
5. A table of the generated numbers is shown on the Java Console.