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}>c$$ ?

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

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

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:
$$x _{0}>x _{1}>x _{n}>x _{n+1}$$
Due to the fact that the function as well as its derivative are >0.
This is true only for $$x_{n}>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}>=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