Matrix Norms, Condition Numbers and Numerical Stability

Let $X$ and $Y$ be normed spaces over $\mathbb{R}$ (A norm on a real vector space, the induced metric, and the dictionary with the metric axioms), let $f:X\to Y$ be a map, and let $x$ be an element of the domain of $f$. Let $\widehat{y}\in Y$ be an approximate value of $f$ at $x$: an element of the target space meant to stand for $f(x)$.

The absolute forward error of $\widehat{y}$ at $x$ is the norm

$\parallel \widehat{y}-f(x)\parallel ,$

and, provided $f(x)\mathrm{\ne }0$, the relative forward error of $\widehat{y}$ at $x$ is

$\frac{\parallel \widehat{y}-f(x)\parallel }{\parallel f(x)\parallel }\mathrm{.}$

The exact value $f(x)$ is called the exact answer, and $\widehat{y}$ the computed (or approximate) answer. Forward error is the error in the answer itself; it is measured in the target space $Y$ and knows nothing about how $\widehat{y}$ was produced.

• Why the relative version needs $f(x)\mathrm{\ne }0$. Relative error divides by $\parallel f(x)\parallel$; when $f(x)=0$ the division is not defined, and the only sensible quantity is the absolute error. Every statement on this page that writes a relative forward error carries the hypothesis $f(x)\mathrm{\ne }0$.

• Approximate values are plain elements of $Y$. No machine arithmetic is assumed here: $\widehat{y}$ can come from hand calculation, a rounded formula, or an algorithm. The floating-point model is introduced separately in The standard relative floating-point model and unit roundoff, and nothing in this definition depends on it.

Let $X$ and $Y$ be normed spaces over $\mathbb{R}$ (A norm on a real vector space, the induced metric, and the dictionary with the metric axioms) and let $f:X\to Y$ be a map. For $x\in X$ and $\delta >0$ write

$P_{f,x}(\delta ):=\{h\in X:0<\parallel h\parallel <\delta ,x+h\in \mathrm{dom}f\}\mathrm{.}$

Define the worst amplification over perturbations of size at most $\delta$ by

