16.8 How Wrong Can the Answer Be

Chapter 3 solved $\mathbf{A}\mathbf{x} = \mathbf{b}$ and Chapter 11 solved it when it had no solution. Neither chapter could ask the question a user of either method asks first: the vector $\mathbf{b}$ is a measurement, so it is wrong in the last few digits, and the answer $\mathbf{x}$ is then wrong too — by how much? The question needs a way to compare the size of an error with the size of the thing it corrupts, and that is what the last seven sections have built.

The answer turns out to be one number attached to $\mathbf{A}$ , independent of $\mathbf{b}$ , and it is the last object this chapter defines. It also carries a warning, and the warning is more useful than the number.

Throughout, matrices are complex, as in Sections 4 to 7, and $\left\| \cdot \right\|$ is a norm on $\mathbb{C}^{n}$ together with the operator norm it induces on $M_n(\mathbb{C})$ (Definition 16.3.2) — the standing convention of Section 5, whose results are used here throughout. A real matrix is read inside $M_n(\mathbb{C})$ , which changes none of the three norms we actually compute with, since Theorem 16.3.3 gives the same three formulas over either field.

16.8.1. A recurring product

Let $\mathbf{A} \in M_n(\mathbb{C})$ be invertible, let $\mathbf{b} \ne \mathbf{0}$ , and let $\mathbf{x}$ solve $\mathbf{A}\mathbf{x} = \mathbf{b}$ . Suppose the data arrives as $\mathbf{b} + \Delta\mathbf{b}$ instead, so the computed answer solves $\mathbf{A}\widetilde\mathbf{x} = \mathbf{b} + \Delta\mathbf{b}$ . Subtracting the two equations, $\mathbf{A}(\widetilde\mathbf{x} - \mathbf{x}) = \Delta\mathbf{b}$ , so $\widetilde\mathbf{x} - \mathbf{x} = \mathbf{A}^{-1}\Delta\mathbf{b}, \qquad \left\| \widetilde\mathbf{x} - \mathbf{x} \right\| \le \left\| \mathbf{A}^{-1} \right\|\,\left\| \Delta\mathbf{b} \right\|$ by Theorem 16.3.2 (a). That is an absolute bound, and absolute bounds are the wrong currency: whether an error of $10^{-3}$ is a catastrophe depends on whether the answer is of size $1$ or of size $10^{6}$ . Divide by $\left\| \mathbf{x} \right\|$ , and use $\left\| \mathbf{b} \right\| = \left\| \mathbf{A}\mathbf{x} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{x} \right\|$ , that is $1/\left\| \mathbf{x} \right\| \le \left\| \mathbf{A} \right\|/\left\| \mathbf{b} \right\|$ : $\frac{\left\| \widetilde\mathbf{x} - \mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \;\le\; \left\| \mathbf{A}^{-1} \right\|\,\left\| \Delta\mathbf{b} \right\|\,\frac{\left\| \mathbf{A} \right\|}{\left\| \mathbf{b} \right\|} \;=\; \left\| \mathbf{A} \right\|\left\| \mathbf{A}^{-1} \right\|\,\frac{\left\| \Delta\mathbf{b} \right\|}{\left\| \mathbf{b} \right\|} .$ The relative error in the answer is at most the relative error in the data, multiplied by $\left\| \mathbf{A} \right\|\left\| \mathbf{A}^{-1} \right\|$ . That product depends only on $\mathbf{A}$ . It will reappear in every estimate in this section, so we name it.

The condition number is the worst factor by which $\mathbf{A}$ can magnify a relative error.

Definition 16.8.1 (Condition Number)

Let $\left\| \cdot \right\|$ be a norm on $\mathbb{C}^n$ , and write $\left\| \cdot \right\|$ also for the operator norm it induces on $M_n(\mathbb{C})$ . For $\mathbf{A} \in M_n(\mathbb{C})$ , the condition number of $\mathbf{A}$ with respect to that norm is $\kappa(\mathbf{A}) \mathrel{:=} \begin{cases} \left\| \mathbf{A} \right\|\,\left\| \mathbf{A}^{-1} \right\| & \text{if } \mathbf{A} \text{ is invertible},\\[2pt] \infty & \text{if } \mathbf{A} \text{ is singular}. \end{cases}$ We write $\kappa_1, \kappa_2, \kappa_{\infty}$ for the condition numbers with respect to $\left\| \cdot \right\|_1$ , $\left\| \cdot \right\|_2$ , $\left\| \cdot \right\|_{\infty}$ ; $\kappa_2$ is also called the spectral condition number. For a rectangular $\mathbf{A} \in M_{m \times n}(\mathbb{C})$ with $m \ge n$ and $\operatorname{rank}\mathbf{A} = n$ , we define $\kappa_2(\mathbf{A}) \mathrel{:=} \frac{\sigma_1(\mathbf{A})}{\sigma_n(\mathbf{A})} ,$ the ratio of the largest to the smallest singular value (Definition 13.8.1).

Clause by clause. The number is attached to $\mathbf{A}$ and to a norm: $\kappa_1(\mathbf{A})$ , $\kappa_2(\mathbf{A})$ and $\kappa_{\infty}(\mathbf{A})$ are three different numbers, and a statement like “ $\kappa(\mathbf{A}) = 400$ ” is incomplete until the norm is named. They cannot disagree wildly — Theorem 16.2.2 traps them within dimension-dependent factors of each other, and Exercise (C1: Changing the norm changes $\kappa$ , but not much) makes that precise — so the order of magnitude of $\kappa$ , which is all anyone uses, does not depend on the choice. The value $\infty$ for a singular matrix is a convention, and the right one: a singular $\mathbf{A}$ either makes $\mathbf{A}\mathbf{x} = \mathbf{b}$ unsolvable or makes its solution set a whole coset $\mathbf{x} + \operatorname{nul}(\mathbf{A})$ with $\operatorname{nul}(\mathbf{A}) \ne \{\mathbf{0}\}$ (Theorem 3.1.3), so no finite bound on the error can hold. Finally, the square case and the rectangular case agree where they overlap: Proposition 16.8.2 (d) shows $\kappa_2(\mathbf{A}) = \sigma_1/\sigma_n$ for an invertible square $\mathbf{A}$ as well.

Before the examples, a small lemma that says what $\kappa$ is measuring. It is the one geometric picture in this section, and it is worth carrying.

Lemma 16.8.1 (The Inverse Measures the Smallest Stretch)

Let $\mathbf{A} \in M_n(\mathbb{C})$ be invertible and let $\left\| \cdot \right\|$ be a norm on $\mathbb{C}^n$ . Then $\left\| \mathbf{A}^{-1} \right\| = \frac{1}{\min\{\left\| \mathbf{A}\mathbf{x} \right\| : \left\| \mathbf{x} \right\| = 1\}}, \qquad \kappa(\mathbf{A}) = \frac{\max\{\left\| \mathbf{A}\mathbf{x} \right\| : \left\| \mathbf{x} \right\| = 1\}}{\min\{\left\| \mathbf{A}\mathbf{x} \right\| : \left\| \mathbf{x} \right\| = 1\}} .$

Idea. Both maxima and the minimum exist by compactness, which is Lemma 16.3.1 and the same argument with a minimum. After that it is one substitution: as $\mathbf{x}$ runs over the non-zero vectors so does $\mathbf{y} = \mathbf{A}\mathbf{x}$ , and the ratio $\left\| \mathbf{A}^{-1}\mathbf{y} \right\|/\left\| \mathbf{y} \right\|$ is the reciprocal of $\left\| \mathbf{A}\mathbf{x} \right\|/\left\| \mathbf{x} \right\|$ .

Proof. The function $\mathbf{x} \mapsto \left\| \mathbf{A}\mathbf{x} \right\|$ is continuous on the unit sphere $S$ , which is compact, so it attains a maximum and a minimum there (Lemma 16.3.1 for the maximum; the same proof, or the extreme value theorem (A4) applied to the same continuous function, for the minimum). Write $m = \min_{\mathbf{x} \in S}\left\| \mathbf{A}\mathbf{x} \right\|$ . Since $\mathbf{A}$ is invertible, $\mathbf{A}\mathbf{x} \ne \mathbf{0}$ for $\mathbf{x} \in S$ , so $m > 0$ .

By Definition 16.3.2 and homogeneity, $\left\| \mathbf{A}^{-1} \right\| = \max\{\left\| \mathbf{A}^{-1}\mathbf{y} \right\|/\left\| \mathbf{y} \right\| : \mathbf{y} \ne \mathbf{0}\}$ . The map $\mathbf{y} \mapsto \mathbf{A}^{-1}\mathbf{y}$ is a bijection of $\mathbb{C}^n \setminus \{\mathbf{0}\}$ onto itself, so substituting $\mathbf{y} = \mathbf{A}\mathbf{x}$ with $\mathbf{x} \ne \mathbf{0}$ , $\left\| \mathbf{A}^{-1} \right\| = \max_{\mathbf{x} \ne \mathbf{0}}\frac{\left\| \mathbf{x} \right\|}{\left\| \mathbf{A}\mathbf{x} \right\|} = \frac{1}{\displaystyle\min_{\mathbf{x} \ne \mathbf{0}}\frac{\left\| \mathbf{A}\mathbf{x} \right\|}{\left\| \mathbf{x} \right\|}} = \frac{1}{m} ,$ the last step by homogeneity again, which lets the minimum over $\mathbf{x} \ne \mathbf{0}$ be taken over $S$ . Multiplying by $\left\| \mathbf{A} \right\| = \max_{\mathbf{x} \in S}\left\| \mathbf{A}\mathbf{x} \right\|$ gives the second formula. This proves the lemma.

So $\kappa(\mathbf{A})$ is the distortion of $\mathbf{A}$ : feed $\mathbf{A}$ the unit sphere and it comes out as a lopsided surface, and $\kappa$ is the ratio of its longest radius to its shortest. A matrix with $\kappa = 1$ carries the sphere to a sphere. A matrix with $\kappa = 10^{6}$ flattens it into something a million times longer than it is wide, and a direction of $\mathbf{b}$ that lands along the short axis has its errors magnified by a million on the way back.

Some values, simplest first.

The identity, and any unitary matrix. $\left\| \mathbf{I} \right\| = 1 = \left\| \mathbf{I}^{-1} \right\|$ , so $\kappa(\mathbf{I}) = 1$ in every norm. For unitary $\mathbf{U}$ , $\left\| \mathbf{U}\mathbf{x} \right\|_2 = \left\| \mathbf{x} \right\|_2$ for every $\mathbf{x}$ (Theorem 11.7.3), so every stretch is $1$ and $\kappa_2(\mathbf{U}) = 1$ by Lemma 16.8.1. These are the best-conditioned matrices there are.
A diagonal matrix. For $\mathbf{D} = \operatorname{diag}(d_1, \dots, d_n)$ with all $d_i \ne 0$ , $\left\| \mathbf{D} \right\|_2 = \max_i\lvert d_i\rvert$ and $\left\| \mathbf{D}^{-1} \right\|_2 = 1/\min_i\lvert d_i\rvert$ , so $\kappa_2(\mathbf{D})$ is the ratio of the largest to the smallest modulus. Thus $\kappa_2(\operatorname{diag}(1, 10^{-6})) = 10^{6}$ .
A small matrix that is perfectly conditioned. $\mathbf{A} = 10^{-6}\mathbf{I}$ has $\left\| \mathbf{A} \right\|_2 = 10^{-6}$ , a tiny norm, and $\kappa_2(\mathbf{A}) = 1$ . Being small and being ill-conditioned are unrelated.
A singular matrix, the degenerate case: $\kappa = \infty$ by convention, consistent with Lemma 16.8.1, where the minimum stretch is $0$ .

Example (Three condition numbers of one matrix)

Compute $\kappa_{\infty}(\mathbf{A})$ and $\kappa_2(\mathbf{A})$ for $\mathbf{A} = \begin{pmatrix} 2 & 1 \\ 1 & 1\end{pmatrix}$ .

Solution. $\det\mathbf{A} = 1$ , so $\mathbf{A}^{-1} = \begin{psmallmatrix} 1 & -1 \\ -1 & 2\end{psmallmatrix}$ . The largest absolute row sums are $3$ for $\mathbf{A}$ and $3$ for $\mathbf{A}^{-1}$ , so by Theorem 16.3.3 (b), $\kappa_{\infty}(\mathbf{A}) = 3 \cdot 3 = 9$ .

For $\kappa_2$ : $\mathbf{A}$ is real symmetric with $\operatorname{tr}\mathbf{A} = 3$ and $\det\mathbf{A} = 1$ , so its eigenvalues are $(3 \pm \sqrt5)/2$ , both positive, and the singular values of a symmetric matrix with positive eigenvalues are those eigenvalues (its $\mathbf{A}^{*}\mathbf{A} = \mathbf{A}^2$ has eigenvalues their squares). Hence $\kappa_2(\mathbf{A}) = \frac{3 + \sqrt5}{3 - \sqrt5} = \frac{(3+\sqrt5)^2}{4} = \frac{7 + 3\sqrt5}{2} \approx 6.854 .$ Two different norms, two different numbers, the same order of magnitude — which is the general picture.

Warning. A large $\kappa$ is not a large determinant defect, and a small determinant is not ill-conditioning. The matrix $10^{-6}\mathbf{I}_{10}$ has determinant $10^{-60}$ and $\kappa_2 = 1$ ; the matrix $\operatorname{diag}(10^{6}, 10^{-6})$ has determinant $1$ and $\kappa_2 = 10^{12}$ . The determinant scales with $c^n$ under $\mathbf{A} \mapsto c\mathbf{A}$ while $\kappa$ does not move at all (Proposition 16.8.2 (b)), so no threshold on $\lvert\det\mathbf{A}\rvert$ can detect ill-conditioning. This is the most common wrong test, and it fails in both directions.

The basic properties are all one line each, and the third is the reason $\kappa$ behaves well under the factorizations of Chapters 11 and 13.

Proposition 16.8.2 (Properties of the Condition Number)

Let $\mathbf{A}, \mathbf{B} \in M_n(\mathbb{C})$ be invertible and let $c \in \mathbb{C} \setminus\{0\}$ . With respect to any operator norm:

(a) $\kappa(\mathbf{A}) \ge 1$ ;
(b) $\kappa(c\mathbf{A}) = \kappa(\mathbf{A})$ ;
(c) $\kappa(\mathbf{A}\mathbf{B}) \le \kappa(\mathbf{A})\kappa(\mathbf{B})$ ;
(d) $\kappa_2(\mathbf{A}) = \sigma_1(\mathbf{A})/\sigma_n(\mathbf{A})$ , and $\kappa_2(\mathbf{U}\mathbf{A}\mathbf{V}) = \kappa_2(\mathbf{A})$ for all unitary $\mathbf{U}, \mathbf{V}$ .

Proof.

(a) $1 = \left\| \mathbf{I} \right\| = \left\| \mathbf{A}\mathbf{A}^{-1} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{A}^{-1} \right\| = \kappa(\mathbf{A})$ , using Theorem 16.3.2 (c) and (d).
(b) $(c\mathbf{A})^{-1} = c^{-1}\mathbf{A}^{-1}$ , so by homogeneity $\left\| c\mathbf{A} \right\|\left\| (c\mathbf{A})^{-1} \right\| = \lvert c\rvert\,\lvert c\rvert^{-1}\left\| \mathbf{A} \right\|\left\| \mathbf{A}^{-1} \right\|$ .
(c) $(\mathbf{A}\mathbf{B})^{-1} = \mathbf{B}^{-1}\mathbf{A}^{-1}$ , so submultiplicativity (Theorem 16.3.2 (d)) gives $\left\| \mathbf{A}\mathbf{B} \right\|\left\| \mathbf{B}^{-1}\mathbf{A}^{-1} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{B} \right\|\left\| \mathbf{B}^{-1} \right\|\left\| \mathbf{A}^{-1} \right\|$ .
(d) By Theorem 16.3.3 (c), $\left\| \mathbf{A} \right\|_2 = \sigma_1(\mathbf{A})$ . By Lemma 16.8.1, $\left\| \mathbf{A}^{-1} \right\|_2 = 1/m$ with $m = \min\{\left\| \mathbf{A}\mathbf{x} \right\|_2 : \left\| \mathbf{x} \right\|_2 = 1\}$ , so it remains to see $m = \sigma_n(\mathbf{A})$ . Write $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ (Theorem 13.8.1) and $\mathbf{y} = \mathbf{V}^{*}\mathbf{x}$ ; unitary matrices preserve $\left\| \cdot \right\|_2$ (Theorem 11.7.3), so $\left\| \mathbf{x} \right\|_2 = \left\| \mathbf{y} \right\|_2$ and $\left\| \mathbf{A}\mathbf{x} \right\|_2 = \left\| \boldsymbol{\Sigma}\mathbf{y} \right\|_2$ . Then $\left\| \boldsymbol{\Sigma}\mathbf{y} \right\|_2^2 = \sum_{i=1}^{n}\sigma_i^2\lvert y_i\rvert^2 \ge \sigma_n^2\sum_{i=1}^{n}\lvert y_i\rvert^2 = \sigma_n^2$ for $\left\| \mathbf{y} \right\|_2 = 1$ , with equality at $\mathbf{y} = \mathbf{e}_n$ , that is at $\mathbf{x} = \mathbf{v}_n$ , the last column of $\mathbf{V}$ . So $m = \sigma_n$ . For the last claim, if $\mathbf{A} = \mathbf{U}_1\boldsymbol{\Sigma}\mathbf{V}_1^{*}$ then $\mathbf{U}\mathbf{A}\mathbf{V} = (\mathbf{U}\mathbf{U}_1)\boldsymbol{\Sigma}(\mathbf{V}^{*}\mathbf{V}_1)^{*}$ , and a product of unitary matrices is unitary, so this is a singular value decomposition of $\mathbf{U}\mathbf{A}\mathbf{V}$ with the same $\boldsymbol{\Sigma}$ : unitary factors do not change the singular values. This proves the proposition.

Part (d) is the reason $\kappa_2$ is the condition number of choice in theory: it is invariant under the unitary changes of coordinates that Chapters 11 to 13 use throughout, so it is a property of the linear map and not of the basis it is written in.

16.8.2. What the condition number predicts

The computation that opened the section is now a theorem, together with the version where $\mathbf{A}$ itself, and not only $\mathbf{b}$ , carries the error. Both halves matter in practice: the entries of $\mathbf{A}$ are measurements too. Section 5 already proved the two perturbations together, in Theorem 16.5.3, and its constant $\left\| \mathbf{A} \right\|\left\| \mathbf{A}^{-1} \right\|$ is the product we have just named; what is added here is that the first half is sharp on its own, and that it needs no smallness hypothesis at all.

Theorem 16.8.3 (Relative Error Under Perturbation of the Data)

Let $\mathbf{A} \in M_n(\mathbb{C})$ be invertible, let $\mathbf{b} \ne \mathbf{0}$ , and let $\mathbf{A}\mathbf{x} = \mathbf{b}$ .

(a) (Perturbing $\mathbf{b}$ .) If $\mathbf{A}\widetilde\mathbf{x} = \mathbf{b} + \Delta\mathbf{b}$ , then $\frac{\left\| \widetilde\mathbf{x} - \mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \le \kappa(\mathbf{A})\,\frac{\left\| \Delta\mathbf{b} \right\|}{\left\| \mathbf{b} \right\|} ,$ and there are $\mathbf{b}$ and $\Delta\mathbf{b}$ for which equality holds.
(b) (Perturbing $\mathbf{A}$ .) Let $\mathbf{E} \in M_n(\mathbb{C})$ with $r \mathrel{:=} \kappa(\mathbf{A})\left\| \mathbf{E} \right\|/\left\| \mathbf{A} \right\| < 1$ . Then $\mathbf{A} + \mathbf{E}$ is invertible; and if $(\mathbf{A} + \mathbf{E})\widetilde\mathbf{x} = \mathbf{b}$ , then $\frac{\left\| \widetilde\mathbf{x} - \mathbf{x} \right\|}{\left\| \widetilde\mathbf{x} \right\|} \le \kappa(\mathbf{A})\,\frac{\left\| \mathbf{E} \right\|}{\left\| \mathbf{A} \right\|}, \qquad \frac{\left\| \widetilde\mathbf{x} - \mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \le \frac{r}{1 - r} .$

Idea. For (a), the displayed computation at the head of the section, plus a choice of the two vectors that makes both inequalities in it equalities — and both are attained, because Lemma 16.3.1 says an operator norm is a maximum and not a supremum. For (b), factor $\mathbf{A} + \mathbf{E} = \mathbf{A}(\mathbf{I} + \mathbf{A}^{-1}\mathbf{E})$ so that Theorem 16.5.1 decides invertibility, then subtract the two equations. Subtracting gives $\widetilde\mathbf{x} - \mathbf{x}$ in terms of $\widetilde\mathbf{x}$ , which is why the clean bound is relative to $\widetilde\mathbf{x}$ ; subadditivity of the norm converts it to a bound relative to $\mathbf{x}$ at the cost of the factor $1/(1-r)$ , and that factor is where “to first order” hides.

Proof. (a). Subtracting $\mathbf{A}\mathbf{x} = \mathbf{b}$ from $\mathbf{A}\widetilde\mathbf{x} = \mathbf{b} + \Delta\mathbf{b}$ gives $\mathbf{A}(\widetilde\mathbf{x} - \mathbf{x}) = \Delta\mathbf{b}$ , so $\widetilde\mathbf{x} - \mathbf{x} = \mathbf{A}^{-1}\Delta\mathbf{b}$ and $\left\| \widetilde\mathbf{x} - \mathbf{x} \right\| \le \left\| \mathbf{A}^{-1} \right\|\left\| \Delta\mathbf{b} \right\|$ by Theorem 16.3.2 (a). Also $\left\| \mathbf{b} \right\| = \left\| \mathbf{A}\mathbf{x} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{x} \right\|$ , and $\mathbf{x} \ne \mathbf{0}$ because $\mathbf{b} \ne \mathbf{0}$ , so $1/\left\| \mathbf{x} \right\| \le \left\| \mathbf{A} \right\|/\left\| \mathbf{b} \right\|$ . Multiplying the two estimates, $\frac{\left\| \widetilde\mathbf{x} - \mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \le \left\| \mathbf{A}^{-1} \right\|\left\| \Delta\mathbf{b} \right\|\cdot\frac{\left\| \mathbf{A} \right\|}{\left\| \mathbf{b} \right\|} = \kappa(\mathbf{A})\frac{\left\| \Delta\mathbf{b} \right\|}{\left\| \mathbf{b} \right\|} .$

For equality, use Lemma 16.3.1 twice. Choose a unit vector $\mathbf{x}$ with $\left\| \mathbf{A}\mathbf{x} \right\| = \left\| \mathbf{A} \right\|$ and put $\mathbf{b} = \mathbf{A}\mathbf{x}$ , so that $\left\| \mathbf{b} \right\| = \left\| \mathbf{A} \right\|\left\| \mathbf{x} \right\|$ and the second estimate is an equality. Choose a unit vector $\mathbf{y}$ with $\left\| \mathbf{A}^{-1}\mathbf{y} \right\| = \left\| \mathbf{A}^{-1} \right\|$ and put $\Delta\mathbf{b} = \mathbf{y}$ , so that the first estimate is an equality. Then $\frac{\left\| \widetilde\mathbf{x} - \mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \Big/ \frac{\left\| \Delta\mathbf{b} \right\|}{\left\| \mathbf{b} \right\|} = \frac{\left\| \mathbf{A}^{-1} \right\|}{1}\cdot\frac{\left\| \mathbf{A} \right\|}{1} = \kappa(\mathbf{A}) .$

(b). Write $\mathbf{A} + \mathbf{E} = \mathbf{A}(\mathbf{I} + \mathbf{A}^{-1}\mathbf{E})$ . By Theorem 16.3.2 (d), $\left\| \mathbf{A}^{-1}\mathbf{E} \right\| \le \left\| \mathbf{A}^{-1} \right\|\left\| \mathbf{E} \right\| = \kappa(\mathbf{A})\frac{\left\| \mathbf{E} \right\|}{\left\| \mathbf{A} \right\|} = r < 1 ,$ so $\mathbf{I} - (-\mathbf{A}^{-1}\mathbf{E})$ is invertible by Theorem 16.5.1, and $\mathbf{A} + \mathbf{E}$ is a product of two invertible matrices, hence invertible. (This is the openness of $\operatorname{GL}_n(F)$ recorded in Corollary 16.5.2, with the radius made explicit.)

Since $b \ne \mathbf{0}$ we have $\widetilde\mathbf{x} = (\mathbf{A} + \mathbf{E})^{-1}\mathbf{b} \ne \mathbf{0}$ . Subtracting $\mathbf{A}\mathbf{x} = \mathbf{b}$ from $(\mathbf{A} + \mathbf{E})\widetilde\mathbf{x} = \mathbf{b}$ gives $\mathbf{A}\widetilde\mathbf{x} - \mathbf{A}\mathbf{x} = -\mathbf{E}\widetilde\mathbf{x}$ , hence $\widetilde\mathbf{x} - \mathbf{x} = -\mathbf{A}^{-1}\mathbf{E}\widetilde\mathbf{x}, \qquad \left\| \widetilde\mathbf{x} - \mathbf{x} \right\| \le \left\| \mathbf{A}^{-1} \right\|\left\| \mathbf{E} \right\|\,\left\| \widetilde\mathbf{x} \right\| = r\,\left\| \widetilde\mathbf{x} \right\|,$ which is the first bound. For the second, $\left\| \widetilde\mathbf{x} \right\| \le \left\| \mathbf{x} \right\| + \left\| \widetilde\mathbf{x} - \mathbf{x} \right\|$ since $\left\| \cdot \right\|$ is subadditive (Definition 16.1.1), so $\left\| \widetilde\mathbf{x} - \mathbf{x} \right\| \le r\left\| \mathbf{x} \right\| + r\left\| \widetilde\mathbf{x} - \mathbf{x} \right\|$ ; as $r < 1$ we may divide by $1 - r > 0$ to get $\left\| \widetilde\mathbf{x} - \mathbf{x} \right\| \le \frac{r}{1-r}\left\| \mathbf{x} \right\|$ . This proves the theorem.

The two bounds in (b) say the same thing differently. The first is exact and needs nothing but invertibility, but it measures the error against the computed answer. The second measures it against the true answer, at the cost of the factor $1/(1-r)$ — which is $1 + r + r^2 + \cdots$ , so for a small $r$ it is $1$ to first order and the two bounds agree. That is all “to first order in the perturbation of $\mathbf{A}$ ” ever means here, and it is now a stated inequality rather than a gesture. Adding the two halves, with the factor $1/(1-r)$ covering both, recovers Theorem 16.5.3 exactly.

Quick check. Where in the proof of (a) is the hypothesis $\mathbf{b} \ne \mathbf{0}$ used, and what goes wrong without it?

Solution. It is used to know $\mathbf{x} \ne \mathbf{0}$ , so that $\left\| \mathbf{x} \right\|$ may be divided by, and to know $\left\| \mathbf{b} \right\| \ne 0$ , so that the relative perturbation $\left\| \Delta\mathbf{b} \right\|/\left\| \mathbf{b} \right\|$ means anything. With $\mathbf{b} = \mathbf{0}$ the true solution is $\mathbf{x} = \mathbf{0}$ and every non-zero $\Delta\mathbf{b}$ produces an infinite relative error. Relative error is only defined against a non-zero reference.

Now a case where the bound of (a) is not merely an inequality. The point of computing the example exactly is to see that $\kappa$ is not a pessimistic overestimate manufactured by the inequalities used to reach it: it is achieved.

Example (A system where the bound is attained)

Let $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 1 & 1.01 \end{pmatrix}, \qquad \mathbf{b} = \begin{pmatrix} 2 \\ 2.01 \end{pmatrix},$ whose solution is $\mathbf{x} = (1, 1)$ . Compute $\kappa_{\infty}(\mathbf{A})$ ; then perturb $\mathbf{b}$ to $\mathbf{b} + \Delta\mathbf{b}$ with $\Delta\mathbf{b} = (0.01, -0.01)$ , solve again, and compare the two relative errors.

Solution. Work with exact fractions: $1.01 = \tfrac{101}{100}$ and $\det\mathbf{A} = \tfrac{101}{100} - 1 = \tfrac1{100}$ , so $\mathbf{A}^{-1} = 100\begin{pmatrix} \tfrac{101}{100} & -1 \\ -1 & 1 \end{pmatrix} = \begin{pmatrix} 101 & -100 \\ -100 & 100 \end{pmatrix}.$ The largest absolute row sums are $\tfrac{201}{100}$ for $\mathbf{A}$ and $201$ for $\mathbf{A}^{-1}$ , so by Theorem 16.3.3 (b), $\kappa_{\infty}(\mathbf{A}) = \tfrac{201}{100}\cdot 201 = \tfrac{40401}{100} = 404.01 .$

Check that $\mathbf{A}\mathbf{x} = \mathbf{b}$ : the two rows give $1 + 1 = 2$ and $1 + \tfrac{101}{100} = \tfrac{201}{100}$ . Now $\widetilde\mathbf{x} - \mathbf{x} = \mathbf{A}^{-1}\Delta\mathbf{b} = \tfrac1{100}\begin{pmatrix} 101 + 100 \\ -100 - 100\end{pmatrix} = \begin{pmatrix} 2.01 \\ -2 \end{pmatrix},$ so $\widetilde\mathbf{x} = (3.01, -1)$ . Verify directly: $3.01 - 1 = 2.01$ and $3.01 - 1.01 = 2$ , which is $\mathbf{b} + \Delta\mathbf{b} = (2.01, 2)$ .

The two relative errors, in $\left\| \cdot \right\|_{\infty}$ : $\begin{aligned} \frac{\left\| \Delta\mathbf{b} \right\|_{\infty}}{\left\| \mathbf{b} \right\|_{\infty}} &= \frac{1/100}{201/100} = \frac{1}{201} \approx 0.50\%, \\ \frac{\left\| \widetilde\mathbf{x} - \mathbf{x} \right\|_{\infty}}{\left\| \mathbf{x} \right\|_{\infty}} &= \frac{201/100}{1} = \frac{201}{100} = 201\% . \end{aligned}$ Their ratio is $\tfrac{201}{100}\cdot 201 = 404.01$ , which is exactly $\kappa_{\infty}(\mathbf{A})$ . A perturbation of half a percent in the data has turned the answer $(1, 1)$ into $(3.01, -1)$ , and the bound of Theorem 16.8.3 (a) is attained, not approached.

Geometrically the example is Lemma 16.8.1 at work: the two rows of $\mathbf{A}$ are nearly parallel, so the two lines whose intersection is $\mathbf{x}$ cross at a very small angle, and moving either line slightly slides the crossing point a long way. Ill-conditioning is that picture, in any dimension.

Warning. The condition number bounds the error; it does not produce it. Theorem 16.8.3 is a worst case over all perturbations $\Delta\mathbf{b}$ of a given size. A particular $\Delta\mathbf{b}$ may do far less damage: in the example above, $\Delta\mathbf{b} = (0.01, 0.01)$ gives $\widetilde\mathbf{x} - \mathbf{x} = \mathbf{A}^{-1}\Delta\mathbf{b} = (0.01, 0)$ , a relative error of $1\%$ against a relative perturbation of $0.5\%$ — a magnification of $2$ , not $404$ . A large $\kappa$ says that some direction is dangerous, not that yours is.

16.8.3. Why the normal equations are worse

Chapter 11 §04 solved the least-squares problem through the normal equations $\mathbf{A}^{*}\mathbf{A}\mathbf{x} = \mathbf{A}^{*}\mathbf{b}$ (Theorem 11.4.2), and Chapter 11 §08 then recommended against actually forming that system. Its words were: “The deeper reason to prefer it is not the operation count: forming $\mathbf{A}^{*}\mathbf{A}$ squares the sensitivity of the problem to rounding, while $(\dagger)$ never forms that product at all. Chapter 24 makes ‘sensitivity’ precise and proves the comparison; here we record only the practice.” The word “sensitivity” now has a meaning, and the word “squares” is now a theorem.

Theorem 16.8.4 (The Normal Equations Square the Condition Number)

Let $m \ge n \ge 1$ and let $\mathbf{A} \in M_{m \times n}(\mathbb{C})$ have rank $n$ . Then $\mathbf{A}^{*}\mathbf{A} \in M_n(\mathbb{C})$ is invertible, and $\kappa_2(\mathbf{A}^{*}\mathbf{A}) = \kappa_2(\mathbf{A})^2 .$

Idea. An SVD of $\mathbf{A}$ is also, after one multiplication, an eigenvalue decomposition of $\mathbf{A}^{*}\mathbf{A}$ : the singular values get squared and nothing else happens. Both condition numbers are then ratios of the same list of numbers, one list being the squares of the other.

Proof. Write $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ with $\mathbf{U} \in M_m(\mathbb{C})$ , $\mathbf{V} \in M_n(\mathbb{C})$ unitary and $\boldsymbol{\Sigma} \in M_{m \times n}(\mathbb{R})$ carrying $\sigma_1 \ge \dots \ge \sigma_n \ge 0$ (Theorem 13.8.1). Since $\operatorname{rank}\mathbf{A} = n$ , exactly $n$ singular values are non-zero (Theorem 13.8.1), so $\sigma_n > 0$ . Using $\mathbf{U}^{*}\mathbf{U} = \mathbf{I}_m$ , $\mathbf{A}^{*}\mathbf{A} = \mathbf{V}\boldsymbol{\Sigma}^{*}\mathbf{U}^{*}\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*} = \mathbf{V}(\boldsymbol{\Sigma}^{*}\boldsymbol{\Sigma})\mathbf{V}^{*}, \qquad \boldsymbol{\Sigma}^{*}\boldsymbol{\Sigma} = \operatorname{diag}(\sigma_1^2, \dots, \sigma_n^2) .$ So $\mathbf{A}^{*}\mathbf{A}$ is unitarily similar to a diagonal matrix with the positive entries $\sigma_i^2$ ; it is therefore invertible, Hermitian and positive definite, with eigenvalues $\sigma_1^2 \ge \dots \ge \sigma_n^2 > 0$ .

The singular values of $\mathbf{A}^{*}\mathbf{A}$ are those same numbers. Indeed the displayed identity is a singular value decomposition of $\mathbf{A}^{*}\mathbf{A}$ , with both unitary factors equal to $\mathbf{V}$ and the diagonal entries already in decreasing order; alternatively, $(\mathbf{A}^{*}\mathbf{A})^{*}(\mathbf{A}^{*}\mathbf{A}) = \mathbf{V}\operatorname{diag}(\sigma_i^4)\mathbf{V}^{*}$ has eigenvalues $\sigma_i^4$ , whose non-negative square roots are the $\sigma_i^2$ (Definition 13.8.1). Hence by Definition 16.8.1 and Proposition 16.8.2 (d), $\kappa_2(\mathbf{A}^{*}\mathbf{A}) = \frac{\sigma_1^2}{\sigma_n^2} = \Bigl(\frac{\sigma_1}{\sigma_n}\Bigr)^{2} = \kappa_2(\mathbf{A})^2 .$ This proves the theorem.

Example (Squaring, on a

3 \times 2

example)

Let $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 0.1 & 0 \\ 0 & 0.1 \end{pmatrix}$ . Compute $\kappa_2(\mathbf{A})$ and $\kappa_2(\mathbf{A}^{\top}\mathbf{A})$ .

Solution. $\mathbf{A}^{\top}\mathbf{A} = \begin{psmallmatrix} 1.01 & 1 \\ 1 & 1.01 \end{psmallmatrix}$ . It sends $(1, 1)$ to $2.01\,(1,1)$ and $(1, -1)$ to $0.01\,(1,-1)$ , so its eigenvalues are $\tfrac{201}{100}$ and $\tfrac1{100}$ . Hence $\sigma_1(\mathbf{A}) = \sqrt{201}/10$ and $\sigma_2(\mathbf{A}) = 1/10$ , so $\kappa_2(\mathbf{A}) = \sqrt{201} \approx 14.18, \qquad \kappa_2(\mathbf{A}^{\top}\mathbf{A}) = \frac{201/100}{1/100} = 201 = \bigl(\sqrt{201}\bigr)^2 .$ A matrix whose conditioning is unremarkable becomes, on forming $\mathbf{A}^{\top}\mathbf{A}$ , a matrix whose conditioning is fourteen times worse.

What is proved here, and what is not. Theorem 16.8.4 is a statement about matrices: the matrix one forms when one writes down the normal equations has the square of the condition number of the matrix one started with. Combined with Theorem 16.8.3, it says that the linear system $\mathbf{A}^{*}\mathbf{A}\mathbf{x} = \mathbf{A}^{*}\mathbf{b}$ , considered as a problem in its own data, is more sensitive than $\mathbf{A}$ itself by a factor $\kappa_2(\mathbf{A})$ — and the $\mathbf{Q}\mathbf{R}$ route $\mathbf{R}\mathbf{x} = \mathbf{Q}^{*}\mathbf{b}$ of Chapter 11 §08 never forms $\mathbf{A}^{*}\mathbf{A}$ , so it never incurs that factor. Indeed the triangular matrix it does solve with is no worse conditioned than $\mathbf{A}$ : from $\mathbf{A} = \mathbf{Q}\mathbf{R}$ with $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_n$ (Theorem 11.8.1) we get $\mathbf{A}^{*}\mathbf{A} = \mathbf{R}^{*}\mathbf{Q}^{*}\mathbf{Q}\mathbf{R} = \mathbf{R}^{*}\mathbf{R}$ , so $\mathbf{A}$ and $\mathbf{R}$ have the same singular values (Definition 13.8.1) and $\kappa_2(\mathbf{R}) = \kappa_2(\mathbf{A})$ exactly.

Three things are not proved here, and all three belong to Chapter 24.

The conditioning of the least-squares problem itself is not $\kappa_2(\mathbf{A})$ . The map $\mathbf{b} \mapsto \mathbf{x}^{+}$ from data to least-squares solution has a sensitivity that depends on $\kappa_2(\mathbf{A})$ , on the residual $\left\| \mathbf{A}\mathbf{x}^{+} - \mathbf{b} \right\|$ and on the angle between $\mathbf{b}$ and $\operatorname{col}(\mathbf{A})$ ; when the residual is large, a term in $\kappa_2(\mathbf{A})^2$ appears even for the QR route. The bound above is about the linear systems being solved, not about the underlying fitting problem.
Nothing here is about arithmetic. A condition number describes a problem, and an error bound of the form “relative error $\le \kappa \cdot$ (relative perturbation)” only becomes a statement about a computation once one knows how large a perturbation the computation itself introduces. That requires a model of floating-point arithmetic and a backward error analysis, neither of which exists in this book yet.
Hence the comparison of the two algorithms — that a stable implementation of the QR route loses about $\log_{10}\kappa_2(\mathbf{A})$ decimal digits while forming and solving the normal equations loses about $2\log_{10}\kappa_2(\mathbf{A})$ — is still Chapter 24’s to prove. What this section supplies is the number that appears in both statements, and the reason a square appears in one of them.

16.8.4. Conditioning is a property of the problem

This is the last warning of the chapter, and it is the one readers most often need.

Warning. Conditioning belongs to the problem; stability belongs to the algorithm. $\kappa(\mathbf{A})$ is computed from $\mathbf{A}$ alone. It knows nothing about how anyone intends to solve $\mathbf{A}\mathbf{x} = \mathbf{b}$ , and it does not change if the method changes. Two consequences, both regularly got wrong:

A large $\kappa(\mathbf{A})$ does not mean a computed answer is wrong. It means that the answer is not determined to high relative accuracy by data of limited accuracy — a statement about the information available, not about the arithmetic performed. If the data are exact and the arithmetic is exact, the answer is exact however large $\kappa$ is. And even in inexact arithmetic, a good algorithm returns the exact answer to a problem whose data differ from yours by a rounding error, which is the most anyone can ask of it.
A small $\kappa(\mathbf{A})$ does not make an algorithm trustworthy. An unstable method can wreck a perfectly conditioned problem all by itself, by introducing errors far larger than the data warrant; Exercise (C3: A well-conditioned problem and a bad method) gives an elementary example in which $\kappa_{\infty}$ is below $5$ and a computed coordinate comes out as $0$ instead of $1$ .

Chapter 24 draws the distinction properly, defines backward stability, and proves which of the algorithms in this book have it. Until then, read $\kappa$ as an upper bound on what any method can promise, and never as a verdict on a particular answer.

16.8.5. What this chapter has settled

Nine chapters wrote promissory notes that only a norm could pay. Here is the ledger, with the section that closed each entry.

Chapter 11 §01 said that not every norm comes from an inner product and that the parallelogram law is the test. Section 1 proved it, in Theorem 16.1.3, building on the $\mathbb{R}^2$ case of Exercise (C1: The parallelogram law characterizes inner-product norms).
Chapter 10 §10 promised that this chapter would prove $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|$ for the norm induced by any vector norm, and would recover $\rho(\mathbf{A})$ as a limit built from the norms of the powers. Section 4 did both: Theorem 16.4.1 and Gelfand’s formula Theorem 16.4.4. The same section also gave $\rho$ the labeled definition Definition 16.4.1 that Chapter 10 used only in prose, and Corollary 16.4.5 restored Chapter 10’s convergence criterion with a rate attached. And Chapter 10’s entrywise convergence turned out to be the convergence, by Corollary 16.2.4.
Chapter 13 §08 and §12 asked, twice, for a name for $\max\{\left\| \mathbf{A}\mathbf{x} \right\| : \left\| \mathbf{x} \right\| = 1\}$ . Section 3 supplied it — Definition 16.3.2 — and separated the name from the computation $\left\| \mathbf{A} \right\|_2 = \sigma_1(\mathbf{A})$ , which is Theorem 16.3.3 (c); Example (The oblique projection, finally measured) measured Chapter 13 §12’s oblique projection. The spectral norm that Chapter 13 §10 needed in order even to state the second half of its approximation theorem now exists; the theorem itself waits for Chapter 17, which proves it from the min–max description of the singular values. The version covering every unitarily invariant norm at once is Chapter 21’s.
Chapter 10 §09 promised a return to $e^{\mathbf{A}}$ with norms available, giving quantitative bounds in place of exact formulas. Section 6 gave them, in Theorem 16.6.1, and its Theorem 16.6.3 is the statement Chapter 12 §10 pointed at when it said that the consequence of stability for $\dot\mathbf{x} = \mathbf{A}\mathbf{x}$ belonged to Chapter 16.
Chapter 12 §01 said that this chapter, “where matrices acquire norms and limits can be spoken of properly, runs arguments of exactly this shape”. Section 7 ran one: Corollary 16.7.5 and Corollary 16.7.6 turn “prove it for diagonalizable matrices, then take a limit” into three lines, and Example (Cayley–Hamilton, by a limit) is the demonstration.
Chapter 11 §08 deferred its reason for preferring $\mathbf{Q}\mathbf{R}$ to the normal equations. Theorem 16.8.4 supplies the matrix half of it; the arithmetic half is Chapter 24’s, as listed above.

What the chapter has not done is equally worth recording. It has not bounded how far an individual eigenvalue moves under a perturbation — Example (A Jordan block’s eigenvalues move like $\varepsilon^{1/k}$ ) shows there is no bound of the obvious kind, and the bounds that do exist, Weyl’s and Bauer–Fike’s, are Chapters 17 and 20. It has not said which norms are invariant under unitary multiplication, which is Chapter 21. And it has not touched arithmetic. The condition number is the bridge to that last subject: it is the exact point at which linear algebra stops and numerical analysis begins.

16.8.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define $\kappa(\mathbf{A})$ , naming what it depends on besides $\mathbf{A}$ .
(b) Explain why $\kappa(\mathbf{A}) \ge 1$ for every invertible $\mathbf{A}$ .
(c) Decide whether each statement is correct, and justify: (i) “if $\kappa(\mathbf{A}) = 10^{8}$ then any computed solution of $\mathbf{A}\mathbf{x} = \mathbf{b}$ has at most a few correct digits”; (ii) “if $\kappa(\mathbf{A})$ is small then any method of solving $\mathbf{A}\mathbf{x} = \mathbf{b}$ is reliable”.
(d) State what $\kappa_2(\mathbf{A}^{*}\mathbf{A})$ is in terms of $\kappa_2(\mathbf{A})$ , and say what that has to do with the $\mathbf{Q}\mathbf{R}$ factorization.

Solution.

(a) See Definition 16.8.1: $\kappa(\mathbf{A}) = \left\| \mathbf{A} \right\|\left\| \mathbf{A}^{-1} \right\|$ , with $\kappa(\mathbf{A}) = \infty$ for singular $\mathbf{A}$ . Besides $\mathbf{A}$ it depends on the choice of vector norm, through the operator norm it induces; $\kappa_1$ , $\kappa_2$ and $\kappa_{\infty}$ are three different numbers.
(b) $1 = \left\| \mathbf{I} \right\| = \left\| \mathbf{A}\mathbf{A}^{-1} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{A}^{-1} \right\|$ , by Theorem 16.3.2 (c) and (d). See Proposition 16.8.2 (a).
(c)
- (i) Incorrect. $\kappa$ bounds the effect of a perturbation of the data; with exact data and exact arithmetic the answer is exact. It says that the answer cannot be determined to high relative accuracy from inaccurate data, which is a statement about the problem, not a verdict on a computed answer. (ii) Incorrect. Conditioning is a property of the problem and stability a property of the algorithm; a small $\kappa$ leaves an unstable method free to introduce errors of its own.
(d) $\kappa_2(\mathbf{A}^{*}\mathbf{A}) = \kappa_2(\mathbf{A})^2$ for $\mathbf{A}$ of full column rank (Theorem 16.8.4). The normal equations form $\mathbf{A}^{*}\mathbf{A}$ and so solve a system with the squared condition number, while the route $\mathbf{R}\mathbf{x} = \mathbf{Q}^{*}\mathbf{b}$ of Chapter 11 §08 never forms that product and keeps $\kappa_2(\mathbf{R}) = \kappa_2(\mathbf{A})$ .

B. Practice

Exercise (B1: Three condition numbers)

For $\mathbf{A} = \begin{pmatrix} 3 & 0 \\ 0 & -\tfrac12 \end{pmatrix}$ and $\mathbf{B} = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$ , compute $\kappa_{\infty}$ and $\kappa_2$ of each. Hint: $\mathbf{B}^{*}\mathbf{B}$ has trace $6$ and determinant $1$ .

Solution. $\mathbf{A}^{-1} = \operatorname{diag}(\tfrac13, -2)$ . Largest absolute row sums: $3$ for $\mathbf{A}$ , $2$ for $\mathbf{A}^{-1}$ , so $\kappa_{\infty}(\mathbf{A}) = 6$ by Theorem 16.3.3 (b). For $\kappa_2$ : $\mathbf{A}^{*}\mathbf{A} = \operatorname{diag}(9, \tfrac14)$ , so $\sigma_1 = 3$ , $\sigma_2 = \tfrac12$ and $\kappa_2(\mathbf{A}) = 6$ by Proposition 16.8.2 (d). The two agree here because $\mathbf{A}$ is diagonal.

$\mathbf{B}^{-1} = \begin{psmallmatrix} 1 & -2 \\ 0 & 1\end{psmallmatrix}$ , and both have largest absolute row sum $3$ , so $\kappa_{\infty}(\mathbf{B}) = 9$ . For $\kappa_2$ : $\mathbf{B}^{*}\mathbf{B} = \begin{psmallmatrix} 1 & 2 \\ 2 & 5\end{psmallmatrix}$ has trace $6$ and determinant $1$ , so its eigenvalues are $3 \pm 2\sqrt2$ , giving $\kappa_2(\mathbf{B}) = \sqrt{\frac{3 + 2\sqrt2}{3 - 2\sqrt2}} = 3 + 2\sqrt2 \approx 5.828 ,$ using $(3 - 2\sqrt2)(3 + 2\sqrt2) = 1$ , so that the ratio is $(3 + 2\sqrt2)^2$ .

Exercise (B2: A perturbation, measured against the bound)

Let $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 1 & 1.01\end{pmatrix}$ and $\mathbf{b} = (2, 2.01)$ as in Example (A system where the bound is attained), and take $\Delta\mathbf{b} = (0, 0.01)$ .

(a) Solve $\mathbf{A}\widetilde\mathbf{x} = \mathbf{b} + \Delta\mathbf{b}$ exactly.
(b) Compute both relative errors in $\left\| \cdot \right\|_{\infty}$ and the factor between them, and compare with $\kappa_{\infty}(\mathbf{A}) = 404.01$ .

Solution.

(a) With $\mathbf{A}^{-1} = \begin{psmallmatrix} 101 & -100 \\ -100 & 100\end{psmallmatrix}$ from Example (A system where the bound is attained) and $\Delta\mathbf{b} = (0, \tfrac1{100})$ , $\widetilde\mathbf{x} - \mathbf{x} = \mathbf{A}^{-1}\Delta\mathbf{b} = \begin{pmatrix} -1 \\ 1 \end{pmatrix}, \qquad \widetilde\mathbf{x} = \begin{pmatrix} 0 \\ 2 \end{pmatrix}.$ Check: $0 + 2 = 2$ and $0 + 2\cdot\tfrac{101}{100} = \tfrac{202}{100} = 2.02 = \mathbf{b} + \Delta\mathbf{b}$ in the second coordinate.
(b) $\left\| \Delta\mathbf{b} \right\|_{\infty}/\left\| \mathbf{b} \right\|_{\infty} = \tfrac{1/100}{201/100} = \tfrac1{201}$ , and $\left\| \widetilde\mathbf{x} - \mathbf{x} \right\|_{\infty}/\left\| \mathbf{x} \right\|_{\infty} = 1$ . The factor is $201$ , which is below $\kappa_{\infty}(\mathbf{A}) = 404.01$ by a factor of about $2$ . The bound holds, as Theorem 16.8.3 (a) requires, and is not attained: this $\Delta\mathbf{b}$ is not the worst direction, which Example (A system where the bound is attained) found.

Exercise (B3: Squaring, again)

Let $\mathbf{A} = \begin{pmatrix} 1 & 0 \\ 0 & \tfrac12 \\ 0 & 0\end{pmatrix}$ .

(a) Compute the singular values of $\mathbf{A}$ and $\kappa_2(\mathbf{A})$ .
(b) Compute $\mathbf{A}^{\top}\mathbf{A}$ and $\kappa_2(\mathbf{A}^{\top}\mathbf{A})$ directly, and confirm Theorem 16.8.4.
(c) Does $\kappa_{\infty}$ also square? Compute $\kappa_{\infty}(\mathbf{A}^{\top}\mathbf{A})$ and compare with $\kappa_{\infty}$ of the square matrix $\begin{psmallmatrix}1 & 0\\ 0 & \frac12\end{psmallmatrix}$ .

Solution.

(a) $\mathbf{A}^{\top}\mathbf{A} = \operatorname{diag}(1, \tfrac14)$ , whose eigenvalues are $1$ and $\tfrac14$ ; so $\sigma_1(\mathbf{A}) = 1$ , $\sigma_2(\mathbf{A}) = \tfrac12$ and $\kappa_2(\mathbf{A}) = 2$ .
(b) $\mathbf{A}^{\top}\mathbf{A} = \operatorname{diag}(1, \tfrac14)$ is diagonal with positive entries, so its singular values are $1$ and $\tfrac14$ and $\kappa_2(\mathbf{A}^{\top}\mathbf{A}) = 4 = 2^2 = \kappa_2(\mathbf{A})^2$ , as Theorem 16.8.4 says.
(c) For a diagonal matrix every $\kappa_p$ is the ratio of the largest to the smallest modulus on the diagonal, so $\kappa_{\infty}(\mathbf{A}^{\top}\mathbf{A}) = 4$ while $\kappa_{\infty}(\operatorname{diag}(1, \tfrac12)) = 2$ ; here the squaring happens in $\kappa_{\infty}$ too. It does not in general: Theorem 16.8.4 is stated for $\kappa_2$ , and the proof uses singular values, which only $\left\| \cdot \right\|_2$ sees. Exercise (C1: Changing the norm changes $\kappa$ , but not much) bounds how far the other condition numbers can stray.

C. Going deeper

Exercise (C1: Changing the norm changes

\kappa

, but not much)

Let $\left\| \cdot \right\|_a$ and $\left\| \cdot \right\|_b$ be norms on $\mathbb{C}^n$ with $c\left\| \mathbf{v} \right\|_b \le \left\| \mathbf{v} \right\|_a \le C\left\| \mathbf{v} \right\|_b$ for all $\mathbf{v}$ , as supplied by Theorem 16.2.2, and write $\kappa_a, \kappa_b$ for the corresponding condition numbers.

(a) Prove that $\left\| \mathbf{A} \right\|_a \le (C/c)\left\| \mathbf{A} \right\|_b$ for every $\mathbf{A} \in M_n(\mathbb{C})$ .
(b) Deduce that $\kappa_a(\mathbf{A}) \le (C/c)^2\kappa_b(\mathbf{A})$ and $\kappa_b(\mathbf{A}) \le (C/c)^2\kappa_a(\mathbf{A})$ for every invertible $\mathbf{A}$ .
(c) Using $\left\| \mathbf{v} \right\|_{\infty} \le \left\| \mathbf{v} \right\|_2 \le \sqrt n\,\left\| \mathbf{v} \right\|_{\infty}$ , bound $\kappa_2$ in terms of $\kappa_{\infty}$ for $n = 2$ , and check the bound on the matrix $\mathbf{B} = \begin{psmallmatrix} 1 & 2 \\ 0 & 1\end{psmallmatrix}$ of Exercise (B1: Three condition numbers).

Solution.

(a) Let $\mathbf{x} \ne \mathbf{0}$ . Then $\frac{\left\| \mathbf{A}\mathbf{x} \right\|_a}{\left\| \mathbf{x} \right\|_a} \le \frac{C\left\| \mathbf{A}\mathbf{x} \right\|_b}{c\left\| \mathbf{x} \right\|_b} \le \frac{C}{c}\,\left\| \mathbf{A} \right\|_b ,$ using the two inequalities and Theorem 16.3.2 (a) for $\left\| \cdot \right\|_b$ . Taking the maximum over $\mathbf{x} \ne \mathbf{0}$ , which is $\left\| \mathbf{A} \right\|_a$ by Definition 16.3.2 and homogeneity, gives the claim.
(b) Apply (a) to $\mathbf{A}$ and to $\mathbf{A}^{-1}$ and multiply: $\kappa_a(\mathbf{A}) = \left\| \mathbf{A} \right\|_a\left\| \mathbf{A}^{-1} \right\|_a \le (C/c)^2\left\| \mathbf{A} \right\|_b\left\| \mathbf{A}^{-1} \right\|_b = (C/c)^2\kappa_b(\mathbf{A})$ . The reverse follows by symmetry, since the hypothesis also reads $C^{-1}\left\| \mathbf{v} \right\|_a \le \left\| \mathbf{v} \right\|_b \le c^{-1}\left\| \mathbf{v} \right\|_a$ , whose ratio of constants is again $C/c$ .
(c) With $\left\| \cdot \right\|_a = \left\| \cdot \right\|_2$ and $\left\| \cdot \right\|_b = \left\| \cdot \right\|_{\infty}$ , we have $c = 1$ and $C = \sqrt n = \sqrt2$ , so $\kappa_2(\mathbf{A}) \le 2\kappa_{\infty}(\mathbf{A})$ and $\kappa_{\infty}(\mathbf{A}) \le 2\kappa_2(\mathbf{A})$ . For $\mathbf{A} = \begin{psmallmatrix}1&2\\mathbf{0}&1\end{psmallmatrix}$ : $\kappa_2 = 3 + 2\sqrt2 \approx 5.83$ and $\kappa_{\infty} = 9$ , and indeed $5.83 \le 18$ and $9 \le 11.66$ . Both bounds hold, with room to spare; the point is only that no choice of norm can turn a well-conditioned matrix into an ill-conditioned one.

Exercise (C2: The condition number is the reciprocal distance to singularity)

Let $\mathbf{A} \in M_n(\mathbb{C})$ be invertible.

(a) Prove that every singular $\mathbf{B} \in M_n(\mathbb{C})$ satisfies $\frac{\left\| \mathbf{A} - \mathbf{B} \right\|}{\left\| \mathbf{A} \right\|} \ge \frac{1}{\kappa(\mathbf{A})} .$
(b) For the $2$ -norm, prove that equality is achieved: exhibit a singular $\mathbf{B}$ with $\left\| \mathbf{A} - \mathbf{B} \right\|_2 = \sigma_n(\mathbf{A})$ . Hint: use a singular value decomposition and delete one term.
(c) Hence interpret $1/\kappa_2(\mathbf{A})$ in one sentence, and say what it gives for the matrix of Example (A system where the bound is attained).

Solution.

(a) Put $\mathbf{E} = \mathbf{B} - \mathbf{A}$ , so $\mathbf{A} + \mathbf{E} = \mathbf{B}$ is singular. If $\left\| \mathbf{A}^{-1}\mathbf{E} \right\| < 1$ then $\mathbf{A} + \mathbf{E} = \mathbf{A}(\mathbf{I} + \mathbf{A}^{-1}\mathbf{E})$ would be invertible, by Theorem 16.5.1 and the fact that a product of invertible matrices is invertible; so $\left\| \mathbf{A}^{-1}\mathbf{E} \right\| \ge 1$ . By Theorem 16.3.2 (d), $1 \le \left\| \mathbf{A}^{-1} \right\|\left\| \mathbf{E} \right\|$ , that is $\left\| \mathbf{E} \right\| \ge 1/\left\| \mathbf{A}^{-1} \right\|$ . Dividing by $\left\| \mathbf{A} \right\|$ , $\frac{\left\| \mathbf{A} - \mathbf{B} \right\|}{\left\| \mathbf{A} \right\|} = \frac{\left\| \mathbf{E} \right\|}{\left\| \mathbf{A} \right\|} \ge \frac{1}{\left\| \mathbf{A} \right\|\,\left\| \mathbf{A}^{-1} \right\|} = \frac{1}{\kappa(\mathbf{A})} .$
(b) Let $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ (Theorem 13.8.1) with $\boldsymbol{\Sigma} = \operatorname{diag}(\sigma_1, \dots, \sigma_n)$ , and put $\mathbf{B} = \mathbf{U}\,\operatorname{diag}(\sigma_1, \dots, \sigma_{n-1}, 0)\,\mathbf{V}^{*} .$ Then $\mathbf{B}$ is singular, since $\operatorname{diag}(\sigma_1, \dots, \sigma_{n-1}, 0)$ is and $\mathbf{U}, \mathbf{V}$ are invertible; and $\mathbf{A} - \mathbf{B} = \mathbf{U}\,\operatorname{diag}(0, \dots, 0, \sigma_n)\,\mathbf{V}^{*}$ , whose singular values are those of $\operatorname{diag}(0, \dots, 0, \sigma_n)$ — for any $\mathbf{M}$ , $(\mathbf{U}\mathbf{M}\mathbf{V}^{*})^{*}(\mathbf{U}\mathbf{M}\mathbf{V}^{*}) = \mathbf{V}\mathbf{M}^{*}\mathbf{M}\mathbf{V}^{*}$ is similar to $\mathbf{M}^{*}\mathbf{M}$ , so unitary factors leave the singular values alone, invertible or not — the largest of them being $\sigma_n$ ; so $\left\| \mathbf{A} - \mathbf{B} \right\|_2 = \sigma_n$ by Theorem 16.3.3 (c). Since $\left\| \mathbf{A} \right\|_2 = \sigma_1$ , the ratio is $\sigma_n/\sigma_1 = 1/\kappa_2(\mathbf{A})$ , matching (a) with equality.
(c) $1/\kappa_2(\mathbf{A})$ is the relative distance, in the $2$ -norm, from $\mathbf{A}$ to the nearest singular matrix. For $\mathbf{A} = \begin{psmallmatrix} 1 & 1 \\ 1 & 1.01\end{psmallmatrix}$ , whose $\kappa_2$ is the ratio of the eigenvalues $(201 \pm \sqrt{40001})/200$ of the symmetric $\mathbf{A}$ , one gets $\kappa_2(\mathbf{A}) \approx 402.0$ , so a relative perturbation of about $0.25\%$ suffices to make $\mathbf{A}$ singular. Ill-conditioned means nearly singular, in exactly this quantitative sense.

Exercise (C3: A well-conditioned problem and a bad method)

Consider the two-by-two system $\begin{aligned} 10^{-15}x_1 + x_2 &= 1, \\ x_1 + x_2 &= 2 , \end{aligned}$ with coefficient matrix $\mathbf{A} = \begin{psmallmatrix} 10^{-15} & 1 \\ 1 & 1\end{psmallmatrix}$ .

(a) Show that $\kappa_{\infty}(\mathbf{A}) < 5$ , so that the problem is well conditioned.
(b) Solve the system exactly.
(c) Eliminate $x_1$ using the first equation as the pivot row, rounding every intermediate quantity to $12$ significant decimal digits, and compare the result with (b). Then do the same after exchanging the two equations, and say what the exchange achieved.
(d) What does this show about the relationship between $\kappa(\mathbf{A})$ and the accuracy of a computed answer?

Solution.

(a) Write $\varepsilon = 10^{-15}$ . Then $\det\mathbf{A} = \varepsilon - 1 \ne 0$ and $\mathbf{A}^{-1} = \frac{1}{\varepsilon - 1}\begin{pmatrix} 1 & -1 \\ -1 & \varepsilon\end{pmatrix} .$ The largest absolute row sum of $\mathbf{A}$ is $2$ , and that of $\mathbf{A}^{-1}$ is $2/(1 - \varepsilon)$ , so by Theorem 16.3.3 (b), $\kappa_{\infty}(\mathbf{A}) = \frac{4}{1 - \varepsilon} < 5 .$
(b) Subtracting the first equation from the second gives $(1 - \varepsilon)x_1 = 1$ , so $x_1 = \frac{1}{1 - \varepsilon} = 1 + 10^{-15} + \dots, \qquad x_2 = 1 - \varepsilon x_1 = \frac{1 - 2\varepsilon}{1 - \varepsilon} = 1 - 10^{-15} + \dots .$ Both coordinates are $1$ to fourteen decimal places.
(c) Without the exchange. The multiplier is $1/\varepsilon = 10^{15}$ , and the second equation becomes $(1 - 10^{15})x_2 = 2 - 10^{15} .$ Both sides need fifteen significant digits to be recorded exactly, so at twelve digits both round to $-1.00000000000 \times 10^{15}$ , and the computed $x_2$ is exactly $1$ — accurate, as it happens. Back-substitution into the first equation then gives $x_1 = \frac{1 - x_2}{\varepsilon} = \frac{0}{10^{-15}} = 0 ,$ against a true value of $1 + 10^{-15}$ : every digit is wrong. The damage was done by subtracting two numbers that agree in all twelve retained digits, so that the difference retains none of them.

With the exchange. Pivoting on $x_1 + x_2 = 2$ , the multiplier is $\varepsilon = 10^{-15}$ and the second equation becomes $(1 - \varepsilon)x_2 = 1 - 2\varepsilon$ . At twelve digits both coefficients round to $1.00000000000$ , giving $x_2 = 1.00000000000$ , and back-substitution gives $x_1 = 2 - x_2 = 1.00000000000$ . Both agree with (b) to all twelve digits. The exchange achieved one thing: it made the multiplier at most $1$ in modulus, so nothing in the elimination was amplified, and no large quantity was ever created to be subtracted from a comparable one. This is why every practical elimination scheme chooses the largest available pivot.
(d) The conditioning of the problem is excellent, $\kappa_{\infty}(\mathbf{A}) < 5$ , and it is the same for both computations, since it does not mention a method. Yet one method returns $(0, 1)$ and the other returns the right answer. Conditioning bounds what any method can promise; whether a given method keeps that promise is stability, and it is Chapter 24’s subject.