Results 1 to 6 of 6

Math Help - Restoring Quadratic Convergence of Newton's Method

  1. #1
    Senior Member
    Joined
    Mar 2009
    Posts
    378

    Restoring Quadratic Convergence of Newton's Method

    I am studying for finals and am looking over previous problems that I missed significant points on. My instructor doesn't comment on why things are incorrect and he doesn't discuss homework, so I am on my own to figure out why I am wrong. Anyway, I would like some help figuring out where I went wrong.

    Prove that if r is a zero of multiplicity k of the function f, then quadratic convergence in Newton's iteration will be restored by making this modification
    <br />
        x_{n+1} = x_n - k \frac{f(x_n)}{f'(x_n)}<br />

    Proof:
    If x^* is a zero of multiplicity k then f(x) can be rewritten as
    <br />
        f(x) = (x - x^*)^k q(x) <br />
    where q(x*) \ne 0, and so we have f^{(k)}(x^*) \ne 0. Writing f(x) \,\text{and} \, f'(x) as its Taylor series expansion about (x - x*)
    <br />
        f(x) = \frac{f^{(k)}(\xi)}{k!}(x - x^*)^k, \quad <br />
        f'(x) = \frac{f^{(k)}(\eta)}{(k - 1)!}(x - x^*)^{k - 1}<br />
    where \xi, \eta are between x and x^*. Thus we have
             g(x) = x - \frac{f^{(k)}(\xi)}{f^{(k)}(\eta)}(x - x^*)
     \lim_{x \to x^*} g'(x) =  1 - \lim_{x \to x^*}\frac{d}{dx}\left[ \frac{f^{(k)}(\xi)}{f^{(k)}(\eta)}(x-x^*)\right]
    This is where I went wrong. I originally thought that the derivative was just 1 - \frac{f^{(k)}(\xi)}{f^{(k)}(\eta)}, but \xi, \eta depend on x so that is not true.
    \lim_{x \to x^*} g'(x) =  1 - \lim_{x \to x^*}\left[\frac{d}{dx} \left(\frac{f^{(k)}(\xi)}{f^{(k)}(\eta)}\right)(x-x^*) + \frac{f^{(k)}(\xi)}{f^{(k)}(\eta)}\right]
    = 1 - \lim_{x \to x^*}\left[\frac{d}{dx} \left(\frac{f^{(k)}(\xi)}{f^{(k)}(\eta)}\right)(x-x^*)\right] + \lim_{x \to x^*}\frac{f^{(k)}(\xi)}{f^{(k)}(\eta)}
     = 1 - \lim_{x \to x^*}\left[\frac{d}{dx} \left(\frac{f^{(k)}(\xi)}{f^{(k)}(\eta)}\right)(x-x^*)\right] + 1
     = \lim_{x \to x^*}\frac{d}{dx} \left[\frac{f^{(k)}(\xi)}{f^{(k)}(\eta)}\right](x-x^*).
     = \lim_{x \to x^*}\frac{d}{dx} \left[\frac{\frac{df^{(k)}}{dx}(\xi) f^{(k)}(\eta) - f^{(k)}(\xi)\frac{df^{(k)}}{dx}(\eta) }{\left[f^{(k)}(\eta)\right]^2}\right](x-x^*).
    This is suppose to go to zero, but I don't really see how. I suppose it has something to do with \frac{df^{(k)}}{dx}(\xi) \to \frac{df^{(k)}}{dx}(\eta)\text{ as } x \to x^*\text{ and } f^{(k)}(\xi) \to f^{(k)}(\eta)\text{ as } x \to x^*.

    Any help is appreciated, also if you have a different way to do this I will be glad to see it. Thank you in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2009
    Posts
    652
    Thanks
    128
    If the error in the n^{th} iterate is denoted by \epsilon_{n}, then Newton's method may be written

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

    The Taylor expansions for the two functions are

    f(x^{*}+\epsilon_n)=f(x^{*})+\epsilon_nf'(x^{*})+\  epsilon^{2}_nf''(x^{*})/2!+\dots\quad(1)
    and
    f'(x^{*}+\epsilon_n)=f'(x^{*})+\epsilon_nf''(x^{*}  )+\epsilon^{2}_nf'''(x^{*})/2!+\dots\quad(2)

    If the zero is of order 1 then f(x^{*})=0 so when you divide (1) by (2) you get \epsilon_n plus higher order terms.
    That means that the \epsilon_n 's on the RHS of the method cancel and you get second order convergence.
    If though the zero is of order 2 then f(x^{*})=f'(x^{*})=0 so that when the division is carried out the leading term is \epsilon_n/2 and in which case the \epsilon_n's no longer cancel out and you are left with first order convergence.
    To restore the quadratic convergence the fractional term in the method is multiplied by 2.
    Now just follow the reasoning 'up the line' to a k^{th} order zero.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Mar 2009
    Posts
    378
    I guess I am missing something and it is probably obvious, but I don't see where the quadratic convergence comes in. Quadratc convergence is defined as given a limit x^* a sequence x_n is said to converge quadratically if
    \lim_{n\to \infty} \frac{\|x_{n+1} - x^*\|}{\|x_n - x^*\|^2} = M where  M > 0. However, I don't see where that comes in.
    Last edited by lvleph; December 6th 2009 at 05:24 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2009
    Posts
    652
    Thanks
    128
    x_{n+1}=x^{*}+\epsilon_{n+1},\quad x_n=x^{*}+\epsilon_n, so your definition is equivalent to \epsilon_{n+1}=M\epsilon_n^{2}, (in the limit as n tends to infinity).
    If, in the limit, \epsilon_{n+1}=M\epsilon_n, then the convergence is linear.
    It seems that you are looking for a slightly more rigorous analysis !
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Mar 2009
    Posts
    378

    Wink

    <br />
\epsilon_{n+1}=\epsilon_n-k\frac{f(x_n)}{f'(x_n)}<br />
    Taking the taylor series of f(x_n) \text{ and } f'(x_n) \text{ about } x^* gives
    f(x_n) = \frac{f^{(k)}(x_n)}{k!}\epsilon_n^k + \frac{f^{(k+1)}(\xi)}{(k+1)!}\epsilon_n^{k+1}
    f'(x_n) = \frac{f^{(k)}(\eta)}{(k-1)!}\epsilon_n^{k-1}.
    Substituting these taylor series we have
     e_{n+1} = e_n - \frac{f^{(k)}(x_n)}{f^{(k)}(\eta)}\epsilon_n - \frac{1}{k} \frac{f^{(k+1)}(\xi)}{f^{(k)}(\eta)}\epsilon^2_n.
    Now taking the limit as x_n \to x^* gives
     e_{n+1} = e_n - \lim_{x_n \to x^*} \left[\frac{f^{(k)}(x_n)}{f^{(k)}(\eta)}\epsilon_n - \frac{1}{k} \frac{f^{(k+1)}(\xi)}{f^{(k)}(\eta)}\epsilon^2_n\r  ight]
     \frac{|e_{n+1}|}{|e_n|^2} = \frac{1}{k} \frac{|f^{(k+1)}(x^*)|}{|f^{(k)}(x^*)|}

    So, I believe this is the solution.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Mar 2009
    Posts
    378
    I have decided that I don't like the proof above. Does anyone have something to add? I am studying for my qualifying exams and I want to make sure I have this one down.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: December 3rd 2010, 05:27 AM
  2. Newton's Method
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 6th 2009, 03:10 PM
  3. Newton's method convergence
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: September 30th 2009, 12:44 AM
  4. Newton's Method of convergence
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 19th 2009, 08:10 AM
  5. need help! using newton's method
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 23rd 2006, 10:41 PM

Search Tags


/mathhelpforum @mathhelpforum