4.9 Newton's Method

Big idea

Most equations cannot be solved by algebra. There is no formula for the root of $x^3 - x - 1 = 0$ that a student would want to use, and none at all for $\cos x = x$. What you can do instead is produce a sequence of numbers that closes in on the root, and stop when the digits you need have stopped changing.

The idea that generates such a sequence is the one from linear approximation. Near a current guess, the function is well modelled by its tangent line. Solving the true equation is hard; solving the tangent line equation is one division. So replace the curve by its tangent line, find where that line crosses the horizontal axis, and take that crossing as the next guess. Repeat.

What makes this more than a plausible trick is the speed. When it works, the number of correct digits roughly doubles at each step, because the error of a tangent line approximation is proportional to the square of the distance from the point of tangency. Three or four steps from a decent start is usually enough for every digit a calculator will show.

The method also fails in specific, understandable ways, and the failures are as instructive as the successes. A nearly horizontal tangent flings the next guess far away. A poor starting point can land you in a cycle that repeats forever. Knowing the failure modes tells you what a good starting guess looks like: close to the root, on a stretch where the curve is not flat and does not change concavity.

Decoder

Replacing $f$ by its tangent line at the current guess and solving the linear equation instead gives the next guess, so each step is one linear approximation.

Every piece of the iteration formula is visible in that sentence. 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 crossing, and naming that crossing $x_{n+1}$ produces the rule you will use.

The phrase carrying the content is “solving the linear equation instead.” Nothing about the method guarantees you get closer to a root; it guarantees only that you did the easy problem exactly. When the tangent line is a good model of the function over the distance involved, its root is near the function’s root, and the process converges. When it is not, the process can do anything.

The classic mistake is stopping at the wrong place, in two senses. Numerically, stopping when $|x_{n+1} - x_n|$ is small is a reasonable rule, but checking that $f(x_{n+1})$ is also small is the honest confirmation. Conceptually, reporting more digits than the iteration has stabilized is claiming accuracy you did not compute.

Definitions and results

The iteration. Starting from an initial guess $x_0$, define

$$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$

for $n = 0, 1, 2, \ldots$, as long as $f'(x_n) \neq 0$.

Where the formula comes from. The tangent line to $y = f(x)$ at $x_n$ is $y = f(x_n) + f'(x_n)(x - x_n)$. Setting $y = 0$ and solving for $x$ gives exactly the expression above. The method is linear approximation applied repeatedly, with the horizontal axis as the target.

The correction term. The quantity $f(x_n)/f'(x_n)$ is the correction. It is large when the function value is far from zero, and large when the slope is shallow, which is the formula’s way of saying that a flat graph gives little information about where its root is.

Rate of convergence. When $f'$ is nonzero at the root and $f''$ is continuous nearby, and the start is close enough, the error at each step is roughly proportional to the square of the previous error. In practice the number of correct decimal places doubles per step.

Stopping rule. Iterate until successive guesses agree to the precision you want, then confirm by checking that $f$ evaluated at the final guess is close to zero.

Failure from a vanishing derivative. If $f'(x_n) = 0$ the step is undefined, and if $f'(x_n)$ is merely close to zero the correction is enormous and the next guess can land far from anything useful.

Failure by cycling. Some starting points produce a loop. For $f(x) = x^3 - 2x + 2$ the start $x_0 = 0$ gives $x_1 = 1$, and $x_1 = 1$ gives $x_2 = 0$, so the iteration alternates forever without approaching the real root near $-1.77$.

Failure by divergence. For $f(x) = x^{1/3}$ the iteration simplifies to $x_{n+1} = x_n - 3x_n = -2x_n$, so every nonzero start doubles in size and flips sign at each step, running away from the root at $0$. The cusp there, where $f'$ blows up, is the cause.

Choosing a start. Sketch the function or evaluate it at a few points to find a sign change, then start inside that bracket, preferring a point where the graph is steep and does not change concavity between the start and the root.

Worked examples

A square root by hand

Find $\sqrt{2}$ by solving $f(x) = x^2 - 2 = 0$.

Here $f'(x) = 2x$, so the iteration is

$$ x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right) $$

which is the averaging rule for square roots, obtained here rather than assumed. Start at $x_0 = 1$:

$$ x_1 = \tfrac12(1 + 2) = 1.5 $$

$$ x_2 = \tfrac12\left(1.5 + \tfrac{2}{1.5}\right) = 1.4166667 $$

$$ x_3 = \tfrac12\left(1.4166667 + \tfrac{2}{1.4166667}\right) = 1.4142157 $$

$$ x_4 = 1.4142136 $$

The true value is $1.41421356\ldots$, so after four steps from a crude start the answer is correct to eight digits. Watch the digit doubling: $x_1$ is right to one significant digit, $x_2$ to two decimal places, $x_3$ to five, and $x_4$ to seven.

Check the final guess: $1.4142136^2 = 2.0000001$, close to $2$ as required.

A root of a cubic

Solve $x^3 - x - 1 = 0$.

First bracket the root. Since $f(1) = -1$ and $f(2) = 5$, a root lies between $1$ and $2$; since $f(1.5) = 0.875 > 0$, it lies between $1$ and $1.5$. Start at $x_0 = 1.5$, where the curve is steep.

With $f'(x) = 3x^2 - 1$:

$$ x_1 = 1.5 - \frac{0.875}{5.75} = 1.3478261 $$

$$ x_2 = 1.3478261 - \frac{0.100682}{4.449906} = 1.3252002 $$

$$ x_3 = 1.3252002 - \frac{0.002056}{4.268465} = 1.3247183 $$

A fourth step no longer changes the first seven digits, so the root is $1.324718$ to six decimal places. Confirm by substitution: $1.324718^3 = 2.3247182$, and subtracting $1.324718$ and $1$ leaves a residual smaller than $10^{-6}$.

A start that cycles forever

Apply the method to $f(x) = x^3 - 2x + 2$ starting at $x_0 = 0$.

Here $f(0) = 2$ and $f'(0) = -2$, so

$$ x_1 = 0 - \frac{2}{-2} = 1 $$

Now $f(1) = 1 - 2 + 2 = 1$ and $f'(1) = 3 - 2 = 1$, so

$$ x_2 = 1 - \frac{1}{1} = 0 $$

The iteration has returned to its starting point and will alternate between $0$ and $1$ forever. Nothing went wrong arithmetically; the tangent lines at these two points simply point at each other. The function does have a real root, near $x = -1.77$, and a start such as $x_0 = -2$ finds it without difficulty. This is the clearest argument for sketching before iterating.

Practice

There is no drill set dedicated to the iteration itself, so practice the two ingredients it is assembled from. Every step of the method is one linear approximation followed by solving a linear equation, so fluency with the linearization is fluency with the method.

Then the geometry of the step. Each guess is the horizontal intercept of a tangent line, so building tangent lines at a given point and finding where they cross an axis is the same computation the iteration performs over and over.

Quiz

Five items on the tangent line behind each step, carrying out the iteration from a given start, and the conditions under which the method converges or fails.