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

10. Frequently Asked Questions

11. 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).