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

[trelek2]

Suppose I am looking for the root of a function of the form:
f(x)=x ^{m}-c, where c,m>1.

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

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

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

However I don't know how should I go about formally proving this.

 

[mathman]

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

x*=x - (x^m-c)/mx^m-1={(m-1)x^m+c}/mx^m-1
< mx^m/mx^m-1=x, since c<x^m.

 

[trelek2]

Hmm, I knew this, but is this a proof?

Don't we need to prove that x^{m}&gt;c ?

I get the impression that if I want to prove that
<br /> x _{0}&gt;x _{1}&gt;x _{n}&gt;x _{n+1}<br />
I need to use x^{m}&gt;c

And it is easy to prove that x^{m}&gt;c but only if we are sure that:
<br /> x _{0}&gt;x _{1}&gt;x _{n}&gt;x _{n+1}<br />

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:
<br /> x _{0}&gt;x _{1}&gt;x _{n}&gt;x _{n+1}<br />
Due to the fact that the function as well as its derivative are >0.
This is true only for x_{n}&gt;c^{1/m}
But we can show that using Newtons method the function x* (what you had written) has a minimum at x_{n}=c^{1/m} (I do this by taking (x*)' and equating it to 0).

Hence we know that x_{n}&gt;=c^{1/m} 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*>c^{1/m}

 

[mathman]

Initially you have c > 1, so the initial guess (c) needs c^m > c, which is certainly true for c > 1.

 

[uart]

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