Newton's method

Newton's method, also called the Newton-Raphson method or Newton iteration, is a root-finding algorithm; that is, a method for finding where a function obtains the value zero.

Description of the method

Newton's method is based on the insight that any smooth function f can be approximated locally by its tangent. If r is a root of f, the tangent of f at any point close to r is a good approximation of f, and hence the point where the tangent intercepts the x-axis is a good approximation of r. This suggests that if we know an approximation x_k for r, we obtain an even better approximation x_k+1 from the root of the tangent line that goes through (x, f(x)). Expressing the equation for the tangent in the terms of $f'$, the derivative of f, gives the solution

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}.$

The calculation of an improved approximation with this formula is called a Newton step or Newton update. Newton's method consists of repeating this step for k = 0, 1, 2, ... to obtain successively better estimates x₁, x₂, x₃, ... for r. Provided that the initial guess x₀ is sufficiently close to r and that f is sufficiently well-behaved, the estimates will converge rapidly to r as k goes to infinity.

Illustration of a single step with Newton's method. The function f has a root at x = r. We start with an initial guess x₀ and calculate the tangent line of f in that point. The root of the tangent, x₁, is a better approximation of r than the initial guess.

Example: calculating the golden ratio

The golden ratio (φ ≈ 1.618) is the largest root of the polynomial $f(x)=x^{2}-x-1$. To calculate this root, we can use the Newton iteration

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}=x_{k}-{\frac {{x_{k}}^{2}-x_{k}-1}{2x_{k}-1}}={\frac {x_{k}^{2}+1}{2x_{k}-1}}$

with the initial estimate x₀ = 1. Using double-precision floating-point arithmetic, which allows a precision of roughly 16 digits, Newton's method produces the following sequence of approximations:

x₀ = 1.0

x₁ = 2.0

x₂ = 1.6666666666666667

x₃ = 1.6190476190476191

x₄ = 1.6180344478216817

x₅ = 1.618033988749989

x₆ = 1.6180339887498947

x₇ = 1.6180339887498949

x₈ = 1.6180339887498949

Since the last update does not change the value, we can be reasonably sure to have obtained a value for the golden ratio that is correct to the available precision. It can be seen that each iteration roughly doubles the number of correct digits. We say that the rate of convergence is quadratic. Newton's method typically — but not always — achieves such fast convergence.

Convergence analysis

Intuitively, Newton's method is based on the idea that a continuous function f can be approximated locally by a line. If both the root r and the initial guess $x_{0}$ lie in a region where f is "sufficiently linear" — we may call such an area a region of convergence, Newton's method is guaranteed to converge to the root.

The convergence rate of Newton's method can be derived using Taylor series. Taking the Taylor series of f around x_k gives

$f(r)=0=f(x_{k})+f'(x_{k})(r-x_{k})+{\frac {1}{2}}f''(\xi _{k})(r-x_{k})^{2}$

where $\xi _{k}\in [r,x_{k}]$. Assuming $f'(x_{k})\neq 0$, dividing through gives

$0={\frac {f(x_{k})}{f'(x_{k})}}-x_{k}+r+{\frac {1}{2}}{\frac {f''(\xi _{k})}{f'(x_{k})}}(r-x_{k})^{2}.$

Moving terms to the left hand side and substituting the Newton update expression for x_k+1 then gives

