Newton's Method (Newton-Raphson Method)

1. Overview

Newton's method is an iterative technique for numerically finding roots of nonlinear equations $f(x) = 0$, and is one of the most fundamental and powerful methods in numerical analysis. It was independently discovered by Isaac Newton and Joseph Raphson, and is also known as the Newton-Raphson method.

The method approximates $f$ at each point by its tangent line (first-order Taylor expansion) and takes the intersection of that tangent line with the $x$-axis as the next approximation. With an appropriate initial value, it exhibits quadratic convergence, meaning the number of correct digits approximately doubles with each iteration.

2. Algorithm

The procedure is as follows.

1. Choose an initial value $x_0$.
2. Compute $x_1, x_2, \ldots$ successively using the iteration formula.
3. Stop when $|x_{n+1} - x_n| < \varepsilon$ or $|f(x_n)| < \delta$ ($\varepsilon$: tolerance for position, $\delta$: tolerance for function value).

3. Graphical Interpretation

The equation of the tangent line at the point $(x_n,\, f(x_n))$ is

and the point where this tangent line intersects the $x$-axis ($y=0$) is $x_{n+1}$.

Animation: Convergence in Action

The animation below shows how Newton's method converges from the initial value $x_0 = 3.5$ to the root $x^* \approx 2.095$.

Derivation of the Formula

The equation of the tangent line at $(x_n, f(x_n))$ can be written as:

Setting $y = 0$ to find where this tangent line intersects the $x$-axis:

This is the next approximation $x_{n+1}$. That is, the iteration formula of Newton's method arises naturally as the $x$-intercept of the tangent line.

4. Quadratic Convergence

This means that the next error is proportional to the square of the current error, multiplied by the constant $C$. For example, if the current error is $10^{-3}$, the next error is approximately $C \times (10^{-3})^2 = C \times 10^{-6}$. The number of correct digits roughly doubles with each iteration, which is why this is called "quadratic" convergence.

5. Example: Computing $\sqrt{2}$

Python implementation

def newton(f, fp, x0, tol=1e-10, max_iter=100):
    """Solve f(x) = 0 by Newton's method.

    Args:
        f, fp: function and its derivative
        x0:    initial guess
        tol:   tolerance applied to both |f(x)| and |Δx|
        max_iter: maximum number of iterations
    Returns:
        (root, iters)
    Raises:
        ValueError: derivative is too close to zero
        RuntimeError: no convergence within max_iter
    """
    x = x0
    for i in range(max_iter):
        fx = f(x)
        if abs(fx) < tol:
            return x, i
        fpx = fp(x)
        if abs(fpx) < 1e-14:
            raise ValueError(f"derivative too small at x={x}")
        x_next = x - fx / fpx
        if abs(x_next - x) < tol:
            return x_next, i + 1
        x = x_next
    raise RuntimeError(f"did not converge in {max_iter} iterations")

# Example: compute sqrt(2)
root, iters = newton(lambda x: x*x - 2, lambda x: 2*x, x0=1.0)
print(root, iters)  # 1.414213562373095 5

6. Multivariable Newton's Method

For a system of nonlinear equations $\mathbf{f}(\mathbf{x}) = \mathbf{0}$ ($\mathbf{x} \in \mathbb{R}^n$), the iteration formula becomes

where $J(\mathbf{x})$ is the Jacobian matrix

Although the iteration formula involves $J^{-1}$, in practice one does not compute the inverse matrix explicitly. Instead, one solves the linear system

via LU decomposition or similar methods, and updates $\mathbf{x}_{n+1} = \mathbf{x}_n + \Delta\mathbf{x}$. There are two main reasons for avoiding the explicit inverse:

• Numerical stability: Computing the inverse is susceptible to catastrophic cancellation, whereas solving the linear system directly via LU decomposition yields higher accuracy.
• Memory efficiency: The inverse is a full $n \times n$ dense matrix that must be stored, whereas LU decomposition works in-place and produces $\Delta\mathbf{x}$ directly.

Since $J(\mathbf{x}_n)$ changes at every iteration, the LU factorization must be recomputed each time.

7. Convergence Conditions and Failure Cases

Sufficient Conditions for Convergence

• $f(x^*) = 0$ and $f'(x^*) \neq 0$ (simple root).
• $f$ is twice continuously differentiable in a neighborhood of the root.
• The initial value $x_0$ is sufficiently close to the root.

Failure Cases

