ExerciseNonlinear equationsbasic

Exercise: bisection by hand

Six bisection iterations for cos²x−x=0 on [0,1], with the chain of intervals, the error bound at each step and the prediction of the required number of iterations.

Solution

ExampleBisection on [0,1]

Approximate the root of $f(x)=\cos^2 x-x$ on $[0,1]$ with six bisection iterations.

Initial check: $f(0)=1>0$ and $f(1)=\cos^2 1-1=-0.708<0$ , so Bolzano's theorem guarantees a root in $(0,1)$ .
$m_1=0.5$ : $f(0.5)=0.270>0$ , same sign as at $0$ → root in $[0.5,\,1]$ .
$m_2=0.75$ : $f(0.75)=-0.215<0$ → root in $[0.5,\,0.75]$ .
$m_3=0.625$ : $f(0.625)=0.033>0$ → root in $[0.625,\,0.75]$ .
$m_4=0.6875$ : $f=-0.090<0$ → $[0.625,\,0.6875]$ . $m_5=0.65625$ : $f=-0.029<0$ → $[0.625,\,0.65625]$ . $m_6=0.640625$ : $f=0.002>0$ → $[0.640625,\,0.65625]$ .
The error bound after 6 iterations is $\frac{b-a}{2^{7}}=\frac{1}{128}=0.0078$ ; in fact $m_6=0.640625$ is only $0.0011$ away from $\alpha=0.641714$ .

With the error bound the cost of more precision can be predicted: for $\varepsilon=10^{-9}$ one would need $k>\log_2(10^9)-1\approx 29$ iterations. Compare with Newton's 5 for the same equation.