45
4.10 Summary
203
set of steps that aim to improve the approximation. Our particular
method for computing roots, the Bisection method, guarantees to find an
approximate root, while other methods, such as the widely used Newton’s
method (see Section A.1.10), can fail to find roots.
The idea of the Bisection method is to start with an interval [a,b] that
contains a root off(x). The interval is halved atm = (a +b)/2, and if
f(x)changessigninthelefthalfinterval[a,m],onecontinueswiththat
interval, otherwise one continues with the right half interval [m,b]. This
procedure is repeated, sayn times, and the root is then guaranteed to
be inside an interval of length 2−n(b−a). The task is to write a program
that implements the Bisection method and verify the implementation.
Solution. ToimplementtheBisectionmethod,weneedtotranslatethe
description in the previous paragraph to a precise algorithm that can be
almost directly translated to computer code. Since the halving of the
interval is repeated many times, it is natural to do this inside a loop. We
start with the interval [a,b], and adjusta tom if the root must be in
the right half of the interval, or we adjustb tom if the root must be in
the left half. In a language close to computer code we can express the
algorithm precisely as follows:
for i = 0,1,2, ..., n:
m = (a + b)/2
if f(a)*f(m) <= 0:
b = m # root is in left half
else:
a = m # root is in right half
# f(x) has a root in [a,b]
Figure 4.2 displays graphically the first four steps of this algorithm for
solving the equationcos(πx) = 0, starting with the interval [0,0.82]. The
graphs are automatically produced by the programbisection_movie.py,
which was run as follows for this particular example:
Terminal
bisection_movie.py ’cos(pi*x)’ 0 0.82
The first command-line argument is the formula forf(x), the next isa,
and the final is b.
In the algorithm listed above, we recomputef(a) in eachif-test, but
this is not necessary ifa has not changed since the lastf(a) computations.
It is a good habit in numerical programming to avoid redundant work.
On modern computers the Bisection algorithm normally runs so fast
that we can afford to do more work than necessary. However, iff(x)
is not a simple formula, but computed by comprehensive calculations
in a program, the evaluation of f f might take minutes or even hours,
and reducing the number of evaluations in the Bisection algorithm is
then very important. We will therefore introduce extra variables in the