5.8 矩阵的逆和线性方程组的解的误差

作为矩阵范数和向量范数的应用，我们来估计在求矩阵的逆和求线性方程组的解的过程中所引起的误差.

如果给定了非奇异矩阵 $A \in M_{n}$ ，可以设想能够准确地计算出逆矩阵 $A^{-1}$ ，但是，如果计算是在数字计算机上用有限长的计算机字符来完成，则不可避免地要出现舍入误差和舍位误差。另外，即使能十分准确地完成所有计算，但可能有这种情形，矩阵 $A$ 的有些元素是某些实验的结果或某些必然会出现误差的计算结果，因此，就不可能十分精确地知道这些结果。那么，计算中的误差和数据中的误差如何影响要计算的逆矩阵呢？

对于许多普通的算法，可以证明，在计算中的舍入误差可以用同一种方式模拟成数据中的误差。也就是说，如果假定 $A \in M_n$ 是给定的非奇异矩阵，并且想计算 $A^{-1}$ ，而实际计算的可能是 $(A + E)^{-1}$ ，其中 $E \in M_n$ 是足够小的矩阵，且使 $A + E$ 为可逆矩阵。于是，误差是 $A^{-1} - (A + E)^{-1} = A^{-1} - (I + A^{-1}E)^{-1}A^{-1}$ 。如果 $\rho(A^{-1}E) < 1$ ，则 $A + E$ 就是可逆矩阵，且我们可以把 $(I + A^{-1}E)^{-1}$ 写成 $A^{-1}E$ 的幂级数，这就给出

A ^ {- 1} - (A + E) ^ {- 1} = A ^ {- 1} - \sum_ {k = 0} (- 1) ^ {k} (A ^ {1} E) ^ {k} A ^ {- 1} = \sum_ {k = 1} (- 1) ^ {k + 1} (A ^ {1} E) ^ {k} A ^ {1}.

因此，关于这个误差的精确公式：

A ^ {t} - (A + E) ^ {- 1} = \sum_ {k = 1} ^ {\prime} (- 1) ^ {k + 1} (A ^ {- 1} E) ^ {k} A ^ {- 1}, \text {如 果} \rho (A ^ {1} E) < 1. \tag {5.8.1}

现在假定 $\| \cdot \|$ 是给定的矩阵范数，且假定 $\| A^{-1}E\| < 1$ ，因而特别有 $\rho (A^{-1}E) < 1$ 和(5.8.1)成立．于是

\left\| A ^ {- 1} \cdot (A + E) ^ {1} \right\| = \left\| \sum_ {k = 1} ^ {\infty} (1) ^ {k - 1} (A ^ {1} E) ^ {k} A ^ {- 1} \right\|

334

\leqslant \sum_ {k = 1} ^ {\prime} \| A ^ {1} E ^ {*} \| A ^ {- 1} \| = \frac {\| A ^ {1} E \|}{1 - \| A ^ {- 1} E \|} \| A ^ {- 1} \|, \tag {335}

由此得出，求逆过程中所引起的相对误差的一个上界是

\frac {\left\| A ^ {1} - (A + E) ^ {1} \right\|}{\left\| A ^ {1} \right\|} \leqslant \frac {\left| A ^ {- 1} E \right\|}{1 - \left| A ^ {- 1} E \right\|}. \text {如 果} \left| A ^ {- 1} E \right\| < 1. \tag {5.8.2}

另外，如果让 $E$ 足够“小”，以至 $\| E\| < 1 / \| A^{-1}\|$ ，则 $\rho (A^{-1}E)\leqslant \| A^{-1}E\| \leqslant \| A^{-1}\| E\| < 1$ 且有估计式

\frac {\left| A ^ {- 1} - (A \mid E) ^ {- 1} \right|}{\left\| A ^ {- 1} \right|} \leqslant \frac {\left| A ^ {- 1} \right| \left| E \right|}{1 - \left| A ^ {- 1} \right| \left| E \right|} = \frac {\left\| A ^ {- 1} \right\| \left\| A _ {1} \left(\left\| E \right| / \left| A \right|\right) \right.}{1 - \left\| A ^ {- 1} \right\| \left\| A _ {1} \left(\left\| E \right| / \left| A \right|\right) \right.}.

