Conditioning and Floating-Point Arithmetic

Two questions about a computation are easy to confuse. One is whether the problem is sensitive: whether its answer changes sharply when its data is perturbed. The other is whether an algorithm is good: whether it computes the answer accurately. They are separate, and keeping them apart is the discipline of error analysis. Conditioning is the first question, a property of the problem alone, and it bites because of the perturbations that floating-point arithmetic supplies at every step.

Measuring error

Before sensitivity can be quantified, error itself needs a measure. For a computed $\hat{x}$ approximating $x$:

• Absolute error $\Vert \hat{x}-x\Vert$ — the raw size of the deviation.
• Relative error $\Vert \hat{x}-x\Vert /\Vert x\Vert$ — the deviation as a fraction of the quantity, and so a count of correct significant digits.
• Componentwise relative error ${\max }_j|{\hat{x}}_j-x_j|/|x_j|$ — relative error demanded of every entry at once, which preserves the zero/nonzero (sparsity) pattern of the data.

Which one applies is a modeling choice: relative error for physical quantities and for rounding, absolute error for numbers on a fixed scale such as probabilities or counts.¹ Relative error is the default below unless noted.

Conditioning of a problem

Model a computation as evaluating a map $f:x\mapsto y=f(x)$, from data to result. Data is never exact — it comes from measurement, or from rounding it into the machine — so instead of $y=f(x)$ one gets $\tilde{y}=f(\tilde{x})$ for some perturbed input $\tilde{x}$.

Ill-conditioning is a fact about the mathematical model. It has nothing to do with computers or algorithms: a sensitive problem is sensitive even under exact arithmetic, and the right response is sometimes to question why the quantity is being computed at all.² For definiteness, take $\kappa \gtrsim 10^5$ as ill-conditioned in what follows.

The geometric archetype is intersecting two lines. Each line is known only to within its drawn width. When the lines cross squarely, the intersection is pinned down about as tightly as the lines themselves. When they meet at a shallow angle — a glancing intersection — a sliver of uncertainty in the lines spreads the crossing point across a long interval. Same problem, opposite conditioning, set by the crossing angle alone.

For a differentiable scalar map $f$, linearizing $f(x+w)\approx f(x)+f^{\prime }(x)w$ turns the definition into a closed formula. With respect to componentwise relative error in $x$ and relative error in $f(x)$,

Applying it to the elementary operations settles which arithmetic is safe.

Multiplication, division, and square root have small, constant condition numbers, and addition of like-signed numbers is condition $1$. The single dangerous operation is subtraction of nearly equal numbers: when $|{\xi }_1-{\xi }_2|\ll |{\xi }_1|+|{\xi }_2|$, the denominator collapses and $\kappa$ explodes. This is cancellation.

For example, subtract two numbers agreeing to eight digits but each uncertain in the ninth:

The uncertain digit, buried in the ninth place of the inputs, has surfaced to the third significant place of the result: six significant digits were lost, and here $\kappa \approx 2.2\times 10^6$. The general statement is worth memorizing:

The condition number of a linear system

For the central problem $Ax=b$, the amplifier of relative error is the condition number of the matrix. Perturb the right-hand side to $b+r$; the solution moves by $A^{-1}r$, and

Perturbing $A$ itself gives the same bound. The amplifying factor gets a name.

In the Euclidean norm this factor is the ratio of the largest to the smallest singular value, ${\kappa }_2(A)={\sigma }_1/{\sigma }_m$. Geometrically, $A$ maps the unit sphere to an ellipsoid whose semi-axes are the singular values; ${\kappa }_2(A)$ is that ellipsoid's eccentricity. A well-conditioned matrix maps the sphere to a nearly round ball, so no direction of the answer is much more sensitive than another; an ill-conditioned one maps it to a long thin sliver, and directions near the short axis are badly amplified.

Kahan's theorem sharpens the meaning of $\kappa (A)$: its reciprocal is the relative distance from $A$ to the nearest singular matrix.

So a large condition number is literal proximity to non-invertibility. If $A$ is only known to relative accuracy $\epsilon$ and ${\kappa }_2(A)\ge {\epsilon }^{-1}$, then $A$'s uncertainty ball reaches a singular matrix, and $A$ is effectively indistinguishable from one; such a matrix is called $\epsilon$-singular. When $\epsilon$ is the machine precision, it is numerically singular.

Conditioning worsens sharply with $n$; in double precision, subtracting the digits lost from the roughly sixteen available leaves only what the last column records.

By $n=6$, solving $H_{6}x=b$ in double precision returns only about nine correct digits, before any algorithmic error enters.

Machine numbers

The perturbations that conditioning amplifies are supplied, unavoidably, by finite-precision arithmetic. A $t$-digit floating-point number in base $\beta$ is

normalized so the leading digit is nonzero. The set of all such numbers, plus zero, is the machine numbers $\mathbb{F}$. Rounding $\mathrm{fl}:\mathbb{R}\to \mathbb{F}$ sends a real to the nearest machine number; it is monotone and idempotent. Its error is bounded relative to the number, not absolutely.

The spacing between machine numbers grows with their magnitude: they are dense near zero and sparse for large values, so the relative gap stays fixed at ${\epsilon }_{\mathrm{mach}}$ across the whole range. Between consecutive powers of $\beta$ the numbers are evenly spaced; at each power the spacing jumps by a factor of $\beta$.

The IEEE 754 standard fixes two binary formats used by essentially all hardware. Every arithmetic operation and the square root return the correctly rounded exact result, which gives the standard model of machine arithmetic.

The standard also defines $\pm \infty$ (from $\pm 1/0$) and $\mathrm{NaN}$ (from $0/0$ or $\infty -\infty$) so exceptions propagate predictably rather than halting. One warning: machine addition and multiplication are not associative or distributive, so parenthesization is a numerical decision, not a cosmetic one.³

The unavoidable error

Rounding strikes before any computation. Merely reading data into the machine replaces $x$ with $\hat{x}=\mathrm{fl}(x)$, at componentwise relative error ${\epsilon }_{\mathrm{mach}}$. Even with subsequent arithmetic done exactly, the answer to the perturbed input already differs from the true answer by the amount conditioning dictates:

This is a floor. No algorithm, however clever, can beat it, because the error is baked in at data entry. The best one can ask of an algorithm is that it not add appreciably to this unavoidable error — and that demand defines stability. For $Ax=b$ the floor is $\kappa (A){\epsilon }_{\mathrm{mach}}$: in double precision, a matrix with ${\kappa }_2(A)\approx 10^{10}$ yields a solution good to only about six digits, no matter how the solve is organized. A stable algorithm such as pivoted $LU$ reaches this floor, leaving the conditioning of the matrix as the whole of the error and nothing more.