[UCAS矩阵论]4.2矩阵的QR分解

Givens 变换与 Householder 变换

Givens 矩阵与 Givens 变换

Givens 矩阵（初等旋转矩阵）：设 \(c,s\in\mathbb R\) 且 \(c^2+s^2=1\)，定义 Givens 矩阵为： \[ T_{ij}=T_{ij}(c,s)= \begin{bmatrix} 1& & & & & & & & & & \\ &\ddots& & & & & & & & & \\ & &1& & & & & & & & \\ & & &c & & & &s& & & \\ & & & &1& & & & & & \\ & & & & &\ddots& & & & & \\ & & & & & &1& & & & \\ & & &-s& & & &c& & & \\ & & & & & & & &1& & \\ & & & & & & & & &\ddots& \\ & & & & & & & & & &1\\ \end{bmatrix} \] 由 Givens 矩阵确定的线性变换称作 Givens 变换（初等旋转变换）。

顾名思义，Givens 变换的作用是旋转。具体而言，是在第 \(i\) 和第 \(j\) 维的平面上绕原点顺时针旋转 \(\theta\)，其中 \(c=\cos\theta,\,s=\sin\theta\).

性质：Givens 矩阵是正交矩阵，且有： \[ [T_{ij}(c,s)]^{-1}=[T_{ij}(c,s)]^T=T_{ij}(c,-s),\quad\det(T_{ij}(c,s))=1 \] 定理：设 \(x=(\xi_1,\ldots,\xi_n)^T\neq0\)，则存在有限个 Givens 矩阵的乘积，记作 \(T\)，使得 \(Tx=|x|e_1\).

直观理解：依次把第 \(2,3,\ldots,n\) 维转到 0 即可。

证明（构造方法）：构造 Givens 矩阵 \(T_{12}(c,s)\)： \[c=\frac{\xi_1}{\sqrt{\xi_1^2+\xi_2^2}}\quad s=\frac{\xi_2}{\sqrt{\xi_1^2+\xi_2^2}}\] 则： \[T_{12}x=\left(\sqrt{\xi_1^2+\xi_2^2},0,\xi_3,\ldots,\xi_n\right)^T\] 再对 \(T_{12}x\) 构造 Givens 矩阵 \(T_{13}(c,s)\)： \[c=\frac{\sqrt{\xi_1^2+\xi_2^2}}{\sqrt{\xi_1^2+\xi_2^2+\xi_3^2}}\quad s=\frac{\xi_3}{\sqrt{\xi_1^2+\xi_2^2+\xi_3^2}}\] 则： \[T_{13}(T_{12}x)=\left(\sqrt{\xi_1^2+\xi_2^2+\xi_3^2},0,0,\xi_4,\ldots,\xi_n\right)^T\] 如此继续下去，最后对 \(T_{1,n-1}\cdots T_{12}x\) 构造 Givens 矩阵 \(T_{1n}(c,s)\)： \[c=\frac{\sqrt{\xi_1^2+\cdots\xi_{n-1}^2}}{\sqrt{\xi_1^2+\cdots\xi_{n-1}^2+\xi_n^2}}\quad s=\frac{\xi_n}{\sqrt{\xi_1^2+\cdots\xi_{n-1}^2+\xi_n^2}}\] 则： \[T_{1n}(T_{1,n-1}\cdots T_{12}x)=\left(\sqrt{\xi_1^2+\cdots\xi_n^2},0,\ldots,0\right)^T\] 令 \(T=T_{1n}T_{1,n-1}\cdots T_{12}\)，则 \(Tx=|x|e_1\).

推论：任给非零列向量 \(x\in\mathbb R^n\) 及单位列向量 \(z\in\mathbb R^n\)，则存在有限个 Givens 矩阵的乘积，记作 \(T\)，使得 \(Tx=|x|z\).

快速 Givens 变换：暂略。

Householder 矩阵与 Householder 变换

