---
title: Conditioning and Floating-Point Arithmetic
module: Numerical Linear Algebra
moduleNumber: 8
lessonNumber: 3
order: 803
summary: >
  A problem's condition number measures how much its answer moves when its data
  is perturbed, independent of any algorithm. Subtraction is ill-conditioned
  under cancellation, and for a linear system the amplifier is the matrix
  condition number κ(A). Floating-point arithmetic supplies the perturbation:
  every real number is rounded to within a relative machine precision, so even
  perfect computation inherits an error of order κ times the unit roundoff.
topics: [Numerical Linear Algebra]
sources:
  - book: Bornemann
    ref: "Part III — Error Analysis; §10 Error Measures, §11 Conditioning of a Problem"
  - book: Bornemann
    ref: "§12 Machine Numbers"
draft: false
---

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** $\lVert \hat{x} - x \rVert$ — the raw size of the deviation.
- **Relative error** $\lVert \hat{x} - x \rVert / \lVert x \rVert$ — the deviation
  as a fraction of the quantity, and so a count of correct significant digits.
- **Componentwise relative error** $\max_j \lvert \hat{x}_j - x_j \rvert /
  \lvert x_j \rvert$ — 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.[^bor-err] 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}$.

> **Definition (Condition number).** For a problem $f$ at data point $x$, the
> **condition number** is the worst-case ratio of output perturbation to input
> perturbation, in the limit of small perturbations:
>
> $$
> \kappa(f; x) = \lim_{\tilde{x}\to x}\ \sup\
> \frac{\lVert f(\tilde{x}) - f(x)\rVert}{\lVert \tilde{x} - x\rVert}.
> $$
>
> The problem is **well-conditioned** if $\kappa \lesssim 1$,
> **ill-conditioned** if $\kappa \gg 1$, and **ill-posed** if $\kappa = \infty$.

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.[^bor-cond] 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.

