3.5 三角分解

如果线性方程组 $Ax = b$ 有一个非奇异三角(0.9.3)系数矩阵 $A \in M_{n}$ ，那么计算它的唯一解 $x$ 是相当容易的。例如，如果 $A$ 是上三角矩阵

158

那么 $\det A = a_{11}a_{22}\dots a_{nn}\neq 0$ ，然后利用后向替换： $a_{m}x_{n} = b_{n}$ 确定 $x_{n};a_{n - 1,n - 1}x_{n - 1} + a_{n - 1,n}x_{n} -$ $b_{n - 1}$ 是含一个未知数的方程，它确定 $x_{n - 1}$ ；一般，方程组

中的每一个是含一个未知数的方程（只要 $x_{i+1}, \cdots, x_n$ 已被确定），它确定 $x_1$ .

练习 设 $A \in M_{n}$ 是非奇异上三角矩阵，如果采用后向替换，试算出解 $Ax = b$ 所必需的纯量乘法和除法运算的次数.

练习 如果 $A \in M_{n}$ 是非奇异下三角矩阵，写出作为 $Ax = b$ 的一个解法的前向替换。

设 $A \in M_{n}$ 是非奇异矩阵，但不是三角矩阵，应指出的是，如果 $A$ 是用形如

的分解形式给出的，其中， $L$ 是下三角矩阵， $U$ 是上三角矩阵，那么解出 $Ax = b$ 可以说是很简便的。

练习 如果 $A = LU$ 如上所述且非奇异，证明， $L$ 和 $U$ 都必须是非奇异的，因而必须有非零对角元.

为了解 $A_{r - 1} = b$ ，可以先用前向替换解

然后用后向替换解

且所需计算量只是系数矩阵为简单的三角矩阵时的两倍。因此，如果得到分解 $LU$ 所需计算量不太大，那么这种分解对解线性方程组是有用的。在这里叙述它们也是适宜的，因为它们的形式特殊，而把一个矩阵分解成这种形式可以不用特征值，而是利用线性方程组。

3.5.1 引理 假定 $A \in M_{n}$ 可以写成

其中 $L \in M_{n}$ 是下三角矩阵，而 $U \in M_{n}$ 是上三角矩阵。对任一分块形式

其中 $A_{11}, L_{11}, U_{11} \in M_k, k \leqslant n$ ，我们有

且

特别是， $L$ 和 $U$ 的左上角子块一定构成 $A$ 的相应子块的一个同型的分解.

练习 用分块乘法运算验证(3.5.1).

3.5.2 定理 假定 $A \in M_{n}$ ，且 $\operatorname{rank} A = k$ 。如果

那么 $A$ 可以分解成

其中， $L \in M_{n}$ 是下三角矩阵， $U \in M_{n}$ 是上三角矩阵，并且可以适当选择分解使得 $L$ 或 $U$ 是非奇异的； $L$ 和 $U$ 都可以选取非奇异矩阵，当且仅当 $k = n$ ，即当且仅当 $A$ 是非奇异的。

证明：首先证明，在关于前主子式的假设条件下， $A(\{1, \cdots, k\})$ 可以分解成 $L(\{1, \cdots, k\})U(\{1, \cdots, k\})$ ，且它们都是非奇异的。能够逐个地求出 $L$ 和 $U$ 的各相关元素。设 $L = [l_{n}]$ 且 $U = [u_{ij}]$ 。令 $u_{11} = 1$ 且令 $l_{i1} = a_{i1}$ ， $i = 1, \cdots, k$ 。求出

继续做下去，令 $u_{22} = 1$ ，且令 $l_{i} = a_{i2} - l_{i1}u_{12}$ ， $i = 2,\dots ,k$ ，求出

160

