Numerical Analysis Home

## Bisection Method

In this chapter we will find roots of a given function $$f$$, i.e., $$x^*$$ for which $$f(x^*)=0$$.

Bisection Method: Suppose $$f$$ is a continuous function on $$[a,b]$$ and $$f(a)$$ and $$f(b)$$ have the opposite signs. Then by the IVT (Intermediate Value Theorem), there is at least one root $$x^*$$ of $$f$$ in $$(a,b)$$. For simplicity, let's assume the root $$x^*$$ is unique. Set $$a_1=a$$ and $$b_1=b$$. Let $$x_1=\displaystyle\frac{a_1+b_1}{2}$$ which breaks $$[a_1,b_1]$$ into two subintervals $$[a_1,x_1]$$ and $$[x_1,b_1]$$. Then there are three possibilities:

1. $$x_1=x^*$$: $$f(x_1)=0$$ and we are done.

2. $$x^*\in (a_1,x_1)$$: $$f(x_1)$$ and $$f(a_1)$$ have the opposite signs and set $$a_2=a_1$$, $$b_2=x_1$$.

3. $$x^*\in (x_1,b_1)$$: $$f(x_1)$$ and $$f(b_1)$$ have the opposite signs and set $$a_2=x_1$$, $$b_2=b_1$$.

Set $$x_2=\displaystyle\frac{a_2+b_2}{2}$$. We can continue this process of bisecting an interval $$[a_n,b_n]$$ containing $$x^*$$ and getting an approximation $$x_n=\displaystyle\frac{a_n+b_n}{2}$$ of $$x^*$$. We will show that $$\{x_n\}$$ converges to $$x^*$$.

Example. Do five iterations by the Bisection Method to approximate the root $$x^*$$ of $$f(x)=e^x-x-2$$ on the interval $$[0,2]$$.
Solution. $\begin{array}{|l|l|c|l|c|l|c|} \hline n & a_n & f(a_n) & b_n & f(b_n) & x_n=\frac{a_n+b_n}{2} & f(x_n)\\ \hline 1 & 0 & - & 2 & + & 1 & -\\ \hline 2 & 1 & - & 2 & + & 1.5 & +\\ \hline 3 & 1 & - & 1.5 & + & 1.25 & +\\ \hline 4 & 1 & - & 1.25 & + & 1.125 & -\\ \hline 5 & 1.125 & - & 1.25 & + & 1.1875 & +\\ \hline \end{array}$ Since $$|x_5-x_4|=|1.1875-1.125 |=0.0625<0.1=10^{-1}$$, we can (roughly) say that the root is $$x_5=1.1875$$ correct to one decimal place. But why roughly?

Observation. If $$x_n$$ is correct to $$t$$ decimal places, then $$|x^*-x_n|<10^{-t}$$. But the converse is not true.

Example. $$x^*=1.146193$$ is correct to $$6$$ decimal places (believe me!). So $$x_{11}=1.145507$$ is only correct to $$2$$ decimal places but $$|x^*-x_{11}|<10^{-3}$$. Similarly if $$x^*=1.000$$ is approximated by $$x=0.999$$, then $$|x^*-x|=0.001<10^{-2}$$. But $$x=0.999$$ is not correct to any decimal places of $$x^*=1.000$$. Also note that we computed $$|x_5-x_4|$$, not $$|x^*-x_5|$$ (which is not known for $$x^*$$).

It would be useful to know the number of iteration that guarantees to achieve a certain accuracy of the root, say within $$10^{-3}$$. That is to find $$n$$ for which $$|x^*-x_n|<10^{-3}$$, i.e., $$x^*-10^{-3}< x_n < x^*+10^{-3}$$. So we have to find an upper bound of the absolute error for the $$n$$th iteration $$x_n$$.

The Maximum Error: Let $$\varepsilon_n$$ be the absolute error for the $$n$$th iteration $$x_n$$. Then $\varepsilon_n=|x^*-x_n|\leq \frac{b-a}{2^n}.$

Since $$x^*\in [a_n,b_n]$$ and $$b_n-a_n=(b_{n-1}-a_{n-1})/2$$ for all $$n$$, $\varepsilon_n=|x^*-x_n|\leq \frac{b_n-a_n}{2}=\frac{b_{n-1}-a_{n-1}}{2^2}=\cdots=\frac{b_1-a_1}{2^n}=\frac{b-a}{2^n}.\; ◼$

Example. Find the number of iteration by the Bisection Method that guarantees to approximate the root $$x^*$$ of $$f(x)=e^x-x-2$$ on $$[0,2]$$ with accuracy within $$10^{-3}$$.
Solution. \begin{align*} & \varepsilon_n=|x^*-x_n|\leq \frac{2-0}{2^n}=\frac{2}{2^n}<10^{-3}\\ \implies & 2\cdot 10^3< 2^n\\ \implies & \ln(2\cdot 10^3) < \ln 2^n \\ \implies & \ln 2+ 3 \ln(10)< n\ln 2 \\ \implies & \frac{\ln 2+ 3\ln(10)}{\ln 2}< n\\ \implies & 10.97\approx\frac{\ln 2+ 3\ln(10)}{\ln 2} < n \end{align*} Thus 11th iteration guarantees to achieve accuracy of the root within $$10^{-3}$$.

Note that the root is $$x^*=1.146193$$ correct to $$6$$ decimal places. So $$x_{10}=1.146484$$ and $$x_{11}=1.145507$$ both have accuracy within $$10^{-3}$$ (check: $$|x^*-x_{10}|<10^{-3}$$, $$|x^*-x_{11}|<10^{-3}$$). Thus accuracy within $$10^{-3}$$ is reached even before 11th iteration.

It is interesting to note that $$x_{10}=1.{\bf 146}484$$ is correct to $$3$$ decimal places whereas $$x_{11}=1. {\bf 14}5507$$ is only correct to $$2$$ decimal places.

Convergence: The sequence $$\{x_n\}$$ constructed by the bisection method converges to the solution $$x^*$$ because $\lim_{n\to \infty}|x^*-x_n|\leq \lim_{n\to \infty}\frac{b-a}{2^n}=0 \implies \lim_{n\to \infty}|x^*-x_n|=0.$ But it converges really slowly in comparison to other methods (See "Order of Convergence").

Algorithm Bisection-Method
Input: $$f(x)=e^x-x-2$$, interval $$[0,2]$$, tolerance $$10^{-3}$$, maximum number of iterations $$50$$
Output: an approximate root of $$f$$ on $$[0,2]$$ within $$10^{-3}$$ or a message of failure
set $$a=0$$ and $$b=2$$;
$$xold=a$$;
for $$i=1$$ to $$50$$
$$x=(a+b)/2$$;
if $$|x-xold|<10^{-3}$$          $$\%$$ checking required accuracy
FoundSolution= true;      $$\%$$ done
break;                               $$\%$$ leave for environment
end if
if $$f(a)f(x)<0$$
a=a and b=x
else
a=x and b=b
end if
$$xold=x$$;      $$\%$$ update $$xold$$ for the next iteration
end for
if FoundSolution
return $$x$$
else
print 'the required accuracy is not reached in 50 iterations'
end if

Last edited