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
$\displaystyle x^{2}-1=0$ , using initial guess $\displaystyle x_{0}=10^{6}$ .

First things first. How would this be set up?

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

Would this give me:

$\displaystyle 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
$\displaystyle x^{2}-1=0$ , using initial guess $\displaystyle x_{0}=10^{6}$ .

First things first. How would this be set up?

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

Would this give me:

$\displaystyle 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 $\displaystyle x_{n+1}$ explicitly in terms of $\displaystyle x_n$

Only after that worry about anything else.

CB

3. ## hi

hi CB

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

Ainīt that just

$\displaystyle 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.
$\displaystyle x_{n+1} \mbox{ explicitly in terms of } x_{n}$ ?

Ainīt that just

$\displaystyle x_{n+1}=x_{n}-\frac{x_{n}^{2}-1}{2x_{n}}$
Which is:

$\displaystyle 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:

$\displaystyle 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 $\displaystyle x_0=10^6$ is linear (we know that this is going to go to $\displaystyle 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 $\displaystyle f(x)=x^{3}+1$ , then:

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

Which behaves like $\displaystyle x_{n+1}=\frac{2}{3}x_{n}$ if $\displaystyle 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 $\displaystyle f(x)=x^{3}+1$ , then:

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

Which behaves like $\displaystyle x_{n+1}=\frac{2}{3}x_{n}$ if $\displaystyle 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 $\displaystyle x_0=10^6$, $\displaystyle \varepsilon_0 \approx 10^6$, $\displaystyle x_1\approx 0.67 \times 10^6$ and $\displaystyle \varepsilon_1\approx 0.67 \times 10^6$ etc
All this is because the root that this iteration is heading for has $\displaystyle |x|=1 \ll x_0$ (it is heading for the real root $\displaystyle x=-1$)