I know how to prove the bound on the error after $k$ steps of the Bisection method.
I.e.
$$|\tau – x_{k}| \leq \left(\frac{1}{2}\right)^{k-1}|b-a|$$
where $a$ and $b$ are the starting points.
But does this imply something about the order of convergence of the Bisection method? I know that it converges with order at least 1, is that implied in the error bound?
Edit
I've had a go at showing it, is what I am doing here correct when I want to demonstrate the order of convergence of the Bisection method?
$$\lim_{k \to \infty}\frac{|\tau – x_k|}{|\tau – x_{k-1}|} = \frac{(\frac{1}{2})^{k-1}|b-a|}{(\frac{1}{2})^{k-2}|b-a|}$$
$$=\frac{(\frac{1}{2})^{k-1}}{(\frac{1}{2})^{k-2}}$$
$$=\frac{1}{2}$$
Show this shows linear convergence with $\frac{1}{2}$ being the rate of convergence. Is this correct?
Best Answer
For the bisection you simply have that $\epsilon_{i+1}/\epsilon_i = 1/2$, so, by definition the order of convergence is 1 (linearly).