1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

First step to proof of convergance using Newton's root finding method

  1. Jan 20, 2010 #1
    Suppose I am looking for the root of a function of the form:
    [tex]f(x)=x ^{m}-c[/tex], where c,m>1.

    Suppose I take my first guess to be [tex]x _{0}=c[/tex].

    Then using newtons method my next guess will be given by:
    [tex]x _{n+1}=x _{n} - \frac {f(x _{n})}{f'(x _{n})}[/tex].

    From this, or thinking about this graphically it is obvoius that
    [tex]x _{0}>x _{1}>x _{n}>x _{n+1}>c^{1/m}[/tex].

    However I don't know how should I go about formally proving this.
     
  2. jcsd
  3. Jan 21, 2010 #2

    mathman

    User Avatar
    Science Advisor

    To save writing, let x be current value and x* the next.

    x*=x - (xm-c)/mxm-1={(m-1)xm+c}/mxm-1
    < mxm/mxm-1=x, since c<xm.
     
  4. Jan 21, 2010 #3
    Hmm, I knew this, but is this a proof?

    Don't we need to prove that [tex]x^{m}>c [/tex] ?

    I get the impression that if I want to prove that
    [tex]
    x _{0}>x _{1}>x _{n}>x _{n+1}
    [/tex]
    I need to use [tex]x^{m}>c [/tex]

    And it is easy to prove that [tex]x^{m}>c [/tex] but only if we are sure that:
    [tex]
    x _{0}>x _{1}>x _{n}>x _{n+1}
    [/tex]

    I'm a physics student so I'm not used to proving things formally. Are you sure what you have written is enough?

    I also thought of the following proof:
    We know that:
    [tex]
    x _{0}>x _{1}>x _{n}>x _{n+1}
    [/tex]
    Due to the fact that the function as well as its derivative are >0.
    This is true only for [tex]x_{n}>c^{1/m} [/tex]
    But we can show that using Newtons method the function x* (what you had written) has a minimum at [tex]x_{n}=c^{1/m} [/tex] (I do this by taking (x*)' and equating it to 0).

    Hence we know that [tex]x_{n}>=c^{1/m} [/tex] Therefore the argument stated in the beginning is definitely true: using this fact we know that x* is strictly decreasing and from this it follows that x*>[tex]c^{1/m} [/tex]
     
  5. Jan 22, 2010 #4

    mathman

    User Avatar
    Science Advisor

    Initially you have c > 1, so the initial guess (c) needs cm > c, which is certainly true for c > 1.
     
  6. Jan 24, 2010 #5

    uart

    User Avatar
    Science Advisor

    Hi trelek, you could also use the "mean value theorem" to prove it fairly easily. An outline would go something like this :

    Let "a" be the root and "b" (with b>a) be the inital guess. By the mean value theorem there exists some k : a < k < b, such that

    f(b) - f(a) = f'(k)(b-a).

    Since f' is monotonic increasing it follows that

    f(b) - f(a) < f'(b)(b-a)

    and since f(a)=0 it follows that f(b) / f'(b) < (b-a)

    so

    b - f(b)/f'(b) > a
     
    Last edited: Jan 24, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook