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

← 4.7 Next: 5.2 →