The Condition Number of a Matrix

For a single function, Conditioning of a Problem measured how input errors grow. For $A\mathbf{x} = \mathbf{b}$ the same role is played by one number built from Vector and Matrix Norms and the inverse: $$\kappa(A) = \lVert A\rVert\,\lVert A^{-1}\rVert,$$ with the norm named when it matters, as in $\kappa_\infty(A)$. Always $\kappa(A) \ge 1$.

Key idea

If $\mathbf{b}$ changes by $\delta\mathbf{b}$, the solution changes by $\delta\mathbf{x}$ with $$\frac{\lVert\delta\mathbf{x}\rVert}{\lVert\mathbf{x}\rVert} \le \kappa(A)\frac{\lVert\delta\mathbf{b}\rVert}{\lVert\mathbf{b}\rVert}.$$ The same bound links a residual $\mathbf{r} = \mathbf{b} - A\tilde{\mathbf{x}}$ to the error in $\tilde{\mathbf{x}}$: a tiny residual can hide a large error when $\kappa$ is large. Roughly, $\log_{10}\kappa$ digits are lost.

Why it works

From $A(\mathbf{x} + \delta\mathbf{x}) = \mathbf{b} + \delta\mathbf{b}$ we get $A\,\delta\mathbf{x} = \delta\mathbf{b}$, so $\lVert\delta\mathbf{x}\rVert \le \lVert A^{-1}\rVert\lVert\delta\mathbf{b}\rVert$. Also $\lVert\mathbf{b}\rVert = \lVert A\mathbf{x}\rVert \le \lVert A\rVert\lVert\mathbf{x}\rVert$, so $\frac{1}{\lVert\mathbf{x}\rVert} \le \frac{\lVert A\rVert}{\lVert\mathbf{b}\rVert}$. Multiply the two inequalities. For the residual, $\tilde{\mathbf{x}}$ solves $A\tilde{\mathbf{x}} = \mathbf{b} - \mathbf{r}$ exactly, so $\delta\mathbf{b} = -\mathbf{r}$.

Nearly parallel lines: a tiny change in b moves the crossing a long way, and a point far along the lines still almost satisfies both equations.

Worked example: Computing κ∞

Find $\kappa_\infty(A)$ for $A = \begin{bmatrix} 1 & 1 \\ 1 & 1.01 \end{bmatrix}$.

$\lVert A\rVert_\infty = 1 + 1.01 = 2.01$.
$\det A = 0.01$, so $A^{-1} = \frac{1}{0.01}\begin{bmatrix} 1.01 & -1 \\ -1 & 1 \end{bmatrix} = \begin{bmatrix} 101 & -100 \\ -100 & 100 \end{bmatrix}$ and $\lVert A^{-1}\rVert_\infty = 201$.
$\kappa_\infty(A) = 2.01 \times 201 \approx 404$: relative changes in $\mathbf{b}$ can be magnified about 400 times.

Answer: $\approx 404$

Worked example: Small residual, large error

With the same $A$ and $\mathbf{b} = (2, 2.01)$, the solution is $(1, 1)$. Test the candidate $\tilde{\mathbf{x}} = (2, 0)$.

$A\tilde{\mathbf{x}} = (2, 2)$, so the residual is $\mathbf{r} = (0, 0.01)$: relative size $\frac{0.01}{2.01} \approx 0.005$.
The error is $\mathbf{x} - \tilde{\mathbf{x}} = (-1, 1)$: relative size $1$, a 100% error.
The bound allows it: $\kappa_\infty \times 0.005 \approx 2 \ge 1$.

Answer: residual 0.005, error 100%

Worked example: Digits to expect

The $10 \times 10$ Hilbert matrix, $h_{ij} = \frac{1}{i + j - 1}$, has $\kappa_2 \approx 1.6 \times 10^{13}$. About how many correct digits should we expect when solving with it in double precision?

Data errors near $10^{-16}$ can grow by $\kappa$: relative error up to about $1.6 \times 10^{13} \times 10^{-16} \approx 2 \times 10^{-3}$.
So only about 3 correct digits, even with a stable method like elimination with partial pivoting.

Answer: about 3

Computing $A^{-1}$ just to find $\kappa$ would cost more than solving the system, so libraries estimate $\kappa_1(A)$ cheaply from the $LU$ factors and report it next to the answer. A few values to keep in mind: $\kappa = 1$ for the identity and, in the 2-norm, for every orthogonal matrix; $\kappa = \infty$ for a singular matrix; and a rough rule that a computed solution has about $16 - \log_{10}\kappa$ correct digits.

Common mistake

Trusting a solution because its residual $\mathbf{b} - A\tilde{\mathbf{x}}$ is tiny. That only says $\tilde{\mathbf{x}}$ nearly satisfies the equations; if $\kappa(A)$ is large, nearly satisfying them is compatible with a large error. Another trap: a small determinant does not mean ill-conditioned ($0.1I$ has determinant $10^{-n}$ but $\kappa = 1$). Check $\kappa$, not $\det$.

The Condition Number of a Matrix

Practice

Builds on

Leads to

Sources and further reading