Newton method

What Is the Newton Method?

The Newton method, also known as the Newton-Raphson method, is an iterative numerical technique for finding the roots or minima of real-valued functions. Named after Isaac Newton and Joseph Raphson, who independently developed related formulations in the seventeenth and eighteenth centuries, it works by constructing a local linear (or quadratic) approximation to the function at each step and solving that simpler problem to obtain the next estimate. The process repeats until the solution converges to within a specified tolerance.

The method draws its theoretical foundation from differential calculus and linear algebra. Given a function f and its derivative f', the iteration updates an estimate x by the rule x_new = x - f(x)/f'(x), replacing the curve with its tangent line at each point and reading off where that tangent crosses zero. For functions with a second derivative, the geometric interpretation is that each step fits a parabola to the graph and advances to that parabola's extremum.

Root Finding

In root finding, the Newton method finds successive approximations to the solutions of f(x) = 0. Under favorable conditions, the method converges quadratically: the number of correct decimal places roughly doubles with each iteration, making it far faster than bisection or secant methods for well-behaved functions. This quadratic convergence property, described in Newton's method and its use in optimization, depends on the initial estimate being sufficiently close to the true root and the function being smooth in that neighborhood. When these conditions are not met, the method may converge slowly, cycle, or diverge. The extension to systems of equations, where f becomes a vector function and the derivative becomes the Jacobian matrix, allows the method to solve nonlinear systems in multiple variables.

The Newton method also applies to locating poles and zeros of complex functions, a key task in filter design and control system analysis. Computing the roots of a characteristic polynomial, for instance, places eigenvalues and determines system stability.

Optimization Methods

In optimization, the Newton method minimizes a function by treating the gradient as the function to be zeroed. The update step uses the inverse of the Hessian matrix, which encodes the local curvature of the objective. Multiplying the gradient by the inverse Hessian rescales the search direction: in directions of high curvature the step is short, in directions of low curvature the step is long. For a strictly convex quadratic objective, a single Newton step reaches the exact minimum. This makes the method particularly well suited to problems where the Hessian can be computed or approximated at low cost.

The MIT OpenCourseWare notes on Newton's method for unconstrained optimization describe how Newton iterations form the inner loop of interior-point algorithms for linear and convex programming, one of the most computationally important applications in modern operations research. Quasi-Newton methods, such as BFGS (Broyden-Fletcher-Goldfarb-Shanno), approximate the Hessian from gradient differences to avoid the O(n^3) cost of matrix inversion at each step, making the approach tractable for large-scale problems.

A critical limitation is locality: convergence is guaranteed only when the starting point lies within a basin around the solution. In practice, globalization strategies such as line search and trust-region methods are paired with Newton steps to improve robustness. Carnegie Mellon's convex optimization course provides a detailed treatment of these modifications.

Applications

The Newton method has applications across many quantitative disciplines, including: