Numerical Stability: When the Algorithm Is the Problem
Numerical Methods & Floating-Point Computation
Chapter 5 · Numerical Stability: When the Algorithm Is the Problem
Chapter 4 fixed one specific formula — the quadratic formula's unstable branch — by restructuring a single subtraction. This chapter generalizes that idea: numerical stability is a property of an algorithm, not of the underlying mathematical problem. Two formulas that are perfectly, provably equal in exact arithmetic can behave completely differently once real floating-point rounding gets involved — and recognizing which formula you're looking at is a skill in its own right.
Two Equivalent Formulas for the Same Quantity: Variance
Statistical variance has two textbook-equivalent formulas. The two-pass formula computes the mean first, then averages the squared distance of each point from that mean. The one-pass ("naive") formula avoids a second pass over the data by expanding the algebra: Var(X) = E[X²] − (E[X])².
Algebraically, these are exactly the same quantity — every statistics textbook derives one from the other with a few lines of expansion. In floating point, they are not remotely the same.
A Genuinely Dramatic, Fully Verified Failure
Take 9 real numbers, each equal to 20,000,000 plus a small random offset between 0 and 1 (a realistic shape for, say, sensor readings with a large fixed baseline and small genuine variation):
0.0672569888025179, matching a 60-digit high-precision reference calculation to a relative error of ≈7.1 × 10⁻¹⁷ — essentially exact. The naive one-pass formula, on the exact same data, gives −0.0625. Variance is mathematically defined as an average of squared quantities — it is never negative, by definition. The naive formula didn't just lose some accuracy; it returned a value that is provably impossible for the quantity it claims to compute.
E[X²] and (E[X])² are both enormous numbers here — each close to (2 × 10⁷)² = 4 × 10¹⁴ — while their true difference (the actual variance) is a tiny fraction of that, around 0.067. Subtracting two huge, nearly-equal numbers to recover a tiny result is exactly the catastrophic-cancellation pattern from Chapter 4 — just spread across an entire sum-of-squares computation instead of a single visible subtraction. The rounding error accumulated while computing the two huge sums is, in this case, larger than the true answer itself, which is exactly how the result can end up negative.
The two-pass formula never runs into this problem, because it subtracts the mean from each data point first — before any squaring or summing happens. Every value it works with afterward is already small and close to zero (each of the 9 offsets, centered), so there are no huge intermediate sums for rounding error to hide inside.
It's Not Always Catastrophic — But It's Never Free
The size of the failure depends on how large the data's offset is relative to its own spread. Using the same 9-point idea but with a smaller offset (around 1,000,000 instead of 20,000,000), the naive formula's relative error was verified at roughly 0.25% — a real, measurable error, but not one that produces an outright impossible result. Push the offset larger still (around 10⁸), and the naive formula's result collapses to exactly 0.0 — complete, 100% information loss, the same complete-collapse pattern Chapter 4 verified for (1+x)-1 at small enough x.
| Data offset relative to spread | Naive one-pass result | Two-pass result |
|---|---|---|
| Moderate (~10⁶) | ~0.25% relative error — noticeably degraded, not catastrophic | ~10⁻¹⁶ relative error — essentially exact |
| Large (~10⁷–10⁸) | Negative variance, or a complete collapse to exactly 0.0 | ~10⁻¹⁶ relative error — unaffected by the data's offset |
Numerical Stability, Defined
An algorithm is numerically stable if small rounding errors introduced at each individual step stay small in the final result, relative to the size of what's being computed. An algorithm is numerically unstable if those small per-step errors can be amplified into a large, disproportionate error in the output — exactly what the naive variance formula does whenever the data's own scale is much larger than its spread. Crucially, stability is a property of how the computation is organized, not of the mathematical quantity being computed — both formulas compute "variance"; only one of them computes it reliably.
a - b sitting directly in the code. Recognizing numerical instability increasingly means recognizing the shape of a computation (large intermediate values feeding into a final subtraction), not just spotting an explicit minus sign.
Where This Connects
| This chapter's finding | What it sets up |
|---|---|
| Stability is a property of the algorithm, distinct from the problem itself | Sets up Chapter 6's condition number, which measures instability that comes from the problem, independent of which algorithm is used |
| The two-pass formula avoids ever subtracting large near-equal numbers | The same "center first, then combine" strategy reappears in Chapter 9's own numerical differentiation/integration techniques |
| Two mathematically identical formulas, one reliable and one not | Directly informs Chapter 8's treatment of Gaussian elimination, where multiple algebraically-equivalent elimination orders differ sharply in reliability |
Hands-On Exercises
Explain, using this chapter's own verified negative-variance result, why a negative output from the naive variance formula is proof of a numerical bug rather than just "a somewhat inaccurate but plausible" result.
📄 View solutionUsing this chapter's own explanation, describe specifically why the two-pass variance formula never suffers the same cancellation problem as the naive formula, even though it still involves subtraction (x - mean) at every single data point.
A junior developer argues: "the two formulas are mathematically the same, so it doesn't matter which one we use — pick whichever runs in one pass over the data for speed." Using this chapter's own findings, write a short, specific explanation of what's wrong with that reasoning.
📄 View solutionChapter 5 Quick Reference
- Numerical stability is a property of an algorithm's structure, not of the mathematical quantity it computes — two formulas can be algebraically identical and numerically very different
- Verified: the naive one-pass variance formula (
E[X²]-(E[X])²) returned−0.0625— a mathematically impossible negative variance — on real data with a large offset; the two-pass formula matched a high-precision reference to≈7×10⁻¹⁷relative error on the same data - The failure scales with the data's offset relative to its spread — verified: ~0.25% error at moderate offset, complete collapse to exactly
0.0at a large enough offset - The root cause is Chapter 4's own cancellation mechanism, hidden inside a multi-step sum rather than a single visible subtraction
- The fix pattern generalizes Chapter 4's: center or otherwise avoid combining large near-equal quantities before the final subtraction happens
- Next chapter: Error propagation & conditioning — separating instability caused by the algorithm from instability that's baked into the problem itself