Householder 矩阵（初等反射矩阵）：设 \(u\in\mathbb R^n\) 是单位列向量，定义 Householder 矩阵为： \[ H=I-2uu^T \] 由 Householder 矩阵确定的线性变换称作 Householder 变换（初等反射变换）。

顾名思义，Householder 变换的作用是反射。具体而言，是对以 \(u\) 为法向量的平面做反射。

性质：Householder 矩阵对称、正交、对合、自逆，且行列式为 \(-1\)： \[ H^T=H,\quad H^TH=I,\quad H^2=I,\quad H^{-1}=H,\quad \det(H)=-1 \] 定理：任给非零列向量 \(x\in\mathbb R^n\) 及单位列向量 \(z\in\mathbb R^n\)，则存在 Householder 矩阵 \(H\)，使得 \(Hx=|x|z\).

直观理解：找到 \(x\) 和 \(z\) 之间对称平面，取 \(u\) 为该平面的单位法向量即可。

证明（构造方法）：若 \(x=|x|z\)，取单位向量 \(u\) 使得 \(u\perp x\)，则 \(H_u=I-2uu^T\)： \[H_ux=(I-2uu^T)x=x-2uu^Tx=x=|x|z\] 否则，\(x\neq|x|z\)，取 \(u=\frac{x-|x|z}{\left|x-|x|z\right|}\)，则： \[\begin{align}H_ux&=\left[I-2\frac{(x-|x|z)(x-|x|z)^T}{|x-|x|z|^2}\right]x\\&=x-\frac{2(x-|x|z)^Tx}{|x-|x|z|^2}(x-|x|z)\\&=x-(x-|x|z)=|x|z\end{align}\]

定理：Givens 变换是两个 Householder 变换的乘积。

换句话说，一次旋转操作可以分解为两次反射操作。

证明：取 \[\begin{align}&u=(0,\ldots,0,\sin(\theta/4),0,\ldots,0,\cos(\theta/4),0,\ldots,0)^T\\&v=(0,\ldots,0,\sin(3\theta/4),0,\ldots,0,\cos(3\theta/4),0,\ldots,0)^T\end{align}\] 可以验证 \(T_{ij}=H_vH_u\). 证毕。

Householder 矩阵并不能由若干个 Givens 矩阵的乘积表示，因为 \(\det(H)=-1,\,\det(G)=1\).

矩阵的 QR 分解

QR 分解的定义

定义：若实/复矩阵 \(A\) 能分解成正交/酉矩阵 \(Q\) 与非奇异上三角矩阵 \(R\) 的乘积，即 \(A=QR\)，则称为 \(A\) 的 QR 分解。

定理：对 \(n\) 阶非奇异矩阵 \(A\)，QR 分解在除去相差一个对角元素的绝对值/模全等于 1 的对角矩阵外，分解唯一。

证明（实数情形）：设 \(A=Q_1R_1=Q_2R_2\)，则 \(P=Q_2^TQ_1=R_2R_1^{-1}\).

注意到 \(P^TP=I\)，所以 \(P^T=P^{-1}\). 由于 \(P\) 是上三角矩阵，所以 \(P^{-1}\) 是上三角矩阵，\(P^T\) 是下三角矩阵，二者又相等，因此只能是对角矩阵。又 \(P^2=I\)，所以对角元只能是 \(\pm1\). 那么 \(Q_1=Q_2P,\,R_1=PR_2\). 证毕。

定理：对 \(m\times n\) 实/复矩阵 \(A\)，其 \(n\) 列线性无关，则 \(A\) 有分解 \(A=QR\)，其中 \(Q\) 是 \(m\times n\) 实/复矩阵，且 \(Q^HQ=I\)（即 \(Q\) 是正交/酉矩阵的一部分），\(R\) 是实/复非奇异上三角矩阵，且除去相差一个对角元素的绝对值/模全等于 1 的对角矩阵外，分解唯一。

计算方法：基于 Gram-Schmidt 正交化过程

