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\);
for \(i=1\) to \(50\)
     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
         a=x and b=b
     end if
     \(xold=x\);      \(\%\) update \(xold\) for the next iteration
end for
if FoundSolution
     return \(x\)
     print 'the required accuracy is not reached in 50 iterations'
end if

Last edited