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

• Nov 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 $\displaystyle |g(x)|<1$ for all $\displaystyle 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 $\displaystyle |g'(x)|<1$ for all $\displaystyle x$ and since Newton's method has that ,

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

I get,

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

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

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

Then,

$\displaystyle (x_{n+1}-x_n)^2 \rightarrow 0$ as $\displaystyle 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,

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

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

but it does not lead me to anything good.

A nice hint would be great! Thanks.
• Dec 1st 2010, 03:40 AM
BobP
A method that's not too heavy on the analysis is to let $\displaystyle x_{n+1}=\alpha+\epsilon_{n+1}$ and $\displaystyle x_{n}=\alpha+\epsilon_{n}$, where $\displaystyle \alpha$ is the root and the $\displaystyle \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 $\displaystyle f(\alpha+\epsilon_{n})$ and its derivative, but you only need the first two terms, (remember that $\displaystyle f(\alpha)=0$ ).
• Dec 2nd 2010, 08:19 PM
Mollier

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

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

Then I expand a Taylor series around $\displaystyle \alpha+\epsilon_n$ to get,
\displaystyle \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 $\displaystyle x=\alpha$ and write it the Taylor series as,

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

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

$\displaystyle 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.
• Dec 2nd 2010, 09:30 PM
Mollier
$\displaystyle x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=g(x_n).$

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

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

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

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

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

So,

$\displaystyle 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! :)
• Dec 3rd 2010, 05:27 AM
BobP
Quote:

Originally Posted by Mollier

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

\displaystyle 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 $\displaystyle x=\alpha$ and write it the Taylor series as,

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

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

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

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

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

Dividing one by the other and plugging back in gets you

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