Ryerson Crest Ryerson Header

MTH 207 Lab Lesson 12

The Bisection Method

Up to Main Lab Page Next Lesson - Newton's Method Previous Lesson - Finding Roots

The Bisection Method

[See section 1.5 of Stewart]

The bisection method is the simplest of the root finding methods. When given this problem from scratch this is the method that most people come up with.

The bisection method relies on the Intermediate Value Theorem:

If f is continuous on the closed interval [a,b] and N is any number between f (a) and f (b), then there exists a number c in the open interval (a,b) such that f (c) = N.

Since the method relies on this theorem it requires that f be continuous on some interval near the root.

The idea is that we find two points a and b such that f (a) > 0 and f (b) < 0.
Then by the theorem, taking N = 0, there must be a c between a and b such that f (c) = 0.
If we now take the midpoint of a and b, d = (a + b)/2, we will either have f (d) > 0 or f (d) < 0.
If f (d) < 0, then the root must lie between a and d (by the Theorem, since f (d) < 0 and f (a) > 0).
If f (d) > 0, then the root must lie between d and b (by the Theorem, since f (d) > 0 and f (b) < 0).
Either way we now have a "bisected" interval half the size which must contain the root.

The Algorithm

Pick a and b such that f (a) > 0 and f (b) < 0 and f is continuous from a to b.
Repeat:
let d := (a+b)/2.
If f (d) < 0,
Let b := d.
Else if f (d) > 0,
Let a := d.
Return d

Note that the algorithm must be provided with an initial a and b, as a starting guess. It is often the case with numerical methods that we must get the method going by providing a reasonable guess to start with. A plot is often useful for determining reasonable starting values.

Methodological Error or Accuracy

We still have the question of how many times to iterate the loop. Usually what we require is that the answer be within a certain amount of the true answer. In order to know how close we are at each iteration we calculate the error associated with the method. This also gives a useful measure of the efficiency of the algorithm, since it tells us how many iterations we will need in order to get within a given amount of the true answer.

At the first iteration we know that the root, c, is within |b - a|/2 of d, i.e. c = d ± |b - a|/2.
Each subsequent iteration halves the interval. Thus if a0 and b0 are the original choice for the interval after the nth iteration we know that d is within |b0 - a0|/2n of the true root.

We define the error at the nth step, En, to be the difference between the true root, c and our aproximation at the nth step, dn.
i.e. En = |c - dn|.

Thus: En <= |b0 - a0|/2n

Note that at the end of the nth iteration of the loop |b - a| is greater than or equal to En.
This provides us with a practiacal way to calculate the error after each iteration.

Note that En = ½ En-1.
Thus the error in the Bisection method decreases linearly.

Example

We will attempt to solve the equation cos2(x) = x.
We first put this equation in the form f (x) = 0, by putting f (x) = cos2(x) - x.
> f := x -> cos(x)^2 - x;

Next we do a plot to find suitable starting values for a and b.
> plot(f(x), x = -Pi..Pi);

Looking at the graph it appears that the root is somewhere between 0 and 1. We take these as our starting values.
> a:= 0;
> b:= 1;

Now we need an error term, how close do we want to get to the answer? We will require an answer within 1020 of the correct answer.
> error := 10^(-20);

Now we implement the algorithm:
> while abs(b-a) > error
> do
> d := (a+b)/2;
> if evalf(f(d)) > 0 then a := d;
> else b := d;
> fi;
> od:

Note the colon ':' in the od: line, rather than a semicolon ';'. This tells Maple that we don't want to see the intermediate calculations of the do loop. If you want to see these calculations replace the ':' with a ';'.

Finally we can see the answer:
> d;

Maple has kept the result as a fraction so to see the decimal form we can use evalf.
> evalf(d);
> evalf(f(d));

But f (d) is 0.2 × 10-9, with 20 digits accuracy in d we would expect a result closer to 0. What went wrong?
The answer is that the default value for Digits is only 10, thus we will never get d to 20 digits accuracy, we were lucky that the algorithm terminated at all.
This highlights how numerical methods are extremely susceptible to calculational or numerical errors.
We can fix this problem by reseting Digits to a reasonable value for our calculation and running the algorithm again.
> Digits := 40;

  1. Go back and rerun the algorithm with Digits = 40, you should get a value of f (d) within 10-20 of 0.
  2. Rewrite the algorithm for the Bisection method to include a counter, which counts the number of iterations through the loop.
    1. How many iterations did the calculation above take?
    2. If error is set to 10-10, guess how many iterations will be needed.
      Use your program to check your answer.
    3. How close will we get with 10 iterations?
  3. Use the Bisection method to estimate a roots of the following to within 10-10. In each case first estimate the number of iterations needed, and then verify your guess when you run the program. Record the number of iterations needed on a piece of paper.
    1. x^6 + x^4 - 3*x^5 + 5*x^3 - 6*x^2 + 2*x - 1 (both roots).
    2. tan(x) = 2x (principal root).
    3. e^x = 3x.
    4. sin(x) - x^2 has a root at x = 0, find the other root.
  4. sin(Pi/2) = 1, by findng the root of sin(x) - 1, get an estimate for Pi/2 to 20 decimal places. Use this estimate to estimate the value of Pi, how accurate do you think this estimate will be?

Problems With The Bisection Method

The bisection method tends to be slow, needing a large number of iterations relative to other methods.

In addition it cannot find roots of even order.
The order or multiplicity of a root c of a polynomial is the power to which the factor (x - c) is raised.
Roots of order 1 are also called simple roots.
Thus, for example, in (x - 1)3(x - 2)2(x - 3)
1 is a root of order 3,
2 is a root of order 2,
3 is a simple root.

Consider the graph of f (x) = (x - 1)2
plot((x-1)^2, x = 0..2);
 There are no values of f (x) near the root for which f (x) < 0, and so the bisection method will fail.

Up to Main Lab Page Next Lesson - Newton's Method Previous Lesson - Finding Roots Top of this Lesson

Maintained by: P. Danziger, Febuary 1998