Newton's method, a first look

Follow the tangent line

Bisection uses only the signs of $f$. Newton's method also uses how steep the graph is, and when it works it is far faster.

Close up, a smooth curve looks almost straight. The straight line that touches the curve at a point, running in the same direction there, is its tangent line. A line is easy to solve, so Newton's method solves the tangent instead of the curve.

Guess a root, $x_0$. Follow the tangent at $x_0$ down to where it crosses the axis, and call that point $x_1$. Repeat from $x_1$ to get $x_2$, and so on: $x_n$ is the guess after $n$ steps.

The slope of a curve, borrowed for now

A line has the same slope everywhere. A curve is steeper in some places than in others, so its slope depends on the point. Write $f'(x)$, read "f prime of x", for the slope of the tangent at $x$.

Lesson 2.2.1 shows where the slope of a curve comes from. For now, borrow three facts. The slope of $x^2$ at $x$ is $2x$, and the slope of $x^3$ is $3x^2$.

Adding a term $mx$ adds $m$ to the slope. Adding a constant changes nothing: it only shifts the graph up or down (lesson 1.1.2).

The Newton step

The tangent at $x_n$ passes through the point $(x_n, f(x_n))$ with slope $f'(x_n)$. By the point-slope form of lesson 1.2.1, it is the line

The next guess is where this line crosses the axis. Set $y = 0$ and solve for $x$, as in lesson 0.3.2: $x - x_n = -\frac{f(x_n)}{f'(x_n)}$.

A first example: $\sqrt{2}$

Take $f(x) = x^2 - 2$, with slope $2x$, and start at $x_0 = 2$. There $f(2) = 2$ and the slope is 4, so $x_1 = 2 - \frac{2}{4} = 1.5$. As a line, the tangent is $y = 2 + 4(x - 2) = 4x - 6$, which crosses the axis at $\frac{6}{4} = 1.5$.

Here are the guesses, with each one's error, its distance from $\sqrt{2}$.

Five steps give $\sqrt{2}$ to every digit a computer stores. Bisection needed 20 steps for six digits.

Algebra gives the step a neat form. For $x^2 - 2$ it simplifies to an average:

Each new guess is the average of $x$ and $\frac{2}{x}$. If $x$ is too big then $\frac{2}{x}$ is too small, so their average lands in between. This rule for square roots is often called the Babylonian method.

Press Next step to follow the tangents yourself. Then pick $x^3 - x - 1$, the cubic from lesson 1.3.2, and count the steps: bisection needed 27.

A second example: the cubic

Take $f(x) = x^3 - x - 1$, with slope $3x^2 - 1$, from $x_0 = 1.5$. The first step is $1.5 - \frac{0.875}{5.75} = 1.3478$, to four places.

Four steps reach an error below $10^{-13}$. Bisection took 27 steps to reach $10^{-8}$.

Why it is so fast

Look at the errors for $\sqrt{2}$: 0.0858, 0.00245, 0.0000021, 0.0000000000016. Each is about a third of the square of the one before. Squaring a small number doubles its zeros after the point, as $0.001^2 = 0.000001$ shows.

So near a root, the number of correct digits roughly doubles each step. Bisection gains the same small amount every step, about three decimal places per 10 steps. Newton's method gains more and more, but only once it is close: far from the root its first steps can go anywhere.

A program needs a rule for when to stop. Stop when a step moves the guess by less than a tolerance. Also give up after a fixed number of steps, so a failure cannot run for ever.

When Newton's method fails

Newton's speed comes with no guarantee. Each failure below is one you will meet in practice.

• A flat tangent. If $f'(x_n) = 0$, the tangent never meets the axis and the step divides by zero: $x^2 - 2$ from $x_0 = 0$ fails at once. A nearly flat tangent is almost as bad. From 0.1 the first step lands at 10.05, and it takes eight steps to get back to $\sqrt{2}$.
• A cycle. Take $x^3 - 2x + 2$, with slope $3x^2 - 2$, from $x_0 = 0$. $f(0) = 2$ and $f'(0) = -2$ give $x_1 = 1$; then $f(1) = 1$ and $f'(1) = 1$ give $x_2 = 0$, the start again. The guesses bounce between 0 and 1 for ever, while the only root is near $-1.7693$.
• A double root. For $(x - 1)^2 = x^2 - 2x + 1$, with slope $2x - 2$, the step simplifies to $\frac{x + 1}{2}$. From 3 the guesses are 2, 1.5, 1.25, 1.125: the error only halves each step, no faster than bisection.
• No root. $x^2 + 1$ has no real root, so the guesses can never settle. From 0.5 they go $-0.75$, 0.29, $-1.57$, $-0.47$, 0.84, jumping about for ever.
• The wrong root. $p(x) = (x - 1)(x - 2)(x - 3)$ has slope $3x^2 - 12x + 11$. From 1.5, halfway between the roots 1 and 2, one step lands on 3. The start decides which root you get, and it need not be the nearest.

To watch the cycle, pick $x^3 - 2x + 2$ in the explorer above and press Next step a few times.

Using it safely

Careful code guards Newton's method. It caps the number of steps and checks $f$ at the answer. It can also keep a bracket from lesson 1.3.2, taking a bisection step whenever a Newton step would leave it.

SciPy's brentq (lesson 1.3.2) mixes safe and fast steps in a similar way. SciPy's newton(f, x0, fprime=slope) runs plain Newton's method, and raises RuntimeError when it has not converged after 50 steps. Without fprime, it estimates each slope from a chord through its last two guesses, so it needs no slope at all.

Case study 1.3.5 uses newton without a slope to find interest rates. Lesson 2.4.3 works out the slope of any function with calculus and runs Newton's method again. Case study 2.4.6 uses it for an option's implied volatility.

Common mistakes

1. Subtract the step: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$. Adding it sends the guess the wrong way.
2. Divide the height by the slope, $\frac{f(x_n)}{f'(x_n)}$, not the slope by the height.
3. Use the slope at the current guess, $f'(x_n)$, not the slope at the start.
4. A zero slope divides by zero. Start somewhere else.
5. It is fast only near the root. Far away the guesses can jump, cycle or wander, so cap the steps and check $f$ at the answer.
6. A double root slows it down to one halving of the error per step.
7. The start picks the root, and not always the nearest one. Nothing keeps the guesses inside a bracket unless you add it.