2.6 QR分解和QR算法

为一个给定的矩阵 $A \in M_{n}$ 提供一种 Schur 酉上三角化 (2.3.1) 的特殊计算方法, 以及 (在某些假设下) 计算特征值的一个通用的数值方法, 称为 QR 算法, QR 算法基于一般矩阵 $A \in M_{n,m}$ 的所谓 QR 分解.

2.6.1 定理 (QR 分解) 如果 $A \in M_{n,m}$ 且 $n \geqslant m$ , 那么存在有标准正交列的矩阵 $Q \in M_{n,m}$ 和上三角矩阵 $R \in M_{m}$ , 使得 $A - QR$ . 如果 $n = m$ , 那么 $Q$ 是酉矩阵; 此外, 如果 $A$ 是非奇异矩阵, 则可以选取 $R$ 为具有正对角元的上三角矩阵, 并且在这种情形, 因子 $Q$ 和 $R$ 都是唯一的. 如果 $A \in M_{n,m}(\mathbf{R})$ , 那么 $Q$ 和 $R$ 都可以取实矩阵.

证明：如果 $A \in M_{n,m}$ ，且 $\operatorname{rank} A = m$ ，则 $A$ 的各列构成 $\mathbf{C}^n$ 的一个无关组，把 Gram-Schmidt 过程(0.6.4)应用于 $A$ 的各列，用矩阵记号描述所得结果正是 $A$ 的 QR 分解。Gram

Schmidt算法的自然推广使同样的矩阵记号描述能够应用于 $A$ 的各列可能是相关的一般情形. 设 $A = [a_{1} \cdots a_{m}]$ 写成了以它的列 $a_{i} \in \mathbb{C}^{n}$ 为子块的分块形式. 如果 $a_{1} = 0$ , 令 $q_{1} = 0$ ; 否则令 $q_{1} = a_{1} / (a_{1}^{*} a_{1})^{1/2}$ . 对每个 $k = 2, 3, \cdots, m$ , 如同在通常的 Gram-Schmidt 过程中那样, 算出

如果 $y_{k} - 0$ （它成立，当且仅当 $\pmb{a}_{k}$ 是 $a_1,a_2,\dots ,a_{k - 1}$ 的线性组合），则令 $q_{k} = 0$ ；否则令 $q_{k} = y_{k} / (y_{k}^{*}y_{k})^{1 / 2}$ ，这时，向量 $q_{1},\dots ,q_{m}$ 是正交组，其中的每个元素或者是单位向量，或者是零向量．每个向量 $q_{j}$ 是 $a_1,\dots ,a_j$ 的线性组合，反过来，上述做法保证每个列 $a_{j}$ 是 $q_{1},\dots ,q_{i}$ 的线性组合．因此存在纯量 $\pmb{r}_{kj}$ 使得

如果对所有 $k > j$ ，令 $r_{kj} = 0$ ，而对于所有使 $q_i = 0$ 的每个 $i$ ，对所有 $j = 1, 2, \dots, m$ ，令 $r_{ij} = 0$ ，那么，经过上述过程，上三角矩阵 $R = [r_{ij}] \in M_m$ 和向量 $q_1, q_2, \dots, q_m$ 由 $a_1, a_2, \dots, a_m$ 所确定。矩阵 $Q \equiv [q_1, \dots, q_m] \in M_{m,m}$ 有正交列（其中有些可能是零），因而(2.6.2)表明 $A = QR$ .

如果 $\operatorname{rank} A = m$ ，则 $Q$ 有标准正交列，因而所要求的分解形式已经得到。特别地，如果 $m = n$ ，且 $A$ 是非奇异矩阵，那么，根据(2.1.4e)， $Q$ 必须是酉矩阵，而非奇异矩阵 $R = Q^{*}A$ 的诸对角元必须是非零的。在这种情形，因为要求 $R$ 是上三角矩阵，故 $q_{1}$ 是 $a_{1}$ 的纯量倍数，并且对于 $i = 2, \cdots, n, q_{i}$ 位于这样一个二维空间内，它在由 $a_{1}, \cdots, a_{i}$ 生成的空间中是 $a_{1}, \cdots, a_{i}$ ，生成空间的正交补。因此，除了差一个绝对值为 1 的比例因子以外，每个 $q_{i}$ 是唯一确定的。于是用 $R' \equiv \mathrm{diag}(|r_{11}| / r_{11}, \cdots, |r_{mn}| / r_{mn}) R$ 代替 $R$ 以及用 $Q' \equiv Q \mathrm{diag}(r_{11} / |r_{11}|, \cdots, r_{mn} / |r_{mn}|)$ 代替 $Q$ ，便给出唯一的分解 $A = Q'R'$ ，这正是定理的叙述中所断言的。

