2
$\begingroup$

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?

2 Answers 2

3

For the bisection you simply have that $\epsilon_{i+1}/\epsilon_i = 1/2$, so, by definition the order of convergence is 1 (linearly).

2

the $\frac12$ you get is called 'asymptotic error constant $\lambda$'. for any method, it's in form $\frac{|p_{n+1}-p|}{(|p_n-p|)^\alpha}=\lambda$. $\lambda$ is called asymptotic error constant, and $\alpha$ is the order of convergence. 1: linearly, 2:quadratically. and usually it converges faster as $\alpha$ gets bigger; and $\lambda$ also effects the speed of convergence but not extend to the order.

source: Numerical Analysis 9th edition, by Richard L. Burden & J.Douglas Fairs.

ISBN-13: 978-0-538-73351-9 (page 79 definition 2.7)