Most equations, like $x^3 - 2x - 5 = 0$, have no neat formula for their solutions. Linear Approximation and Differentials suggests a strategy: replace the curve by its tangent line, whose zero is easy to find, and repeat.
Key idea
Newton's method. Start with a guess $x_0$ near a root of $f$. Repeat $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.$$ Each new guess is where the tangent line at the old guess crosses the $x$-axis. Near a simple root, the number of correct digits roughly doubles each step.
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 gives $x = x_n - \frac{f(x_n)}{f'(x_n)}$. Near a root the curve and its tangent line are almost the same, so the tangent's zero lands close to the curve's zero. The error after a step is roughly proportional to the square of the error before it, which is why the method converges so fast.
Worked example: Square root of 2
Use two steps of Newton's method on $f(x) = x^2 - 2$ from $x_0 = 2$.
- $f'(x) = 2x$, so $x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{x_n^2 + 2}{2x_n}$.
- $x_1 = \frac{4 + 2}{4} = \frac{3}{2}$.
- $x_2 = \frac{9/4 + 2}{3} = \frac{17}{12} \approx 1.416667$.
Answer: $x_2 = \frac{17}{12}$, within $0.003$ of $\sqrt{2}$.
Worked example: A cubic
Apply one step of Newton's method to $x^3 - 2x - 5 = 0$ from $x_0 = 2$.
- $f(2) = 8 - 4 - 5 = -1$; $f'(x) = 3x^2 - 2$, so $f'(2) = 10$.
- $x_1 = 2 - \frac{-1}{10} = 2.1$.
- (A second step gives $x_2 \approx 2.0946$; the root is $2.09455\ldots$)
Answer: $x_1 = 2.1$
| $n$ | $x_n$ | error $lvert x_n - sqrt{2} vert$ |
|---|---|---|
| 0 | 2 | 0.59 |
| 1 | 1.5 | 0.086 |
| 2 | 1.416666667 | 0.0025 |
| 3 | 1.414215686 | 0.0000021 |
| 4 | 1.414213562 | about $10^{-12}$ |
In practice you stop when two successive guesses agree to the accuracy you need. The method needs $f'(x_n) \ne 0$, and it works best when the starting guess is already near the root; a quick sketch or the The Intermediate Value Theorem is a good way to find one.
Common mistake
Starting where $f'(x_0) = 0$: the tangent is horizontal and never crosses the axis, so $x_1$ cannot be computed. A start near such a point sends $x_1$ far away. The method can also cycle or head to a different root. Check: if the guesses jump around instead of settling, choose a better starting point (a graph helps).