数

\kappa (A) \equiv \left\{ \begin{array}{l l} \| A ^ {- 1} \| \| A \| & \text {如 果} A \text {是 非 奇 异 矩 阵}; \\ \infty & \text {如 果} A \text {是 奇 异 矩 阵} \end{array} \right. \tag {5.8.3}

称为矩阵逆关于矩阵范数 $\| \cdot \|$ 的条件数。注意 $\kappa(A) = \| A^{-1} \| A \| \geqslant \| A^{-1} A \| = |I| \geqslant 1$ 对任意矩阵范数都成立。

利用这个记号，有估计式

\frac {\left| A ^ {- 1} - (A + E) ^ {- 1} \right|}{\left\| A ^ {- 1} \right\|} \leqslant \frac {\kappa (A)}{1 - \kappa (A) \left( \right.\left\| \right. E ^ {2} / \left\| A ^ {- 1} \right\|\left. \right)} \frac {\left\| E \right\|}{\left\| A \right\|}, \text {如 果} \left\| E _ {1} \right\|\left\| A ^ {- 1} \right\| < 1, \tag {5.8.4}

在采用的范数是谱范数的普通情形，条件数有一个有趣的几何特征。设 $\theta(A)$ 表示当 $x$ 和 $y$ 取遍所有正交单位向量偶时向量 $Ax$ 与 $Ay$ 间的最小角。利用谱范数， $\kappa(A) = \cot[\theta(A)/2]$ 。因此，若 $A$ 是酉矩阵，则 $\theta(A) = \pi/2$ 且 $\cot(\pi/4) = 1 = \kappa(A)$ 。若 $A$ “近乎奇异矩阵”，则有某个正交单位向量偶 $x, y$ ，使得 $Ax$ “几乎平行”于 $Ay$ ， $\theta(A)$ 就会很小，而 $\kappa(A) = \cot[\theta(A)/2]$ 就会很大。欲知详情，请参看例(7.4.26)。

练习证明，如果 $A \in M_{n}$ 可逆，则 $\kappa(A) = \kappa(A^{-1})$ 。

练习证明，如果 $U, V \in M_{\kappa}$ 是酉矩阵，且采用谱范数（或者任何其他酉不变范数），则 $\kappa(A) = \kappa(UA) = \kappa(AY) = \kappa(UAV)$ 。因此，一个给定矩阵的酉变换不会使它比原有的性态更加病态。这个论断为许多稳定数值线性代数算法奠定了基础。

练习证明总有 $\kappa(AB) \leqslant \kappa(A)\kappa(B)$ . $\kappa(\cdot)$ 是 $M_{n}$ 上的矩阵范数或向量范数吗？

利用上述这些条件同样可以对线性方程组解的精确性给出先验的界。假定希望解方程组

A r = b, A \in M _ {n}, b \in \mathbf {C} ^ {n} \tag {5.8.5}

但是，因为计算上的误差或数据不精确，实际上是解方程组

336

(A + E) \hat {x} = b, A, E \in M _ {n}, b \in \mathbf {C} ^ {\prime \prime}. \tag {5.8.6}

关于误差 $x \sim \hat{x}$ ，可以说些什么呢？

如果 $E$ 足够“小”，使得 $\rho(A^{-1}E) < 1$ ，则根据(5.8.1)有

\begin{array}{l} x - \hat {x} = A ^ {1} b - (A + E) ^ {1} b = \left[ A ^ {1} - (A + E) ^ {1} \right] b \\ = \sum_ {k = 1} ^ {3} (- 1) ^ {k + 1} (A ^ {- 1} E) ^ {k} A ^ {- 1} b = \sum_ {k = 1} ^ {3} (- 1) ^ {k + 1} (A ^ {- 1} E) ^ {k} x. \\ \end{array}

如果 $\| \cdot \|$ 是矩阵范数，且 $|A^{-1}E| < 1$ ，又如果 $\| \cdot \|$ 是相容向量范数，则关于误差的范数的上界是

\| x - \hat {x} \| \leqslant \sum_ {k = 1} ^ {\infty} \| A ^ {1} E \| ^ {k} \| x \| = \frac {\| A ^ {1} E \|}{1 - \| A ^ {- 1} E \|} \| x \|.

关于相对误差，这说明，如果 $\| A^{-1}E\| < 1$ ，且 $\| \cdot \|$ 是与矩阵范数 $\| \cdot \|$ 相容的矩阵范数，则

\frac {\| x - \hat {x} \|}{\| x \|} \leqslant \frac {\left| A ^ {- 1} E \right|}{1 - \left| A ^ {- 1} E \right|}. \tag {5.8.7}

值得注意的是，这与关于矩阵逆的相对误差的上界(5.8.2)是相同的，且与线性方程组的右边 $b$ 无关.

利用 $A$ 的条件数，用来推导(5.8.4)的证明同样可以证明，如果 $\| A^{-1} \| |E| < 1$ ，且向量范数 $\|\cdot\|$ 与矩阵范数 $\|\cdot\|$ 相容，则(5.8.5)的解的相对误差有界

337

\frac {\| x - \bar {x} \|}{\| x \|} \leqslant \frac {\kappa (A)}{1 - \kappa (A) (\| E \| / \| A \|)} \frac {\| E \|}{\| A \|}. \tag {5.8.8}

无论采用什么算法来解线性方程组(5.8.5)，它的解的相对误差与其系数矩阵的逆的相对误差有相同的界.

像标准线性方程组(5.8.5)的系数矩阵 $A$ 的元素一样，它的右边 $\pmb{b}$ 的元素也可能产生误差，影响方程组的解，于是想用

(A + E) \hat {x} = b + e \tag {5.8.9}

代替(5.8.6)，其中 $E \in M_{n}$ 和 $e \in \mathbb{C}^{n}$ 看成是“小”的数据误差。

采用相同的方法，在关于(5.8.8)的相同假设下，（如果 $b \neq 0$ ）求得(5.8.5)的解与(5.8.9)的解之间的相对误差为

\frac {\| x - \hat {x} \|}{\| x \|} \leqslant \frac {\kappa (A)}{1 - \kappa (A) (\| E \| / \| A \|)} \frac {\| E \|}{\| A \|} + \frac {\kappa (A)}{1 - \kappa (A) (\| E \| / \| A \|)} \frac {\| e \|}{\| b \|} \tag {5.8.10}

这样，相对误差界有两项，一项是关于系数矩阵 $A$ 的相对误差界，一项是关于右边 $b$ 的相对误差界。在确定关于解误差的界对数据误差的界的灵敏度方面，条件数 $\kappa(A)$ 仍然起着决定性的作用。

至此，我们的所有估计式都有一个先验的误差界；它们不涉及所计算出的解或者由它导出的任何量。但是，假定通过计算已经求出方程组(5.8.5)的某个“解” $x$ 。恰好有 $A\hat{x} = b$ 的情形往往是不可能的，不过，可以从剩余向量 $r \equiv b - A\hat{x}$ 得到 $\hat{x}$ 与真解 $x$ 如何接近的估计式。因为 $A^{-1}r = A^{-1}[b - A\hat{x}] = A^{-1}b - \hat{x} = x - \hat{x}$ ，所以有简明的界 $\|x - \hat{x}\| \leqslant \|A^{-1}r\|$ 。如果 $\|\cdot\|$ 是与

向量范数 $\| \cdot \|$ 相容的矩阵范数，则我们有 $\| b \| = \| Ax \| \leqslant \| A \| \| x \|$ ，或者当 $b \neq 0$ 时， $1 \leqslant \| A \| \| x \| / \| b \|$ ，因而

\| x - \hat {x} \| \leqslant \| A ^ {- 1} \| \| r \| \leqslant \frac {\| A \| \| x \|}{\| b \|} \| A ^ {- 1} \| \| r \| = \| A \| \| A ^ {- 1} \| \frac {\| r \|}{\| b \|} \| x \|.

因此，如果 $b \neq 0$ ，计算出的 $\hat{r}$ （适合 $A\hat{x} = b - r$ )与真解 $x$ （适合 $Ax = b$ )间的相对误差有界

