Applications: Root Finding Algorithms

Learning Objectives

By the end of this section you will be able to:

1. Explain why root-finding is the canonical application of continuity, and why the IVT gives us our first algorithm for free.
2. Derive Newton's method from the equation of a tangent line in a single line — and visualise it as "slide down the tangent to the x-axis."
3. State and explain the meaning of quadratic convergence — why Newton roughly doubles the number of correct digits per step.
4. Build the secant method as the finite-difference cousin of Newton, and place its $\varphi \approx 1.618$ super-linear order between bisection and Newton.
5. Recognise the failure modes of Newton's method — vanishing derivatives, cycles, and divergence — and choose a hybrid strategy that gets bisection's safety with Newton's speed.
6. Implement all three methods in plain Python and in PyTorch using autograd, demonstrating exactly the kind of building block that powers modern optimisation in deep learning.

The Question Calculus Was Built To Answer

Solving the equation $f(x) = 0$ is the most ancient problem in mathematics. The Babylonians computed square roots four thousand years ago by averaging an estimate with the quotient — what we now call $x_{n+1} = \tfrac{1}{2}\!\left(x_n + \tfrac{a}{x_n}\right)$ — and the algorithm was so accurate that the cuneiform tablet YBC 7289 records $\sqrt{2} \approx 1.41421296\ldots$, correct to six decimals. Three millennia later, that exact algorithm turns out to be a special case of Newton's method applied to $f(x) = x^2 - a$.

Every modern computer can take square roots, cube roots, logarithms, sines, and exponentials — and at the bottom of every one of those routines is a root-finding loop. The CPU's sqrt instruction is Newton's method. TensorFlow's tf.math.lgamma uses Halley's. SciPy's fsolve wraps a damped Newton. We are about to build the same machinery from continuity alone.

The big idea. Continuity guarantees a root EXISTS (IVT). A derivative tells us WHICH WAY the root lies (Newton). And iterating either idea gives us an algorithm that computers can run a billion times a second. Three chapters of calculus collapse into one paragraph here — that is why we treat root finding as Chapter 3's capstone.

From the IVT to an Algorithm

Section 3.5 established a theoretical fact: if $f$ is continuous on $[a, b]$ and $f(a)$ and $f(b)$ have opposite signs, then there exists a number $c \in (a, b)$ with $f(c) = 0$. The theorem is non-constructive — it promises an answer without showing us where to look.

Watch how a single observation turns an existence proof into a procedure: if the IVT works on $[a, b]$, it also works on the half-interval that still contains a sign change. Pick the midpoint $m = (a + b)/2$, evaluate $f(m)$, throw away the half whose endpoints agree in sign, and repeat. The root is trapped in an interval that shrinks geometrically. This is bisection: an existence theorem made algorithmic by a loop.

Recap: Bisection — Continuity's Algorithm

We covered bisection in detail in section 3.5; here is the one-paragraph crib. Start with a bracket $[a, b]$ with $f(a) \cdot f(b) < 0$. Compute the midpoint $c = (a + b)/2$. Whichever of $[a, c]$ or $[c, b]$ still contains a sign change, keep that half. After $n$ iterations, the bracket has width $(b - a)/2^n$, so the error $|c_n - r|$ is at most that. Setting $(b - a)/2^n \le \varepsilon$ and solving for $n$ gives the famous count

For $b - a = 1$ and $\varepsilon = 10^{-12}$, that is $\lceil 12 \log_2 10 \rceil = 40$ iterations. Reliable, but slow.

Newton's Method — Slide Down the Tangent

Bisection treats $f$ as a black box — it asks only for signs. But if $f$ is differentiable, we have far richer information at our disposal: at any point $x_n$, we know not just the function value $f(x_n)$ but also the slope $f'(x_n)$ — and a slope tells us which direction to head.

Imagine a hiker on a smooth hillside trying to reach sea level. At her current position she can see how the ground is tilted; she draws an imaginary straight ramp (the tangent line) that follows that exact tilt; she walks along the ramp until it reaches the imaginary sea-level plane. That landing point becomes her next estimate. Then she repeats. If the hill is nearly flat near the coast, a single straight ramp gets her practically there; if it's curvy, she repeats. That is Newton's method.

The One-Line Derivation

