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

1. Jan 20, 2010

### 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})}$$.

$$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.

2. Jan 21, 2010

### mathman

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.

3. Jan 21, 2010

### 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}$$

4. Jan 22, 2010

### mathman

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

5. Jan 24, 2010

### 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

Last edited: Jan 24, 2010