\frac {\| x - \hat {x} \|}{\| x \|} \leqslant \kappa (A) \frac {\| r \|}{\| b \|}, \tag {5.8.11}

其中，假定用来计算条件数 $\kappa(A)$ 的矩阵范数是与向量范数 $\|\cdot\|$ 相容的。对于良态问题，解的相对误差不会比剩余向量的相对大小（更）坏；对于病态问题，即使计算出的解产生一个小的剩余向量，它仍然可能与真解相差很大。

关于误差的范数估计的最后一个注释，我们指出，本节所导出的各个上界仅仅是上界而已。尽管上界可能很大，但是实际误差仍然可能很小。这些界的一个共同特征是它们的保守性：它们给出的误差界对许多问题未免太笼统了。但是，如果一个有适当阶数的矩阵 $A$ 具有适当大小的各元素，且有较大的条件数，则 $A^{-1}$ 一定有某些大元素，于是，对下述理由多加考虑是有益的。

如果 $Ax = b$ ，且令 $C = [c_{ij}] \equiv A^{-1}$ ，那么，关于元 $bj$ 微分恒等式 $x = Cb$ 便得恒等式

\frac {\partial x _ {i}}{\partial b _ {i}} = c _ {v}, i, j = 1, 2, \dots , n. \tag {5.8.12}