设 \(A=(a_1,\ldots,a_n)\) 非奇异，对其各列实施 Gram-Schmidt 正交化过程： \[ \begin{cases} b_1=a_1\\ b_2=a_2-k_{21}b_1\\ \quad\vdots\\ b_n=a_n-k_{n,n-1}b_{n-1}-\cdots-k_{n1}b_1 \end{cases}\implies \begin{cases} a_1=b_1\\ a_2=b_2+k_{21}b_1\\ \quad\vdots\\ a_n=b_n+k_{n,n-1}b_{n-1}+\cdots+k_{n1}b_1 \end{cases} \] 写作矩阵形式： \[ \begin{align} A=BK&\implies(a_1,a_2,\ldots,a_n)=(b_1,b_2,\ldots,b_n)\begin{bmatrix}1&k_{21}&\cdots&k_{n1}\\&1&\cdots&k_{n2}\\&&\ddots&\vdots\\&&&1\end{bmatrix}\\ &\implies(a_1,a_2,\ldots,a_n)=\underbrace{\begin{bmatrix}\dfrac{b_1}{|b_1|},\dfrac{b_2}{|b_2|}\ldots,\dfrac{b_n}{|b_n|}\end{bmatrix}}_Q\underbrace{\begin{bmatrix}|b_1|&&&\\&|b_2|&&\\&&\ddots&\\&&&|b_n|\end{bmatrix}\begin{bmatrix}1&k_{21}&\cdots&k_{n1}\\&1&\cdots&k_{n2}\\&&\ddots&\vdots\\&&&1\end{bmatrix}}_R\\ &\implies A=QR \end{align} \]

基于 Gram-Schmidt 正交化过程的 QR 分解计算方法在高阶时容易出现数值不稳定，需要用下文的基于 Givens 变换或 Householder 变换的方法计算。

计算方法：基于 Givens 变换

任何 \(n\) 阶实非奇异矩阵 \(A\) 都可以通过左连乘 Givens 初等旋转矩阵化为上三角矩阵。

1. 由于 \(\det(A)\neq0\)，因此 \(A\) 的第一列 \((a_{11},a_{21},\ldots,a_{n1})^T\neq 0\)，根据前文的定理，存在有限个 Givens 矩阵的乘积 \(T_1\)，使得 \[ T_1(a_{11},a_{21},\ldots,a_{n1})^T=\left|(a_{11},a_{21},\ldots,a_{n1})^T\right|\cdot e_1 \] 将 \(T_1\) 作用在 \(A\) 上得： \[ T_1A=\left[\begin{array}{c:ccc} a_{11}^{(1)}&a_{12}^{(1)}&\cdots&a_{1n}^{(1)}\\ \hdashline 0&&&\\ \vdots&&A^{(1)}&\\ 0&&& \end{array}\right] \]

2. 由于 \(\det(A^{(1)})\neq0\)，因此 \(A^{(1)}\) 的第一列 \(\left(a_{22}^{(1)},a_{32}^{(1)},\ldots,a_{n2}^{(1)}\right)^T\neq0\)，于是存在有限个 Givens 矩阵的乘积 \(T_2\)，使得 \[ T_2\left(a_{22}^{(1)},a_{32}^{(1)},\ldots,a_{n2}^{(1)}\right)^T=\left|\left(a_{22}^{(1)},a_{32}^{(1)},\ldots,a_{n2}^{(1)}\right)^T\right|\cdot e_1 \] 将 \(T_2\) 作用在 \(A\) 上得： \[ T_2A^{(1)}=\left[\begin{array}{c:ccc} a_{22}^{(2)}&a_{23}^{(2)}&\cdots&a_{2n}^{(2)}\\ \hdashline 0&&&\\ \vdots&&A^{(2)}&\\ 0&&& \end{array}\right] \]

3. 重复上述步骤，直到第 \(n-1\) 步： \[ T_{n-1}A^{(n-2)}=\begin{bmatrix}a_{n-1,n-1}^{(n-1)}&a_{n-1,n}^{(n-1)}\\0&a_{nn}^{(n-1)}\end{bmatrix} \]

