Finding an interval of convergence for the bisection method, and finding number of iterates needed for desired accuracy.

Question

I was given the following problem:

---

Let $\alpha$ be the largest root of $$ f(x)\equiv e^{x}-x-2=0. $$ Find and interval $[a,b]$ containing $\alpha$ for which the bisection method will converge to $\alpha$. Then estimate the number of iterates needed to find $\alpha$ within an accuracy of $5\times 10^{-8}.$

---

In class we were told only to find $a,b$ such that $f(a)\cdot f(b)<0$, so I picked $a=1,b=2$. The following is my solution:

Given $\varepsilon$ we want to find $n$ such that $$ |a-c_{n}|\le\frac{1}{2^{n}}\left(b-a\right)<\varepsilon, $$ which yields $$ n> \log_{2}{\frac{1}{\varepsilon}(b-a)}. $$ Picking $a=1,b=2$, we see that \begin{alignat*}{2} f(a)&=e3&&<0 \\ f(b)&=e^{2}-4&&>0. \end{alignat*} Given $\varepsilon=5\times10^{-8}$ and letting $a=1,b=2$, we get \begin{alignat*}{2} &&n &> \log_{2}\frac{1}{\varepsilon} \\ &\implies\quad &&> -\log_{2}{\varepsilon} \notag\\ &\implies\quad &&> -\log_{2}{5\times10^{-8}}\approx{24.2535} \notag\\ &\implies\quad &n &\ge 25. \end{alignat*}

How can I know whether this condition is sufficient for the convergence of the method?

Answer 1

Consider $$f(x)= e^{x}-x-2 \implies f'(x)=e^x-1 \implies f''(x)=e^x \quad > \,\, \forall x$$ The first derivative cancels at $x_*=0$ and the second derivative test shows that this is a minimum.

So, two roots : one is positive (you got it) and the second is negative.

Answer 2

When you apply the bisection method to a continuous function over an interval $[a,b]$, such that $f(a) f(b) < 0$, you get, by construction, convergence to a solution of the equation $f(x)=0$. This is simply due to the fact that you construct a sequence of intervals $[a_n,b_n]$ that always contain a solution of the equation and such that $b_n-a_n \to 0$.