另外，把 $C = A^{-1}$ 看成 $A$ 的函数，则它的各元只是 $A$ 的各元的有理函数，因而可微。恒等式 $CA = I$ 表明，对所有 $i, q = 1, \dots, n$ ，有

\sum_ {p = 1} ^ {n} c _ {i p} a _ {p i} \simeq \delta_ {k},

因而

\sum_ {p = 1} ^ {n} \left[ \frac {\partial c _ {i p}}{\partial a _ {j k}} a _ {p q} + \delta_ {p q, j k} c _ {i p} \right] - \left[ \sum_ {p = 1} ^ {n} \frac {\partial c _ {i p}}{\partial a _ {j k}} a _ {p q} \right] + \delta_ {q k} c _ {i j} = 0,

或

\sum_ {p = 1} ^ {n} \frac {\partial c _ {i p}}{\partial a _ {j k}} a _ {p k} = - \delta_ {q k} c _ {i j}, i, j, k = 1, \dots , n.

现在关于 $a_{jk}$ 微分恒等式 $x = Cb$ 使得

\begin{array}{l} \frac {\partial x _ {i}}{\partial a _ {j k}} = \sum_ {p = 1} ^ {n} \frac {\partial x _ {i p}}{\partial a _ {j k}} b _ {p} = \sum_ {p = 1} ^ {n} \sum_ {q = 1} ^ {n} \frac {\partial x _ {i p}}{\partial a _ {j k}} a _ {p i} x _ {q} \\ = \sum_ {q = 1} ^ {n} \left[ \sum_ {p = i} ^ {n} \frac {\partial c _ {i p}}{\partial a _ {j k}} u _ {i q} \right] x _ {i j} = \sum_ {q = 1} ^ {n} \left[ - \delta_ {a k} c _ {i j} \right] x _ {q} = - c _ {i j} x _ {k}, \\ \end{array}

它是恒等式

\frac {\partial x _ {i}}{\partial a _ {j k}} = - c _ {i j} \sum_ {p = 1} ^ {n} c _ {k p} b _ {p}. \tag {5.8.13}

因此，(5.8.12)和(5.8.13)同时提醒我们，如果 $C = A^{-1}$ 有相对大的任意元素，则解 $\pmb{x}$ 的某个元素对 $\textit{\textbf{b}}$ 和A的某些元素的扰动就可能有难以避免的较大灵敏度.

习题

证明非奇异正规矩阵的逆关于谱范数的条件数是

\kappa (A) = \rho (A) \rho (A ^ {1}) = | \lambda_ {\max } (A) / \lambda_ {\min } (A) |.

求矩阵

