Newton's Method
Stephen Smale

The expression is a mathematical description of Newton's Method.

Long before Newton, the concept already was used by the Greeks for finding the square root of a positive number. Since Newton, the iteration has been used more generally to give an approximation to a solution of the equation f (x) = 0. Early in my mathematical career I was intrigued by the question, why does this method work so fast and so well and what are the limitations.

In the special case that f is a polynomial, the Fundamental Theorem of Algebra asserts that the equation f (x) = 0 has a solution. The solution x could be a real or a complex number. Gauss, early in the 19th century, gave a proof of this existence result based on an algorithm which can be realized as a succession of applications of Newton's method (his proof had a gap). My 1981 paper "The Fundamental Theorem of Algebra and Complexity Theory" was based on Newton's Method and related to the Gauss idea.

Complexity (computational) theory is perhaps the central theme of theoretical computer science; in this theory a problem is called tractable in case there is an algorithm solving it using a polynomial bound (relative to the input size) on the number of bit-sized operations. On one hand I was inspired by this theme of computer science. On the other hand I found the formalism of this subject useless for analyzing the complexity of Newton's method.

In the above paper I counted the arithmetic operations, not the bit operations to measure the complexity. Moreover the concept of "condition number" of numerical analysis played a role in my complexity treatment of the Fundamental Theorem of Algebra. I showed tractability from this point of view.

The problem of finding a zero of a polynomial has a natural generalization to a system of polynomial equations. Toward dealing with this extension I was joined by Mike Shub in writing a series of joint papers we called "Complexity of Bezout's Theorem." Our goal was to make this problem tractable by finding an algorithm that yields an approximation in polynomial time. We failed in this effort and today it remains an important open problem. However Peter Burgisser and Felipe Cucker have come very close to a solution in a recent paper in the Annals of Mathematics journal. They used developments of Carlos Beltran and Luis Pardo along the way, and certainly Newton's method played a central role in their work.

Mike Shub and I were joined by Lenore Blum and together we generalized the Turing Machine of computer science to give foundational support for the zero-finding studies. The associated real number algorithms of this 3-person project became imbedded in setting of polynomial time, NP-completeness, tractability and all this made good sense. Eventually Felipe Cucker joined us to write the book, "Complexity and Real Computation." A reference is Volume 3 (650 pages) of my collected works.

John Keats has written, "Beauty is truth, truth beauty ...." He has also written "A thing of beauty is a joy forever." I wish to add, beauty is simple and it is profound. I hope that my few words will convince you that Newton's Method is a concept of great beauty.