Matrix Norms and Condition Numbers

Induced matrix norms

A vector norm measures vector size. The corresponding induced matrix norm measures the largest factor by which a matrix can stretch a vector:

\|A\|=\sup_{x\ne0}\frac{\|Ax\|}{\|x\|}=\max_{\|x\|=1}\|Ax\|

This definition immediately gives two essential bounds for dimensionally compatible matrices and vectors:

\|Ax\|\le\|A\|\|x\|

The $chosen vector norm$ determines the induced matrix norm.

Vector norm	Induced matrix norm
$\displaystyle\\|x\\|_1=\sum_{i=1}^{n}\lvert x_i\rvert$	$\displaystyle\\|A\\|_1=\max_j\sum_i\lvert a_{ij}\rvert$ , the largest absolute column sum
$\displaystyle\\|x\\|_\infty=\max_i\lvert x_i\rvert$	$\displaystyle\\|A\\|_\infty=\max_i\sum_j\lvert a_{ij}\rvert$ , the largest absolute row sum
$\displaystyle\\|x\\|_2=\sqrt{x^{\mathsf T}x}$	$\displaystyle\\|A\\|_2=\sigma_{\max}(A)$ , the largest singular value

Spectral radius and spectral norm

For a square matrix, the spectral radius is

\rho(A)=\max_{\lambda\in\operatorname{spec}(A)}|\lambda|

Every induced matrix norm bounds the spectral radius:

\rho(A)\le\|A\|

The spectral norm satisfies

\|A\|_2=\sigma_{\max}(A)=\sqrt{\lambda_{\max}(A^{\mathsf T}A)}

If $A$ is real symmetric, its singular values are the absolute values of its eigenvalues, so

\|A\|_2=\max_i|\lambda_i(A)|=\rho(A)

For a general nonnormal matrix, the spectral radius and spectral norm $need not be equal$ .

Condition number of a linear solve

For an invertible square matrix and an induced norm, define

\kappa(A)=\|A\|\|A^{-1}\|

The condition number is at least one. A singular matrix has infinite condition number. In the Euclidean norm,

\kappa_2(A)=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}

For an invertible symmetric matrix, this becomes

\kappa_2(A)=\frac{\max_i|\lambda_i(A)|}{\min_i|\lambda_i(A)|}

Use the eigenvalue with the $smallest magnitude$ in the denominator. Its sign does not decide the choice.

Size of $\kappa(A)$	Interpretation
Near $1$	In the $worst case$ , the relative change in the solution is about as large as the relative change in the input.
Large	Some input directions can produce much larger relative changes in the solution.
Infinite	The matrix is singular, so the inverse problem is not uniquely solvable.

Sensitivity of a Two Dimensional Diagonal System

Consider

A=\begin{pmatrix}1&0\\0&\varepsilon\end{pmatrix},\qquad 0<\varepsilon\ll1

Its singular values are $1$ and $\varepsilon$ , hence

\kappa_2(A)=\frac{1}{\varepsilon}

For $b=(b_1,b_2)^{\mathsf T}$ , the solution is

x=A^{-1}b=\begin{pmatrix}b_1\\b_2/\varepsilon\end{pmatrix}

A small change in $b_2$ is $amplified by$ $1/\varepsilon$ in the second solution component. The matrix is close to singular because it multiplies vectors along the second coordinate direction by $\varepsilon$ , which is close to zero.

Set $\varepsilon=1/1000$ and compare two right-hand sides. Only the second observation changes.

$b$	$x=A^{-1}b$
$(1,1/1000)^T$	$(1,1)^T$
$(1,2/1000)^T$	$(1,2)^T$

\Delta b_2=\frac1{1000},\qquad\Delta x_2=\frac{1/1000}{1/1000}=1

Perturbation bound

Assume $A$ is invertible and $b\ne0$ , so the relative errors below have $nonzero denominators$ . Compare the original system $Ax=b$ with a system whose matrix and vector change slightly:

(A+\delta A)(x+\delta x)=b+\delta b

Use the same induced norm for every quantity. The following bound requires

\kappa(A)\frac{\|\delta A\|}{\|A\|}<1

Under this condition, the relative solution change is bounded by

\begin{aligned} \frac{\|\delta x\|}{\|x\|} &\le\frac{\kappa(A)}{1-\kappa(A)\|\delta A\|/\|A\|} \\ &\quad{}\cdot\left(\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right) \end{aligned}

This bound describes the worst case. Most perturbations may produce less amplification.

Problem Conditioning and Algorithmic Stability

Problem conditioning and algorithmic stability describe different properties:

$conditioning$ describes the $sensitivity of the mathematical problem to input changes$
$stability$ describes how much additional error a numerical algorithm introduces

A stable algorithm cannot remove sensitivity already present in an ill-conditioned problem. Conversely, a well-conditioned problem can still be solved poorly by an unstable implementation. A small residual $\|b-A\hat{x}\|$ alone also does not guarantee a small forward error $\|x-\hat{x}\|$ when $\kappa(A)$ is large.

In numerical work, estimate the reciprocal condition number from a trusted factorization. This gives $\kappa(A)$ without explicitly forming $A^{-1}$ .