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?

3 Answers 3

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)

-2

g(x)=(x+x)/2,

g(x)=2x/2,

g(x)=x,

if x=p then g(p)=p

now

g'(x)=1

g'(p)=1

this implies that

g'(p) does not equal to zero and hence order is one,

therefore bisection method is linearly convergent.