2 The bisection method

Suppose that, by trial and error for example, we know that a single zero of some function $f$ lies between $x=a$ and $x=b$ . The root is said to be bracketed by $a$ and $b$ . This must mean that $f\left(a\right)$ and $f\left(b\right)$ are of opposite signs, that is that $f\left(a\right)f\left(b\right)<0$ .

Example 23

The single positive zero of the function $f\left(x\right)=xtanh\left(\frac{1}{2}x\right)-1$  models the wave number of water waves at a certain frequency in water of depth $0.5$ (measured in some units we need not worry about here). Find two points which bracket the zero of $f$ .

Solution

We simply evaluate $f$ at a selection of $x$ -values.

$\begin{array}{cc}\hfill x& f\left(x\right)=xtanh\left(\frac{1}{2}x\right)-1\hfill \\ ̲& ̲& ̲\\ \hfill 0& 0\times tanh\left(0\right)-1\hfill & =-1\hfill \\ \hfill 0.5& 0.5\times tanh\left(0.25\right)-1=0.5\times 0.2449-1\hfill & =-0.8775\hfill \\ \hfill 1& 1\times tanh\left(0.5\right)-1=1\times 0.4621-1\hfill & =-0.5379\hfill \\ \hfill 1.5& 1.5\times tanh\left(0.75\right)-1=1.5\times 0.6351-1\hfill & =-0.0473\hfill \\ \hfill 2& 2\times tanh\left(1\right)-1=2\times 0.7616-1\hfill & =0.5232\hfill \end{array}$

From this we can see that $f$ changes sign between $1.5$ and $2$ . Thus we can take $a=1.5$ and $b=2$ as the bracketing points. That is, the zero of $f$ is in the bracketing interval $1.5<x<2$ .

Task!

The function $f\left(x\right)=cos\left(x\right)-x$  has a single positive zero. Find bracketing points $a$ and $b$ for the zero of $f$ . Arrange for the difference between $a$ and $b$ to be equal to $\frac{1}{2}$ .

(NB - be careful to use radians on your calculator!)

Answer

The aim with the bisection method is to repeatedly reduce the width of the bracketing interval $a<x<b$ so that it “pinches" the required zero of $f$ to some desired accuracy. We begin by describing one iteration of the bisection method in detail.

Let $m=\frac{1}{2}\left(a+b\right)$ , the mid-point of the interval $a<x<b$ . All we need to do now is to see in which half (the left or the right) of the interval $a<x<b$ the zero is in. We evaluate $f\left(m\right)$ . There is a (very slight) chance that $f\left(m\right)=0$ , in which case our job is done and we have found the zero of $f$ . Much more likely is that we will be in one of the two situations shown in Figure 13 below. If $f\left(m\right)f\left(b\right)<0$ then we are in the situation shown in (a) and we replace $a<x<b$ with the smaller bracketing interval $m<x<b$ . If, on the other hand, $f\left(a\right)f\left(m\right)<0$ then we are in the situation shown in (b) and we replace $a<x<b$ with the smaller bracketing interval $a<x<m$ .

Either way, we now have a bracketing interval that is half the size of the one we started with. We have carried out one iteration of the bisection method. By successively reapplying this approach we can make the bracketing interval as small as we wish.

Example 24

Carry out one iteration of the bisection method so as to halve the width of the bracketing interval $1.5<x<2$ for

$f\left(x\right)=xtanh\left(\frac{1}{2}x\right)-1.$

Solution

The mid-point of the bracketing interval is $m=\frac{1}{2}\left(a+b\right)=\frac{1}{2}\left(1.5+2\right)=1.75$ . We evaluate

$f\left(m\right)=1.75\times tanh\left(\frac{1}{2}\times 1.75\right)-1=0.2318,$