再继续下去，依次设 $U$ 的各对角元为1，然后求出 $L(\{1, \cdots, k\})$ 的下-列和 $U(\{1, \cdots, k\})$ 的下一行。每次都有一个含一个未知数的方程需要求解。因为每个 $l_n$ 不为零[因为根据(3.5.1)， $\det L(\{l, \cdots, i\}) \times \det U(\{1, \cdots, i\}) = \det A(\{1, \cdots, i\})$ ，所以这个方程将是可解的。这就完成了 $A(\{1, \cdots, k\})$ 的分解。

将 $A$ 如(3.5.1)中那样分块，因为 $\operatorname{rank} A = k = \operatorname{rank} A_{11}$ ，由此可知 $[A_{21}A_{22}]$ 的各行是 $[A_{11}A_{12}]$ 的诸行的唯一线性组合，即对每个唯一确定的 $B \in M_{n,k,k}$ ，有

现在将欲求的 $L$ 和 $U$ 同样如(3.5.1)中那样分块，注意到非奇异的 $L_{11}$ 和 $U_{11}$ 已被确定。于是可以用(3.5.1)求出

然后求出

为了完成分解，必需而且只需

例如，可以选取 $L_{22}$ （相应地， $U_{22}$ ）为 $M_{n - k}$ 中的任一非奇异下（相应地，上）三角矩阵，希望选取 $U_{22}$ （相应地， $L_{22}$ ）为0．因为 $L_{11}$ 和 $U_{12}$ 是非奇异的， $L$ 或 $U$ 可以选为非奇异的．如果 $k = n$ ， $L = L_{11}$ 和 $U = U_{11}$ 就是可非奇异的；如果 $k < n$ ，因为 $A$ 是奇异的， $L$ 和 $U$ 不可能都是非奇异的．这就完成了证明. □

3.5.3 例 不是每个矩阵都有一个LU分解，考虑

如果 $A$ 可以写成

$l_{11}U_{11} = 0$ 将要求 $L$ 或 $U$ 是奇异的，但是 $LU - A$ 是非奇异的.

练习 证明，一个非奇异矩阵的左上角有一个 $k \times k$ 奇异主子阵，它就不可能有 LU 分解。

161

3.5.4 例 $A \in M_{n}$ 可以有 LU 分解而不满足 (3.5.2) 的主子式条件。例如

有秩1，但是它的1，1元是0.

练习（3.5.4）中的 $LU$ 的分解是不唯一的，即使要求 $U$ 的各对角元都为1．试写出 $\left[ \begin{array}{ll}0 & 0\\ 1 & 2 \end{array} \right]$ 的其他几种分解.

现在已经很清楚了，一个已知矩阵的 $LU$ 分解是不唯一的，它可能存在，或可能不存在。不过，这许多麻烦，或者是由 $A$ 的奇异性，或者是由 $A$ 的前主子阵的奇异性引起的。然而可以采用(3.5.1)和(3.5.2)的方法，对非奇异的情形给出一个完美的描述，并且可以利用规范化使分解是唯一的（标准的）。

3.5.5推论 假定 $A\in M_n$ 是非奇异的．那么， $\pmb{A}$ 可以写成

且使 $L \in M_{n}$ 是下三角矩阵和 $U \in M_{n}$ 为上三角矩阵，当且仅当

此外， $L$ 和 $\pmb{U}$ 是非奇异的，而分解实质上是唯一的，矩阵A可以写成

其中， $L^{\prime}$ （相应地， $\mathbf{U}^{\prime})\in M_{n}$ 是所有对角元等于1的下（相应地，上）三角矩阵，而 $D$ 是由

所确定的非奇异对角矩阵. 因子 $L^{\prime}, U^{\prime}$ 和 $D$ 被 $\Lambda$ 唯一确定.

练习 利用(3.5.1)，（3.5.2）和前一个练习，详细证明(3.5.5).

再回到线性方程组

162

的解法，假定 $A \in M_{n}$ 不能分解成 $LU$ ，但能分解成 $PLU$ ，其中， $P \in M_{n}$ 是置换矩阵(0.9.5)，而 $L$ 和 $U$ 如前，是下三角矩阵和上三角矩阵。这相当于在分解之前重排各个方程，在这种情形， $Ax = b$ 的解法仍然是相当简单的，只要作替换

就是了。应当知道，任一非奇异的 $A \in M_{n}$ 都可以这样分解，而且任一 $A \in M_{n}$ 可以分解成 $PLUQ$ ，其中 $Q \in M_{n}$ 也是一个置换矩阵。

3.5.6 引理 设 $A \in M_{n}$ 是非奇异矩阵。那么，存在一个置换矩阵 $P \in M_{k}$ ，使得

注意， $P^i A$ 正好是 $A$ 的各解的一个重排

证明：证明是对 $k$ 作归纳法。如果 $k = 1$ 或 2，经过验证，结论显然成立；假定结论一直到 $k - 1$ 都是正确的。考虑非奇异矩阵 $A \in M_k$ ，并且去掉它的最后一列。余下的 $k - 1$ 列是线性无关的，因而含有 $k - 1$ 个线性无关解。把这些解调换到前 $k - 1$ 个解的位置，然后对位于上方的非奇异的 $(k - 1) \times (k - 1)$ 子矩阵应用归纳假设。这就确定了一个欲求的整个置换矩阵。因为 $P^{\prime}A$ 是非奇异的，所以证明完毕。

3.5.7 定理 设 $A \in M_{n}$ , 则存在置换矩阵 $P, Q \in M_{n}$ , 下三角矩阵 $L \in M_{n}$ 和上三角矩阵 $U \in M_{n}$ , 使得

