Phase 5 - Lesson 5.1

Floating-Point Arithmetic, Conditioning, and Stability

Why finite-precision numbers are enough - and the two independent things that can still ruin an answer.

⏱ 50 min● Intermediate🔗 Prereqs: 4.x linear algebra

Builds on: Phase 4 built exact linear algebra; here every number is rounded.
Leads to: Conditioning and stability are the lens for judging LU, QR, Cholesky and eigen-solvers in 5.2–5.5.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Explain the IEEE-754 double model and bound rounding by machine epsilon.
Define the condition number of a problem and compute it for matrix solves.
Distinguish a well-posed but ill-conditioned problem from an unstable algorithm.
Interpret backward stability and the rule of thumb error ≤ condition × machine epsilon.
Implement a 2-norm condition-number routine and diagnose catastrophic cancellation.

Key Vocabulary

Machine epsilon: The gap between 1 and the next representable double, $\epsilon_{\text{mach}}\approx 1.1\times10^{-16}$; bounds relative rounding error.

Floating-point number: A value $\pm(1.f)_2\times 2^{e}$ with a finite mantissa; only finitely many exist in any range.

Condition number: How much a problem amplifies relative input error; for solving $Ax=b$ it is $\kappa(A)=\lVert A\rVert\,\lVert A^{-1}\rVert$.

Backward stability: An algorithm is backward stable if its computed answer is the exact answer to a slightly perturbed input.

Catastrophic cancellation: Loss of significant digits when subtracting two nearly equal, individually rounded numbers.

Forward error: The difference between the computed and true answer; bounded by (condition)×(backward error).

Intuition & Motivation

Intuition

Two very different things can wreck a numerical answer, and confusing them is the classic beginner error. The first belongs to the problem: some questions are inherently sensitive - a hair’s-width change in the input swings the true answer wildly. That sensitivity is the condition number, and no clever code can remove it. The second belongs to the algorithm: even a well-behaved problem can be mangled by a method that amplifies rounding. That is stability. The master rule ties them together: $\text{forward error} \lesssim \kappa \cdot \epsilon_{\text{mach}}$ for a backward-stable method.

Floating point in one model

A double stores a sign, a 52-bit mantissa, and an 11-bit exponent. The key fact for analysis is that rounding any real $x$ to its nearest double $\text{fl}(x)$ costs at most a relative $\epsilon_{\text{mach}}$:

\[\text{fl}(x) = x(1+\delta),\qquad |\delta|\le \epsilon_{\text{mach}}\approx 1.1\times 10^{-16}.\] (5.1)

Each elementary operation $\{+,-,\times,\div\}$ incurs one such $\delta$. Errors normally accumulate gently - except under subtraction of near-equal numbers, where the leading digits cancel and only rounding noise remains.

Definition - Condition number of a problem

For a problem $y=f(x)$, the (relative) condition number is $\kappa = \lim_{\varepsilon\to0}\sup_{\lVert\delta x\rVert\le\varepsilon\lVert x\rVert}\frac{\lVert\delta y\rVert/\lVert y\rVert}{\lVert\delta x\rVert/\lVert x\rVert}$. For solving $Ax=b$ with respect to $b$ it equals $\kappa(A)=\sigma_{\max}/\sigma_{\min}$.

Theorem - Backward-stability bound

If an algorithm is backward stable (computed $\hat y$ is exact for input $x(1+\delta)$, $|\delta|=O(\epsilon_{\text{mach}})$), then the relative forward error obeys $\lVert\hat y - y\rVert/\lVert y\rVert = O(\kappa\,\epsilon_{\text{mach}})$.

Worked Example - Ill-conditioning is real, not a bug

Take $A=\begin{psmallmatrix}1&1\\1&1.001\end{psmallmatrix}$, $b=(2,\,2.001)^\top$. Since $\det A = 0.001$, the exact solution is $x=(1,1)^\top$.

Perturb only the last entry of $b$ by $0.001$ to $(2,\,2.002)^\top$ - a relative input change near $5\times10^{-4}$.

The new exact solution is $x=(0,2)^\top$: a full-scale swing. The output moved thousands of times more than the input.

That amplification is $\kappa_2(A)\approx 4\times10^{3}$. A perfect solver still returns garbage-sensitive answers - the fault is the problem, not the code.

Interactive: watch a solve amplify error

Drag the near-singular entries and see how the solution of $Ax=b$ reacts to tiny changes - the geometric meaning of a large condition number.