$S_{f,x}(\delta ):=\{\begin{array}{ll}0,& P_{f,x}(\delta )=\mathrm{\varnothing },\\ \sup \{{\displaystyle \frac{\parallel f(x+h)-f(x)\parallel }{\parallel h\parallel }}:h\in P_{f,x}(\delta )\},& P_{f,x}(\delta )\mathrm{\ne }\mathrm{\varnothing }\mathrm{.}\end{array}$

so $S_{f,x}(\delta )\in [0,+\mathrm{\infty }]$ in every case.

For each fixed $x$ the map $\delta \mapsto S_{f,x}(\delta )$ is nondecreasing as $\delta$ increases, so the infimum over all $\delta >0$ exists in $[0,+\mathrm{\infty }]$. The absolute (local) condition number of $f$ at $x$ is

${\kappa }_{\mathrm{a}\mathrm{b}\mathrm{s}}(f,x):={\inf }_{\delta >0}{S}_{f,x}(\delta )={\lim }_{\delta \to 0^{+}}{S}_{f,x}(\delta )\in [0,+\mathrm{\infty }]\mathrm{.}$

If $x\mathrm{\ne }0$ and $f(x)\mathrm{\ne }0$, the relative (local) condition number of $f$ at $x$ is

${\kappa }_{\mathrm{r}\mathrm{e}\mathrm{l}}(f,x):={\kappa }_{\mathrm{a}\mathrm{b}\mathrm{s}}(f,x)\cdot \frac{\parallel x\parallel }{\parallel f(x)\parallel }\in [0,+\mathrm{\infty }]\mathrm{.}$

For the computed value $\widehat{y}=f(x+h)$ of Absolute and relative forward error for an approximate value of a problem map, the quantity $\parallel h\parallel$ is the absolute backward error. When $x\mathrm{\ne }0$, the quotient $\parallel h\parallel \mathrm{/}\parallel x\parallel$ is the relative backward error: the amount by which the data must be moved, relative to its size, for the computed answer to be exactly correct. At $x=0$ only the absolute backward error is defined. The condition number converts backward error into a bound on forward error; that conversion is Local conditioning times backward error controls forward error to first order.

• The infimum form is the limit of the supremum form. Because $S_{f,x}$ is monotone in $\delta$, the infimum over $\delta >0$ equals the one-sided limit ${\lim }_{\delta \to 0^{+}}{S}_{f,x}(\delta )$, which is the familiar definition of a condition number as the worst relative amplification of infinitesimal perturbations. The infimum formulation is used below because it is an honest value of the library's ordered arithmetic with no separate limit apparatus.

• The value is allowed to be $+\mathrm{\infty }$. An ill-posed (discontinuous) map has infinite condition number at a point of discontinuity; ${\kappa }_{\mathrm{a}\mathrm{b}\mathrm{s}}=+\mathrm{\infty }$ is a legitimate value and no arithmetic is performed with it. The first-order conversion theorem only yields a finite bound when ${\kappa }_{\mathrm{a}\mathrm{b}\mathrm{s}}<+\mathrm{\infty }$.

• Conditioning belongs to the problem, not to the algorithm. The condition number depends only on $f$, the point $x$, and the two norms; no algorithm enters its definition. The separate notion of stability belongs to an algorithm under an arithmetic model and is defined in Forward and backward stability for a problem family under an arithmetic model.

Let $m,n\in \mathbb{N}$, let $p\in \mathbb{Q}$ with $p\ge 1$, and let $A=(a_{ij})\in M_{m\times n}(\mathbb{R})$ be a real matrix (Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes), regarded as the linear map $x\mapsto Ax$ from ${\mathbb{R}}^n$ to ${\mathbb{R}}^m$ with the published $p$-norms (The $p$-norms $\parallel x{\parallel }_p$ for rational $p\ge 1$, and $\parallel x{\parallel }_{\mathrm{\infty }}$). The matrix $p$-norm induced by $\parallel \cdot {\parallel }_p$ is

$\parallel A{\parallel }_p:=\sup \{\parallel Ax{\parallel }_p:x\in {\mathbb{R}}^n,\parallel x{\parallel }_p\le 1\}\mathrm{.}$

When $n\ge 1$, the following three displayed quantities are the same number:

$\parallel A{\parallel }_p={\sup }_{\parallel x{\parallel }_p\le 1}\parallel Ax{\parallel }_p={\sup }_{\parallel x{\parallel }_p=1}\parallel Ax{\parallel }_p={\sup }_{x\mathrm{\ne }0}\frac{\parallel Ax{\parallel }_p}{\parallel x{\parallel }_p},$

the equalities following from positive homogeneity of $\parallel \cdot {\parallel }_p$ (Each $\parallel \cdot {\parallel }_p$ is a norm on ${\mathbb{R}}^n$, and the induced metrics are exactly $d_1$, $d_2$ and $d_{\mathrm{\infty }}$ of the published metric-spaces page, axiom (N2)) and the equality $\parallel 0{\parallel }_p=0$.

The value is a finite nonnegative real. For $n\ge 1$ the norms $\parallel \cdot {\parallel }_p$ and $\parallel \cdot {\parallel }_2$ are equivalent by For $n\ge 1$ all norms on ${\mathbb{R}}^n$ are equivalent, so there is $C>0$ with $\parallel x{\parallel }_{\mathrm{\infty }}\le C\parallel x{\parallel }_p$ for every $x$. For every $i<m$, $\mathrm{\mid }(Ax{)}_i\mathrm{\mid }\le {\sum }_{j<n}\mathrm{\mid }{a}_{ij}\mathrm{\mid }\mathrm{\mid }{x}_j\mathrm{\mid }\le ({\sum }_{j<n}\mathrm{\mid }{a}_{ij}\mathrm{\mid })\parallel x{\parallel }_{\mathrm{\infty }}\le C({\sum }_{j<n}\mathrm{\mid }{a}_{ij}\mathrm{\mid })\parallel x{\parallel }_p$, so $\parallel Ax{\parallel }_p\le ({\sum }_{i<m}({\sum }_{j<n}\mathrm{\mid }{a}_{ij}\mathrm{\mid }{)}^p{)}^{1\mathrm{/}p}C\parallel x{\parallel }_p$; hence the supremum over the unit ball is at most the finite constant $({\sum }_{i<m}({\sum }_{j<n}\mathrm{\mid }{a}_{ij}\mathrm{\mid }{)}^p{)}^{1\mathrm{/}p}C$.

The induced infinity norm is a separate named case. When $m,n\ge 1$, define

$\parallel A{\parallel }_{\mathrm{\infty }}:=\sup \{\parallel Ax{\parallel }_{\mathrm{\infty }}:x\in {\mathbb{R}}^n,\parallel x{\parallel }_{\mathrm{\infty }}\le 1\}\mathrm{.}$

As in the rational-$p$ case, positive homogeneity gives

$\parallel A{\parallel }_{\mathrm{\infty }}={\sup }_{\parallel x{\parallel }_{\mathrm{\infty }}\le 1}\parallel Ax{\parallel }_{\mathrm{\infty }}={\sup }_{\parallel x{\parallel }_{\mathrm{\infty }}=1}\parallel Ax{\parallel }_{\mathrm{\infty }}={\sup }_{x\mathrm{\ne }0}\frac{\parallel Ax{\parallel }_{\mathrm{\infty }}}{\parallel x{\parallel }_{\mathrm{\infty }}}\mathrm{.}$

The supremum is finite because for every $i<m$ one has $\mathrm{\mid }(Ax{)}_i\mathrm{\mid }\le {\sum }_{j<n}\mathrm{\mid }{a}_{ij}\mathrm{\mid }\mathrm{\mid }{x}_j\mathrm{\mid }\le ({\sum }_{j<n}\mathrm{\mid }{a}_{ij}\mathrm{\mid })\parallel x{\parallel }_{\mathrm{\infty }}$, so

$\parallel Ax{\parallel }_{\mathrm{\infty }}\le {\max }_{i<m}{\sum }_{j<n}\mathrm{\mid }{a}_{ij}\mathrm{\mid }\parallel x{\parallel }_{\mathrm{\infty }}\mathrm{.}$

At $n=0$ the convention is explicit. The only element of ${\mathbb{R}}^0$ is the zero vector, the only matrix $A\in M_{m\times 0}(\mathbb{R})$ is the empty matrix, and the unit-ball definition gives $\parallel A{\parallel }_p=0$. The unit sphere and the set of nonzero vectors are empty, so the two ratio formulas above are not asserted in this case.

The induced quantity is a norm on the matrix space $M_{m\times n}(\mathbb{R})$: for each rational $p\ge 1$, and likewise for the separately named $\mathrm{\infty }$-case when $m,n\ge 1$, separation, absolute homogeneity and the triangle inequality follow from the same three axioms of the underlying vector norm (Each $\parallel \cdot {\parallel }_p$ is a norm on ${\mathbb{R}}^n$, and the induced metrics are exactly $d_1$, $d_2$ and $d_{\mathrm{\infty }}$ of the published metric-spaces page) through the defining supremum. The compatibility with matrix-vector multiplication, the submultiplicativity and the value on identity matrices are Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1; the explicit value at $p=1$ and the separate $\mathrm{\infty }$-formula are The induced 1-norm is the maximum column sum and the induced infinity-norm is the maximum row sum.

• At $p=2$ this is the published operator norm. The vector $2$-norm is the Euclidean norm (Each $\parallel \cdot {\parallel }_p$ is a norm on ${\mathbb{R}}^n$, and the induced metrics are exactly $d_1$, $d_2$ and $d_{\mathrm{\infty }}$ of the published metric-spaces page), so the induced $2$-norm of a real matrix is the operator norm of the published spectral/SVD page; The operator norm is 0 on the zero domain and otherwise equals the largest singular value, attained at a right-singular vector identifies it with the largest singular value. No second operator norm is introduced here.

• Only rational $p\ge 1$ are used. The published The $p$-norms $\parallel x{\parallel }_p$ for rational $p\ge 1$, and $\parallel x{\parallel }_{\mathrm{\infty }}$ exist for rational exponents only, and this definition inherits that restriction verbatim; no statement on this page ranges $p$ over a real interval.

Let $p\in \mathbb{Q}$ with $p\ge 1$ and let $m,n,q\in \mathbb{N}$, with the induced $p$-norms of The matrix norm induced by a published vector p-norm.

1. Compatibility. For every $A\in M_{m\times n}(\mathbb{R})$ and every $x\in {\mathbb{R}}^n$, $\parallel Ax{\parallel }_p\le \parallel A{\parallel }_p\parallel x{\parallel }_p\mathrm{.}$
2. Submultiplicativity. For every $A\in M_{m\times n}(\mathbb{R})$ and $B\in M_{n\times q}(\mathbb{R})$, $\parallel AB{\parallel }_p\le \parallel A{\parallel }_p\parallel B{\parallel }_p\mathrm{.}$
3. Normalisation. For every $n\ge 1$, $\parallel I_n{\parallel }_p=1,$ where $I_n$ is the identity matrix of Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes; at $n=0$ the unique empty matrix $I_0\in M_0(\mathbb{R})$ has $\parallel I_0{\parallel }_p=0$, the convention of The matrix norm induced by a published vector p-norm.

Let $m,n\in \mathbb{N}$ with $m\ge 1$ and $n\ge 1$, and let $A=(a_{ij})\in M_{m\times n}(\mathbb{R})$, with the induced $1$-norm and the separately defined induced $\mathrm{\infty }$-norm of The matrix norm induced by a published vector p-norm.

1. Maximum column sum. $\parallel A{\parallel }_1={\max }_{j<n}{\sum }_{i<m}\mathrm{\mid }{a}_{ij}\mathrm{\mid }$.
2. Maximum row sum. $\parallel A{\parallel }_{\mathrm{\infty }}={\max }_{i<m}{\sum }_{j<n}\mathrm{\mid }{a}_{ij}\mathrm{\mid }$.

Let $\mathbb{F}$ be $\mathbb{R}$ or $\mathbb{C}$, let $m,n\in \mathbb{N}$ and let $A=(a_{ij})\in M_{m\times n}(\mathbb{F})$. The Frobenius norm of $A$ is

$\parallel A{\parallel }_F:=({\sum }_{i<m}{\sum }_{j<n}\mathrm{\mid }{a}_{ij}{\mathrm{\mid }}^2{)}^{1\mathrm{/}2},$

where $\mathrm{\mid }\cdot \mathrm{\mid }$ is the absolute value on $\mathbb{R}$ (Absolute value in an ordered field) for $\mathbb{F}=\mathbb{R}$ and the modulus on $\mathbb{C}$ (Real and imaginary parts, complex conjugation, and modulus) for $\mathbb{F}=\mathbb{C}$, and the outer power is the nonnegative real square root.

The displayed quantity is a norm. Regard $A$ as the element of the coordinate space ${\mathbb{F}}^{mn}$ whose $j+in$-th entry is $a_{ij}$. The standard coordinate inner product of The standard formulas $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$ and ${\sum }_{k<n}{x}_k\overline{y_k}$ on ${\mathbb{C}}^n$ are inner products satisfies $⟨A,A⟩={\sum }_{i,j}{a}_{ij}\overline{a_{ij}}$, which equals ${\sum }_{i,j}\mathrm{\mid }{a}_{ij}{\mathrm{\mid }}^2$ because $z\bar{z}=\mathrm{\mid }z{\mathrm{\mid }}^2$ (Conjugation is an involutive real-field automorphism, $z\bar{z}=\mathrm{\mid }z{\mathrm{\mid }}^2$, and modulus is definite, multiplicative, and subadditive). Thus $\parallel A{\parallel }_F$ is exactly the inner-product norm of The norm $\parallel v\parallel =\sqrt{⟨v,v⟩}$ induced by a real or complex inner product evaluated at $A$, and the three norm axioms hold for $\parallel \cdot {\parallel }_F$ because they hold for every inner-product norm. For real matrices the same sum is ${\sum }_{i,j}{a}_{ij}^2$, since $\mathrm{\mid }x{\mathrm{\mid }}^2=x^2$ for real $x$ by the two cases of Absolute value in an ordered field.

The Frobenius norm is the Euclidean norm of the full entry list, not the largest factor by which the matrix stretches a single vector. It can coincide with an induced $2$-norm in one-row or one-column cases, but in general it is a different matrix norm from the induced operator norms used on this page. Its relation to the spectral norm, its unitary invariance and its singular-value formula are Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison.

• The name records the entry-sum definition. Different sources write $\parallel A{\parallel }_F$, $\parallel A{\parallel }_{\mathrm{F}}$, or $\parallel A{\parallel }_{2,\mathrm{H}\mathrm{S}}$; this library uses $\parallel \cdot {\parallel }_F$ exclusively and does not fold it into the induced $p$-norm notation.

• Zero-sized shapes are included. At $m=0$ or $n=0$ the double sum is the empty sum $0$, so the unique empty matrix has Frobenius norm $0$; this is the value of the inner-product norm of the zero space.

Let $\mathbb{F}$ be $\mathbb{R}$ or $\mathbb{C}$, let $A\in M_{m\times n}(\mathbb{F})$, and let ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0$ be the positive singular values of $A$, where $r=\mathrm{rank}A$; write ${\sigma }_1=0$ when $r=0$.

1. Spectral formula. $\parallel A{\parallel }_2={\sigma }_1$, where $\parallel \cdot {\parallel }_2$ is the operator norm of The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||.
2. Frobenius formula. $\parallel A{\parallel }_F=({\sigma }_1^2+\cdots +{\sigma }_r^2{)}^{1\mathrm{/}2}$.
3. Unitary invariance. For every unitary $U\in M_m(\mathbb{F})$ and $V\in M_n(\mathbb{F})$ (over $\mathbb{F}=\mathbb{R}$: orthogonal matrices), $\parallel UAV{\parallel }_2=\parallel A{\parallel }_2,\parallel UAV{\parallel }_F=\parallel A{\parallel }_F\mathrm{.}$
4. Sharp rank comparison. $\parallel A{\parallel }_2\le \parallel A{\parallel }_F\le \sqrt{r}\parallel A{\parallel }_2\mathrm{.}$ The lower inequality is an equality exactly when $r\le 1$; the upper inequality is an equality exactly when ${\sigma }_1=\cdots ={\sigma }_r$, that is, when all nonzero singular values coincide. In particular $\parallel A{\parallel }_F\le \sqrt{\min (m,n)}\parallel A{\parallel }_2$.

Let $n\in \mathbb{N}$ with $n\ge 1$, let either $p\in \mathbb{Q}$ with $p\ge 1$ or $p=\mathrm{\infty }$, and let $A\in {\mathrm{GL}}_n(\mathbb{R})$ be an invertible real matrix (Invertible matrices and the general linear group ${\mathrm{GL}}_n(F)$), so that the linear system $Ax=b$ has the unique solution $x=A^{-1}b$ for every right-hand side $b\in {\mathbb{R}}^n$. The condition number of the linear system (equivalently, of the matrix $A$) with respect to the induced $p$-norm of The matrix norm induced by a published vector p-norm, using its separately defined infinity case when $p=\mathrm{\infty }$, is

${\kappa }_p(A):=\parallel A{\parallel }_p\parallel A^{-1}{\parallel }_p\in [1,+\mathrm{\infty })\mathrm{.}$

The value is at least one and is never infinite. The inverse $A^{-1}$ is the unique two-sided inverse of $A$ (Invertible matrices and the general linear group ${\mathrm{GL}}_n(F)$), so $A{A}^{-1}=I_n$ and $A^{-1}A=I_n$. For rational finite $p$, submultiplicativity and normalisation are Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1. For $p=\mathrm{\infty }$, the same properties follow directly from the defining supremum: $\parallel Ax{\parallel }_{\mathrm{\infty }}\le \parallel A{\parallel }_{\mathrm{\infty }}\parallel x{\parallel }_{\mathrm{\infty }}$ and applying this estimate twice gives submultiplicativity, while $I_{n}x=x$ gives $\parallel I_n{\parallel }_{\mathrm{\infty }}=1$. Hence in either case

$1=\parallel I_n{\parallel }_p=\parallel A{A}^{-1}{\parallel }_p\le \parallel A{\parallel }_p\parallel A^{-1}{\parallel }_p={\kappa }_p(A)\mathrm{.}$

Equivalently, ${\kappa }_p(A)$ is the product of the largest factor by which $A$ stretches a nonzero vector and the largest factor by which $A^{-1}$ stretches one. Applying the same estimate to $A^{-1}$ in place of $A$ gives ${\kappa }_p(A^{-1})={\kappa }_p(A)$.

• The matrix must be square and invertible. For a rectangular or singular matrix $A$ there is no $A^{-1}$ in the sense of Invertible matrices and the general linear group ${\mathrm{GL}}_n(F)$ and the displayed product is not defined; the rectangular least-squares case uses the singular-value ratio ${\sigma }_{\max }\mathrm{/}{\sigma }_{\min }$ instead, as in For full-column-rank A, the normal equations square the spectral condition number.

• The subscript names the norm. ${\kappa }_1$, ${\kappa }_2$ and ${\kappa }_{\mathrm{\infty }}$ are different numbers attached to the same matrix; the dependence on the norm is genuine: for $A=\left(\begin{array}{ccc}1& 2& 0\\ 0& 3& 1\\ 0& 0& 4\end{array}\right)$ one has ${\kappa }_1(A)=5$ and ${\kappa }_{\mathrm{\infty }}(A)=22\mathrm{/}3$, while the diagonal rescaling $D=\mathrm{diag}(10,1,1)$ changes ${\kappa }_1$ from $5$ to $23$.

• A system is well or ill conditioned, an algorithm is stable or unstable. The condition number is a property of the problem $Ax=b$ and its norms; it is computed without any algorithm. The separate notion of stability is Forward and backward stability for a problem family under an arithmetic model.

Let $n\ge 1$, let $p\in \mathbb{Q}$ with $p\ge 1$, let $A\in {\mathrm{GL}}_n(\mathbb{R})$, let $b,\delta b\in {\mathbb{R}}^n$ with $b\mathrm{\ne }0$, let $x=A^{-1}b$, and let $\delta x\in {\mathbb{R}}^n$ satisfy $A(x+\delta x)=b+\delta b$. Then

$\frac{\parallel \delta x{\parallel }_p}{\parallel x{\parallel }_p}\le {\kappa }_p(A)\frac{\parallel \delta b{\parallel }_p}{\parallel b{\parallel }_p}\mathrm{.}$

In words: the relative perturbation of the solution is at most the condition number ${\kappa }_p(A)$ of The condition number kappa_p(A) = ||A||_p ||A^{-1}||_p of a nonsingular linear system times the relative perturbation of the right-hand side.

• The bound is sharp at $p=2$. The constant ${\kappa }_2(A)$ is optimal, but the two equalities in the proof are attained on different singular directions: choose $x$ along a right singular vector for the largest singular value of $A$, so $b=Ax$ has norm ${\sigma }_{\max }\parallel x{\parallel }_2$, and choose $\delta b$ along a left singular vector for the smallest singular value, so $\parallel A^{-1}\delta b{\parallel }_2={\sigma }_{\min }^{}\parallel \delta b{\parallel }_2$. Then the bound is attained with coefficient ${\sigma }_{\max }\mathrm{/}{\sigma }_{\min }={\kappa }_2(A)$.

Let $n\ge 1$, let $p\in \mathbb{Q}$ with $p\ge 1$, let $A\in {\mathrm{GL}}_n(\mathbb{R})$, let $b\in {\mathbb{R}}^n$ with $b\mathrm{\ne }0$, let $\delta A\in M_n(\mathbb{R})$, let $x=A^{-1}b$, and suppose $\delta x\in {\mathbb{R}}^n$ satisfies $(A+\delta A)(x+\delta x)=b$. Put

$c:=\parallel A^{-1}{\parallel }_p\parallel \delta A{\parallel }_p={\kappa }_p(A)\frac{\parallel \delta A{\parallel }_p}{\parallel A{\parallel }_p}\mathrm{.}$