• Multiple roots: When $f'(x^*)=0$, convergence degrades to linear. If the multiplicity $m$ is known, the modified Newton's method $x_{n+1} = x_n - m\,f(x_n)/f'(x_n)$ restores quadratic convergence. When $m$ is unknown, one can apply Newton's method to $u(x) = f(x)/f'(x)$ instead, whose roots are all simple.
• Zero derivative: If $f'(x_n) \approx 0$ during iteration, the method diverges.
• Periodic oscillation: For example, with $f(x) = x^3 - 2x + 2$ and $x_0 = 0$, the iterates oscillate as $x_0 \to 1 \to 0 \to 1 \to \cdots$.

Improved Methods and Practical Remedies

Global convergence can be ensured by damped Newton's method ($x_{n+1} = x_n - \alpha_n\, f(x_n)/f'(x_n)$, where $\alpha_n$ is determined by line search) or by combining with the bisection method.

8. Comparison with the Bisection Method

9. Advanced Topics and Related Methods

Below are advanced topics related to Newton's method.

Classical square-root algorithms (the Babylonian and Heron's methods)

The recurrence $x_{n+1} = \dfrac{1}{2}\!\left(x_n + \dfrac{2}{x_n}\right)$ for $\sqrt{2}$ seen in §5 is a special case of the general form $x_{n+1} = \dfrac{1}{2}\!\left(x_n + \dfrac{a}{x_n}\right)$ obtained by applying Newton's method to $f(x) = x^2 - a$. This coincides exactly with the classical Babylonian method (ancient Mesopotamia) and Heron's method (described by Heron of Alexandria in the 1st century) for computing square roots. Newton's method can be regarded as a unified generalization of such individual root-extraction algorithms to arbitrary equations.

The Newton fractal (basins of attraction)

Applying Newton's method to a function on the complex plane (the classic example being $z^3 - 1 = 0$) and coloring each initial value $z_0$ according to which root it converges to produces a self-similar figure called the Newton fractal. The set of initial values converging to a given root is called that root's basin of attraction, and the boundaries between basins have a fractal structure. This visually demonstrates sensitivity to the initial value—a tiny change can lead to convergence to a completely different root—and is a striking example of how the global behavior of Newton's method is generally hard to predict.

Higher-order methods (Halley's method)

Using the second derivative $f''$ as well, one can construct iterations with a higher order of convergence than Newton's method. A representative example is Halley's method, which converges cubically:

The cost per step increases, but it is advantageous when very high accuracy is required or when $f''$ is cheap to evaluate. Newton's method (quadratic convergence) is the most basic case of such higher-order iterations.

Quasi-Newton methods (derivative-approximating variants)

When the derivative or Jacobian is difficult or expensive to compute, variants that approximate them are used. In one dimension, the secant method approximates $f'$ by a finite difference (order of convergence $\varphi \approx 1.618$); in several dimensions, quasi-Newton methods approximate and update the Jacobian at each iteration. The classic instance is Broyden's method (1965), which performs a low-rank update of the Jacobian approximation from the change in function values at each step. The BFGS method, widely used in optimization, is also a quasi-Newton method.

10. Summary

• Newton's method iteration formula: $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$
• It is a graphical method that uses the intersection of the tangent line with the $x$-axis as the next approximation.
• Quadratic convergence: the number of correct digits approximately doubles with each iteration.
• Computation of the derivative $f'(x)$ is required.
• The choice of initial value is critical, and convergence is not guaranteed in all cases.
• Extension to multiple variables requires the Jacobian matrix and solving a linear system.

11. Frequently Asked Questions

12. References

• Wikipedia, "Newton's method"
• Wikipedia, "Kantorovich theorem"
• R. L. Burden & J. D. Faires, Numerical Analysis, 10th ed., Cengage, 2016.
• J. Nocedal & S. J. Wright, Numerical Optimization, 2nd ed., Springer, 2006.
• J. M. Ortega & W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, 1970 (the standard reference for multivariate Newton and the Kantorovich theorem).
• L. V. Kantorovich, "Functional analysis and applied mathematics," Uspekhi Mat. Nauk, vol. 3, no. 6, pp. 89--185, 1948 (original Kantorovich convergence theorem).
• N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002 (Chapter 3 on numerical stability of iterations and stopping-criterion pitfalls).
• Wikipedia, "Newton fractal" (basins of attraction on the complex plane).
• Wikipedia, "Quasi-Newton method" (Broyden, BFGS).