Numerical Linear Algebra Pitfalls
Numerical Methods & Floating-Point Computation
Chapter 8 · Numerical Linear Algebra Pitfalls
Linear Algebra Fundamentals covered Gaussian elimination as an exact, always-correct algebraic procedure. In floating point, it is not always safe to run exactly as written — the order in which rows are eliminated can make the difference between an accurate answer and a badly wrong one, on the very same system of equations.
Plain Gaussian Elimination Can Fail — Even Without a Genuinely Ill-Conditioned System
Solve this ordinary-looking 2×2 system:
Standard Gaussian elimination uses the first row's leading entry as the pivot to eliminate x from the second row. Here, that pivot is 1 × 10⁻¹⁶ — tiny, but not literally zero, so nothing raises an error. The elimination step computes a multiplier m = 1 / 10⁻¹⁶ = 10¹⁶ and uses it to combine the rows.
y comes out as 0.9999999999999998 — essentially exact, relative error ≈1.2 × 10⁻¹⁶. But x comes out as 2.220446049250313 — a relative error of ≈1.22, meaning the computed answer is more than double the true value of 1.0. Same system, same elimination procedure, one variable essentially perfect and the other one completely unusable.
x as (1 − y) / 10⁻¹⁶. y itself carries a tiny rounding error (as verified, extremely small on its own) — but subtracting it from 1 triggers exactly Chapter 4's cancellation pattern, and then dividing that already-damaged result by the tiny original pivot multiplies whatever error survived the subtraction by 10¹⁶. The huge multiplier used during elimination is what makes this catastrophic: it's the same "divide by something close to zero" danger Chapter 6 and Chapter 7 (Newton's method near a double root) already flagged, now appearing inside a multi-step linear-system solve.
The Fix: Partial Pivoting
Partial pivoting is a simple, mechanical rule: before eliminating a column, swap rows so that the row with the largest available magnitude in that column becomes the pivot row. It doesn't change the mathematical system being solved — just the order the rows are processed in.
1 instead of 10⁻¹⁶, giving a multiplier of just 10⁻¹⁶ instead of 10¹⁶): x now comes out as exactly 1.0 (relative error ≈1 × 10⁻¹⁶) and y stays just as accurate as before. Nothing about the underlying equations changed — only the order of elimination — and the catastrophic failure disappears completely.
≤1 — by construction, since the pivot is always at least as large as everything below it in that column. A multiplier that never exceeds 1 can never amplify rounding error the way this chapter's 10¹⁶ multiplier did, which is exactly why partial pivoting is the industry-standard default in virtually every real linear algebra library, not an optional refinement.
Ill-Conditioned Matrices, Revisited With Real Numbers
Partial pivoting fixes an unstable algorithm (Chapter 5's territory) — but Chapter 6 already showed some systems are ill-conditioned problems, which no algorithm can fix. The matrix condition number, cond(A) = ‖A‖ · ‖A⁻¹‖, puts a precise number on this, computed directly using Linear Algebra Fundamentals' own determinant and inverse formulas.
A = [[1,1],[1,1.0001]]: det(A) = 0.0001, and by the standard 2×2 inverse formula, A⁻¹ = [[10001, −10000], [−10000, 10000]]. Using the largest-row-sum matrix norm: ‖A‖ = 2.0001 and ‖A⁻¹‖ = 20001, giving cond(A) = 40,004.0001 — directly explaining the roughly 10,000× amplification Chapter 6 measured empirically for that exact system (the condition number is an upper bound on amplification across any perturbation direction; Chapter 6's experiment perturbed only one entry, so it measured somewhat below this worst-case bound). For contrast, a well-behaved diagonal matrix B = [[2,0],[0,3]] gives cond(B) = 1.5 — close to the best-possible value of 1.
10⁻¹⁶-pivot example, because that system was well-conditioned — its true solution isn't especially sensitive to small input changes; only the naive elimination order was the problem. The near-singular matrix above is a genuinely different situation: cond(A)=40,004 means the problem itself amplifies input error by that much, regardless of pivoting, regardless of algorithm choice — exactly Chapter 6's own conclusion, now expressed as a single computable number for an entire matrix instead of one subtraction.
Two Genuinely Different Diagnoses, Side by Side
| This chapter's 10⁻¹⁶-pivot system | Chapter 6's near-singular system | |
|---|---|---|
| What was actually wrong | Elimination order (small pivot, huge multiplier) | The matrix's own geometry (near-parallel rows) |
| Diagnosis | Algorithm instability (Ch.5) | Problem ill-conditioning (Ch.6) |
| Fixed by partial pivoting? | Yes — verified, error dropped from 1.22 to ≈10⁻¹⁶ | No — pivoting reorders rows, it doesn't change cond(A) |
| The real fix, if one exists | Use a stable algorithm (done) | Better input precision, or accept/report the uncertainty (Ch.6's own conclusion) |
Where This Connects
| This chapter's finding | What it resolves or sets up |
|---|---|
| A huge elimination multiplier amplifies rounding error via Chapter 4's cancellation | Direct extension of Chapter 4-5's single-operation cancellation into a full multi-step linear solve |
cond(A) computed via Linear Algebra Fundamentals' own determinant/inverse formulas | Fully quantifies Chapter 6's near-singular example, closing a loop that chapter left as "roughly 10,000×" |
| Stability (fixable) vs. conditioning (not fixable) applied to a real matrix | Chapter 10's capstone audit checks for both patterns directly in real code |
Hands-On Exercises
Using this chapter's own verified 10⁻¹⁶-pivot example, explain specifically why y came out essentially perfect while x came out more than 100% wrong, from the exact same elimination process on the exact same system.
Explain, using this chapter's own reasoning about multiplier size, why partial pivoting's rule (always use the largest-magnitude available entry as the pivot) guarantees every multiplier has magnitude no greater than 1.
A developer, having read this chapter's first example, concludes "always use partial pivoting, and every linear system will then be solved reliably." Using this chapter's own comparison between the two worked examples, explain what's wrong with that conclusion.
📄 View solutionChapter 8 Quick Reference
- Plain Gaussian elimination with a tiny pivot uses a huge multiplier, which amplifies rounding error via Chapter 4's cancellation mechanism during back-substitution — verified: a
10⁻¹⁶pivot produced a122%relative error in one variable, while the other stayed accurate - Partial pivoting — always eliminate using the largest-magnitude available entry as the pivot — bounds every multiplier to magnitude
≤1, fully fixing this specific failure: verified error dropped to≈10⁻¹⁶ - The matrix condition number
cond(A)=‖A‖·‖A⁻¹‖, computed via Linear Algebra Fundamentals' own inverse formula, quantifies Chapter 6's near-singular system precisely:cond(A)≈40,004, vs.cond(B)=1.5for a well-conditioned matrix - Pivoting fixes algorithm instability (Ch.5) but cannot fix problem ill-conditioning (Ch.6) — the two failures verified in this chapter needed genuinely different diagnoses and genuinely different fixes
- Next chapter: Numerical differentiation & integration, revisited — a deeper pass through territory Calculus & Optimization only introduced