Up to Main Lab Page | Next Lesson - Newton's Method | Previous Lesson - Finding Roots |
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.
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.
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 a_{0} and b_{0} are the
original choice for the interval after the n^{th} iteration we know
that d is within
|b_{0} - a_{0}|/2^{n}
of the true root.
We define the error at the n^{th} step,
E_{n}, to be the difference between the
true root, c and our aproximation at the n^{th}
step, d_{n}.
i.e. E_{n} = |c - d_{n}|.
Thus: E_{n} <= |b_{0} - a_{0}|/2^{n}
Note that at the end of the n^{th} iteration of the loop
|b - a| is greater than or equal to E_{n}.
This provides us with a practiacal way to calculate the error after each
iteration.
Note that E_{n} = ½ E_{n-1}.
Thus the error in the Bisection method decreases linearly.
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 10^{20} 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;
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 |