Stopping criteria when using the bisection method

Question

I'm working on old exams in basic numerical modeling.

The problem is:

$2x \ - e^{-x}=0 $ has a root in the interval $(0, 1.6)$. Find it with an error less than $0.02$ using the Bisection method.

The theoretical basis (copies from Rao's Numerical Methods) says $|f(x_{mid})| \le \epsilon $ is the stopping criterion, which gives $r = 0.35$ and $|f(0.35)|=0.0046880897$.

Theoretical basis:

The solution proposal says $r = 0.35625$ and $|f(0.35625)|=0.0122024760$. Why aren't the iterations stopped when $|f(0.35)|\le \epsilon=0.02$?

Answer 1

The error relates to $x$, that is ideally $|x-x_*|\simeq 0.2$ where $x_*$. However, the nature of the problem is that $x_*$ is not known so you have to use information that is available during the computation.

As a bracketing method you know that $x_*\in [a_n,b_n]$ in every step $n$, so that when you use the midpoint $x=c_n=\frac12(a_n+b_n)$, then you know that $$|x_*-c_n|\le r_n=\frac12(b_n-a_n).$$ Which means that you can stop when the interval reaches length $0.4$.

 n     a[n]      b[n]      c[n]          f(c[n])        r[n]

 0  0.000000  1.600000  0.80000000   1.150671035883  0.80000000
 1  0.000000  0.800000  0.40000000   0.129679953964  0.40000000
 2  0.000000  0.400000  0.20000000  -0.418730753078  0.20000000
 3  0.200000  0.400000  0.30000000  -0.140818220682  0.10000000
 4  0.300000  0.400000  0.35000000  -0.004688089719  0.05000000
 5  0.350000  0.400000  0.37500000   0.062710721209  0.02500000
 6  0.350000  0.375000  0.36250000   0.029065686321  0.01250000
 7  0.350000  0.362500  0.35625000   0.012202476032  0.00625000
 8  0.350000  0.356250  0.35312500   0.003760623283  0.00312500
 9  0.350000  0.353125  0.35156250  -0.000462874346  0.00156250

which gives the result as the midpoint of the sixth computed interval, so that $$|x_*-0.3625|\le0.0125<0.02$$

---

That $f$ has, among the evaluated point, the smallest value at $0.35$ only shows that the bisection method is not very "intelligent" and that other methods that also include the function values in the midpoint calculation, like the variants of regula falsi, will be faster.

---

The error in the book probably happened with a table as above that was produced without stopping criterion. Then the function values were compared manually with the error bound from bottom to top to find where the error bound is first violated, which happens from line 7 to line 6 with $c_7=0.35625$, without checking further.