Numerical Analysis proof?

[Keith]

If this question is not posed correctly, please let me know and I will add more detail...

Prove that if f in C^2 is increasing, concaved up, and has a zero, then Newton's method will converge to it from ANY starting point.

[Sean H]

Newton's method is iteratively defined:

x_{i+1} = x_i - f(x_i)/f'(x_i)

The first thing to notice is that because f is increasing, f'(x) is never zero, so no matter what point you start at you at least can always iterate.

Next, let's suppose y is the zero (f(y) = 0). Then the idea is to prove that |x_{i+1} - y| < e*|x_i - y| for some 0<e<1 and any x_i>y (where x_{i+1} is defined from Newton's method). From this it's pretty easy to see that you have convergence starting from any x_0>y. Also it's not too hard to see that if x_0 < y then x_1 >y because of the concavity and the fact f is increasing. Thus if you prove the above inequality, then you're done. So, how to prove this inequality?

Well, one way is to use Taylor's Theorem. One version of this states:

f(x) = f(y) + f'(y)*(x-y) - int_x^y f''(t)*(y-t) dt = f'(y)*(x-y) - int_x^y f''(t)*(y-t) dt

and

f'(x) = f'(y) - int_x^y f'(t) dt.

So, plugging this into Newton's method:

x_{i+1} = x_i - (f'(y)*(x_i-y) - int_{x_i}^y f''(t)*(y-t) dt)/(f'(y) - int_{x_i}^y f'(t) dt).

Subtract y from both sides and use the fact f''(t)*(t-y)>0 for t>y (I'm assuming x_i>y) to get to:

x_{i+1} - y < (x_i - y)*(1 - f'(y)/(f'(y) - int_{x_i}^y f'(t) dt))

Finally, int_{x_i}^y f'(t) dt <0 since f'(t) >0, and so

0< 1 - f'(y)/(f'(y) - int_{x_i}^y f'(t) dt) < 1.

This almost proves the result, there is one small detail left. If you take e = 1 - f'(y)/(f'(y) - int_{x_i}^y f'(t) dt then e depends on x_i, but you can get around that. All you have to show is that for a given starting x_0 > y, this quantity is bounded away from 1.

[Dragon'sFire]

Wait up you caught me off guard, I have to look up newton's
method!!., and you may be right!.