§ 01The Root-Finding Problem
A root (or zero) of a function f is a value x = r such that f(r) = 0. Finding roots is one of the oldest and most important problems in all of mathematics, equations of the form f(x) = 0 arise constantly in physics, engineering, economics, and computer science.
For simple functions, roots can be found exactly using algebra. The quadratic formula gives the roots of any quadratic polynomial. But for equations like x⁵ − 3x + 1 = 0, or cos x = x, or ex = 3x², there is no general algebraic formula. We need a different approach, a numerical method that produces increasingly accurate approximations to the root.
The oldest numerical approach is the bisection method: if f(a) and f(b) have opposite signs, the Intermediate Value Theorem guarantees a root in (a, b), so you repeatedly halve the interval to zero in on it. Bisection is reliable but slow: it adds roughly one correct binary digit per iteration, which means about 3.3 iterations per additional decimal place.
Newton's Method (also called the Newton–Raphson method) is dramatically faster under the right conditions. It uses not just the value of f but also the derivative f′ (the tangent line) to make a much more intelligent estimate of where the root lies. When it works, it is roughly quadratically convergent: the number of correct decimal places doubles with each iteration. That means two correct digits become four, then eight, then sixteen. In practice, six or seven iterations typically gives you fifteen-digit machine precision.
§ 02Deriving the Iteration Formula
The derivation is based on a single geometric insight: replace the curve with its tangent line, find where that line crosses the x-axis, and use that crossing as the next approximation.
Suppose we have a current approximation xn to the root. The tangent line to y = f(x) at the point (xn, f(xn)) has the equation:
This is just the point–slope form of a line through (xn, f(xn)) with slope f′(xn).
To find where this tangent line crosses the x-axis, set y = 0 and solve for x:
This x-intercept is our improved approximation xn+1.
This gives the Newton–Raphson iteration formula:
by subtracting the ratio of the function value to the derivative at the current point.
Repeat until |xn+1 − xn| or |f(xn+1)| is smaller than your desired tolerance.
The formula requires that f′(xn) ≠ 0 at every step. If the derivative is zero at some iterate, the tangent line is horizontal and has no x-intercept, the method breaks down at that point. This is one of the key failure modes we examine in § 07.
§ 03Geometric Interpretation — Step by Step
Every iteration of Newton's Method has an identical geometric description: draw the tangent line at the current point, find where it hits the x-axis, and move there. The diagram below shows three successive iterations converging rapidly to the root.
Notice how the distances between successive iterates shrink: x₀ to x₁ is a large step; x₁ to x₂ is a smaller step; x₂ to x₃ would be tiny. This accelerating convergence is the signature of Newton's Method and is what distinguishes it from slower algorithms like bisection.
The geometric picture also reveals when the method might have trouble: if the tangent line at xₙ is nearly horizontal (f′ ≈ 0), its x-intercept will be far away from xₙ, potentially overshooting the root entirely. If the curve has a lot of curvature near the starting guess, the tangent line may not be a good approximation to the curve over a large step. These geometric observations motivate the failure analysis in § 07.
§ 04Convergence and Quadratic Speed
The most remarkable feature of Newton's Method is how fast it converges when it works. This speed is described precisely by the concept of order of convergence.
Where Does Quadratic Convergence Come From?
Let r be the exact root (f(r) = 0) and let eₙ = xₙ − r be the error at step n. Expand f(xₙ) and f′(xₙ) in Taylor series around r:
The eₙ terms cancel exactly! What remains is proportional to eₙ². This is quadratic convergence.
The convergence constant is C = |f″(r)|/(2|f′(r)|). For convergence, we need f′(r) ≠ 0 (the root must be simple, not a repeated root). If the root is a double root (f(r) = f′(r) = 0), Newton's Method degrades to linear convergence with rate C = 1/2.
§ 05The Algorithm in Practice
Here is Newton's Method laid out as a step-by-step algorithm you can follow by hand or implement in code.
Input: function f, derivative f′, initial guess x₀, tolerance ε (e.g. ε = 10⁻⁶), maximum iterations N.
1. Set n = 0.
2. Compute xn+1 = xn − f(xn)/f′(xn). Check that f′(xn) ≠ 0 first.
3. If |xn+1 − xn| < ε or |f(xn+1)| < ε, stop, convergence achieved.
4. Set n = n + 1. If n < N, go to step 2. Otherwise stop: did not converge.
Output: xn+1 as the approximate root.
Choosing a Good Starting Point
The starting guess x₀ is the single most important decision. Newton's Method is guaranteed to converge only when x₀ is "sufficiently close" to the root, a condition that is hard to quantify precisely in advance but can be guided by the following principles:
1. Plot f first. Even a rough sketch identifies approximately where f crosses the x-axis. Use this region to anchor x₀. The Intermediate Value Theorem confirms a root in (a, b) whenever f(a) and f(b) have opposite signs.
2. Use the sign of f. Bracket the root by finding a and b with f(a) < 0 and f(b) > 0. Start x₀ anywhere in (a, b), or use the midpoint as a safe starting value.
3. Avoid inflection points and local extrema. If x₀ happens to be near a local maximum or minimum of f, the derivative f′(x₀) will be small, making the correction term huge. Start away from stationary points of f.
§ 06Worked Examples
This is Newton's own original example from 1669. The root is r ≈ 2.09455148…
Formula: xn+1 = xn − (xn³ − 2xn − 5)/(3xn² − 2)
| n | xₙ | f(xₙ) | f′(xₙ) | xₙ₊₁ |
|---|---|---|---|---|
| 0 | 2.000000000 | −1.000000 | 10.000000 | 2.100000000 |
| 1 | 2.100000000 | 0.061000 | 11.230000 | 2.094568121 |
| 2 | 2.094568121 | 0.000130 | 11.153937 | 2.094551482 |
| 3 | 2.094551482 | 0.000000 | 11.153572 | 2.094551482 |
√2 is the positive root of f(x) = x² − 2. So f′(x) = 2x.
xn+1 = xn − (xn² − 2)/(2xn) = (xn + 2/xn) / 2This is the Babylonian method, one of the oldest known algorithms, now seen as a special case of Newton's Method. Start at x₀ = 1.
| n | xₙ | Error |xₙ − √2| |
|---|---|---|
| 0 | 1.000000000000 | 0.414214 |
| 1 | 1.500000000000 | 0.085786 |
| 2 | 1.416666666667 | 0.002453 |
| 3 | 1.414215686275 | 0.0000021 |
| 4 | 1.414213562375 | 1.6 × 10⁻¹² |
Write f(x) = cos x − x = 0. Then f′(x) = −sin x − 1.
xn+1 = xn − (cos xn − xn) / (−sin xn − 1)| n | xₙ | f(xₙ) = cos xₙ − xₙ |
|---|---|---|
| 0 | 1.000000 | −0.459698 |
| 1 | 0.750364 | 0.018368 |
| 2 | 0.739113 | 0.000033 |
| 3 | 0.739085 | < 10⁻¹⁰ |
∛7 is the positive root of f(x) = x³ − 7. So f′(x) = 3x².
xn+1 = xn − (xn³ − 7)/(3xn²) = (2xn/3) + 7/(3xn²)| n | xₙ | xₙ³ |
|---|---|---|
| 0 | 2.000000000 | 8.000 |
| 1 | 1.916666667 | 7.036 |
| 2 | 1.912939166 | 7.000064 |
| 3 | 1.912931183 | ≈ 7.000000000 |
f′(x) = eˣ − 3. Note: f has two roots (one near x ≈ 0.62, one near x ≈ 1.51). Starting at x₀ = 1.5 finds the larger root.
xn+1 = xn − (e^{x_n} − 3xn)/(e^{x_n} − 3)| n | xₙ | f(xₙ) |
|---|---|---|
| 0 | 1.500000 | −0.018 |
| 1 | 1.512134 | −0.000005 |
| 2 | 1.512138 | ≈ 0 |
For f(x) = ax + b (a linear function), one Newton step from any x₀ gives the exact root in one iteration.
The exact root of ax + b = 0 is x = −b/a. Newton reaches it immediately because a tangent to a line is the line itself.
f(x) = x1/3 has a root at x = 0. But f′(x) = (1/3)x−2/3, which is undefined at x = 0. The root at x = 0 is not differentiable: Newton's Method cannot be applied directly at the root.
The iterates oscillate: x₀ = 1 → x₁ = −2 → x₂ = 4 → x₃ = −8 → · · · Divergence!
f′(x) = 2x. The roots are ±√5 ≈ ±2.2360679…
xn+1 = xn − (xn² − 5)/(2xn) = (xn + 5/xn)/2x₁ = (2 + 5/2)/2 = 2.25 x₂ = (2.25 + 5/2.25)/2 ≈ 2.23611 x₃ ≈ 2.23607 ✓
x₁ = (−2 + 5/(−2))/2 = −2.25 x₂ ≈ −2.23611 x₃ ≈ −2.23607 ✓
§ 07When Newton's Method Fails
Newton's Method is not guaranteed to converge for every function and starting point. Understanding the failure modes is essential for using the method safely.
Fix: Restart with a different x₀, or apply a small perturbation.
Classic example: f(x) = x³ − 2x with x₀ = 1 cycles between 1 and −1.
Example: f(x) = arctan x with x₀ large: the tangent is nearly horizontal, the correction is huge.
Fix: Bracket the desired root before starting, or test multiple starting points.
Fix: Use the modified formula xₙ₊₁ = xₙ − m·f(xₙ)/f′(xₙ), which restores quadratic convergence when m is known.
§ 08Common Mistakes
§ 0910-Question Quiz
Questions cover the formula, carrying out iterations, convergence properties, and identifying failure modes.