warming up your workspace

Newton's method, the root finder that doubles its accuracy every step, until it explodes

Somewhere under sqrt, under every optimizer that trains a model, under the solver in your circuit simulator, there is a good chance Newton's method is turning. It answers a basic question, "for what x does f(x) = 0?", and it answers it astonishingly fast: near the answer, the number of correct digits roughly doubles every iteration. Six steps can take you from a rough guess to the limit of floating-point precision. But that speed comes with a temper. Feed it the wrong starting point and it will cycle forever or sprint off to infinity. Build it and you get both the power and the failure modes in one sitting.

The one idea

You have a guess x that is close to a root but not on it. Newton says: pretend the function is a straight line at your current point, the tangent, and slide to where that line hits zero. The tangent's slope is the derivative, so the step is x minus f(x) over f'(x). Because a smooth curve looks almost exactly like its tangent up close, that landing spot is much nearer the true root than where you started. Repeat, and each step's error is roughly the square of the last one. Square a small error and it collapses fast. That squaring is the whole reason for the speed, and, it turns out, the whole reason for the failures.

Build it

The method is one line inside a loop.

function newton(f, df, x0; tol=1e-12, maxit=50)
    x = x0
    for i in 1:maxit
        fx = f(x)
        abs(fx) < tol && return (x, i)   # close enough to a root
        x = x - fx / df(x)               # slide down the tangent line
    end
    return (x, maxit)
end

# find sqrt(2): the positive root of x^2 - 2
root, iters = newton(x -> x^2 - 2, x -> 2x, 1.0)

Watch the digits double as it converges to the square root of two:

step 1: 1.5                 (error 0.0857)
step 2: 1.4166666666666667  (error 0.00245)
step 3: 1.4142156862745099  (error 0.00000212)
step 4: 1.4142135623746899  (error 0.0000000000016)
step 5: 1.4142135623730951  (error 0.0)

Three correct digits, then six, then twelve, then exact. Five steps. That doubling, one, two, six, twelve correct digits, is what "quadratic convergence" means, and it is why this method won.

When it explodes

Now the temper. Newton assumes the tangent points toward the root. When it does not, the method turns against you. Two failure modes, both from ordinary functions:

# f(x) = x^3 - 2x + 2, started at x = 0: it cycles forever
step 1: 1.0
step 2: 0.0
step 3: 1.0
step 4: 0.0        # trapped between 0 and 1, never converging

# f(x) = atan(x), started a little too far out at x = 2: it diverges
step 1: -3.54
step 2: 13.95
step 3: -279.34
step 4: 122017.0
step 5: -23386004197.9    # sprinting to infinity

Three details that matter:

  • The cycle happens when the tangent at each point lands you exactly on the other point, whose tangent lands you back. There is a real root nearby, but this starting value orbits a trap instead of falling in. A different x0 finds the root immediately.
  • The atan blowup is overshoot. Far from zero, atan is nearly flat, so its derivative is tiny, and dividing by a tiny slope launches the next guess further out than the last, where the slope is even flatter. Each step makes it worse.
  • The near-zero derivative in the denominator is the danger sign in general. When f'(x) approaches zero, the step f(x)/f'(x) blows up. Any production Newton solver guards this: it caps the step size, falls back to a slower but safe method like bisection when a step misbehaves, and gives up after a bounded number of iterations.

Where this shows up

Newton's method is the engine of numerical computing. Optimizers use it, or its multi-dimensional cousin with the gradient and Hessian, to find where a loss function's slope is zero. Physics engines use it to solve the implicit equations that keep a simulation stable at large time steps. Its safeguarded variants, damped Newton, trust-region methods, Newton with a line search, exist precisely because the raw method explodes, and the safeguards are the hard-won engineering around this beautiful, fragile idea.

If you want to build the safeguarded solvers, the multi-dimensional version, and the optimizers on top of them, that is the ground the scientific-computing track on IWTLP covers in Julia.