如果 $A$ 的各列不是无关的，取由 $Q$ 的非零列组成的（标准正交）组，然后把它扩充为 $\mathbf{C}$ 的一个标准正交基；用上述方法得来的新向量记作 $z_{1}, z_{2}, \cdots, z_{p}$ 。现在，用 $z_{1}$ 代替 $Q$ 的第1个零列，用 $z_{2}$ 代替第2个零列，如此做下去，直到所有零列都被这种方式所取代；用 $Q'$ 表示所得到的矩阵。因为 $Q'$ 的新列与 $R$ 的零行相对应，于是 $Q'$ 有标准正交列，且 $QR = Q'R$ ，因此 $A = Q'R$ 是所要求的分解式。

如果 $A$ 是实矩阵，注意到所有必要的运算都可经实的运算来完成，因而所得到的因子是实矩阵. □

练习 如果 $A \in M_{n,m}$ ，且 $n \leqslant m$ ，证明， $A$ 可以分解成 $A = LP$ ，其中， $L \in M_n$ 是下三角矩阵，而 $P \in M_{n,m}$ 具有标准正交行；至于其余的论断，这个分解有与(2.6.1)相平行的叙述。

练习 证明，任一个形如 $B = A^{*}A$ 的矩阵 $B \in M_{n}$ （其中 $A \in M_{n}$ ）都可以写成 $B = LL^{*}$ ，其中 $L \in M_{n}$ 是具有非负对角元的下三角矩阵，并证明，如果 $A$ 是非奇异矩阵，那么这个分解是唯一的。称这个分解为 $B$ 的 Cholesky 分解；每个正定矩阵都可以按这种方式分解（见第7章）。提示：写出 $A = QR$ 。

QR分解有重要的数值意义[例如，（2.6.3)]，然而作为一种理论方法，它同样是有价值的。例如，已知矩阵 $A \in M_{n}$ 经酉相似的上三角化，可以直接从它的通常的相似上三角化得到。

112

113

如果 $S^{-1}AS = T$ 是上三角矩阵，且如(2.6.1)中， $S - QR$ ，那么 $R^{-1}Q^{*}AQR = T$ 且 $Q^{*}AQ = RTR^{-1}$ ，而它作为上三角矩阵的乘积仍是上三角矩阵。用同样的方式可以推出，有关同时三角化的定理，例如(2.4.15)，实际上是同时两三角化定理。这就是说，如果 $M_{n}$ 中的某个矩阵族可经相似同时三角化，那么它同样可经西等价同时三角化。

下面，不加证明地叙述计算特征值的QR算法，并简要地说明它的某些特性。

2.6.3 QR 算法 设 $A_{ij} \in M_{n}$ 已知，写出 $A_{ij} - Q_{ij}R_{i}$ ，其中 $Q_{ij}$ 和 $R_{ij}$ 如(2.6.1)所示，然后定义 $A_{ij} = R_{ij}Q_{ij}$ ，再写出 $A_{ij} - Q_{ij}R_{i}$ ，其中 $Q_{ij}$ 是酉矩阵，而 $R_{ij}$ 是上三角矩阵，这样继续做下去，一般地，如果因子 $A_{ii} = Q_iR_i$ ，就定义 $A_{k-1} = R_kQ_k$ .

练习 证明，用QR算法得到的每个 $A_{k}$ 西等价于 $A_{1}, k = 1, 2, \cdots$

在某些情形（例如，如果 $A_{ii}$ 的所有特征值有不同的绝对值），当 $k \to \infty$ 时，QR迭代值 $A_{k}$ 将收敛于一个上三的矩阵，因为这个上三角矩阵西等价于 $A_{ii}$ ，所以 $A_{ii}$ 的各特征值便被计算出来。

