Root-Finding Methods
Numerical Methods & Floating-Point Computation
Chapter 7 · Root-Finding Methods
Finding an x where f(x) = 0 is one of the most common tasks in applied computing — and it's where this course's earlier chapters stop being abstract cautionary tales and start directly shaping how a real algorithm is built. This chapter covers three approaches with three genuinely different reliability profiles: bisection (always works, but slowly), Newton's method (usually fast, but can fail outright — reusing Calculus & Optimization's own derivative rules directly), and fixed-point iteration, the general framework both of the others turn out to be special cases of.
Bisection: Guaranteed, Slow, and Hard to Break
If f(a) and f(b) have opposite signs, the Intermediate Value Theorem guarantees a root exists somewhere between them. Bisection exploits this directly: check the midpoint's sign, keep whichever half still brackets the root, and repeat. Every single iteration is guaranteed to halve the interval containing the root — no more, no less.
[2, 3] (since f(2)=−1 and f(3)=16), reaching a tolerance of 10⁻¹² took exactly 39 iterations, converging to 2.094551481542112 — matching the true root, 2.0945514815423265, to the requested precision.
Newton's Method: Reusing Calculus & Optimization's Own Derivative Rules
Newton's method uses the derivative to take a far more informed step: approximate f near the current guess with its tangent line (exactly the derivative Calculus & Optimization Chapter 3 defined), and jump to where that tangent line crosses zero: x_{n+1} = x_n − f(x_n)/f'(x_n).
x₀=2.0, Newton's method reaches the same 10⁻¹² tolerance in just 4 iterations: 2.0 → 2.1 → 2.094568121... → 2.094551481698... → 2.0945514815423265 — the last two steps alone gained roughly 6 and then 10+ correct digits. This is quadratic convergence: the number of correct digits roughly doubles every step, versus bisection's fixed, one-bit-per-step linear rate. 39 iterations vs. 4, for the identical equation and tolerance.
Two Genuine Ways Newton's Method Fails
Newton's speed comes at a real cost: unlike bisection, it has no built-in guarantee. Two distinct, verified failure modes:
Failure 1 — A Permanent Cycle
f(x) = x³ − 2x + 2 starting at x₀=0: the iteration produces 0 → 1 → 0 → 1 → 0 → 1 → ... — an exact, permanent 2-cycle that never approaches the function's real root (near −1.77). This isn't slow convergence; it's no convergence at all, from a starting point that looks entirely reasonable.
Failure 2 — Degraded Convergence at a Double Root
Newton's method divides by f'(x) at every step — which is exactly the kind of division Chapter 6 flagged as dangerous when the denominator is close to zero. At a double root (where both f(x)=0 and f'(x)=0 at the same point), that's precisely what happens as the iteration converges.
f(x) = (x−1)² (a double root at x=1) starting at x₀=5: the error shrinks as 4.0 → 2.0 → 1.0 → 0.5 → 0.25 → ... — the ratio between successive errors is exactly 0.5, every single step. That's linear convergence, at precisely bisection's own rate — Newton's usual quadratic speed advantage disappears completely, because f'(x) → 0 right along with f(x) → 0, making the division step increasingly ill-conditioned exactly as it approaches the root.
Fixed-Point Iteration: The General Framework Underneath Both
A fixed-point iteration repeatedly applies x_{n+1} = g(x), hoping the sequence settles at a point where x = g(x). The convergence rule is precise: the iteration converges near a fixed point if |g'(x)| < 1 there, and diverges if |g'(x)| > 1 — a direct, exact echo of Chapter 6's condition-number logic, now applied to a repeated process instead of a single evaluation.
√2 ≈ 1.4142135623730951 using three algebraically valid rearrangements of the same equation, all starting from x₀=1.4:
Iteration g(x) | |g'(√2)| | Verified behavior |
|---|---|---|
g(x) = 2/x | ≈1.0 (marginal) | Never converges — locks into a permanent 2-cycle: 1.4 → 1.42857... → 1.4 → 1.42857... → ..., forever |
g(x) = (x + 2/x)/2 | ≈0.0 | Converges to 1.414213562373095 in just 4 iterations — and is, in fact, exactly Newton's method applied to x²−2=0 |
g(x) = x² + x − 2 | ≈3.83 (>1) | Diverges immediately and dramatically: 1.4 → 1.36 → 1.21 → 0.67 → −0.87 → −2.11 → ..., never settling anywhere near √2 |
g(x) = x − f(x)/f'(x). This isn't a coincidence — it's exactly why the second rearrangement above, (x+2/x)/2, converges so fast: it's what you get from applying Newton's own formula to f(x)=x²−2. The general fixed-point convergence rule, |g'(x)|<1, is the same underlying idea as Newton's quadratic convergence — Newton's method is simply a particularly clever choice of g that drives g'(root) all the way down to 0 for a well-behaved (non-double) root, which is exactly why it usually beats plain bisection so decisively.
Where This Connects
| This chapter's finding | What it resolves or sets up |
|---|---|
Newton's method divides by f'(x), degrading near a double root | Direct application of Chapter 6's conditioning — a near-zero denominator is exactly the ill-conditioned-division pattern already established |
Fixed-point convergence rule |g'(x)|<1 | The same contraction-mapping logic reappears in Chapter 8's iterative linear-system solvers, applied to a vector instead of a single number |
| A permanent 2-cycle from a "reasonable" starting point | A concrete warning Chapter 10's capstone audit checks for directly — Newton's method needs a real convergence safeguard in production code, not blind trust |
Hands-On Exercises
Using this chapter's own verified iteration counts (39 for bisection, 4 for Newton's method, on the same equation and tolerance), explain in your own words why "always use Newton's method, it's faster" would still be bad advice for a general-purpose root finder, using this chapter's own two verified Newton failure modes.
📄 View solutionUsing this chapter's own connection between Newton's method and Chapter 6's conditioning material, explain specifically why a double root (where f(x)=0 and f'(x)=0 at the same point) causes Newton's method to slow down to linear convergence rather than simply failing outright the way division by exactly zero would.
Using this chapter's own verified g(x)=2/x example (which locks into a permanent 2-cycle rather than diverging to infinity or slowly converging), explain what a condition number very close to exactly 1 — as opposed to clearly less than 1 or clearly greater than 1 — predicts about a fixed-point iteration's behavior, and why that's a genuinely different outcome from both convergence and divergence.
Chapter 7 Quick Reference
- Bisection: guaranteed to converge given a sign change, but slow (linear, one bit of precision per step) — verified: 39 iterations to
10⁻¹² - Newton's method:
x_{n+1}=x_n-f(x_n)/f'(x_n), usually much faster (quadratic — digits roughly double each step) but not guaranteed — verified: 4 iterations to the same tolerance, on the same equation - Verified Newton failure 1: a permanent 2-cycle (
f(x)=x³-2x+2,x₀=0) that never converges at all - Verified Newton failure 2: degrades to exactly linear convergence (error ratio
=0.5every step) at a double root, sincef'(x)→0makes the division step ill-conditioned — a direct application of Chapter 6 - Fixed-point iteration
x_{n+1}=g(x)converges near a fixed point iff|g'(x)|<1— verified with three rearrangements of the same equation: one converges in 4 steps, one locks into a 2-cycle, one diverges outright - Newton's method is itself a fixed-point iteration,
g(x)=x-f(x)/f'(x)— the two methods aren't separate ideas, just different choices ofg - Next chapter: Numerical linear algebra pitfalls — the same conditioning and stability ideas, applied to solving systems of equations rather than a single-variable root