如果 $A$ 是非奇异矩阵，可以取 $Q = I$ ，且 $A$ 可以写成

证明：如果 $\operatorname{rank} A = k$ 则 $A$ 有一个 $k \times k$ 非奇异子矩阵(0.4.4d)，它可以通过互换 $A$ 的各行和各列调换到左上角的位置。现在把(3.5.6)应用于左上角，再应用(3.5.2)便得到第一型式的分解。如果 $A$ 是非奇异的，(3.5.6)表明，为应用(3.5.2)，右边的置换矩阵是不必要的，这说明第二个分解是正确的，证毕。

习题

1. 本节所提出的理论是就 $LU$ 分解而论的，其中 $L$ 是下三角矩阵， $U$ 是上三角矩阵。试说明，可以平行地提出 $UL$ 分解的理论，但这两个因子一般与 $LU$ 分解的因子不相同。

2. 从(2.6)节习题3可知，任一 $A \in M_{n}$ 的QR分解可以有效地经 $n - 1$ 次Housholder交

换得到。这里， $Q$ 是酉矩阵，而 $R$ 是上三角矩阵。如果 $A$ 分解成QR形，试描述可以怎样解出 $Ax - b$ 。

1. 证明， $A \in M_{1}$ 可以写成

其中 $L \in M_{n}$ 是非奇异下三角矩阵， $U \in M_{n}$ 是非奇异上三角矩阵，而 $P_{\nu}$ 是一个次置换矩阵[当 $\operatorname{rank} A < n$ 时，置换矩阵中的一些元素1换成元素0，使其元素1的个数与 $\operatorname{rank} A$ 相同]。提示：进行初等行变换和初等列变换。

1. 如果 $A \in M_{n}$ 的所有前主子式都非零，试描述如何运用第二种初等行变换将 $A$ 的对角线下方的各个元素都化成零，从而使 $A$ 有 LU 分解。

5.（Lanczos-对角化算法.）设 $A \in M_{n}$ 和 $x \in \mathbb{C}^{n}$ 都是给定的，定义 $X = [x A x A^{2} x \cdots A^{n-1} x]$ . 称 $X$ 的诸列构成一个 krylov 序列。假定 $X$ 是非奇异的。（a)证明 $X^{-1}AX$ 是 $A$ 的特征多项式的友矩阵(3.3.12). (b)若 $R \in M_{n}$ 是任意一个给定的非奇异上三角矩阵且 $S \equiv XR$ ，证明 $S^{-1}AS$ 向上 Hessenberg 形式。（c)设 $y \in \mathbb{C}^{n}$ 且定义 $Y = [yA^{*}y(A^{*})^{2}y \cdots (A^{*})^{n-1}y]$ ，假定 $Y$ 是非奇异的且 $Y^{*}X$ 可以写成 $LDU$ ，其中， $L$ 是下一三角矩阵， $U$ 是上三角矩阵，且都是非奇异的，而 $D$ 是对角矩阵且是非奇异的。证明，存在非奇异上三角矩阵 $R$ 和 $T$ ，使得 $(XR)^{-1} = T^{-1}Y^{*}$ 且使 $T^{-1}Y^{*}AXR$ 是相似于 $A$ 的三对角矩阵。（d)若 $A \in M_{n}$ 是 Hermite 矩阵，利用上述思路确定一个算法来得到一个相似于 $A$ 的三对角 Hermite 矩阵。

1. 两个矩阵 $A, B \in M_{m,n}$ 称为等价，指的是存在非奇异矩阵 $S \in M_m$ 和 $T \in M_n$ ，使得

(a) 证明这个等价概念是 $M_{m,n}$ 上的一个等价关系. (b) 证明, 每个矩阵 $A \in M_{m,n}$ 等价于一个形如 $\left[ \begin{array}{cc} I & 0 \\ 0 & 0 \end{array} \right] \in M_{m,n}$ 的矩阵. $I \in M_{k}, k \leqslant \min \{m, n\}$ . 提示: 利用初等行变换得到行简化梯形, 然后对所得到的矩阵采用初等列变换. (c) 证明, $M_{m,n}$ 中的两个矩阵等价, 当且仅当它们有相同的秩. (d) 假定 $A \in M_{m,n}$ 等价于 (b) 中所述的特殊形式, $S\left[ \begin{array}{cc} I & 0 \\ 0 & 0 \end{array} \right]T = A$ . 试用等价性阐述关于线性方程组 $Ax = b$ 的解理论.

进一步阅读上述习题5是从[Ste]改编过来的，在[Ste]中还可以找到关于LU分解的数值应用的其他资料.