Newton's Method: Quadratic Convergence Proof and Stopping Rule
Let $f : \mathbb{R} \to \mathbb{R}$ be twice continuously differentiable, and suppose $f(\alpha) = 0$ with $f'(\alpha) \neq 0$ (i.e., $\alpha$ is a simple root).
- Write down Newton's method for approximating $\alpha$.
- Prove that Newton's method converges locally and quadratically: if $x_0$ is sufficiently close to $\alpha$, then $|x_{n+1} - \alpha| \leq C |x_n - \alpha|^2$ for some constant $C$.
- State a practical stopping rule that controls the absolute error in the root estimate.
Hints
- Write the error $e_n = x_n - \alpha$ and express $e_{n+1}$ in terms of $e_n$ by substituting the Newton update. You need to show the leading term is proportional to $e_n^2$.
- Use Taylor's theorem to expand both $f(x_n)$ and $f'(x_n)$ around $\alpha$. The $f(\alpha) = 0$ condition cancels the zeroth-order term in $f$, which is why the error becomes quadratic.
- The asymptotic error constant is $|f''(\alpha)|/(2|f'(\alpha)|)$. For the stopping rule, note that $|x_{n+1} - x_n| \approx |x_n - \alpha|$ in the quadratic convergence regime.
Worked Solution
How to Think About It: Newton's method is the workhorse of numerical root-finding. The idea is simple: at each step, approximate $f$ by its tangent line and solve for where the tangent crosses zero. Geometrically, you are linearizing $f$ around your current guess. The reason it converges so fast (quadratically) is that a smooth function is well-approximated by its tangent near the root, and the approximation error is second-order in the distance to the root. The key assumption is that $f'(\alpha) \neq 0$ -- if the derivative vanishes at the root, convergence degrades to linear.
Part 1: Newton's Method.
Given an initial guess $x_0$, the iteration is:
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
This is obtained by setting the tangent line $f(x_n) + f'(x_n)(x - x_n) = 0$ and solving for $x$.
Part 2: Proof of Local Quadratic Convergence.
Define the error $e_n = x_n - \alpha$. We want to show $|e_{n+1}| \leq C |e_n|^2$.
By Taylor's theorem, expand $f(x_n)$ around $\alpha$:
$$f(x_n) = f(\alpha) + f'(\alpha) e_n + \frac{1}{2} f''(\xi_n) e_n^2$$
where $\xi_n$ is between $x_n$ and $\alpha$. Since $f(\alpha) = 0$:
$$f(x_n) = f'(\alpha) e_n + \frac{1}{2} f''(\xi_n) e_n^2$$
Similarly, expand $f'(x_n)$:
$$f'(x_n) = f'(\alpha) + f''(\eta_n) e_n$$
for some $\eta_n$ between $x_n$ and $\alpha$.
Now compute the error at step $n+1$:
$$e_{n+1} = x_{n+1} - \alpha = x_n - \frac{f(x_n)}{f'(x_n)} - \alpha = e_n - \frac{f(x_n)}{f'(x_n)}$$
$$= \frac{e_n f'(x_n) - f(x_n)}{f'(x_n)}$$
Substituting the Taylor expansions into the numerator:
$$e_n f'(x_n) - f(x_n) = e_n [f'(\alpha) + f''(\eta_n) e_n] - [f'(\alpha) e_n + \tfrac{1}{2} f''(\xi_n) e_n^2]$$
$$= f'(\alpha) e_n + f''(\eta_n) e_n^2 - f'(\alpha) e_n - \tfrac{1}{2} f''(\xi_n) e_n^2$$
$$= e_n^2 \left[ f''(\eta_n) - \tfrac{1}{2} f''(\xi_n) \right]$$
As $x_n \to \alpha$, both $\eta_n, \xi_n \to \alpha$, so $f''(\eta_n) - \frac{1}{2}f''(\xi_n) \to \frac{1}{2} f''(\alpha)$. Thus:
$$e_{n+1} = \frac{e_n^2 [f''(\eta_n) - \frac{1}{2}f''(\xi_n)]}{f'(x_n)}$$
For $x_0$ sufficiently close to $\alpha$, $f'(x_n)$ is bounded away from zero (since $f'(\alpha) \neq 0$ and $f'$ is continuous), and the bracketed term is bounded. Therefore there exists $C > 0$ such that:
$$|e_{n+1}| \leq C |e_n|^2$$
More precisely, the asymptotic error constant is:
$$\lim_{n \to \infty} \frac{|e_{n+1}|}{|e_n|^2} = \frac{|f''(\alpha)|}{2|f'(\alpha)|}$$
This confirms quadratic convergence: each iteration roughly squares the error (and scales by the constant $|f''(\alpha)|/(2|f'(\alpha)|)$).
Part 3: Practical Stopping Rule.
The standard practical stopping rule uses the step size as a proxy for the error. By the mean value theorem:
$$f(x_n) = f(x_n) - f(\alpha) = f'(\zeta_n)(x_n - \alpha)$$
so $|x_n - \alpha| = |f(x_n)|/|f'(\zeta_n)| \approx |f(x_n)|/|f'(x_n)| = |x_n - x_{n+1}|$.
Therefore, a practical stopping rule is:
$$|x_{n+1} - x_n| < \epsilon$$
where $\epsilon$ is the desired absolute error tolerance. This works because in the regime of quadratic convergence, $|x_{n+1} - x_n| \approx |x_n - \alpha|$, so the step size is a good proxy for the actual error. An alternative (or additional) criterion is $|f(x_n)| < \delta$ for some tolerance $\delta$, but this can be misleading when $|f'(\alpha)|$ is very large or very small.
For robust implementations, use both criteria:
$$|x_{n+1} - x_n| < \epsilon \quad \text{and} \quad |f(x_n)| < \delta$$
Answer: Newton's iteration is $x_{n+1} = x_n - f(x_n)/f'(x_n)$. It converges quadratically with asymptotic constant $|f''(\alpha)|/(2|f'(\alpha)|)$, proven via Taylor expansion of the error recurrence. A practical stopping rule is $|x_{n+1} - x_n| < \epsilon$.
Intuition
Newton's method achieves quadratic convergence because it exploits first-order information (the derivative) to cancel the linear part of the error. At each step, the tangent line captures the linear behavior of $f$ perfectly, so the residual error comes from the curvature (the $f''$ term), which is second-order. This is why the convergence constant involves $f''/f'$ -- large curvature relative to slope means the linearization is less accurate, slowing convergence.
In quant work, Newton's method shows up everywhere: implied volatility solvers (inverting Black-Scholes), calibrating yield curves, fitting SABR parameters, and solving nonlinear portfolio optimization constraints. The practical lesson is that quadratic convergence means the number of correct digits roughly doubles each iteration -- so 3-4 iterations usually suffice for machine precision. But the method can fail spectacularly if your initial guess is too far from the root (the tangent line shoots off to infinity), or if $f'$ is near zero (division by a small number). Always pair Newton's method with a bracketing method as a fallback.