The Bisection Method

  Suppose that we have a function f of one argument and we want to find a real number x such that f(x) = 0. As you know, there can be zero or more solutions to an equation of this form. We are interested in finding one of them.

The bisection method works by assuming that we know of two values h and l such that f(h) > 0 and f(l) < 0. If this is the case (and the function f is continuous), then there must be at least one value v that falls between h and l such that f(v) = 0.

This fact is best appreciated graphically. Suppose that we want to find a root of the function

f := x -> cos(x) - x;

It is easy to verify that f(0) is positive whereas f(1) is negative. If we plot f between these two points

plot(f(x), x=0..1);

we see that since the plot crosses the x-axis, there must be a root between 0 and 1.

The bisection method works by repeatedly narrowing the gap between h and l until it closes in on the correct answer. It narrows the gap by taking the average v of h and l. If f(v) is positive, then v becomes the new value of h. If f(v) is negative, then v becomes the new value of l. In either event, we still have the root bracketed by h and l. If we repeat this process long enough, we'll eventually converge down to a good approximation to that root.

Let's look at a couple of repetitions through this algorithm. The average of 0 and 1 is 0.5, and f(0.5) is positive. Thus, our new value for h is 0.5, and our value for l remains 1.0. Let's plot this:

plot(f(x), x=0.5..1);

Notice that the scale of the x-axis is half what it was before. We're narrowing in on an answer.

The average of 0.5 and 1 is 0.75, and f(0.75) is negative. Thus, our new value for l is 0.75 and our value for h remains 0.5. Let's plot this:

plot(f(x), x=0.5..0.75);

We can continue this process until our root is close enough.