$x_{k+1}-r={\frac {1}{2}}{\frac {f''(\xi _{k})}{f'(x_{k})}}(r-x_{k})^{2}$

and a final division shows that

${\frac {|x_{k+1}-r|}{|x_{k}-r|^{2}}}={\frac {1}{2}}\left|{\frac {f''(\xi _{k})}{f'(x_{k})}}\right|.$

This is the expression for a rate of convergence that is at least quadratic. If the second derivative $f''$ vanishes near the root, the convergence is faster than quadratic. However, if $f'(r)=0$, meaning that f has a double root, the result becomes slightly different: it can then be shown that the convergence is only linear.

Most functions do not globally resemble lines: in general, function graphs contain curvature, stationary points, and discontinuities. Does Newton's method work in these cases? The answer is maybe. If we start with an initial guess that lies outside a region of convergence, Newton's method produces a sequence of numbers that may jump back and forth erratically or even gradually move away from the root. If we are lucky, a value eventually ends up a region of convergence. But if we are unlucky, Newton's method may entirely fail to converge.

For example, if Newton's method is used to solve the equation $x^{3}-5x=0$ with the initial guess $x_{0}=1$, it will produce the endlessly repeating sequence $1,-1,1,-1,1,...$.

It may also happen that Newton's method converges to a root, but the wrong one. For example, if we attempt to calculate $\pi$ as the smallest positive solution to $\sin x=0$, we must choose an initial value close to 3.14. Newton's method started near 0 would converge to 0; if started near 6.28, it would converge to $2\pi$. If we start with $x_{0}$ close to $\pi /2$, where the sine curve is horizontal, $x_{1}$ may end up close to $n\pi$ for some enormous n.

Complex functions

Newton's method also works for complex functions, but its convergence behavior become more intricate.

Leads to Newton fractals.

Newton's method as an optimization algorithm

Instead iterate

$x_{k+1}=x_{k}-{\frac {f'(x_{k})}{f''(x_{k})}}.$

Multidimensional version

Gauss-Newton's method

Variations and practical implementation concerns

Damped, bracketed and hybrid methods

The fact that Newton's method may converge slowly or fail to converge for functions with horizontal tangents, or when given poor initial values, makes it unsuitable in raw form as a general-purpose root-finding algorithm. It is therefore typically combined with some mechanism for detecting and correcting convergence failure.

One way to detect failure is count the number of iterations and break if the number exceeds some specified limit. Another technique is bracketing: the root is supplied along with known bounds for its location. Failure is signaled if the Newton iteration produces a value that lies outside the bounds.

In case of failure, it may be possible to recover by switching to a slower but safer algorithm, such as the bisection algorithm. After taking a few steps with the safe method, one can switch back to Newton's method and try again. This is called a hybrid method. Another option is the damped Newton's method, in which the derivative is multiplied by a damping factor $\alpha$, with $0<\alpha <1$.

Quasi-Newton methods

Newton's method requires that the derivative of the object function be known, but in some situations the derivative or Jacobian may be unavailable or prohibitively expensive to calculate. The cost can be higher still when Newton's method is used as an optimization algorithm, in which case the second derivative or Hessian is also needed.

An alternative in these situations is to use an approximation of the derivative or second-derivative, which leads to so-called quasi-Newton methods. The most common strategy is to use the function values from two successive iterations to calculate a finite difference approximation for the derivative. This is equivalent to the secant method and reduces the rate of convergence from 2 to 1.618 (more precisely, the golden ratio). An alternative is to compute a value for the derivative or second derivative accurately, but reusing the same value for several successive iterations.

Modifications of Newton's method can also lead to more specialized algorithms, such as the Durand-Kerner method which is used to find simultaneous roots of a polynomial.

Calculating inverse functions

Using Newton's method as described above, the time complexity of finding a simple root of a function f with n-digit precision is $O((\log n)F(n))$ where F is the cost of calculating $f/f'$ with n-digit precision. If f can be evaluated with variable precision, the algorithm can be improved. Because of the "self-correcting" nature of Newton's method, it is only necessary to use m-digit precision at a step where the approximation has m-digit accuracy. Hence, the first iteration can be performed with a precision twice as high as the accuracy of x₀, the second iteration with a precision four times as high, and so on. If the precision levels are chosen suitably, only the final iteration requires f and its derivative to be evaluated at full n-digit precision. Provided that F grows superlinearly, which is the case in practice, the cost of finding a root is thus only $O(F(n))$.

Root-finding is essentially the same thing as calculating an inverse function. Hence, due to the aforementioned result, two differentiable functions that are inverse functions of each other have equivalent computational complexity and can be calculated in terms of each other in practice using Newton's method. In particular, it can be shown that:

• The exponential function, the natural logarithm, the trigonometric functions, and the inverse trigonometric functions, are all equivalent
• The algebraic operations of multiplication, division, and square root extraction are equivalent

During the second half of the 20th century, very efficient algorithms were found for multiplying large numbers and calculating high-precision natural logarithms with the aid of computers. Combined with Newton's method, all of the functions listed above can be calculated with this efficiency.

History

Newton's method was described by Isaac Newton in De analysi per aequationes numero terminorum infinitas (written in 1669, published in 1711 by William Jones) and in De metodis fluxionum et serierum infinitarum (written in 1671, translated and published as Method of Fluxions in 1736 by John Colson). However, his description differs substantially from the modern description given above: Newton applies the method only to polynomials. He does not compute the successive approximations x_k, but computes a sequence of polynomials and only at the end, he arrives at an approximation for the root r. Finally, Newton views the method as purely algebraic and fails to notice the connection with calculus. Isaac Newton probably derived his method from a similar but less precise method by François Viète. The essence of Viète's method can be found in the work of Sharaf al-Din al-Tusi.

Newton's method was first published in 1685 in A Treatise of Algebra both Historical and Practical by John Wallis. In 1690, Joseph Raphson published a simplified description in Analysis aequationum universalis. Raphson again viewed Newton's method purely as an algebraic method and restricted its use to polynomials, but he describes the method in terms of the successive approximations x_k instead of the more complicated sequence of polynomials used by Newton. Finally, in 1740, Thomas Simpson described Newton's method as an iterative methods for solving general nonlinear equations using fluxional calculus, essentially giving the description above. In the same publication, Simpson also gives the generalization to systems of two equations and notes that Newton's method can be used for solving optimization problems by setting the gradient to zero.

References

• Michael T. Heath (2002), Scientific Computing: An Introductory Survey, Second Edition, McGraw-Hill
• Jonathan M. Borwein & Peter B. Borwein (1987), Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity, Wiley Interscience
• Tjalling J. Ypma (1995), Historical development of the Newton-Raphson method, SIAM Review 37 (4), 531–551.