to 4 decimal places. We found earlier (Example 20, page 63) that $f\left(a\right)<0$ and $f\left(b\right)>0$ , the fact that $f\left(m\right)$ is of the opposite sign to $f\left(a\right)$ means that the zero of $f$ lies in the bracketing interval $1.5<x<1.75$ .

Task!

Carry out one iteration of the bisection method so as to halve the width of the bracketing interval $0.5<x<1$ for

$f\left(x\right)=cos\left(x\right)-x.$

Answer

So we have a way of halving the size of the bracketing interval. By repeatedly applying this approach we can make the interval smaller and smaller.

The general procedure, involving (possibly) many iterations, is best described as an algorithm:

1. Choose an error tolerance.
2. Let $m=\frac{1}{2}\left(a+b\right)$ , the mid-point of the bracketing interval.
3. There are three possibilities:
   1. $f\left(m\right)=0$ , this is very unlikely in general, but if it does happen then we have found the zero of $f$ and we can go to step 7 ,
   2. the zero is between $m$ and $b$ ,
   3. the zero is between $a$ and $m$ .
4. If the zero is between $m$ and $b$ , that is if $f\left(m\right)f\left(b\right)<0$ (as in Figure 13(a)) then let $a=m$ .
5. Otherwise the zero must be between $a$ and $m$ (as in Figure 13(b)) so let $b=m$ .
6. If $b-a$ is greater than the required tolerance then go to step 2 .
7. End.

One feature of this method is that we can predict in advance how much effort is required to achieve a certain level of accuracy.

Example 25

A given problem using the bisection method starts with the bracketing points $a=1.5$ and $b=2$ . How many iterations will be required so that the error in the approximation is less that $\frac{1}{2}\times 10^{-6}$ ?

Solution

Before we carry out any iterations we can write that the zero to be approximated is $1.75\pm 0.25$ so that the maximum magnitude of the error in 1.75 may be taken to be equal to 0.25.

Each successive iteration will halve the size of the error, so that after $n$ iterations the error is equal to

$\frac{1}{2^n}\times 0.25$

We require that this quantity be less than $\frac{1}{2}\times 10^{-6}$ . Now,

$\frac{1}{2^n}\times 0.25<\frac{1}{2}\times 10^{-6}\text{implies that}{2}^n>\frac{1}{2}\times 10^6.$

The smallest value of $n$ which satisfies this inequality can be found by trial and error, or by using logarithms to see that $n>\left(ln\left(\frac{1}{2}\right)+6ln\left(10\right)\right)∕ln\left(2\right)$ . Either way, the smallest integer which will do the trick is

$n=19.$

It takes 19 iterations of the bisection method to ensure the required accuracy.

Task!

A function $f$ is known to have a single zero between the points $a=3.2$ and $b=4$ . If these values were used as the initial bracketing points in an implementation of the bisection method, how many iterations would be required to ensure an error less than $\frac{1}{2}\times 10^{-3}$ ?

Answer

2.1 Pros and cons of the bisection method

Pros

• the method is easy to understand and remember
• the method always works (once you find values $a$ and $b$ which bracket a single zero)
• the method allows us to work out how many iterations it will take to achieve a given error tolerance because we know that the interval will exactly halve at each step

Cons

• the method is very slow
• the method cannot find roots where the curve just touches the $x$ -axis but does not cross it (e.g. double roots)

The slowness of the bisection method will not be a surprise now that you have worked through an example or two! Significant effort is involved in evaluating $f$ and then all we do is look at this $f$ -value and see whether it is positive or negative! We are throwing away hard won information.

Let us be realistic here, the slowness of the bisection method hardly matters if all we are saying is that it takes a few more fractions of a second of computing time to finish, when compared with a competing approach. But there are applications in which $f$ may be very expensive (that is, slow) to calculate and there are applications where engineers need to find zeros of a function many thousands of times. (Coastal engineers, for example, may employ mathematical wave models that involve finding the wave number we saw in Example 20 at many different water depths.) It is quite possible that you will encounter applications where the bisection method is just not good enough.