Newton’s method is an iterative algorithm for approximating a root of an equation, usually written (f(x)=0). Starting from an initial estimate, it replaces a function by a local linear approximation and uses that approximation’s root as the next estimate. It is a fundamental technique in numerical analysis, with extensions to nonlinear systems and mathematical optimization. Its effectiveness depends on both the function and the starting point. (math.ubc.ca)
Iteration and geometric interpretation
For a differentiable function of one variable, Newton’s iteration is
[ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}, \qquad n=0,1,2,\ldots, ]
provided that the derivative (f'(x_n)) is nonzero. The initial estimate (x_0) must be supplied separately; the formula does not itself locate a suitable starting region. (personal.math.ubc.ca)
Geometrically, the method draws the tangent line to (y=f(x)) at ((x_n,f(x_n))). Its equation is
[ y=f(x_n)+f'(x_n)(x-x_n). ]
Setting (y=0) produces the next iterate. Thus, each step solves a linear approximation rather than the original nonlinear equation. For a nonconstant linear function, this approximation is exact, and one step finds the root. The construction connects calculus with computational root finding. (personal.math.ubc.ca)
For example, applying the formula to the polynomial (f(x)=x^2-2) gives
[ x_{n+1}=\frac12\left(x_n+\frac{2}{x_n}\right). ]
Starting with (x_0=1), successive estimates are (1.5), approximately (1.4166667), and approximately (1.4142157), approaching (\sqrt2). These values illustrate how rapidly accuracy can improve once the estimates are near a root. (personal.math.ubc.ca)
Convergence
A standard local result assumes that (f) is twice continuously differentiable near a root (r) and that (f'(r)\ne0). Such a root is called simple. If the initial estimate is sufficiently close to (r), Newton’s method converges with at least quadratic convergence: the new error is bounded by a constant times the square of the previous error. (dlmf.nist.gov)
Writing (e_n=x_n-r), the asymptotic error relation is
[ e_{n+1} =\frac{f''(r)}{2f'(r)}e_n^2+o(e_n^2). ]
Consequently, the number of correct digits often roughly doubles per iteration in the local convergence regime. If the leading coefficient vanishes, convergence can be faster. This error analysis follows from a Taylor expansion around the root. (dlmf.nist.gov)
For a root of multiplicity (m>1), ordinary Newton iteration generally converges only linearly, with asymptotic error factor (1-1/m). When (m) is known, the modified update
[ x_{n+1}=x_n-m\frac{f(x_n)}{f'(x_n)} ]
restores local quadratic convergence under suitable smoothness assumptions. (dlmf.nist.gov)
Failure and starting-point sensitivity
Local convergence does not imply convergence from every initial estimate. A step may encounter a zero derivative, move far from the intended root, or enter a cycle. Different initial estimates may also lead to different roots. (openstax.org)
A simple cycling example is
[ f(x)=x^3-2x+2. ]
Starting at (x_0=0) gives (x_1=1), followed by (x_2=0). The sequence therefore alternates indefinitely between two points, neither of which is a root. A small derivative can likewise produce an excessively large correction because it appears in the denominator. (openstax.org)
These limitations motivate safeguarded approaches. Bracketing methods such as the bisection method retain an interval containing a root, while hybrid algorithms combine that reliability with faster interpolation or Newton-like steps. (docs.scipy.org)
Systems of nonlinear equations
For (F:\mathbb R^d\to\mathbb R^d), Newton’s method replaces the scalar derivative by the Jacobian matrix (J_F(x)), whose entries are the first partial derivatives of the component functions. At each iteration, the correction (s_n) satisfies
[ J_F(x_n)s_n=-F(x_n), \qquad x_{n+1}=x_n+s_n. ]
The nonlinear problem is thereby reduced to a system of linear equations at each step. Local quadratic convergence requires suitable regularity and a nonsingular Jacobian at the solution. (dlmf.nist.gov)
Optimization
For a smooth objective function (g), Newton’s method can solve the stationarity equation (\nabla g(x)=0). Its update uses the gradient and Hessian matrix:
[ \nabla^2g(x_n)s_n=-\nabla g(x_n). ]
Unlike gradient descent, it incorporates second-order curvature information. When the Hessian is positive definite, the Newton direction is a descent direction; without that property, solving the stationarity equation does not necessarily identify a minimum. (stanford.edu)
A damped iteration takes (x_{n+1}=x_n+\alpha_ns_n), with the step length selected through a line search. This can improve behavior away from the solution. Computing the direction requires evaluating derivatives and solving a linear system, so individual iterations may be substantially more expensive than first-order steps. Large-scale variants exploit matrix structure or approximately solve the Newton system. (stanford.edu)
Implementation and related methods
Termination commonly uses a small residual, a small change between successive estimates, or an iteration limit. A small step alone does not guarantee that a root has been found; the residual must be checked separately. (docs.scipy.org)
The secant method replaces the derivative with a slope calculated from two previous estimates. It avoids explicit derivative evaluation, trading Newton’s local convergence rate for cheaper iterations. Halley’s method additionally uses second derivatives and can achieve cubic local convergence. (math.ubc.ca)
Historical development
The method is named after Isaac Newton, who described an early polynomial-based procedure in 1669. Joseph Raphson introduced substantial changes in 1690, and Thomas Simpson contributed further changes in 1740. The modern derivative-based iteration therefore reflects a historical development rather than an unchanged transcription of Newton’s original procedure. (personal.math.ubc.ca)