Newton's method

Newton's method, also called the Newton-Raphson method or Newton iteration, is a root-finding algorithm first described by Isaac Newton.

Description

Newton's method is based on the insight that any differentiable 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.

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 floating-point arithmetic, which allows a precision of roughly 16 digits, we obtain the following 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

Suppose we have a function f with f(r) = 0. To analyze the convergence properties of Newton's method, we can use the Taylor series of f around x_k. This 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|.$

Hence, the rate of convergence is at least quadratic. However, if $f'(r)=0$, meaning that f has a double root, it can be shown that the convergence is only linear.

• More detail needed

Examples of non-quadratic convergence

• Insert some example of linear convergence and/or convergence failure here

In rare cases, Newton's method may converge faster than quadratically. One such situation appears if we attempt to calculate π as the smallest positive number x for which sin x = 0. This equation leads to the Newton iteration

$x_{k+1}=x_{k}-{\frac {\sin x_{k}}{\cos x_{k}}}=x_{k}-\tan {x_{k}}.$

Knowing that π is a little larger than 3, we may start with the initial value x₀ = 3. Three iterations give a value of π that is correct to full double precision:

x₀ = 3.0

x₁ = 3.1425465430742778

x₂ = 3.141592653300477

x₃ = 3.1415926535897931

In this case, the convergence is cubic; that is, every iteration roughly triples the number of correct digits.

It is important to note that the choice of initial value determined the outcome of this calculation. If we had started with a number too close to 0, the iteration would have converged to 0. More generally, if we had started with an approximation close to nπ for some integer n other than n = 1, the iteration would have converged to nπ. If we had started with a value x₀ close to (n + 1/2)π, tan x₀ would have been a very large number and x₁ would have turned out far away from the origin.

Complex functions

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 estimates, 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.

• Bracketed, hybrid

Newton's method can be combined with a slower but safer algorithm, such as the bisection algorithm.

limit number of iterations

• Damped

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.

Computational complexity of inversion

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.

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