Conditioning and Sensitivity

Definition Let $A$ be an invertible $n \times n$ real matrix, let $\mathbf{b}$ be a vector in $\mathbb{R}^n$, and let $\mathbf{x}$ be the solution of $A\mathbf{x} = \mathbf{b}$. A perturbation of the data replaces $\mathbf{b}$ by $\mathbf{b} + \delta\mathbf{b}$ while $A$ stays fixed. The new solution is $\mathbf{x} + \delta\mathbf{x}$, and subtracting the two systems gives

Sizes are measured with a chosen vector norm, on this page the Euclidean length $\lVert \cdot \rVert$. The absolute error, or absolute change, of the solution is $\lVert \delta\mathbf{x} \rVert$, and for $\mathbf{x} \ne \mathbf{0}$ its relative error is $\lVert \delta\mathbf{x} \rVert / \lVert \mathbf{x} \rVert$. The data have absolute error $\lVert \delta\mathbf{b} \rVert$ and, for $\mathbf{b} \ne \mathbf{0}$, relative error $\lVert \delta\mathbf{b} \rVert / \lVert \mathbf{b} \rVert$. Against a zero baseline a relative error is undefined, and only the absolute error is reported. Changes in the matrix $A$ itself need a separate analysis.

Definition Let $A$ be a real $m \times n$ matrix. Its induced Euclidean norm is the largest length of $A\mathbf{u}$ over unit vectors $\mathbf{u}$ in $\mathbb{R}^n$,

The maximum is always attained. It follows that $\lVert A\mathbf{v} \rVert \le \lVert A \rVert_2 \lVert \mathbf{v} \rVert$ for every $\mathbf{v}$ in $\mathbb{R}^n$, both sides being $0$ when $\mathbf{v} = \mathbf{0}$, and that $\lVert A \rVert_2$ is the smallest number with this property. For a product of compatible matrices, $\lVert AB \rVert_2 \le \lVert A \rVert_2 \lVert B \rVert_2$. Other vector norms induce other matrix norms in the same way, and the subscript records which one is meant.

Definition For an invertible $n \times n$ real matrix $A$, the Euclidean condition number is

The smallest stretch $\min_{\lVert \mathbf{u} \rVert = 1} \lVert A\mathbf{u} \rVert$ equals $1 / \lVert A^{-1} \rVert_2$, so $\kappa_2(A)$ is the ratio of the largest stretch of $A$ to its smallest. It satisfies $\kappa_2(A) \ge 1$, because $1 = \lVert I \rVert_2 \le \lVert A \rVert_2 \lVert A^{-1} \rVert_2$, and $\kappa_2(cA) = \kappa_2(A)$ for every scalar $c \ne 0$. For a singular matrix the definition gives no finite number.

The condition number bounds the effect of a perturbation of the data. Suppose $A$ is fixed, $\mathbf{b} \ne \mathbf{0}$, $A\mathbf{x} = \mathbf{b}$ and $A(\mathbf{x} + \delta\mathbf{x}) = \mathbf{b} + \delta\mathbf{b}$. Then

To prove it, combine $\lVert \delta\mathbf{x} \rVert = \lVert A^{-1}\delta\mathbf{b} \rVert \le \lVert A^{-1} \rVert_2 \lVert \delta\mathbf{b} \rVert$ with $\lVert \mathbf{b} \rVert = \lVert A\mathbf{x} \rVert \le \lVert A \rVert_2 \lVert \mathbf{x} \rVert$, where $\mathbf{x} \ne \mathbf{0}$ because $\mathbf{b} \ne \mathbf{0}$. When $\mathbf{b} = \mathbf{0}$, use the absolute bound $\lVert \delta\mathbf{x} \rVert \le \lVert A^{-1} \rVert_2 \lVert \delta\mathbf{b} \rVert$ instead. The bound is a worst case. For every $A$ some choice of $\mathbf{b}$ and $\delta\mathbf{b}$ attains it, but when $\kappa_2(A)$ is large a particular perturbation may be amplified far less.

Definition A square system $A\mathbf{x} = \mathbf{b}$ with invertible $A$ is ill-conditioned when $\kappa_2(A)$ is large, so that for some right-hand sides a small relative change in the data can cause a much larger relative change in the exact solution. It is well-conditioned when $\kappa_2(A)$ is small, so that no relative change in the data can grow by more than a modest factor. There is no fixed cutoff. If the data carry relative errors up to $\varepsilon$, the bound above only limits the relative error of the solution to $\kappa_2(A)\,\varepsilon$, so whether $\kappa_2(A)$ counts as large depends on how accurate the data are. Ill-conditioning is a property of the exact problem in its chosen units and norm, and the size of $\det A$ does not decide it.

Definition Conditioning is a property of a problem. It describes how much the exact answer changes when the exact data change, and the condition number measures it. Stability is a property of an algorithm. A stable algorithm keeps the errors it introduces through rounding under control, and one common standard, backward stability, asks that the computed answer be the exact answer for slightly changed data. A stable algorithm can still return an inaccurate answer to an ill-conditioned problem, because that small change in the data can be amplified, in the worst case by a factor of about the condition number. An unstable algorithm can fail even on a well-conditioned problem.

Three practices improve the computation without changing the problem. Pivoting exchanges rows so that elimination never divides by a needlessly small pivot, and partial pivoting takes the entry of largest absolute value available in the column. Guard digits are extra digits kept in intermediate steps, with rounding only at the end. In least squares with a design matrix $X$ of full column rank, the normal equations replace $X$ by $X^{\top}X$, and the ratio of the largest to the smallest stretch of $X^{\top}X$ is the square of that ratio for $X$, a fact the singular value decomposition explains in general later in the course. A QR method solves $R\mathbf{c} = Q^{\top}\mathbf{y}$ instead, and $\lVert R\mathbf{u} \rVert = \lVert QR\mathbf{u} \rVert = \lVert X\mathbf{u} \rVert$ for every $\mathbf{u}$ because $Q$ has orthonormal columns, so $R$ keeps the stretches of $X$. None of these practices can lower the condition number of the problem itself.

Definition Let $A$ be an invertible $n \times n$ matrix, let $\mathbf{x}$ be the exact solution of $A\mathbf{x} = \mathbf{b}$, and let $\hat{\mathbf{x}}$ be any proposed solution. Its residual $\mathbf{r} = \mathbf{b} - A\hat{\mathbf{x}}$ lives in the output space, and its error $\mathbf{e} = \mathbf{x} - \hat{\mathbf{x}}$ lives in the input space. They are related by $A\mathbf{e} = \mathbf{r}$, so

and when $\mathbf{b} \ne \mathbf{0}$,

A small residual guarantees a small error only when $\lVert A^{-1} \rVert_2$, or in relative terms $\kappa_2(A)$, is moderate.