2nd order one dimensional newtons method?

Question

Can anyone provide me with a credible source for the proof that the one dimensional newtons method for solving non-linear functions is 2nd order?

Answer 1

There is a proof at the link I list below. In fact, I'll sketch a similar proof here. It turns out that 2nd order convergence is actually part of the *derivation* of Newton's method.

Consider a function f(x) and its Taylor series expansion around x = a:

f(x) = f(a) + f'(a) (x-a) + (1/2) f''(a) (x-a)^2 + ...

Say that we have a sequence of real numbers x_0, x_1, x_2, ..., x_n, ... subject to the following three conditions:

1) x_n is "close" to a zero of f(x).
2) x_{n+1} is even "closer," so that we'll approximate f(x_{n+1}) = 0.
3) x_n and x_{n+1} are "close" to each other, so that we'll approximate (x_{n+1} - x_n)^2 = 0.

(The third assumption is 2nd order convergence.) With these assumptions, we'll substitute a = x_n and x = x_{n+1} in the Taylor series expansion above:

f(x_{n+1}) = f(x_n) + f'(x_n) (x_{n+1} - x_n) + (1/2) f''(x_n) (x_{n+1} - x_n)^2 + ...

This simplifies to

0 = f(x_n) + f'(x_n) (x_{n+1} - x_n) + 0

Solving for x_{n+1} in terms of x_n gives

x_{n+1} = x_n - f(x_n) / f'(x_n)

Of course, this is precisely the sequence found in Newton's method.

I should mention that this can be generalized to a 3rd order method by assuming (x_{n+1} - x_n)^3 = 0 rather than (x_{n+1} - x_n)^2 = 0. This yields a quadratic equation for x_{n+1}, but the sequence converges remarkably fast. This is usually called Halley's method.

Answer 2

sophisticated matter. try searching at bing and yahoo. that will could help!