Guides / Derivatives

Newton's method: x − f(x)/f′(x), digits that double, and the starts that run away

Newton's method solves f(x) = 0 by replacing f with its tangent line at the current guess, solving the line instead, and repeating from where the line crosses zero. Near a simple root the error at each step is roughly a constant times the square of the error before, so the number of correct digits about doubles. The conventions are those of the practice set: x_n is the n-th guess, r the root, and e_n = x_n − r the error. The tangent line is the first-order Taylor approximation, and finding a minimum means finding a critical point, as in the maxima and minima guide. The mistakes come from adding the step instead of subtracting it, from finding a root of f when its minimum was wanted, and from trusting a small f(x) when the guesses are running away.

Why it works

The tangent line at x_n is y = f(x_n) + f′(x_n)(x − x_n). Setting y = 0 and solving for x gives the update. The line is the best linear model of f near x_n, and its error is the quadratic Taylor term, of size ½f″ · (distance)². So the line's root misses f's root by an amount proportional to the square of how far off the guess was. That is where e_n+1 ≈ C e_n² comes from, with C = f″(r)/(2f′(r)).

The same argument says when it fails. If f′(r) = 0, at a double root, C is infinite and the convergence drops to linear. If the start is far away, the tangent can point somewhere useless: past a hump where f′ = 0, or out to where f flattens. For a minimum, the step on f′ jumps to the minimum of the quadratic Taylor model at x_n, which is the one-variable form of the Newton step that uses the Hessian in several variables.

Example 1: √5 as exact fractions

Use f(x) = x² − 5 from x₀ = 2, and track the error.

1. x − (x² − 5)/(2x)The update, with f′(x) = 2x …
2. = (x + 5/x)/2… which simplifies to the average of x and 5/x.
3. x₁ = (2 + 5/2)/2 = 9/42.25, error 0.0139.
4. x₂ = 161/72(9/4 + 20/9)/2: 2.2361111, error 4.3 × 10⁻⁵.
5. x₃ = 51841/231842.2360679779, error 4.2 × 10⁻¹⁰.
6. √5 = 2.2360679775…Each error is the one before squared and divided by 2x, which is positive: 0.014, then 4.3 × 10⁻⁵, then 4.2 × 10⁻¹⁰. The correct digits roughly double, and every guess after the first is too big.

Example 2: a cubic, and the error ratio

Solve x³ − x − 1 = 0 from x₀ = 1.5, and check the constant C.

1. f′(x) = 3x² − 1Power rule.
2. x₁ = 1.5 − 0.875/5.75f(1.5) = 3.375 − 1.5 − 1 and f′(1.5) = 6.75 − 1.
3. x₁ ≈ 1.347826Error 0.0231.
4. x₂ ≈ 1.325200Error 0.00048.
5. x₃ ≈ 1.3247182Error 2.2 × 10⁻⁷; the root is r ≈ 1.3247180.
6. C = 6r/(2(3r² − 1))f″(x) = 6x in f″(r)/(2f′(r)) …
7. C ≈ 0.932… and the observed ratios e_n+1/e_n² are 0.75, 0.90 and 0.93, closing in on it.

Example 3: a minimum

Minimize f(x) = x² + e^−x from x₀ = 0.

1. f′ = 2x − e^−xThe equation to solve is f′(x) = 0.
2. f″ = 2 + e^−xAlways positive, so f is convex and the critical point is the minimum.
3. x₁ = 0 − (−1)/3 = 1/3f′(0) = −1, f″(0) = 3.
4. x₂ ≈ 0.351689The same step from 1/3.
5. x₃ ≈ 0.3517337The next step changes it only in the tenth decimal place.
6. x* ≈ 0.351734The minimum value is about 0.827. The step is f′/f″, one derivative higher than for a root: it finds where the slope is zero.

Example 4: one function, two starts

Apply the method to f(x) = xe^−x, whose only root is 0, from x₀ = 0.5 and from x₀ = 2.

1. f′(x) = (1 − x)e^−xProduct rule. It is 0 at x = 1, the top of the hump.
2. x_n+1 = −x_n²/(1 − x_n)f/f′ = x/(1 − x); subtract it from x.
3. 0.5 → −1/2 → −1/6From 0.5 the first step overshoots to the other side …
4. → −1/42 → −1/1806… then the errors square: e_n+1 ≈ −e_n².
5. 2 → 4 → 16/3 ≈ 5.33From 2, past the hump, the tangent slopes down to the right …
6. → 6.56 → 7.74 → …… and crosses zero further right each time. f tends to 0 as x grows, so the guesses chase a "root at infinity", gaining about 1 per step.

Common mistakes, and the exact line they happen on

1. Adding the step

Example 1's first step.

1. f(2) = −1, f′(2) = 4Right so far.
2. x₁ = 2 + (−1)/4 = 1.75This is the mistake. The tangent crosses zero at x − f/f′. With f negative and the slope positive, the root is to the right, at 2.25. The check: |f(1.75)| = 1.9375 is larger than |f(2)| = 1, so the step went the wrong way.

2. Finding a root of f when its minimum is wanted

Example 3, with the root-finding step.

1. minimize x² + e^−xRight so far.
2. x_n+1 = x_n − f/f′This is the mistake. That looks for f = 0, and this f is always positive, so there is nothing to find. From 0 the guesses wander: 1, 0.162, 1.826, 0.825, −0.098, … The minimum needs f′/f″.

3. Trusting a small f(x)

Example 4 from x₀ = 2, stopped when f looks close to 0.

1. x₄ ≈ 7.744Right so far: the arithmetic is correct.
2. f(7.744) ≈ 0.0034, so a rootThis is the mistake. f is small because it flattens out, not because x is near a root. The steps are 2, 1.33, 1.23, 1.18, heading toward 1 instead of shrinking, which is the sign of a run-away. Stop on a small step and a small f together, and check the answer.

Practice

1. Take one Newton step for √10 from x₀ = 3.

   Show answer

   (3 + 10/3)/2 = 19/6 ≈ 3.1667. The true value is 3.1623.

2. Take one step for the cube root of 20 from x₀ = 3, using f(x) = x³ − 20.

   Show answer

   x₁ = (2 · 3 + 20/9)/3 = 74/27 ≈ 2.7407. The true value is 2.7144.

3. Minimize f(x) = x² − 4x + 7 with Newton's method from x₀ = 10. How many steps does it take?

   Show answer

   One: 10 − (2 · 10 − 4)/2 = 2. For a quadratic, the quadratic model is f itself, so the first step lands on the minimum from any start.

4. Take one step for e^x = 3 from x₀ = 1.

   Show answer

   x₁ = 1 − (e − 3)/e = 3/e ≈ 1.1036. The root is ln 3 ≈ 1.0986.

5. Apply the method to f(x) = x², whose root 0 is a double root. What happens to the error?

   Show answer

   x_n+1 = x_n − x_n²/(2x_n) = x_n/2. The error halves each step: linear convergence, because f′(0) = 0.