Results 1 to 5 of 5

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

  1. #1
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2009
    Posts
    660
    Thanks
    133
    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 ).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    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,
    <br />
\begin{aligned}<br />
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 \\<br />
\end{aligned}<br />
.

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2009
    Posts
    660
    Thanks
    133
    Quote Originally Posted by Mollier View Post

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

    <br /> <br />
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 \\<br />
\end{aligned}<br />
.

    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 .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Trapezoid method, fixed-point iteration
    Posted in the Differential Equations Forum
    Replies: 5
    Last Post: November 22nd 2010, 05:31 AM
  2. Convergence of fixed point iteration question
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: April 20th 2010, 04:35 AM
  3. Noninear system - fixed point method
    Posted in the Math Software Forum
    Replies: 6
    Last Post: April 4th 2010, 04:04 PM
  4. Fixed Point free automorphism of order 3
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 7th 2009, 12:34 PM
  5. Fixed point method : where is my error?
    Posted in the Calculus Forum
    Replies: 3
    Last Post: May 24th 2008, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum