# Convergence rate

• May 3rd 2009, 02:42 AM
Twig
Convergence rate
Hi

Not really sure where to post this question, but here we go.

I need to compute the first several iterations of Newton´s method for solving
$x^{2}-1=0$ , using initial guess $x_{0}=10^{6}$ .

First things first. How would this be set up?

$\mbox{Newtons method: }x_{k+1}=x_{k} - \frac{f(x_{k})}{f'(x_{k})}$

Would this give me:

$x_{1}=10^{6}-\frac{(10^{6})^{2}-1}{2\cdot 10^{6}}$

If so, how do I decide in general the apparent convergence rate?
What should the asymptotic convergence rate be?
How many iterations are required before the asymptotic convergence is reached?
Finally, give an analytical explanation of the behavior one observes.

I don´t even know what asymptotic convergence is.

Thanks!
• May 3rd 2009, 10:11 AM
CaptainBlack
Quote:

Originally Posted by Twig
Hi

Not really sure where to post this question, but here we go.

I need to compute the first several iterations of Newton´s method for solving
$x^{2}-1=0$ , using initial guess $x_{0}=10^{6}$ .

First things first. How would this be set up?

$\mbox{Newtons method: }x_{k+1}=x_{k} - \frac{f(x_{k})}{f'(x_{k})}$

Would this give me:

$x_{1}=10^{6}-\frac{(10^{6})^{2}-1}{2\cdot 10^{6}}$

If so, how do I decide in general the apparent convergence rate?
What should the asymptotic convergence rate be?
How many iterations are required before the asymptotic convergence is reached?
Finally, give an analytical explanation of the behavior one observes.

I don´t even know what asymptotic convergence is.

Thanks!

Start by writing $x_{n+1}$ explicitly in terms of $x_n$

Only after that worry about anything else.

CB
• May 3rd 2009, 11:33 AM
Twig
hi
hi CB

I don´t really understand what you mean.
$x_{n+1} \mbox{ explicitly in terms of } x_{n}$ ?

Ain´t that just

$x_{n+1}=x_{n}-\frac{x_{n}^{2}-1}{2x_{n}}$
• May 3rd 2009, 01:11 PM
CaptainBlack
Quote:

Originally Posted by Twig
hi CB

I don´t really understand what you mean.
$x_{n+1} \mbox{ explicitly in terms of } x_{n}$ ?

Ain´t that just

$x_{n+1}=x_{n}-\frac{x_{n}^{2}-1}{2x_{n}}$

Which is:

$x_{n+1}=\frac{x_n}{2}+\frac{1}{2x_n}$

But your initial value is so large, that for the first few itterations this behaves like:

$x_{n+1}=\frac{x_n}{2}$

CB
• May 3rd 2009, 01:56 PM
Twig
hi
Hi CB

Yeah ok, so what does this tell me about convergence rates? That it is 1/2 ?

I don´t even know what the word "asymptotic" means (Worried)
• May 3rd 2009, 10:06 PM
CaptainBlack
Quote:

Originally Posted by Twig
Hi CB

Yeah ok, so what does this tell me about convergence rates? That it is 1/2 ?

I don´t even know what the word "asymptotic" means (Worried)

It tells you that the initial convergence rate when $x_0=10^6$ is linear (we know that this is going to go to $x_{\infty}=+1$).

That is the error on the n-th iteration is approximately a constant multiple of the error on the n-1 th iteration.

CB
• May 4th 2009, 01:23 PM
Twig
hey

So if my function was instead $f(x)=x^{3}+1$ , then:

$x_{n+1}= x_{n} - \frac{x_{n}^{3}+1}{3x^{2}}$

Which behaves like $x_{n+1}=\frac{2}{3}x_{n}$ if $x_{n}$ is large ?

Is my rate of convergence linear here also?
Will the error on the n-th iteration be the constant 2/3 times the error on the n-1 th iteration ?

Thanks!

• May 4th 2009, 02:16 PM
CaptainBlack
Quote:

Originally Posted by Twig
hey

So if my function was instead $f(x)=x^{3}+1$ , then:

$x_{n+1}= x_{n} - \frac{x_{n}^{3}+1}{3x^{2}}$

Which behaves like $x_{n+1}=\frac{2}{3}x_{n}$ if $x_{n}$ is large ?

Is my rate of convergence linear here also?
Will the error on the n-th iteration be the constant 2/3 times the error on the n-1 th iteration ?

Thanks!

Start with $x_0=10^6$, $\varepsilon_0 \approx 10^6$, $x_1\approx 0.67 \times 10^6$ and $\varepsilon_1\approx 0.67 \times 10^6$ etc
All this is because the root that this iteration is heading for has $|x|=1 \ll x_0$ (it is heading for the real root $x=-1$)