Interactive: compute the condition number

Implement the 2-norm condition number from the SVD and confirm the diagnosis above numerically.

Common Mistakes to Avoid

Blaming the solver for a large forward error when the matrix is ill-conditioned - that error is unavoidable.
Testing floating-point results with == instead of a tolerance.
Computing variance as E[x²]−E[x]² on clustered data, inviting catastrophic cancellation (use a two-pass or Welford method).
Assuming more iterations always help; past $\kappa\epsilon_{\text{mach}}$ accuracy you are only refining noise.

Quant Practitioner Tips

Report the condition number alongside any linear solve; it tells you how many digits you can trust.
Prefer backward-stable factorizations (QR, Cholesky) over forming $A^{-1}$ or normal equations explicitly.
Rule of thumb: you lose about $\log_{10}\kappa$ decimal digits solving $Ax=b$.
Scale/equilibrate columns so units don’t artificially inflate the condition number.

Practice this in the Euler Lab

Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.

Warm-up:
#24 Lexicographic Permutations (6%, tier A) #65 Convergents of $e$ (6%, tier A) #205 Dice Game (10%, tier A) #68 Magic 5-gon Ring (9%, tier B)

Applied:
#816 Shortest Distance Among Points (17%, tier B) #323 Bitwise-OR Operations on Random In (18%, tier B) #479 Roots on the Rise (19%, tier B)

Challenge:
#666 Polymorphic Bacteria (41%, tier C) #869 Prime Guessing (41%, tier C)

146 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.

Knowledge Check

Q1 Medium

A matrix has condition number $\kappa\approx10^{8}$. Using a backward-stable double-precision solver, roughly how many correct digits can you expect?

About 16

About 8

About 0

It depends only on the algorithm, not $\kappa$

Q2 Easy

Which statement best separates conditioning from stability?

Both are properties of the algorithm

Conditioning is a property of the problem; stability is a property of the algorithm

Conditioning is a property of the algorithm; stability of the problem

They are two names for the same thing

Q3 Medium

Catastrophic cancellation is most severe when you:

Add two large numbers of the same sign

Multiply two nearly equal numbers

Subtract two nearly equal, already-rounded numbers

Divide by a number near 1

Practical Exercise

Explain, using the backward-stability bound, why solving the normal equations $A^\top A x = A^\top b$ for least squares can lose twice as many digits as a QR-based solve. Give the key inequality.

▶ Show full solution

The conditioning of the least-squares problem scales with $\kappa(A)$. Forming $A^\top A$ squares the singular values, so $\kappa(A^\top A)=\kappa(A)^2$.

A backward-stable solve of the normal equations therefore yields forward error $\sim\kappa(A)^2\,\epsilon_{\text{mach}}$, whereas a QR-based solve keeps the conditioning at $\kappa(A)$, giving $\sim\kappa(A)\,\epsilon_{\text{mach}}$.

\[\kappa(A^\top A)=\kappa(A)^2\;\Rightarrow\; \text{digits lost} \approx 2\log_{10}\kappa(A)\ \text{vs.}\ \log_{10}\kappa(A).\]

After the reveal, answer for yourself: When is squaring the condition number harmless? (When $\kappa(A)$ is already tiny, e.g. an orthonormal design.)

Lesson Summary

Every double is exact to a relative $\epsilon_{\text{mach}}\approx10^{-16}$. Two independent failure modes remain: an ill-conditioned problem amplifies input error by $\kappa$ regardless of the code, and an unstable algorithm adds error a good method would not. The unifying rule for backward-stable methods is forward error $\lesssim\kappa\,\epsilon_{\text{mach}}$.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: State the backward-stability rule of thumb.
A: For a backward-stable algorithm, relative forward error is on the order of $\kappa\,\epsilon_{\text{mach}}$; you lose about $\log_{10}\kappa$ digits.

Q: Why is forming the normal equations risky?
A: Because $\kappa(A^\top A)=\kappa(A)^2$, squaring the conditioning and doubling the digits lost; QR avoids this.

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lec 12–15 - Lectures 12–15: floating point, conditioning, stability, backward error.
Linear Algebra Done Right (Sheldon Axler, 4th ed., 2024) current - Ch. 7 - Singular values and operator norms behind $\kappa=\sigma_{\max}/\sigma_{\min}$.

← 4.7 Next: 5.2 →