Newton's Method

Tangent-line iteration that converges fast to a root.

The idea

Newton's method is an iteration for solving an equation $f(x) = 0$ numerically. Most equations admit no solution formula — nothing algebraic gives the number where $\cos x = x$ — so instead of solving in one stroke, the method starts from a guess and repeatedly improves it.

The improvement rests on the fact that a smooth curve looks like its tangent line up close. At a guess $x_n$, replace $f$ by its tangent line there, $y = f(x_n) + f'(x_n)(x - x_n),$ and solve the line instead of the curve. Setting $y = 0$ and rearranging gives the next guess: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.$ Geometrically, $x_{n+1}$ is the point where the tangent at $x_n$ crosses the $x$-axis.

Algorithm.

Algorithm: Newton's Method Input: differentiable f, starting guess x, tolerance ε > 0 Output: an approximate solution of f(x) = 0 1. if f'(x) = 0, stop // horizontal tangent: no next guess 2. x_new = x - f(x)/f'(x) // where the tangent at x crosses the axis 3. if |x_new - x| ≤ ε, return x_new // the guesses have settled 4. x = x_new, go to step 1

Repeating the step produces a sequence $x_0, x_1, x_2, \ldots$ which, started near a simple root, converges to that root — and quickly, roughly doubling the number of correct digits at every step. The method can also fail: a guess where $f'$ is zero has a horizontal tangent and no next step at all, and a guess far from a root can be sent further away.

Ways to work on it

• Walkthrough. Build the update from the tangent line and iterate toward a root.
• Practice. Take one Newton step for a randomized function and start point.
• Hardest. Set up the iteration for a non-algebraic root and take a step.

Not sure where to start? Take the ten-question placement test.