## 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:

- \(x_1=x^*\): \(f(x_1)=0\) and we are done.
- \(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\).
- \(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

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