🎯Newton's Method

There is a brass rail bolted to the long bench at the Tangent Laboratory, and a bead that runs along it. Technician Fluxion sets the rail against a curve at whatever point you name, lets the bead go, and it slides to where the rail meets the floor. Then the rail is picked up, set against the curve at the *new* point, and the bead slides again. Three or four goes and the bead is sitting almost exactly over a root.

That rail is the tangent line, the floor is the x-axis, and the game is Newton's method.

Here is the whole idea in one picture. You have a guess x0 at a root of f. The curve is complicated, but the tangent at x0 is a straight line, and straight lines are easy: you can find exactly where a line crosses the axis. So you pretend, for one step, that the curve *is* its tangent, take the tangent's x-intercept as your new guess, and repeat.

Work out where that intercept is. The tangent at x0 has slope f'(x0) and passes through the point (x0, f(x0)):

y - f(x0) = f'(x0)*(x - x0)

Set y = 0, because that is what "crosses the x-axis" means, and solve for x:

-f(x0) = f'(x0)*(x - x0) x - x0 = -f(x0)/f'(x0) x = x0 - f(x0)/f'(x0)

And that is the formula. Nothing else in this craft is new:

x_(n+1) = x_n - f(x_n)/f'(x_n)

Read it as a sentence: the new estimate is the old estimate, minus the height divided by the slope. The height f(x_n) says how far off the axis you are; the slope f'(x_n) converts that height into a horizontal distance. A tall curve with a steep slope needs only a small sideways move; the same height on a gentle slope needs a huge one.

Three things to notice before you use it once.

• ◆The minus sign is doing work. Subtracting walks towards the root; adding walks away from it. This is the single most common slip in the whole topic.
• ◆The quotient is f over f'. Not f' over f. The units decide it: a height divided by a slope is a length along the x-axis, which is exactly what you want to move.
• ◆f'(x0) is a number, not a rule. Differentiate to get f'(x), then substitute the start. Leaving 2x in the denominator instead of 2 times the start is the second most common slip.

Take one step, exactly. Let f(x) = x² - 10 and start at x0 = 3.

f(3) = 9 - 10 = -1 f'(x) = 2x, so f'(3) = 6 x1 = 3 - (-1)/6 = 3 + 1/6 = 19/6

Keep it as 19/6. Do not write 3.17 — the next step will double the number of correct digits you have, so it can only double the digits you actually hand it. Rounding early is throwing away the answer before you have finished earning it.

Take another. From x1 = 19/6:

f(19/6) = 361/36 - 10 = 1/36 f'(19/6) = 19/3 x2 = 19/6 - (1/36)/(19/3) = 19/6 - 1/228 = 721/228 = 3.162280...

The true square root of 10 is 3.1622776... So x1 was right to 1 decimal place, and x2 is right to 5. That is the pattern: the number of correct decimal places roughly doubles at every step.

Write the iteration once and reuse it. Instead of doing the algebra from scratch each time, substitute f and f' into the formula and keep the result. Writing x for x_n:

f(x) = x² - a => x_(n+1) = x - (x² - a)/(2x)

Tidy that up and something lovely happens:

x - (x² - a)/(2x) = (2x² - x² + a)/(2x) = (x² + a)/(2x) = (x + a/x)/2

Average your guess with a divided by your guess. That rule is thousands of years older than calculus, and Newton's method has just rediscovered it. Two more worth knowing:

• ◆f(x) = x³ - a gives x_(n+1) = x - (x³ - a)/(3x²), which tidies to (2x³ + a)/(3x²).
• ◆f(x) = 1/x - a gives x_(n+1) = 2x - a*x², with no division anywhere at all. That is how a machine with no divider builds reciprocals: it multiplies its way to 1/a and then multiplies by the numerator.

When you write an iteration down, bracket the whole denominator. x - (x³ - 2x - 5)/(3x² - 2) is right; leaving those last brackets off changes what the division applies to.

