1. ## 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!

2. 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

3. ## 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}}$

4. 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

5. ## 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

6. 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
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

7. 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!

8. 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$)