A = \left[ \begin{array}{c c} 1 & - 1 \\ - 1 & 1 + \varepsilon \end{array} \right], \varepsilon > 0

的特征值和逆矩阵。证明，当 $\varepsilon \to 0$ 时， $A$ 的最大特征值与最小特征值之比为数量级 $\varepsilon^{-1}$ 。试用习题1证明，关于谱范数有 $\kappa(A) = O(\varepsilon^{-1})$ 。证明，关于任意范数有 $\kappa(A) = O(\varepsilon^{-1})$ ，因而对于求逆来说， $A$ 是病态的。试用 $A$ 的显示形式证明，对任何范数有 $\kappa(A) = O(\varepsilon^{-1})$ 。

求矩阵

B = \left[ \begin{array}{l l} 1 & - 1 \\ 1 & 1 + \varepsilon \end{array} \right], \varepsilon > 0

的特征值和逆矩阵。证明，当 $\varepsilon \to 0$ 时， $B$ 的最大特征值与最小特征值之比为数量级1。但是证明，关于任何矩阵范数有 $\kappa(B) = O(\varepsilon^{-1})$ ，因而当 $\varepsilon \to 0$ 时，对于求逆来说， $B$ 是病态的。由此可知，最大模特征值与最小模特征值之比不一定是非正规矩阵的条件数。

矩阵逆的条件数 $\kappa(A)$ 依赖于所采用的矩阵范数，但是可以证明，所有条件数在下述意义下是等价的：如果 $\kappa_{\alpha}(A) = \| A^{-1} \|_{\alpha} \| A \|_{\alpha}$ ，且 $\kappa_{\beta} = |A^{-1}|_{\beta} \| A \|_{\beta}$ ，则存在有正常数 $C_m$ 和 $C_M$ 使得

C _ {m} \kappa_ {\alpha} (A) \leqslant \kappa_ {\beta} (A) \leqslant C _ {M} \kappa_ {\alpha} (A)

对所有 $A \in M_{n}$ 成立.

证明，关于谱范数，每个酉矩阵 $U$ 对于求逆是优态的 $[\kappa(U) = 1]$ ，但是，如果采用 $l_{2}$ 范数，每个内矩阵 $U \in M_{n}$ 的条件数 $\kappa(U)$ 是 $n$ 。
证明，对任意非奇异矩阵 $A \in M_{n}$ 和任意矩阵范数有 $\kappa(A) \geqslant |\lambda(A)|_{\max} / |\lambda(A)|_{\min}$ （ $\max$ 和 $\min$ 在这种情形是指特征值的极大模和极小模）。因此，如果这个特征值的比是大的，则该矩阵对于求逆一定是病态的，而不管它是否为正规矩阵。但是习题3说明，如果矩阵不是正规阵，即使这个比不大，它仍可能是病态的。
试对界(5.8.8)的推广(5.8.10)给出详细证明，当 $e = 0$ 时，界(5.8.10)就简化成(5.8.8).
设 $x$ 是 $\mathbf{C}^n$ 中的单位向量，且设 $\lambda > 0$ ，证明 $A \equiv I + \lambda xx^*$ 是Hermite矩阵，且有 $(n - 1)$ 重特征值1和特征值 $1 + \lambda$ 。证明： $\kappa(A) = 1 + \lambda$ （关于谱范数），于是，这给出了产生可逆矩阵的简单方法，且使该矩阵具有有界元素和任意大的条件数。为什么？
设 $B$ 是习题3中的矩阵，考虑具有精确解 $x = [1, 0]^T$ 的线性方程组 $Bx = [1, 1]^T$ 及其近似解 $\hat{x} = [1 + \varepsilon^{1/2}, \varepsilon^{1/2}]^T$ 。证明，当 $\varepsilon \to 0$ 时；剩余向量的相对误差为 $\|r\| / \|b\| = O(\varepsilon^{1/2}) \to 0$ ；但是，当 $\varepsilon \to 0$ 时，解的相对误差为 $\|x - \hat{x}\| / \|x\| = O(\varepsilon^{-1/2}) \to \infty$ 。这样，有大误差的近似解可以产生小的剩余向量。试用界(5.8.11)来说明。
如果 $\det A$ 是小的（或大的）， $\kappa(A)$ 就一定大吗？提示：考虑 $A = \lambda I \in M_n$
一般，(5.8.4)的结果比(5.8.2)的要弱，这是因为假设条件 $\| A^{-1} \| E \| < 1$ 比 $\| A^{-1} E \| < 1$ 有更强的限制。不过，即使较强的假设条件被满足，(5.8.2)仍然可以给出比(5.8.4)较好的上界。试用 $E = \varepsilon A$ ， $0 < \varepsilon < 1$ ，作出说明。
如果方程(5.8.5)和(5.8.6)用