最后，令： \[ T=\begin{bmatrix}I_{n-2}&O\\O&T_{n-1}\end{bmatrix}\cdots\begin{bmatrix}I_{2}&O\\O&T_{3}\end{bmatrix}\begin{bmatrix}I_{1}&O\\O&T_{2}\end{bmatrix}T_1 \] 则： \[ TA=\begin{bmatrix} a_{11}^{(1)}&a_{12}^{(1)}&\cdots&a_{1,n-1}^{(1)}&a_{1n}^{(1)}\\ &a_{22}^{(2)}&\cdots&a_{2,n-1}^{(2)}&a_{2n}^{(2)}\\ &&\ddots&\vdots&\vdots\\ &&&a_{n-1,n-1}^{(n-1)}&a_{n-1,n}^{(n-1)}\\ &&&&a_{nn}^{(n-1)} \end{bmatrix} \] 即 \(A=QR\)，其中 \(Q=T^{-1}=T^T\)，\(R\) 就是上面化出来的那一大坨上三角矩阵。

该过程与高斯消元法有异曲同工之妙。

计算方法：基于 Householder 变换

任何 \(n\) 阶实非奇异矩阵 \(A\) 都可以通过左连乘 Householder 初等反射矩阵化为上三角矩阵。

1. 由于 \(\det(A)\neq0\)，因此 \(A\) 的第一列 \((a_{11},a_{21},\ldots,a_{n1})^T\neq 0\)，根据前文的定理，存在一个 Householder 矩阵 \(H_1\)，使得 \[ H_1(a_{11},a_{21},\ldots,a_{n1})^T=\left|(a_{11},a_{21},\ldots,a_{n1})^T\right|\cdot e_1 \] 将 \(H_1\) 作用在 \(A\) 上得： \[ H_1A=\left[\begin{array}{c:ccc} a_{11}^{(1)}&a_{12}^{(1)}&\cdots&a_{1n}^{(1)}\\ \hdashline 0&&&\\ \vdots&&A^{(1)}&\\ 0&&& \end{array}\right] \]

2. 由于 \(\det(A^{(1)})\neq0\)，因此 \(A^{(1)}\) 的第一列 \(\left(a_{22}^{(1)},a_{32}^{(1)},\ldots,a_{n2}^{(1)}\right)^T\neq0\)，于是存在一个 Householder 矩阵 \(H_2\)，使得 \[ H_2\left(a_{22}^{(1)},a_{32}^{(1)},\ldots,a_{n2}^{(1)}\right)^T=\left|\left(a_{22}^{(1)},a_{32}^{(1)},\ldots,a_{n2}^{(1)}\right)^T\right|\cdot e_1 \] 将 \(H_2\) 作用在 \(A\) 上得： \[ H_2A^{(1)}=\left[\begin{array}{c:ccc} a_{22}^{(2)}&a_{23}^{(2)}&\cdots&a_{2n}^{(2)}\\ \hdashline 0&&&\\ \vdots&&A^{(2)}&\\ 0&&& \end{array}\right] \]

3. 重复上述步骤，直到第 \(n-1\) 步： \[ H_{n-1}A^{(n-2)}=\begin{bmatrix}a_{n-1,n-1}^{(n-1)}&a_{n-1,n}^{(n-1)}\\0&a_{nn}^{(n-1)}\end{bmatrix} \]

最后，令： \[ H=\begin{bmatrix}I_{n-2}&O\\O&H_{n-1}\end{bmatrix}\cdots\begin{bmatrix}I_{2}&O\\O&H_{3}\end{bmatrix}\begin{bmatrix}I_{1}&O\\O&H_{2}\end{bmatrix}H_1 \] 则： \[ HA=\begin{bmatrix} a_{11}^{(1)}&a_{12}^{(1)}&\cdots&a_{1,n-1}^{(1)}&a_{1n}^{(1)}\\ &a_{22}^{(2)}&\cdots&a_{2,n-1}^{(2)}&a_{2n}^{(2)}\\ &&\ddots&\vdots&\vdots\\ &&&a_{n-1,n-1}^{(n-1)}&a_{n-1,n}^{(n-1)}\\ &&&&a_{nn}^{(n-1)} \end{bmatrix} \] 即 \(A=QR\)，其中 \(Q=H^{-1}=H^T\)，\(R\) 就是上面化出来的那一大坨上三角矩阵。