Newton's method answers exactly one question: where is a root of f? So every problem begins by turning "find this number" into "find a root of this function". Write the number you want as an equation, then move everything to one side so the other side is 0.

• ◆the square root of 7 -> x² = 7 -> f(x) = x² - 7
• ◆the cube root of 20 -> x³ = 20 -> f(x) = x³ - 20
• ◆the solution of cos(x) = x -> f(x) = x - cos(x)
• ◆the solution of x*e^x = 1 -> f(x) = x*e^x - 1

Check your choice by substituting the number you wanted: a correct f gives exactly 0 there. Note that f(x) = x² + 7 has no real root at all, and f(x) = sqrt(x) - 7 has its root at 49 rather than at the square root of 7 — both are the same slip, of writing the equation down without rearranging it.

Then pick a start. A rough sketch, a sign change, or simply the nearest whole number is enough; the method is forgiving about where you begin, so long as you begin somewhere sensible.

Knowing when to stop. Newton's method never announces that it has arrived, so you need a rule. The usual one is a gap test: stop as soon as

|x_(n+1) - x_n| < 0.001

Read that carefully, because the answer to "at which n" is the smaller subscript. Suppose a run on x² - 45 from x0 = 8 gives

x0 = 8.000000, x1 = 6.812500, x2 = 6.709002, x3 = 6.708204, x4 = 6.708204

The gaps are 1.187500, then 0.103498, then 0.000798. The first gap under 0.001 is |x3 - x2|, so n = 2, and x3 is the estimate you keep. There are five numbers in that list but only four gaps between them, which is why counting rows gives the wrong answer.

Knowing how good the answer is. If you happen to know the true value, compare digit by digit after the decimal point and stop at the first disagreement. Against sqrt(45) = 6.708204, the estimate 6.709002 agrees in the 7 and the 0 and then differs at the next digit, so it has earned 2 decimal places; 6.708204 has earned all six shown. And if you know only that the error is about 0.01 right now, you already know a great deal about the next step: the error is roughly squared, so about 0.0001 comes next, and about 0.00000001 after that. Halving would be a slow method; squaring is why three or four steps is usually the whole job.

Newton's method is fast, not infallible. Four things can go wrong, and all four are visible in the picture of the sliding tangent.

A horizontal tangent. If f'(x0) = 0 the step divides by zero, and there is no next estimate at all. Geometrically the tangent is a flat line that never meets the x-axis, so the bead has nowhere to slide to. Take f(x) = x² - 8x + 3 from x0 = 4: f'(x) = 2x - 8, so f'(4) = 0 and the method stops before it starts. The cure is trivial — start a little to the left or the right. It is worth checking the derivative at a candidate start *before* iterating, because this one costs nothing to spot.

A nearly horizontal tangent. Not zero, but small, and the step is enormous. From f(x) = x² - 7 at x0 = 0.1 the slope is only 0.2, and

x1 = 0.1 - (-6.99)/0.2 = 35.05

The estimate is thrown far away. Nothing is broken — the method works its way back and does eventually settle on the square root of 7 — but a start near a turning point costs several wasted steps.

A cycle. Take f(x) = x³ - 2x + 2 from x0 = 0. Then f(0) = 2 and f'(0) = -2, so x1 = 1. And f(1) = 1, f'(1) = 1, so x2 = 0. The estimates bounce between 0 and 1 for ever and the real root near -1.769 is never approached. A tiny change of start breaks the cycle at once.

The wrong basin. This one is not a breakdown, and it catches people out precisely because everything looks healthy. Newton's method has no idea which root you were hoping for; it goes wherever the tangent points. For f(x) = x² - 25, whose roots are 5 and -5, a start at x0 = -1 gives

x1 = -1 - (1 - 25)/(-2) = -1 - 12 = -13

and the estimates then close in tidily on -5. The method has done its job perfectly and answered a different question. The root you find is chosen by the start, not by which root is nearest — and with three roots in play the nearest root often is not the one you land on. Work the first step out and see which root x1 has landed beside; that is what decides, every time.