Conditioning

Two lines cross at one point. Watch what a tiny nudge does to that point as the lines become almost parallel.

Two lines that almost agree

When two lines cross at a wide angle, moving one a little moves the crossing a little. When they are almost parallel, the same small move slides the crossing a long way along them. In the picture the nudge is always 0.01, but the crossing moves 100 times further at $\varepsilon=0.01$ than at $\varepsilon=1$.

Nothing is wrong with the arithmetic. The answer itself is sensitive: the data hardly decide where nearly parallel lines meet. A problem like that is ill-conditioned.

The condition number

The singular value decomposition turns the unit circle into an ellipse with semi-axes $\sigma_1$ and $\sigma_\text{min}$. The condition number is their ratio:

A round ellipse has $\kappa=1$; a long thin one has a large $\kappa$. Solving $\mathbf{A}\mathbf{x}=\mathbf{b}$ means running the ellipse backwards, and the short axis is where a small change in $\mathbf{b}$ becomes a big change in $\mathbf{x}$. In numbers, a relative change in $\mathbf{b}$ can grow by up to $\kappa$ in $\mathbf{x}$:

For the lines in the picture, $\kappa$ is 6.854 at $\varepsilon=1$, 42.08 at 0.1 and 402.0 at 0.01: about $4/\varepsilon$ once $\varepsilon$ is small.

Digits lost

A computer keeps about 16 significant digits. Solving a system with condition number $\kappa$ can lose about $\log_{10}\kappa$ of them, through rounding errors that the problem itself amplifies.

So a condition number of $10^8$ leaves about 8 trustworthy digits, and one of $10^{16}$ leaves none: the answer is noise.

Hard problems and unstable methods

Two different things can go wrong, and they need different fixes.

A hard problem has a large $\kappa$. No method can do better than the problem allows; the remedy is to change the problem, for example by measuring something that separates the nearly parallel lines.

A bad method loses accuracy on a problem that is fine. Take

with $\kappa=2.618$, perfectly healthy, and answer very nearly $(1,1)$. Eliminate in the written order, as Elimination does for clarity, with no row exchange. The pivot is $10^{-20}$, the multiplier $10^{20}$, and the second pivot $1-10^{20}$, which a computer rounds to $-10^{20}$: the 1 is lost. The computed answer comes out $(0,1)$. Exchange the two rows first, so the larger number is the pivot, and the answer comes out right. The lessons eliminate in order only for clarity; standard solvers always choose the largest pivot.

Squaring makes it worse. Forming $\mathbf{A}^\top\mathbf{A}$, as the normal equations of Least squares do, squares the condition number: $\kappa(\mathbf{A}^\top\mathbf{A})=\kappa(\mathbf{A})^2$. For the matrix of QR factorisation with $\varepsilon=10^{-8}$, $\kappa(\mathbf{A})=1.41\times10^8$ is manageable, but $\kappa(\mathbf{A}^\top\mathbf{A})=2\times10^{16}$ is past what 16 digits can carry. That is the failing run of that page, and why least squares is solved by QR or the SVD.

Worked example

1. A nearly singular system. $\mathbf{A}=\begin{bmatrix}1&1\\1&1.0001\end{bmatrix}$ and $\mathbf{b}=(2,\,2.0001)$ give $\mathbf{x}=(1,1)$. Change $\mathbf{b}$ to $(2,\,2.0002)$. Subtracting the first row from the second gives $0.0001\,y=0.0002$, so $y=2$, $x=0$: the answer jumps to $(0,2)$. The relative change in $\mathbf{b}$ is $10^{-4}/2.8285=3.5\times10^{-5}$; in $\mathbf{x}$ it is $\lVert(-1,1)\rVert/\lVert(1,1)\rVert=1$. The change grew about $2.8\times10^4$ times, within the bound $\kappa\approx4.0\times10^4$: the singular values are about 2 and $5\times10^{-5}$.

2. Healthy matrices. $\begin{bmatrix}2&-1\\1&1\end{bmatrix}$ has $\sigma=(\sqrt{13}\pm1)/2$, that is 2.303 and 1.303, so $\kappa=1.768$. The matrix $\begin{bmatrix}3&0\\4&5\end{bmatrix}$ has $\kappa=6.708/2.236=3$.

3. Eigenvalues can be sensitive too. $\begin{bmatrix}1&1\\\varepsilon&1\end{bmatrix}$ has eigenvalues $1\pm\sqrt\varepsilon$, as in Similar matrices and the Jordan form: a change of $10^{-16}$ moves them by $10^{-8}$.

Try these before you read the answers.

• $\kappa$ of a matrix with orthonormal columns? 1: it turns without stretching.
• $\kappa$ of $\mathrm{diag}(1,\ 0.001)$? 1000.
• At $\kappa=10^8$, how many digits are left of 16? About 8.
• If $\kappa(\mathbf{A})=10^4$, what is $\kappa(\mathbf{A}^\top\mathbf{A})$? $10^8$.

Where you’ll meet this

Polynomial fits. Fitting a high-degree polynomial gives columns $1,x,x^2,\dots$ that are nearly parallel, and a large condition number. Good fitting software reports it, or quietly works around it.

Adaptive filters. An adaptive filter that learns by small steps converges slowly when its input’s correlation matrix has a large condition number, as Adaptive filters: LMS shows.

Filters in hardware. A filter built as one high-order polynomial can become unstable from rounding alone; built from second-order sections it is far less likely to.

Reference card