如果 $A_{0}$ 是实矩阵， $QR$ 迭代值 $A_{k}$ 可以通过实的运算来计算。如果 $A_{0}$ 有非实特征值，那么就不能指望 $QR$ 迭代值会收敛于一个上一角矩阵。这是因为这个上三角极限必须是实矩阵。不过，在某些情形，可以选取迭代值 $A_{k}$ ，使它们收敛于一个具有 $1 \times 1$ 和 $2 \times 2$ 主对角子块的实分块上三角矩阵。而出现这种情形的充分条件是，除了各个成双成对的非实复共轭特征值有相同的模以外， $A_{0}$ 的所有实特征值都有不同的模。因为分块三角矩阵的各特征值是诸对角子块特征值的集合之并，所以 $A_{0}$ 的特征值是作为 $QR$ 迭代值 $A_{k}$ 的分块一角极限的 $1 \times 1$ 对角元以及该极限的 $2 \times 2$ 对角子块的特征值（的复共轭对）而出现的，它们可以很容易地用实数运算和二次公式计算出来。

2.6.4 例 下述例子说明， $QR$ 算法不一定总收敛于一个三角矩阵。设

于是， $\sigma(A) = \{i\}$ ，特征值没有不同的模。如果 $A_{ij} = A$ ，这个算法的一个可能的序列是

另一个是

在这两种情形都出现了循环，因而序列 $\{A_k\}$ 不收敛于上三角矩阵。但是，存在 $\{A_k\}$ 的一个选择，它收敛于一个分块上三角矩阵。

习题