$$
% caption: Two lines known only to within their width. A transverse crossing
% (left) locates the intersection tightly; a glancing crossing (right) smears it
% across a wide region — the ill-conditioned case.
\begin{tikzpicture}[scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
% left: transverse
\draw[acc, line width=2.2pt, opacity=0.5] (-1.4,-1.0) -- (1.4,1.0);
\draw[acc, line width=2.2pt, opacity=0.5] (-1.4,1.0) -- (1.4,-1.0);
\fill[black] (0,0) circle (2pt);
\node[anchor=north] at (0,-1.2) {transverse: well-conditioned};
% right: glancing
\begin{scope}[xshift=5.4cm]
\draw[acc, line width=2.2pt, opacity=0.5] (-1.8,-0.35) -- (1.8,0.55);
\draw[acc, line width=2.2pt, opacity=0.5] (-1.8,0.15) -- (1.8,0.35);
\draw[black, dashed] (-0.9,-0.05) rectangle (1.5,0.6);
\node[anchor=north] at (0,-1.2) {glancing: ill-conditioned};
\end{scope}
\end{tikzpicture}
$$

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

$$
\kappa(f; x) = \frac{\lvert f'(x)\rvert \cdot \lvert x\rvert}{\lvert f(x)\rvert}.
$$

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

| $f$ | $\xi_1 + \xi_2$ | $\xi_1 - \xi_2$ | $\xi_1\xi_2$ | $\xi_1/\xi_2$ | $\sqrt{\xi_1}$ |
| --- | --- | --- | --- | --- | --- |
| $\kappa$ | $\dfrac{\lvert\xi_1\rvert+\lvert\xi_2\rvert}{\lvert\xi_1+\xi_2\rvert}$ | $\dfrac{\lvert\xi_1\rvert+\lvert\xi_2\rvert}{\lvert\xi_1-\xi_2\rvert}$ | $2$ | $2$ | $1/2$ |

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 $\lvert\xi_1-\xi_2\rvert
\ll \lvert\xi_1\rvert + \lvert\xi_2\rvert$, the denominator collapses and $\kappa$
explodes. This is **cancellation**.

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

$$
\xi_1 = 1.23456\,89\underline{?},
\qquad
\xi_2 = 1.23456\,78\underline{?},
\qquad
\xi_1 - \xi_2 = 1.1\underline{?}\times 10^{-6}.
$$

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:

> **Rule (Digit loss).** Solving a problem of condition number $\kappa$ loses about
> $\log_{10}\kappa$ significant decimal digits relative to the data.[^bor-cond]

## 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

$$
\frac{\lVert \tilde{x} - x\rVert}{\lVert x\rVert}
\le \lVert A^{-1}\rVert\,\lVert A\rVert\cdot
\frac{\lVert r\rVert}{\lVert b\rVert}.
$$

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

> **Definition (Matrix condition number).** For an induced matrix norm and
> invertible $A$,
>
> $$
> \kappa(A) = \lVert A^{-1}\rVert\,\lVert A\rVert \ge 1,
> $$
>
> with $\kappa(A) = \infty$ for singular $A$. A relative perturbation of size
> $\varepsilon$ in the data of $Ax = b$ produces a relative error in $x$ of at
> most $\kappa(A)\,\varepsilon$.[^bor-cond]

In the Euclidean norm this factor is the ratio of the largest to the smallest
[singular value](/linear-algebra/symmetric-quadratic-svd/singular-value-decomposition),
$\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.

$$
% caption: $A$ carries the unit circle to an ellipse with semi-axes $\sigma_1 \ge
% \sigma_2$; the condition number $\kappa_2(A) = \sigma_1/\sigma_2$ is its
% eccentricity, and a large ratio means the near-flat direction is highly
% sensitive.
\begin{tikzpicture}[scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
% unit circle
\draw[black] (0,0) circle (0.9);
\draw[->, black] (0,0) -- (0.9,0);
\draw[->, black] (0,0) -- (0,0.9);
\node[anchor=north] at (0,-1.1) {unit circle};
% arrow
\draw[->, black, thick] (1.7,0) -- (2.9,0);
\node[anchor=south] at (2.3,0.1) {$A$};
% ellipse
\begin{scope}[xshift=5.6cm]
\draw[acc, fill=acc!8] (0,0) ellipse (2.0 and 0.55);
\draw[->, acc, thick] (0,0) -- (2.0,0); \node[acc, anchor=north] at (1.6,-0.08) {sigma 1};
\draw[->, acc, thick] (0,0) -- (0,0.55); \node[acc, anchor=west] at (0.05,0.4) {sigma 2};
\node[anchor=north] at (0,-1.1) {image ellipse};
\end{scope}
\end{tikzpicture}
$$

> **Worked example.** The matrix
>
> $$
> A = \begin{bmatrix} 1 & 1 \\ 1 & 1.0001 \end{bmatrix}
> $$
>
> is nonsingular but nearly so, with $\det A = 10^{-4}$. Solve $Ax = b$ for two
> right-hand sides differing only in the last digit of one entry:
>
> $$
> b = \begin{bmatrix} 2 \\ 2 \end{bmatrix} \Rightarrow x = \begin{bmatrix} 2 \\ 0 \end{bmatrix},
> \qquad
> b' = \begin{bmatrix} 2 \\ 2.0001 \end{bmatrix} \Rightarrow x' = \begin{bmatrix} 1 \\ 1 \end{bmatrix}.
> $$
>
> A relative change $\lVert b' - b\rVert / \lVert b\rVert \approx 3.5\times 10^{-5}$
> in the data produces a relative change $\lVert x' - x\rVert / \lVert x\rVert
> \approx 0.7$ in the solution: an amplification near $2\times 10^{4}$. That factor
> is the condition number, $\kappa_\infty(A) = \lVert A\rVert_\infty \lVert
> A^{-1}\rVert_\infty = 2.0001\cdot(2.0001\times 10^{4}) \approx 4\times 10^{4}$.

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

> **Theorem (Kahan, 1966).** For an induced matrix norm,
>
> $$
> \kappa(A)^{-1} = \min\left\{\frac{\lVert E\rVert}{\lVert A\rVert} :
> A + E \text{ is singular}\right\}.
> $$

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

> **Worked example.** The Hilbert matrix $H_n$ with entries $(H_n)_{ij} = 1/(i +
> j - 1)$ is a standard ill-conditioned test case. For
>
> $$
> H_2 = \begin{bmatrix} 1 & \tfrac{1}{2} \\ \tfrac{1}{2} & \tfrac{1}{3} \end{bmatrix},
> $$
>
> the eigenvalues solve $\lambda^2 - \tfrac{4}{3}\lambda + \tfrac{1}{12} = 0$
> (trace $\tfrac{4}{3}$, determinant $\tfrac{1}{12}$), so $\lambda = (4 \pm
> \sqrt{13})/6$, giving $\lambda_{\max} \approx 1.268$ and $\lambda_{\min} \approx
> 0.0657$. Because $H_2$ is symmetric positive-definite, $\kappa_2(H_2) =
> \lambda_{\max}/\lambda_{\min} \approx 19.3$, a loss of about $\log_{10} 19.3
> \approx 1.3$ digits.

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

| $n$ | $\kappa_2(H_n)$ | digits lost $\approx \log_{10}\kappa$ | correct digits (double) |
| --- | --- | --- | --- |
| 2 | $1.9\times 10^1$ | $1.3$ | $15$ |
| 3 | $5.2\times 10^2$ | $2.7$ | $13$ |
| 4 | $1.6\times 10^4$ | $4.2$ | $12$ |
| 5 | $4.8\times 10^5$ | $5.7$ | $10$ |
| 6 | $1.5\times 10^7$ | $7.2$ | $9$ |

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

$$
% caption: Digits lost to conditioning for the Hilbert matrix $H_n$, one bar per
% dimension: the loss is $\log_{10}\kappa_2(H_n)$ and climbs by roughly $1.5$ per
% added row, so double precision runs out near $n = 11$.
\begin{tikzpicture}[scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
% axes
\draw[->, black] (0,0) -- (0,5.4) node[anchor=south] {digits lost};
\draw[->, black] (0,0) -- (7.2,0) node[anchor=west] {n};
% y ticks in digit units, plotted at 0.65 scale
\foreach \d in {2,4,6} {\draw[black] (-0.08,{\d*0.65})--(0.08,{\d*0.65}); \node[anchor=east] at (-0.12,{\d*0.65}) {\d};}
% bars: (n, digits lost) scaled y*0.65
\foreach \n/\x/\h in {2/1/1.3, 3/2/2.7, 4/3/4.2, 5/4/5.7, 6/5/7.2} {
  \fill[acc!16] (\x-0.28,0) rectangle (\x+0.28,{\h*0.65});
  \draw[acc] (\x-0.28,0) rectangle (\x+0.28,{\h*0.65});
  \node[anchor=north] at (\x,-0.05) {\n};
}
\node[acc, anchor=south] at (5,{7.2*0.65+0.05}) {7.2};
\end{tikzpicture}
$$

## Machine numbers

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

$$
\xi = \pm\, d_1.d_2\cdots d_t \times \beta^{e},
\qquad d_1 \ne 0,\quad d_k \in \{0, \dots, \beta - 1\},\quad e \in \mathbb{Z},
$$

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.

> **Lemma (Machine precision).** The relative rounding error is bounded by the
> **machine precision** (unit roundoff) $\varepsilon_{\mathrm{mach}} = \tfrac{1}{2}
> \beta^{1-t}$:
>
> $$
> \frac{\lvert \mathrm{fl}(\xi) - \xi\rvert}{\lvert\xi\rvert}
> \le \varepsilon_{\mathrm{mach}},
> \qquad\text{equivalently}\qquad
> \mathrm{fl}(\xi) = \xi(1 + \epsilon),\ \ \lvert\epsilon\rvert \le
> \varepsilon_{\mathrm{mach}}.
> $$

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 $\varepsilon_{\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$.

$$
% caption: Machine numbers have a fixed relative spacing: between $1$ and $2$ the
% gap is $2\varepsilon_{\mathrm{mach}}$, and it doubles past every power of two, so
% the absolute gap grows while the relative gap stays constant.
\begin{tikzpicture}[scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
\draw[black] (0,0) -- (9,0);
% ticks between 0.5 and 1: fine
\foreach \x in {0,0.375,0.75,1.125,1.5} \draw[black] (\x,-0.1)--(\x,0.1);
% between 1 and 2: coarser
\foreach \x in {1.5,2.25,3.0,3.75,4.5} \draw[acc] (\x,-0.12)--(\x,0.12);
% between 2 and 4: coarsest
\foreach \x in {4.5,6.0,7.5,9.0} \draw[black] (\x,-0.14)--(\x,0.14);
\node[anchor=north] at (0,-0.25) {$1/2$};
\node[acc, anchor=north] at (1.5,-0.25) {$1$};
\node[anchor=north] at (4.5,-0.25) {$2$};
\node[anchor=north] at (9,-0.25) {$4$};
\node[acc, anchor=south] at (3.0,0.2) {gap = 2 eps};
\end{tikzpicture}
$$

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.

> **Standard model.** For $\xi, \eta \in \mathbb{F}$ and any operation $\ast \in
> \{+, -, \cdot, /, \sqrt{\ }\}$, the machine realization $\hat{\ast}$ satisfies
>
> $$
> \xi\ \hat{\ast}\ \eta = (\xi \ast \eta)(1 + \epsilon),
> \qquad \lvert\epsilon\rvert \le \varepsilon_{\mathrm{mach}},
> $$
>
> i.e. the computed result is the exact result perturbed by one relative rounding.

| | Single precision | Double precision |
| --- | --- | --- |
| Storage | 32 bits | 64 bits |
| Mantissa length $t$ | $24$ bits | $53$ bits |
| Precision $\varepsilon_{\mathrm{mach}}$ | $2^{-24} \approx 6\times 10^{-8}$ | $2^{-53} \approx 1.1\times 10^{-16}$ |
| Decimal digits | $\approx 8$ | $\approx 16$ |
| Overflow threshold | $\approx 3.4\times 10^{38}$ | $\approx 1.8\times 10^{308}$ |

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.[^bor-mach]

## 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
$\varepsilon_{\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:

$$
\frac{\lVert f(\hat{x}) - f(x)\rVert}{\lVert f(x)\rVert}
= O\!\big(\kappa(f; x)\,\varepsilon_{\mathrm{mach}}\big).
$$

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)\,\varepsilon_{\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](/linear-algebra/numerical-linear-algebra/stability-and-error-analysis)
algorithm such as pivoted $LU$ reaches this floor, leaving the conditioning of the
matrix as the whole of the error and nothing more.

[^bor-err]: **Bornemann**, _Numerical Linear Algebra_, §10 — Error Measures: absolute, relative, and componentwise relative error, and the modeling choice between them.
[^bor-cond]: **Bornemann**, §11 — Conditioning of a Problem: the condition-number definition, the linearized formula $\kappa = \lvert f'(x)\rvert\lvert x\rvert / \lvert f(x)\rvert$, the elementary-operation table with cancellation, the linear-system condition number $\kappa(A) = \lVert A^{-1}\rVert\lVert A\rVert$, and Kahan's distance-to-singularity theorem.
[^bor-mach]: **Bornemann**, §12 — Machine Numbers: floating-point representation, $\varepsilon_{\mathrm{mach}} = \tfrac{1}{2}\beta^{1-t}$, IEEE 754 single/double formats, the standard model $\xi\,\hat{\ast}\,\eta = (\xi\ast\eta)(1+\epsilon)$, and input-rounding error.