Bisection Methods Aplication

The equation $f(x)=x^3+4x^2-10=0$ has a root in $[1,2]$ since $f(1)=-5$ and $f(2)=14$. It is easily seen from a sketch of the graph of $f$ in Figure 2.2 that there is only one root in $[1,2].$

Figure 2.2

To use Maple to approximate the root, we define the function $f$ by the command

>f:=x->x^3+4*x^2-10;

The values of $a_{1}$ and $b_{1}$ are given by

>a1:=1; b1:=2;

We next compute $f(a_{1})=-5$ and $f(b_{1})=14$ by


>fa1:=f(a1); fb1:=f(b1);

and the midpoint $p_{1}=1.5$ and $f(p_{1})=2.375$ by


>p1:=a1+0.5*(b1-a1);

>pf1:=f(p1);

Since $f(a_{1})$ and $f(p_{1})$ have opposite signs, we reject $b_{1}$ and let $a_{2}=a_{1}$ and $b_{2}=p_{1}$ . This process is continued to find $p_{2},p_{3},$ and so on.

As discussed in the Preface, each of the methods we consider in the book has an accompanying set of programs contained on the CD that is in the back of the book. The programs are given for the programming languages C, FORTRAN, and Pascal, and also in Maple V, Mathematica, and MATLAB. The program BISECT21, provided with the inputs $a=1,b=2,TOL=0.0005$, and $N_{0}=20$, gives the values in Table 2.1. The actual root $p$, to 10 decimal places, is $p=1.3652300134$, and $\left|p-p_{11}\right|<0.0005$. Since the expected number of iterations is $\log_{2}((2-1)/0.0005)\approx10.96$, the bound $N_{0}$ was certainly sufficient.

Table 2.1

The Bisection method, though conceptually clear, has serious drawbacks. It is slow to converge relative to the other techniques we will discuss, and a good intermediate approximation may be inadvertently discarded. This happened, for example, with $p_{9}$ in Example 1. However, the method has the important property that it always converges to a solution and it is easy to determine a bound for the number of iterations needed to ensure a given accuracy. For these reasons, the Bisection method is frequently used as a dependable starting procedure for the more efficient methods presented later in this chapter.

The bound for the number of iterations for the Bisection method assumes that the calculations are performed using infinite-digit arithmetic. When implementing the method on a computer, consideration must be given to the effects of round-off error. For example, the computation of the midpoint of the interval $[a_{n},b_{n}]$ should be found from the equation

$$p_{n}=a_{n}+\frac{b_{n}-a_{n}}{2}$$
instead of from the algebraically equivalent equation
$$p_{n}=\frac{a_{n}+b_{n}}{2}$$

The first equation adds a small correction, $(b_{n}-a_{n})/2$, to the known value $a_{n}$ . When $b_{n}-a_{n}$ is near the maximum precision of the machine, this correction might be in error, but the error would not significantly affect the computed value of $p_{n}$

However, in the second equation, if $b_{n}-a_{n}$ is near the maximum precision of the machine, it is possible for $p_n$ to return a midpoint that is not even in the interval $[a_{n},b_{n}]$.

A number of tests can be used to see if a root has been found. We would normally use a test of the form
$$\left|f\left(p_{n}\right)\right|<\varepsilon,$$

where $\varepsilon>0$ would be a small number related in some way to the tolerance. However, it is also possible for the value $f(p_{n})$ to be small when $p_{n}$ is not near the root $p$. As a final remark, to determine which subinterval of $[a_{n},b_{n}]$ contains a root of $f$, it is better to make use of signum function, which is defined as
$$\text{sgn}\left(x\right)=\begin{cases} -1 & \text{if }x<0,\\ 0, & \text{if }x=0,\\ 1, & \text{if }x<0, \end{cases}$$
The test
$$\text{sgn}\left(f\left(a_{n}\right)\right)\text{sgn}\left(f\left(p_{n}\right)\right)<0\,\,\,\text{instead of}\,\,\,\, f\left(a_{n}\right)f\left(p_{n}\right)<0$$
gives the same result but avoids the possibility of overflow or underflow in the multiplication of $f(a_{n})$ and $f(p_{n})$.