Order of convergence of fixed-point to Newton's method

Printable View

November 30th 2010, 11:37 PM
Mollier

Order of convergence of fixed-point to Newton's method

Hi,

In a problem I first show that the order of convergence of simple iteration is 1 and that in order for it to converge I need $|g(x)|<1$ for all $x$ .
From this I must show that Newton's method has an order of convergence of 2. I usually show this by starting with a Taylor expansion etc.

I'm thinking that I could perhaps start by saying that fixed-point iteration will converge if $|g'(x)|<1$ for all $x$ and since Newton's method has that ,

$|g(x)|=\bigg|x-\frac{f(x)}{f'(x)}\bigg|,$

I get,

$|g'(x)| = \bigg|1 - \frac{[f'(x)]^2-f(x)f''(x)}{[f'(x)]^2}\bigg|=\bigg|\frac{f(x)f''(x)}{[f'(x)]^2}\bigg|<1$

Since Newton's method is defined as

$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} \Rightarrow f'(x_n)=-\frac{f(x_n)}{(x_{n+1}-x_n)}$ ,

we get that,

$|g'(x_n)| = \frac{f''(x_n)(x_{n+1}-x_n)^2}{f(x_n)}<1$

Then,

$(x_{n+1}-x_n)^2 \rightarrow 0$ as $n \rightarrow \infty$ but that doesn't show that Newton's is a second order method..

---------------------------------------------------------------------------

I've also started by saying that since simple iteration is of order 1, we have that,

$\frac{|x_{n+1}-\xi|}{|x_n-\xi|} = |g'(c)|$

where $c \in [x_n,\xi]$ and $|g'(c)|\in(0,1)$ ,

but it does not lead me to anything good.

A nice hint would be great! Thanks.
December 1st 2010, 03:40 AM
BobP

A method that's not too heavy on the analysis is to let $x_{n+1}=\alpha+\epsilon_{n+1}$ and $x_{n}=\alpha+\epsilon_{n}$ , where $\alpha$ is the root and the $\epsilon$ 's are the errors in the iterations. Substitute into the N-R formula and tidy up. It requires the division of the Taylor expansions of $f(\alpha+\epsilon_{n})$ and its derivative, but you only need the first two terms, (remember that $f(\alpha)=0$ ).
December 2nd 2010, 08:19 PM
Mollier

Hi BobP, thanks for replying.

The way I understand this is to first reqrite N-R method as,

$\epsilon_{n+1} = \epsilon_n - \frac{f(\alpha+\epsilon_n)}{f'(\alpha+\epsilon_n)}$ .

Then I expand a Taylor series around $\alpha+\epsilon_n$ to get,
$ \begin{aligned} f(x)&=&f(\alpha+\epsilon_n) + f'(\alpha+\epsilon_n)(x-(\alpha+\epsilon_n)) + \frac{f ''(\alpha+\epsilon_n)}{2}(x-(\alpha+\epsilon_n))^2+ R \\ \end{aligned} $ .

I then let $x=\alpha$ and write it the Taylor series as,

$f(\alpha+\epsilon_n) = -f'(\alpha+\epsilon_n)\epsilon_n - \frac{f''(\alpha+\epsilon_n)}{2}\epsilon^2_n - R$ .

I find $f'(x)$ , let $x=\alpha$ and rewrite to get,

$f'(\alpha+\epsilon_n) = -f''(\alpha+\epsilon_n)\epsilon_n - R$ .

If I substitute this into N-R, I do not get a reasonable answer. Where have I gone wrong?

Thanks.
December 2nd 2010, 09:30 PM
Mollier

$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=g(x_n).$

Fixed-point iterations converge if $|g'(x)|<1$ .

$g'(x) = 1-\frac{f'(x)f'(x)-f(x)f''(x)}{[f''(x)]^2}=\frac{f(x)f''(x)}{[f'(x)]^2}$

$g(x) = g(r) + g'(r)(x-r) + \frac{g''(\xi)}{2}(x-r)^2,$

where $\xi$ is between $x$ and $r$ . I now let $x=x_n$ , noticing that $g'(r)=0$ and write the Taylor series as,

$g(x_n)-g(r) = \frac{g''(\xi)}{2}(x_n-r)^2$

So,

$x_{n+1}-r = \frac{g''(\xi)}{2}(x_n-r)^2$

which shows that N-R is a second order method.

Gotta run to work! :)
December 3rd 2010, 05:27 AM
BobP

Quote:

Originally Posted by Mollier

$\epsilon_{n+1} = \epsilon_n - \frac{f(\alpha+\epsilon_n)}{f'(\alpha+\epsilon_n)}$ .

$ f(x)&=&f(\alpha+\epsilon_n) + f'(\alpha+\epsilon_n)(x-(\alpha+\epsilon_n)) + \frac{f ''(\alpha+\epsilon_n)}{2}(x-(\alpha+\epsilon_n))^2+ R \\ \end{aligned} $ .

I then let $x=\alpha$ and write it the Taylor series as,

$f(\alpha+\epsilon_n) = -f'(\alpha+\epsilon_n)\epsilon_n - \frac{f''(\alpha+\epsilon_n)}{2}\epsilon^2_n - R$ .

I find $f'(x)$ , let $x=\alpha$ and rewrite to get,

$f'(\alpha+\epsilon_n) = -f''(\alpha+\epsilon_n)\epsilon_n - R$ .

If I substitute this into N-R, I do not get a reasonable answer. Where have I gone wrong?

Thanks.

$f(\alpha+\epsilon_{n})=f(\alpha)+\epsilon_{n}f'(\a lpha)+\epsilon_{n}^{2}f''(\alpha)/2! + \dots,$

$f'(\alpha+\epsilon_{n})=f'(\alpha)+\epsilon_{n}f'' (\alpha)+\dots.$

Dividing one by the other and plugging back in gets you

$\epsilon_{n+1}=\frac{\epsilon_{n}^{2}}{2}\frac{f'' (\alpha)}{f'(\alpha)}+\dots .$