Chapter 2: Newton's Method (Newton-Raphson Method)
basic
Published: 2026-03-27
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
Newton's Method Iteration Formula
When $f$ is differentiable and $f'(x_n) \neq 0$,
The procedure is as follows.
- Choose an initial value $x_0$.
- Compute $x_1, x_2, \ldots$ successively using the iteration formula.
- Stop when $|x_{n+1} - x_n| < \varepsilon$ or $|f(x_n)| < \varepsilon$.
3. Geometric Interpretation
The equation of the tangent line at the point $(x_n,\, f(x_n))$ is
$$y = f(x_n) + f'(x_n)(x - x_n)$$and the point where this tangent line intersects the $x$-axis ($y=0$) is $x_{n+1}$.
Derivation of the Formula
The equation of the tangent line at $(x_n, f(x_n))$ can be written as:
$$y - f(x_n) = f'(x_n)(x - x_n)$$Setting $y = 0$ to find where this tangent line intersects the $x$-axis:
$$0 - f(x_n) = f'(x_n)(x - x_n)$$ $$x = x_n - \frac{f(x_n)}{f'(x_n)}$$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
Theorem (Quadratic Convergence)
If $f$ is twice continuously differentiable and $x_0$ is taken sufficiently close to a simple root $x^*$ ($f(x^*)=0$, $f'(x^*)\neq 0$), then Newton's method converges quadratically:
Outline of the proof: Expanding in a Taylor series around $x^*$,
$$0 = f(x^*) = f(x_n) + f'(x_n)(x^* - x_n) + \frac{f''(\xi_n)}{2}(x^* - x_n)^2$$Rearranging using the iteration formula $x_{n+1} = x_n - f(x_n)/f'(x_n)$, we obtain
$$x_{n+1} - x^* = \frac{f''(\xi_n)}{2f'(x_n)}(x_n - x^*)^2$$where $\xi_n$ is a point between $x_n$ and $x^*$.
Meaning of Quadratic Convergence
Since the error decreases quadratically, the number of correct digits approximately doubles with each iteration.
Example: $10^{-2} \to 10^{-4} \to 10^{-8} \to 10^{-16}$
5. Example: Computing $\sqrt{2}$
Applying Newton's Method to $f(x) = x^2 - 2$
Since $f'(x) = 2x$, the iteration formula becomes:
$$x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\!\left(x_n + \frac{2}{x_n}\right)$$Starting from the initial value $x_0 = 1$:
| $n$ | $x_n$ | Error $|x_n - \sqrt{2}|$ | Correct digits |
|---|---|---|---|
| 0 | 1.000000000 | 4.14 × 10⁻¹ | 0 |
| 1 | 1.500000000 | 8.58 × 10⁻² | 1 |
| 2 | 1.416666667 | 2.45 × 10⁻³ | 2 |
| 3 | 1.414215686 | 2.12 × 10⁻⁶ | 5 |
| 4 | 1.414213562 | 1.59 × 10⁻¹² | 11 |
In just 4 iterations, 11 digits of accuracy are obtained. The progression of correct digits 0 → 1 → 2 → 5 → 11, approximately doubling each time, demonstrates the power of quadratic convergence.
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
$$J(\mathbf{x}) = \begin{pmatrix} \dfrac{\partial f_1}{\partial x_1} & \cdots & \dfrac{\partial f_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \dfrac{\partial f_n}{\partial x_1} & \cdots & \dfrac{\partial f_n}{\partial x_n} \end{pmatrix}$$In practice, instead of computing the inverse matrix directly, one solves the linear system $J(\mathbf{x}_n)\,\Delta\mathbf{x} = -\mathbf{f}(\mathbf{x}_n)$ at each iteration using LU decomposition or similar methods, and sets $\mathbf{x}_{n+1} = \mathbf{x}_n + \Delta\mathbf{x}$. 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.
Practical Remedies
- Use the bisection method to narrow down an approximate range, then apply Newton's method.
- Limit the step size when $|f'(x_n)|$ is too small.
- Set an upper bound on the number of iterations.
8. Comparison with the Bisection Method
| Bisection Method | Newton's Method | |
|---|---|---|
| Convergence rate | First-order (linear) | Second-order (quadratic) |
| Required information | $f(x)$ only | $f(x)$ and $f'(x)$ |
| Convergence guarantee | Always converges | Depends on initial value |
| Typical iterations | 20–50 | 5–10 |
9. Summary
- Newton's method iteration formula: $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$
- It is a geometric 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
Q1. What is Newton's method?
It is a technique for iteratively finding roots of a nonlinear equation $f(x)=0$ using tangent-line approximation. The iteration formula is $x_{n+1} = x_n - f(x_n)/f'(x_n)$.
Q2. How fast does Newton's method converge?
Near a simple root, it converges quadratically. That is, the number of correct digits approximately doubles with each iteration. For multiple roots, convergence degrades to linear.
Q3. Can Newton's method fail?
It can fail when the derivative is close to zero, when the initial value is too far from the root, or when periodic oscillation occurs. Damped Newton's method or combining with the bisection method can address these issues.
11. References
- Wikipedia, "Newton's method" (English)
- Wikipedia, "Newton's method" (Japanese)
- R. L. Burden & J. D. Faires, Numerical Analysis, 10th ed., Cengage, 2016.
- J. Nocedal & S. J. Wright, Numerical Optimization, 2nd ed., Springer, 2006.