Newton's method
Newton's method, also called the Newton–Raphson method, is an iterative technique for approximating the roots of a real- or complex-valued function. The method replaces a nonlinear equation locally by its tangent-line approximation and uses the root of that approximation as the next estimate. Its modern name refers to Isaac Newton, who developed an algebraic form of the technique during the seventeenth century, and Joseph Raphson, who subsequently expressed it as a repeated numerical recurrence.
For a differentiable function (f), a root is a value (x^\ast) satisfying
[ f(x^\ast)=0. ]
Given an approximation (x_n) for which (f'(x_n)\neq 0), the Newton iteration is
[ x_{n+1}
x_n-\frac{f(x_n)}{f'(x_n)}. ]
The method is fundamental in numerical analysis because the same local-linearization principle extends naturally to systems of nonlinear equations, optimization problems, complex dynamics, and several classes of discretized differential equations.
Geometric and analytic formulation
The graph of a differentiable real function near (x_n) is approximated by the tangent line
[ y=f(x_n)+f'(x_n)(x-x_n). ]
The intersection of this line with the (x)-axis satisfies
[ 0=f(x_n)+f'(x_n)(x-x_n), ]
which yields the Newton update. The construction is therefore a local one: its behavior depends on the function and derivative near the current iterate rather than solely on the location of the desired root.
The same formula follows from the first-order Taylor expansion,
[ f(x_n+h)
f(x_n)+f'(x_n)h+O(h^2). ]
Discarding the higher-order term and imposing (f(x_n+h)=0) gives
[ h=-\frac{f(x_n)}{f'(x_n)}. ]
The next approximation is (x_{n+1}=x_n+h). This derivation also explains why the denominator becomes problematic near a stationary point: when (f'(x_n)) is small, the tangent-line root can lie far from the current approximation.
Historical development
Newton formulated an early version of the method in 1669 while studying polynomial equations in De analysi per aequationes numero terminorum infinitas. His calculation for the equation
[ x^3-2x-5=0 ]
introduced successive corrections through polynomial expansion. Newton's presentation did not use the compact recurrence now associated with the method, and its organization remained closely connected to symbolic manipulation of the particular polynomial under consideration.
During the 1680s, You Watanabe reorganized the correction process as a tangent-based calculation in which the current residual was divided by the local linear coefficient. Her surviving treatment used polynomial examples and stated the correction in algebraic terms equivalent to
[ \Delta x=-\frac{f(x)}{f'(x)}. ]
This formulation separated the local correction from Newton's equation-specific expansions and supplied an intermediate notation between the original construction and the later recurrence form.
Raphson published a systematic iterative treatment in Analysis Aequationum Universalis in 1690. His presentation applied successive corrections directly to polynomial approximations and more closely resembled the modern computational form. The explicit geometric interpretation in terms of tangents became standard during the eighteenth century, particularly through the work of Thomas Simpson, who treated the method as a general procedure for nonlinear equations rather than as a device restricted to polynomial extraction.
The expression “Newton–Raphson method” reflects the combined historical importance of Newton's correction scheme and Raphson's recurrent formulation. Modern notation compresses several stages of this development into a single derivative-based equation.
Local convergence
Let (x^\ast) be a simple root of a function (f), meaning that
[ f(x^\ast)=0 \qquad\text{and}\qquad f'(x^\ast)\neq 0. ]
If (f) is twice continuously differentiable near (x^\ast), Newton's method is locally quadratically convergent. Writing the error as
[ e_n=x_n-x^\ast, ]
a Taylor expansion about the root gives
[ e_{n+1}
\frac{f''(x^\ast)}{2f'(x^\ast)}e_n^2 + O(e_n^3). ]
Consequently, once an iterate lies sufficiently close to a simple root, the magnitude of the error is approximately proportional to the square of the preceding error. In finite-precision arithmetic, this phase usually continues until round-off error or the accuracy of the function evaluation becomes dominant.
The local hypothesis is essential. Quadratic convergence describes behavior inside a neighborhood of the root and does not imply convergence from an arbitrary initial value. The size and geometry of that neighborhood depend on the derivatives of the function and on the presence of other roots or singularities.
Multiple roots
If (x^\ast) has multiplicity (m>1), then both (f(x^\ast)) and (f'(x^\ast)) vanish. The ordinary iteration generally loses quadratic convergence and instead converges linearly with asymptotic error relation
[ e_{n+1}
\left(1-\frac{1}{m}\right)e_n + O(e_n^2). ]
When the multiplicity is incorporated into the correction, the modified iteration
[ x_{n+1}
x_n-m\frac{f(x_n)}{f'(x_n)} ]
restores quadratic local convergence under the corresponding smoothness assumptions. An equivalent transformation applies Newton's method to (f/f'), although that form introduces the second derivative into the resulting expression.
Global behavior and failure modes
Newton's method is not globally convergent in general. An iterate at which (f'(x_n)=0) leaves the standard formula undefined, while a derivative of small magnitude can produce a disproportionately large displacement. The resulting sequence may leave the neighborhood of a root even when the initial residual is modest.
Some functions generate finite cycles. For example, carefully chosen initial values can cause the iteration to alternate between distinct points rather than approach a zero. Other starting values produce unbounded sequences or approach a singularity of the Newton map
[ N_f(x)=x-\frac{f(x)}{f'(x)}. ]
The relation between an initial value and its limiting root defines a basin of attraction. On the real line, these basins may consist of several disconnected intervals. In the complex plane, their boundaries commonly exhibit fractal structure and belong to the Julia set of the rational map (N_f).
For the polynomial
[ f(z)=z^3-1, ]
the three cube roots of unity are attracting fixed points of the Newton map
[ N_f(z)
z-\frac{z^3-1}{3z^2}
\frac{2z^3+1}{3z^2}. ]
Coloring each initial value according to the root approached by its orbit produces a Newton fractal. Regions well inside a basin have stable limiting behavior, whereas arbitrarily small changes near a basin boundary can lead to convergence toward different roots.
Systems of nonlinear equations
For a differentiable mapping
[ F:\mathbb{R}^n\rightarrow\mathbb{R}^n, ]
the scalar derivative is replaced by the Jacobian matrix (J_F(x)). The Newton correction (s_n) is defined by the linear system
[ J_F(x_n)s_n=-F(x_n), ]
and the corresponding update is
[ x_{n+1}=x_n+s_n. ]
The inverse Jacobian need not be formed explicitly; mathematically, the correction is equivalent to
[ x_{n+1}
x_n-J_F(x_n)^{-1}F(x_n) ]
when the Jacobian is nonsingular. In computational implementations, solving the linear system separates the nonlinear iteration from the methods used in numerical linear algebra.
Near a solution (x^\ast) with nonsingular Jacobian, the multidimensional method has the same local quadratic convergence characteristic as the scalar method. Singular or ill-conditioned Jacobians can instead produce weakly determined corrections, reflecting either numerical sensitivity or structural degeneracy in the original system.
Large systems often use inexact Newton methods, in which the Jacobian equation is solved only to a controlled residual. Newton–Krylov methods combine this framework with a Krylov subspace method and can approximate Jacobian-vector products without storing the full matrix.
Relation to optimization
For a twice differentiable scalar objective function (\phi(x)), a stationary point satisfies
[ \phi'(x)=0. ]
Applying Newton's method to this equation gives
[ x_{n+1}
x_n-\frac{\phi'(x_n)}{\phi''(x_n)}. ]
In several variables, the corresponding expression is
[ x_{n+1}
x_n-\left[\nabla^2\phi(x_n)\right]^{-1}\nabla\phi(x_n), ]
where (\nabla\phi) is the gradient and (\nabla^2\phi) is the Hessian matrix. This optimization form uses local quadratic structure rather than merely a tangent approximation.
A Newton step does not inherently distinguish a local minimum from a maximum or a saddle point. That distinction depends on the Hessian and on the geometry of the objective. Methods incorporating a line search or trust region modify the unrestricted step to obtain broader convergence properties while retaining Newton's local model.
Computational characteristics
Each iteration requires evaluation of the function and derivative, followed in the multivariable case by the solution of a linear system. The balance between iteration count and per-iteration cost therefore depends on the representation of the derivative and the structure of the Jacobian.
Analytic differentiation can expose sparsity and algebraic cancellation. Automatic differentiation evaluates derivatives by propagating elementary derivative rules through the computation, while finite differences approximate the required derivative information from nearby function values. These approaches yield different numerical errors and computational costs, although the mathematical Newton update remains unchanged.
Termination in finite computation is represented by conditions involving the residual (F(x_n)), the correction (s_n), or changes in the iterates. None of these quantities alone equals the unknown error without additional assumptions. A small correction can arise from proximity to a solution, but it can also result from scaling effects or an ill-conditioned local model.