Proof that Newton's Method gives better and better approximations with each iteration?

1.1k Views Asked by At

I've seen this question and answer: Why does Newton's method work?

It gives some geometric intuition as to what is going on when applying Newton's method, but what I really need to know is why it works that way.

How can you prove that each approximation is closer to the correct value than the previous one?

And also, if the following is indeed true, how can you prove that the "gap" between each two subsequent approximations gets smaller and smaller as you keep going up in the sequence of approximations?

1

There are 1 best solutions below

3
On BEST ANSWER

Proof that Newton's method converges is a standard and elementary result that can be found in any textbook on numerical analysis, as well as in any number of places online (including Wikipedia or Pete Clark's excellent notes).

The real interesting observation, though, is that Newton's method work a lot better in practice than is guaranteed by the theory. Many times Newton's method will converge, and converge quickly, even when starting far from the root, or when the function Hessian is replaced by a crude approximation (a property that quasi-Newton methods like BFGS take advantage of). Closing the gap between how well Newton-type methods work in practice, and what is proven theoretically, is an active research topic.