矩阵分析与应用-4.7-QR分解及其应用

前言

本文学习过程来源是《矩阵分析与应用-张贤达》一书. 可以通过 z-lib 下载.

一、\(\mathrm{QR}\) 分解的性质

定理 1 ( \(\mathrm{QR}\) 分解 ): 若 \(A \in R^{m \times n}\), 且 \(m \ge n\), 则存在列正交的矩阵 \(Q \in R^{m \times m}\) 和上三角矩阵 \(R \in R^{m \times n}\) 使得 \(A = QR\)

当 \(m = n\) 时, \(Q\) 是正交矩阵. 如果 \(A\) 是非奇异的 \(n \times n\) 矩阵, 则 \(R\) 的所有对角线元素均为正, 并且在这种情况下 \(Q\) 和 \(R\) 二者是唯一的. 若 \(A\) 是复矩阵, 则 \(Q\) 和 \(R\) 取复值.

( 补充一个小知识: \(Q\) 其实是源于 orthogonal matrices 或 orthonormal basis, 为了避免 \(O \ 0\) 不好区分的问题; \(R\) 是指代 right triangular matrices )

引理 1 : 若 \(A\) 和 \(B\) 是任意两个 \(m \times n\) 矩阵, 则

\[ A^{\mathrm{H}}A = B^{\mathrm{H}}B \tag{1} \]

当且仅当存在一个 \(m \times m\) 酉矩阵 \(Q\), 使得

\[ QA = B \tag{2} \]

二、采用修正 \(\mathrm{Gram-Schmidt}\) 法的 \(\mathrm{QR}\) 分解

矩阵 \(A\) 的 \(QR\) 分解可以利用 \(\mathrm{Gram-Schmidt}\) 正交化方法实现.

这个方法在之前就已经提到过, 这里就不再赘述了. 我们最后要得到的就是一组标准正交基 \(q_1,q_2,\cdots,q_n\)

容易验证, \(q_i\) 是标准正交基, 即满足

\[ q_i^{\mathrm{H}}q_j = \delta_{ij} \tag{3} \]

其中, \(\delta_{ij}\) 为 \(\mathrm{Kronecker} \ \delta\) 函数. 简单说一下这个函数, 它和 \(\mathrm{Dirac} \ \delta\) 非常相似.