A X - B \quad {\text {和}} \quad (A + E) {\hat {X}} - B

来代替，其中， $A$ ， $E\in M_{n}$ ，而 $X$ ， $B\in M_{n,k}$ ，求关于界(5.8.7)和(5.8.8)的类似界．考虑 $k = n$ 和 $B = I$ 的特殊情形；这有助于“说明”为什么(5.8.2)中与(5.8.7)中的上界是相同的吗？

我们已经导出的矩阵逆的误差的各个界都依赖于(5.8.1)，它要求 $\rho(A^{-1}E) < 1$ 。证明，如果 $A$ 和 $A + E$ 都是可逆矩阵，则不论 $A^{-1}E$ 的阶数如何，

\left\| A ^ {- 1} \quad (A + E) ^ {- 1} \right\| \leqslant \left\| A ^ {- 1} \right\| \left\| (A + E) ^ {- 1} \right\| | E |

对任何矩阵范数 $|\cdot \cdot \cdot |$ 都成立，提示：证明 $A\quad (A + E)^{-1} = (A + E)$ EA.

或许被引用得最多的病态矩阵的例子是用 $h_{ij} = 1 / (i + j - 1)$ 定义的 Hilbert 矩阵 $H_{n} = [h_{ij}] \in M_{n}$ . 证明 $H_{n}$ 关于谱范数的条件数是用 $\lambda_{\max} / \lambda_{\min}$ 给出的. 其事实是 $H_{n}$ 的条件数是渐近地等于 $e^{m}$ , 其中常数 $c$ 大约是 3.5, 另一个事实是当 $n \to \infty$ 时 $\rho(H_{n}) = \pi + O[1 / (\log n)]$ . 我们有 $\kappa(H_{d}) \sim 5 \times 10^{2}$ , $\kappa(H_{6}) \sim 1.5 \times 10^{7}$ 和 $\kappa(H_{8}) \sim 1.5 \times 10^{10}$ . 说明, 即使 $II_{n}$ 的各元都一致有界 $[I, \rho(H_{n})]$ 不是很大, 为什么 $H_{n}$ 还是坏条件的.
如果采用谱范数，证明 $\kappa(A^{*}A) = \kappa(AA^{*}) = [\kappa(A)]^{2}$ ，试说明，为什么采用数值方法解 $A^{*}Ax = y$ 的问题可能不会比解 $Ax = z$ 的问题真正来得容易。
设 $A \in M_{n}$ 是非奇异矩阵。试用(5.6)节37题中的不等式证明 $\kappa(A) \geqslant \|A\| / \|A - B\|$ 对任一奇异矩阵 $B \in M_{n}$ 成立。这里 $\|\cdot\|$ 是任一矩阵范数，而 $\kappa(\cdot)$ 是相应的条件数。这个下界可以用来证明一个给定矩阵 $A$ 是病态的。
设 $A = [a_{ij}] \in M_n$ 是所有 $a_{n} \neq 0$ 的上三角矩阵，试用习题16证明关于极大行和范数的条件数有下界

\kappa (A) \geqslant \frac {\left| A \right\|}{\min _ {1 \leqslant i \leqslant n} \left| a _ {u} \right.}.

进一步阅读在解线性方程组时求误差的先验界的问题已是数值线性代数的一个中心问题；见[Ste].

5.8_矩阵的逆和线性方程组的解的误差

5.8 矩阵的逆和线性方程组的解的误差

习题