Hessenberg 矩阵的正交相似

Hessenberg 矩阵：次对角线以下全为零。 \[ F=\begin{bmatrix} a_{11}&a_{12}&a_{13}&\cdots&a_{1,n-1}&a_{1n}\\ a_{21}&a_{22}&a_{23}&\cdots&a_{2,n-1}&a_{2n}\\ 0&a_{32}&a_{33}&\cdots&a_{3,n-1}&a_{3n}\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&a_{n-1,n-1}&a_{n-1,n}\\ 0&0&0&\cdots&a_{n,n-1}&a_{nn} \end{bmatrix} \] 定理：任何实方阵都可以通过初等旋转变换正交相似于 Hessenberg 矩阵。即：设 \(A\in\mathbb R^{n\times n}\)，则存在有限个 Givens 矩阵之积 \(Q\)，使得 \(QAQ^T=F\).

证明：

1. 对 \(A\)，若 \(\beta^{(0)}=(a_{21},\ldots,a_{n2})^T\neq0\)，则存在有限个 Givens 矩阵之积 \(T_0\)，使得 \(T_0\beta^{(0)}=|\beta^{(0)}|e_1=a_{21}^{(1)}e_1\)： \[\begin{bmatrix}1&\\&T_0\end{bmatrix}A\begin{bmatrix}1&\\&T_0\end{bmatrix}^T=\left[\begin{array}{c:cccc}a_{11}&a_{12}^{(1)}&a_{13}^{(1)}&\cdots&a_{1n}^{(1)}\\\hdashline a_{21}^{(1)}&&&&\\0&&&&\\\vdots&&&A^{(1)}&\\0&&&&\end{array}\right]\] 若 \(\beta^{(0)}=0\)，转 2；

2. 对 \(A^{(1)}\)，若 \(\beta^{(1)}=(a_{32}^{(1)},\ldots,a_{n2}^{(1)})^T\neq0\)，则存在有限个 Givens 矩阵之积 \(T_1\)，使得 \(T_1\beta^{(1)}=|\beta^{(1)}|e_1=a_{32}^{(1)}e_1\)： \[\begin{bmatrix}1&\\&T_1\end{bmatrix}A^{(1)}\begin{bmatrix}1&\\&T_1\end{bmatrix}^T=\left[\begin{array}{c:cccc}a_{22}&a_{23}^{(1)}&a_{24}^{(1)}&\cdots&a_{2n}^{(1)}\\\hdashline a_{32}^{(1)}&&&&\\0&&&&\\\vdots&&&A^{(2)}&\\0&&&&\end{array}\right]\] 若 \(\beta^{(1)}=0\)，转 3；

3. 反复执行上述操作，直到 \(n-2\) 步结束。

最后，令： \[Q=\begin{bmatrix}I_{n-2}&\\&T_{n-3}\end{bmatrix}\cdots\begin{bmatrix}I_{2}&\\&T_{1}\end{bmatrix}\begin{bmatrix}1&\\&T_{0}\end{bmatrix}\] 则 \(QAQ^T=F\).

定理：任何实方阵都可以通过初等反射变换正交相似于 Hessenberg 矩阵。即：设 \(A\in\mathbb R^{n\times n}\)，则存在有限个 Householder 矩阵之积 \(Q\)，使得 \(QAQ^T=F\).

类似上一个定理的证明。

推论：任何实对称矩阵都可以通过初等旋转变换或初等反射变换正交相似于三对角矩阵。