At each iteration in the bisection method the absolute error becomes half of the previous iteration. Thus if we approximate the root $x$ of some equation in some interval $[a,b]$ (say) by means of a sequence $\{x_n\}$ converging to $x$ in the bisection method then we should have $|x_n-x| \le \frac {b-a} {2^n}$ If we want to approximate $x$ in such a way that the absolute error $\le \epsilon$ for some given $\epsilon >0$ then we first calculate the maximum probable iterations for which $|x_n-x|>\epsilon$ or in other words the maximum probable iterations for which $\frac {b-a} {2^n} > \epsilon$. This would yield the maximum possible value of $n$ is $\frac {\ln (b-a) – \ln \epsilon} {\ln 2}$ i.e. for all $n \ge \frac {\ln (b-a) – \ln \epsilon} {\ln 2}$ we have $|x_n-x| \le \epsilon$. Now my question is $:$
Can I say that the least $n$ for which it just exceeds the quantity $\frac {\ln (b-a) – \ln \epsilon} {\ln 2}$ is the least value of $n$ for which $|x_n-x| \le \epsilon$? This question immediately came to my mind when I was trying to solve the following problem $:$
Find the minimum number iterations needed to approximate the root of the equation $e^x-3x^2=0$ in $(3,4)$ such that the absolute error $\le 10^{-3}$.
Now if the answer to my last question is "yes" then I find the answer to the above problem which is $10$ but if it isn't then I don't find any clue to find such $n$.
Please help me to overcome my confusion.
Best Answer
The bisection method bases all decisions purely on the sign of the function value. There is no size information used, even less slope information.
Thus even if the root were $3.500001$ so that the best approximation could be found in the first step, there is no way to detect this, the result of the first step is only that the root is somewhere in $[3.5,4]$.
It is really only the length of the bracketing interval that gives any information on the quality of the root approximation by endpoint or midpoint.
What you can do is to always return the midpoint (without a final function evaluation there), so that for an error of $10^{-3}$ you need an interval length smaller than $2ยท10^{-3}$ which is reached after $9$ steps with $b_9-a_9=\frac1{512}$ or $11$ function evaluations.