\[ \delta_{ij} = \left\{\begin{matrix} 0& \mathrm{if} \ i \neq j\\ 1& \mathrm{if} \ i = j \end{matrix}\right. \tag{4} \]

如果令 \(m \times n\) 矩阵 \(A\) 的列向量为 \(a_1,a_2,\cdots,a_n\), 则以 \(q_1,q_2,\cdots,q_n\) 为列向量的矩阵 \(Q\) 与 \(A\) 之间有下列关系:

\[ A=QR \tag{5} \]

又由于 \(q_i\) 组成标准正交基, 所以

\[ Q^{\mathrm{H}}Q=I_n \]

这里提出一种修正正交化算法, 之前是使上三角矩阵 \(R\) 的元素不是按列, 而是按行计算.

和经典正交化算法不同的是, 经典算法是一个一个基计算, 计算到某个基时就减去与之前求得的基相平行的分量. 修正后的算法就是每算出一个基就对后面未正交化的基执行减去平行分量的操作.

修正后的正交化算法减小误差的效果更明显.

三、\(\mathrm{Householder}\) \(\mathrm{QR}\) 分解

\(\mathrm{Householder}\) 变换可以实现任意 \(m \times n\) 矩阵 \(A\) 的 \(QR\) 分解, 其原理时使用变维向量的 \(\mathrm{Householder}\) 变换, 使得该向量除第一个元素外, 其他元素皆变成 0.

使一个 \(p\) 维向量 \(x=[x_1,x_2,\cdots,x_p]^{\mathrm{T}}\) 的第 1 个元素后面的所有元素变为 0, 则 \(p\) 维的 \(\mathrm{Householder}\) 向量应取

\[ \omega = \frac{x - \beta e_1}{\sqrt{\bar{\beta} (\beta - x_1)}} \tag{6} \]

式中

\[ \bar{\beta} = - |x_1| \lVert x \rVert, \quad \beta = - \frac{x_1}{|x_1|} \lVert x \rVert \tag{7} \]

首先令 \(x=a_1=[a_{11},a_{21},\cdots,a_{m1}]^{\mathrm{T}}\), 并取 \(p=m\), 按照式子 (6) 和式子 (7), 可以计算得到 \(u_1=\omega_m\). 此时,

\[ H_1 = I - u_1 u_1^{\mathrm{T}} \to A_1 = H_1A = [a_1^{(1)},a_2^{(1)},\cdots,a_n^{(1)}] \tag{8} \]

变换后矩阵 \(A_1\) 的第 1 列 \(a_1^{(1)}\) 的第一个元素等于 \((a_{11}^2 + a_{21}^2 + \cdots + a_{m1}^2)^{1/2}\) (像第二范数). 其他元素全为 0.

接下来就是针对矩阵 \(A_1\) 的第 2 列 \(a_2^{(1)}\), 令 \(p = m-1\) 和

\[ x = [a_{22}^{(1)},a_{32}^{(1)},\cdots,a_{m2}^{(1)}]^{\mathrm{T}} \]

按照式子 (6) 和式子 (7), 可以计算得到 \((m-1)\) 维向量 \(\omega_{m-1}\). 此时, 取 \(u_2 = \begin{bmatrix} 0\\ \omega_{m-1}\end{bmatrix}\), 又可得到

\[ H_2 = I - u_2 u_2^{\mathrm{T}} \to A_2 = H_2A_1 = H_2H_1A = [a_1^{(1)},a_2^{(2)},\cdots,a_n^{(2)}] \tag{9} \]

可以发现矩阵 \(A_2\) 的第 1 列与 \(A_1\) 的第 1 列相同, 而第 2 列 \(a_1^{(1)}\) 的第一个元素等于 \(a_{12}^{(1)}\), 第二个元素等于 \([ |a_{22}^{(1)}|^2 + |a_{32}^{(1)}|^2 + \cdots + |a_{m2}^{(1)}|^2 ]^{1/2}\) , 而该列的其他元素全部为 0, 以此类推.

假定矩阵 \(A\) 经过 \(k -1\) 次 \(\mathrm{Householder}\) 变换后, 已变成 \(A^{(k-1)}\) 即有

\[ \begin{aligned} A^{(k-1)} &= H_{k-1}A^{(k-2)}=H_{k-1} \cdots H_1A &= [a_1^{(k-1)},a_2^{(k-1)},\cdots,a_n^{(k-1)}], \quad k = 2,3,\cdots \end{aligned} \]

并且其前 \(k-1\) 列具有以下变换结果:

\[ a_j^{(k-1)} = [a_{1j}^{(k-1)},\cdots,a_{jj}^{(k-1),0,\cdots,0}]^{\mathrm{T}}, \quad j=1,2,\cdots,k-1 \]

因此, 第 \(k\) 次 \(\mathrm{Householder}\) 变换的目的就是保证前 \(k-1\) 列不变, 实现 \(A^{(k-1)}\) 的第 \(k\) 列的下述变换:

\[ \tilde{H_k}\begin{bmatrix} a_{k,k}^{(k-1)}\\ a_{k+1,k}^{(k-1)}\\ \vdots \\ a_{m,k}^{(k-1)} \end{bmatrix} = \begin{bmatrix} a_{k,k}^{(k)}\\ 0\\ \vdots \\ 0 \end{bmatrix} \]

这相当于对矩阵 \(A^{(k-1)}\) 进行 \(\mathrm{Householder}\) 变换 \(H_kA^{(k-1)}\) 时取

\[ H_k = \begin{bmatrix} I_{k-1} & 0\\ 0 & \tilde{H_k} \end{bmatrix} \]

取 \(n\) 次 \(\mathrm{Householder}\) 变换后, 即可实现 \(\mathrm{QR}\) 分解.