The tangent line to $y = f(x)$ at the point $(x_n, f(x_n))$ has equation

Setting $y = 0$ to find where the tangent crosses the x-axis,

That is the entire Newton update. Calling the result $x_{n+1}$:

Two observations. First, the update has units of length: $f/f'$ has the dimension of $x$ (function value over slope cancels the function units), which is exactly the dimension we need to add to $x_n$. Second, when $f(x_n) = 0$, the update size is zero — Newton stops at the root, as it should.

Interactive: Newton's Method Explorer

Pick a function from the three buttons. Drag the slider to choose a starting guess $x_0$. Step through the iterations and watch each red tangent line meet the x-axis — that landing point becomes the next purple starting point, and the error column on the right halves of decades at each step.

Why Newton Converges Quadratically

Let $r$ denote the true root and $e_n = x_n - r$ the error at step $n$. We expand $f$ around $r$ using Taylor (we will derive Taylor's theorem properly in Chapter 14; here you can think of it as "polynomial approximation of order 2"):

(using $f(r) = 0$). Similarly $f'(x_n) = f'(r) + f''(\eta)\, e_n$. Plug into the Newton update and simplify:

That last expression says $|e_{n+1}| \le C\, e_n^2$ with $C = |f''(r)/(2 f'(r))|$. The error squares. If $e_n = 10^{-3}$, then $e_{n+1} \approx 10^{-6}$, then $10^{-12}$, then $10^{-24}$ — except double-precision floats have already run out of precision, so we stop at 10⁻¹⁶.

Worked Example — Computing √2 By Hand

Secant Method — Newton Without the Derivative

Newton's method is beautiful but it has one practical demand: you must be able to compute $f'(x)$. For tabulated data, black-box simulators, or functions defined by long pipelines, the derivative may be unavailable or expensive. The secant method patches this by replacing the tangent with a secant line through the two most recent iterates.

Given two estimates $x_{n-1}$ and $x_n$, draw the straight line through $(x_{n-1}, f(x_{n-1}))$ and $(x_n, f(x_n))$. Its slope is the finite difference

— a discrete approximation to $f'(x_n)$. Substituting $m_n$ in place of $f'(x_n)$ in the Newton update gives

That is the secant iteration. It needs two starting points (we provide $x_0, x_1$) but never asks for a derivative. As $x_{n-1} \to x_n$ the secant slope approaches the tangent slope, so geometrically secant is "Newton, but with a delayed slope estimate."

Interactive: The Three Methods Race for √2

Three colours, three slopes, same destination. Toggle between log and linear y-axes to see the geometry of convergence change.

On the log axis, look at three separate behaviours:

• Bisection (red): a perfectly straight line. Each iteration cuts the error by exactly $1/2$, so on a log axis that's a constant downward slope of $-\log_{10} 2 \approx -0.301$ per step. Predictable and pedestrian.
• Newton (blue): a curve that bends sharply downward. The error squares each step, so the log of the error doubles in magnitude — a parabola on this plot. After 5 steps we hit machine zero (≈10⁻¹⁵) and stop.
• Secant (green): visibly between the two. Curves downward, just not as steeply as Newton — exactly what an exponent of $\varphi \approx 1.618$ looks like geometrically.

Linear, Super-Linear, Quadratic — What the Orders Mean

We've used three phrases — linear, super-linear, quadratic. They have a precise meaning that ties together every iterative method you will meet for the rest of this book and beyond.

Notice the trade-off pattern: higher order requires more derivative information per step. There is no universal "best" — the right choice depends on whether your function is cheap or expensive to differentiate.

When Newton's Method Goes Off the Rails

Quadratic convergence is a local property — it only kicks in once you're near the root. Globally Newton can do almost anything. Here are the four classical failure modes, each worth knowing.

Python — All Three Methods, Side By Side

One file, three solvers, one root. The driver runs all three on the same problem and prints the iteration counts side by side. Trace through the explanations to see exactly how the IVT, the tangent line, and the secant slope encode themselves as Python.

true sqrt(2)        = 1.414213562373095
bisection (52 it.)  = 1.414213562373
   err = 1.11e-13
newton    ( 5 it.)  = 1.414213562373095
   err = 0.00e+00
secant    ( 7 it.)  = 1.414213562373095
   err = 2.22e-16

1# Three classical root-finders on the same target:
2#     find r > 0 such that  f(r) = r^2 - 2 = 0    (so r = sqrt(2))
3
4def f(x):
5    return x * x - 2.0
6
7def df(x):
8    return 2.0 * x                  # analytic derivative
9
10# --- Method 1: bisection (needs only continuity + a sign change) ---
11def bisection(a, b, tol=1e-12, max_iter=80):
12    if f(a) * f(b) > 0:
13        raise ValueError("need a sign change in [a, b]")
14    history = []
15    for n in range(1, max_iter + 1):
16        c = 0.5 * (a + b)
17        history.append(c)
18        if abs(f(c)) < tol or (b - a) < tol:
19            return c, history
20        if f(a) * f(c) < 0:
21            b = c
22        else:
23            a = c
24    return 0.5 * (a + b), history
25
26# --- Method 2: Newton (needs differentiability + a good guess) ---
27def newton(x0, tol=1e-14, max_iter=20):
28    x = x0
29    history = [x]
30    for n in range(max_iter):
31        fx, dfx = f(x), df(x)
32        if dfx == 0.0:
33            raise ZeroDivisionError("derivative vanished")
34        x = x - fx / dfx                  # the Newton step
35        history.append(x)
36        if abs(fx) < tol:
37            return x, history
38    return x, history
39
40# --- Method 3: secant (needs only function values, not the derivative) ---
41def secant(x0, x1, tol=1e-14, max_iter=30):
42    history = [x0, x1]
43    for n in range(max_iter):
44        fx0, fx1 = f(x0), f(x1)
45        if fx1 == fx0:
46            break
47        x2 = x1 - fx1 * (x1 - x0) / (fx1 - fx0)
48        history.append(x2)
49        if abs(fx1) < tol:
50            return x1, history
51        x0, x1 = x1, x2
52    return x1, history
53
54# --- Driver: race all three on the same root ---
55import math
56root_bi, h_bi = bisection(1.0, 2.0)
57root_nw, h_nw = newton(2.0)
58root_sc, h_sc = secant(1.0, 2.0)
59true_root = math.sqrt(2.0)
60
61print(f"true sqrt(2)        = {true_root:.15f}")
62print(f"bisection (52 it.)  = {root_bi:.15f}   err = {abs(root_bi-true_root):.2e}")
63print(f"newton    ( 5 it.)  = {root_nw:.15f}   err = {abs(root_nw-true_root):.2e}")
64print(f"secant    ( 7 it.)  = {root_sc:.15f}   err = {abs(root_sc-true_root):.2e}")

PyTorch — Newton with Autograd

Newton needs $f'(x)$. In a research notebook where the function changes every few minutes, hand-coding the derivative is a tax on experimentation. PyTorch's autograd gives us the derivative for free — and the resulting Newton loop is the same code we'd use inside an optimiser. If you ever wondered "is gradient descent like Newton?" — yes, gradient descent is the simplified cousin where we replace $1/f'$ with a fixed learning rate.

Newton-via-autograd: root = 2.094551481542
Function value:       f(root) = 0.00e+00
Took 5 iterations:
  x_1 = 2.100000000000
  x_2 = 2.094568121104
  x_3 = 2.094551481698
  x_4 = 2.094551481542
  x_5 = 2.094551481542

1import torch
2
3# A more interesting target: solve f(x) = x^3 - 2*x - 5 = 0
4# (Newton famously used this exact equation in 1669.)
5def f(x: torch.Tensor) -> torch.Tensor:
6    return x ** 3 - 2 * x - 5
7
8def newton_autograd(x0: float, tol=1e-12, max_iter=20):
9    """Newton with the derivative computed automatically via autograd."""
10    x = torch.tensor(x0, dtype=torch.float64, requires_grad=True)
11    history = []
12    for n in range(max_iter):
13        # Forward pass: evaluate f(x) and record the graph
14        y = f(x)
15
16        # Backward pass: dy/dx is filled into x.grad
17        if x.grad is not None:
18            x.grad.zero_()                # always zero accumulators
19        y.backward()
20        dfx = x.grad                      # this IS f'(x), computed automatically
21
22        # The Newton step — exactly the same line as the plain-Python version
23        with torch.no_grad():
24            x_new = x - y / dfx
25            history.append(x_new.item())
26            if y.abs().item() < tol:
27                return x_new.item(), history
28            x.copy_(x_new)                # in-place update, preserves graph
29    return x.item(), history
30
31root, hist = newton_autograd(x0=2.0)
32print(f"Newton-via-autograd: root = {root:.12f}")
33print(f"Function value:       f(root) = {f(torch.tensor(root, dtype=torch.float64)).item():.2e}")
34print(f"Took {len(hist)} iterations:")
35for n, v in enumerate(hist):
36    print(f"  x_{n+1} = {v:.12f}")

Where Root-Finding Lives in Practice

Root finding is the universal solvent of applied mathematics. Whenever a problem reduces to "find $x$ such that some condition holds," you are almost certainly going to call a root-finder somewhere in the implementation.

Hardware square roots and trig

x86's FSQRT, ARM's FSQRT instruction, and the GPU intrinsic __fsqrt_rn all implement Newton's method on $f(x) = x^2 - a$, refined to give the correctly-rounded result. The infamous Fast Inverse Square Root from Quake III is a single Newton step on $f(x) = 1/x^2 - a$ seeded by a magic integer constant.

Implicit equations of state

Compressors, gas pipelines, and refrigeration cycles need to solve van der Waals or Peng–Robinson equations of the form $P(V, T) = P_{\text{set}}$ for $V$. There is no closed form. Every iteration of the plant's control loop invokes a Newton solver on the residual $f(V) = P(V, T) - P_{\text{set}}$.

Implicit ODE integration

Stiff differential equations — chemical kinetics, electrical circuits, structural dynamics — are solved by implicit methods (backward Euler, BDF). Each time step requires solving a nonlinear equation in the new state. That "solve a nonlinear equation" is Newton, called millions of times per simulation.

Machine learning: maximum likelihood and Newton optimisation

Maximum likelihood estimation seeks the parameters $\theta^*$ that satisfy the score equation $\nabla_\theta \ell(\theta^*) = 0$. That's root finding on the gradient. Newton's method generalised to vectors gives the celebrated Newton-Raphson iteration for logistic regression: $\theta_{n+1} = \theta_n - H^{-1} g$, where $H$ is the Hessian and $g$ is the gradient.

Implied volatility in option pricing

The Black-Scholes formula gives an option price as a function of volatility. To recover the market's implied volatility from the observed price, you invert that formula numerically — which means finding the root of $f(\sigma) = \text{BS}(\sigma) - P_{\text{market}}$. Every quote feed in every options exchange runs this loop in real time.

Common Pitfalls

• Forgetting that "converged" is not always "right". A small $|f(x_n)|$ doesn't guarantee a small error. If the slope is huge, you can be far from the root and still have a tiny function value. Always inspect both $|f(x_n)|$ AND $|x_{n+1} - x_n|$.
• Trusting Newton near multiple roots. If $f$ has a double root (e.g. $f(x) = (x - 1)^2$), Newton degrades to linear convergence because $f'(r) = 0$. Modified Newton (multiply the step by the multiplicity) restores quadratic convergence.
• Picking a step that flies off the chart. Always sanity-check that $|x_{n+1} - x_n| < D$ for some maximum trust radius $D$. If the proposed Newton step exceeds it, shrink it.
• Mixing tolerances. Some implementations stop on $|f(x)|$, others on $|x_{n+1} - x_n|$. Be explicit about which one you want and document it in the API.
• Using float32 when you wanted float64. A solver tuned for double precision can fail silently in single precision because the algorithm hits the noise floor before reaching the requested tolerance.

Summary

Continuity is not just a definition — it is the engine that drives a whole class of algorithms. The IVT gives us bisection. Differentiability adds Newton. Finite-difference approximations to the derivative add the secant method. Each method buys speed at the cost of a stronger assumption, and the convergence-order ladder — linear, super-linear, quadratic — quantifies that trade exactly.

Chapter 4 introduces the derivative formally — and immediately you will recognise the Newton update as the very first non-trivial use of derivatives, almost three centuries before its inventors knew the word "derivative." Calculus and computation, from the very first chapter, have always been the same subject.