1. 设 $x_{1}, \cdots, x_{m}$ 是 $\mathbf{C}^{n}$ 中的给定无关向量组，且设 $X \equiv [x_{1}x_{2}\cdots x_{m}] \in M_{n,m}$ ，假定对向量 $x_{1}, \cdots, x_{m}$ 实施(0.6.4)中所描述的Gram-Schmidt过程得到标准正交组 $z_{1}, \cdots, z_{m}$ 且设 $Z \equiv |z_{1}\cdots z_{m}| \in M_{n,m}$ . (a) 对 $k = 1, 2, \cdots, m$ ，设 $Z_{k} = [z_{1}z_{2}\cdots z_{k}x_{k - 1}x_{k + 2}\cdots x_{m}]$ ，其中 $z_{k}$ 是经Gram-Schmidt过程的第 $k$ 步而得到的单位向量，因而 $Z_{m} = Z$ 。证明， $Z_{1} = X\Delta_{1}$ ， $Z_{2} = Z_{1}\Delta_{2}$ ，…， $Z_{m} = Z_{m - 1}\Delta_{m}$ ，其中，每个 $\Delta_{i}$ 都是非奇异上三角矩阵，而 $\Delta_{i} = I - \text{一个除第 } i$ 列以外其余各列全为零的上三角矩阵. (b) 设 $T_{i} = \Delta_{1}\Delta_{2}\cdots\Delta_{k}$ ， $k = 1, 2, \cdots, m$ 。说明 $T_{k}$ 是上三角矩阵且 $Z_{k} = XT_{k}$ ， $k = 1, 2, \cdots, m$ 。设 $T = T_{m}$ ，因而 $Z = XT$ 。（c）矩阵 $T$ 与定理(2.6.1)证明中的上三角矩阵 $R$ 之间的相互关系是什么？（d）证明，对 $j - k + 1, k + 2, \cdots, m$ ， $Z_{i}$ 和 $T_{i}$ 的前 $k$ 列不会变动，因此，(gram-Schmidt过程的第 $k$ 步就产生最终得到的矩阵 $Z$ 和 $T$ 的第 $k$ 列.

2. 设 $r_1, \cdots, r_m$ 是 $\mathbf{C}^n$ 中给定的线性无关向量组，又设 $X \equiv |x_1 \cdots x_n| \in M_{n,m}$ 。考虑下面的算法：

3. 令 $Z = X$ ，且记 $Z = [z_1 \cdots z_m]$ ，一开始先让每列 $z_i = x_i, i = 1, \cdots, m$ .

Ⅱ. 对 $k = 1, 2, \dots, m$ ，实施以下代换：

（1）首先，列 $z_{k}$ 用 $\left(z_{k}, z_{k}\right)^{1,2}$ 代替；
（ii）对 $j = k + 1, k + 2, \dots, m$ ，每列 $z_{i}$ 用 $z_{i} - (z_{i}, z_{k})z_{k}$ 代替.

我们用 $(x, y) = y^{\prime} x$ 表示 $\mathbf{C}^{n}$ 上的普通内积。（a）证明这个过程的最后结果是矩阵 $Z$ 具有标准正交列，它与习题1中用Gram-Schmidt过程得到的矩阵 $Z$ 是相同的。（b）若 $Z_{k}$ 表示该算法在第 $k$ 步中止时矩阵 $Z$ 的存储信息， $k - 1, 2, \dots, m$ ，证明 $Z_{1} - X\Delta_{1}, Z_{2} - Z_{1}\Delta_{2}, \dots, Z_{m} - Z_{m + 1}\Delta_{m}$ ；这里，每个 $\Delta_{i}$ 是一个非奇异上三角矩阵，其形式是 $\Delta_{i} - I - 1$ 个除第 $i$ 行以外其余各行全为零的上三角矩阵。（c）设 $T_{k} = \Delta_{1}\Delta_{2}\dots \Delta_{k}, k - 1, 2, \dots, m$ 。注意到 $T_{k}$ 是上三角矩阵，而 $Z_{k} = XT_{k}, k = 1, 2, \dots, m$ 。证明每个 $T_{k}$ 的前 $k$ 列与习题1中矩阵 $T_{i}$ 的前 $k$ 列是相同的，即使 $\Delta_{k}$ 和 $Z_{k}$ 可能各不相同。设 $T - T_{m}$ 。（d）证明，对 $j - k + 1, k \cdot 2, \dots, m, Z_{j}$ 和 $T_{j}$ 的前 $k$ 列不会变动，因此该算法的第 $k$ 步就产生最终得到的矩阵 $Z$ 和 $T$ 的第 $k$ 列。这个算法称为修改的Gram-Schmidt过程；它通过重新调整计算得到与通常的Gram-Schmidt过程相同的结果。虽然修改的算法与通常的Gram-Schmidt算法在数学上是等价的，但是对于数值计算来说，修改的Gram-Schmidt过程更受欢迎，因为它需要的存储较少，在遇到 $X$ 的某些列接近平行这样一些难题时，它有助于得到一个能算出的 $Z$ 。这个 $Z$ 的诸列要比用通常的Gram-Schmidt算法得到的 $Z$ 更接近于正交。在遇到难题时可以方便地通过列旋转策略使它的性能进一步改进：在实施步骤Ⅱ（I）之前，首先选作 $z_{k}$ 的是一个余下的列 $z_{j}, j \geqslant k$ ，其长度的平方 $z_{j}^{\prime}z_{j}$ 最大。在数值计算中每一步（不要求反演）实际上得到 $\Delta_{i}^{1}$ ，然后累积这些因子的乘积可以计算 $X$ 的QR分解中的三角因子。

1. 说明如何用一系列由 Householder 变换组成的乘积来实现 QR 分解。证明上述过程必须用 $n$ 个 Householder 变换来完成，且 Q 是这些变换的乘积。一般认为，这个方法在计算上优于(2.6.1)证明中所采用的 Gram-Schmidt 算法。

2. 如果应用于 $A_{1} \in M_{n}$ 的QR算法收敛于一个上三角矩阵，可以怎样计算 $A_{0}$ 的特征向量

呢？提示：需要解一个右边也是零的（奇异）三角形方程组

1. 设将 $QR$ 算法应用于某个矩阵 $A \in M_{n}$ ，且设 $\{A_{k}\}$ 是 $QR$ 迭代值的序列。如果序列收敛，且 $\lim_{k \to \infty} A_{k} = B$ ，用选择原理(2.1.8)仔细说明为什么 $B$ 酉等价于 $A$ 。这为什么是重要的？

进一步阅读 关于Gram-Schmidt、修改的Gram-Schmidt以及几个其他的正交化过程的另外的参考资料和详细的叙述，可参看[GVI]的pp.146-169．关于QR算法和证明方法，以及另外的参考资料可见由D.Watkins写的综述，“Understanding the QR Algorithm,"SIAM Rev.24(1982)；也可参看[Ste]，427-440.