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:
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}.\]
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").
Last edited