Convergence of Bisection method

$\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?

$\endgroup$

2 Answers

$\begingroup$

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

$\endgroup$ $\begingroup$

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)

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy