QR分解

定义

如果实（复）非奇异矩阵$A$能化成正交（酉）矩阵$Q$与实（复）非奇异上三角矩阵的乘积，即
$$A=QR$$
则称是$A$的$QR$分解

定理1

任何实的非奇异$n$阶矩阵$A$可以分解成正交矩阵$Q$和上三角矩阵$R$的乘积，且除去相差一个对角线元素之绝对值全等于1的对角矩阵因子$D$外，唯一分解

证明：
设$A$的列向量分别为${\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_n$,由于$A$非奇异，所以他们线性无关，经过施密特正交化和单位化后，得到$n$个标准正交的向量${\beta }_1,{\beta }_2,\cdots ,{\beta }_n$,且
$$\{\begin{array}{ll}{\beta }_1& =b_{11}{\alpha }_1,\\ {\beta }_2& =b_{12}{\alpha }_1+b_{22}{\alpha }_2\\ & ⋮\\ {\beta }_n& =b_{1n}{\alpha }_1+b_{2n}{\alpha }_2+\cdots +b_{nn}{\alpha }_n\end{array}$$
这里$b_{ij}$都是常数，且由正交化过程可知$b_{ii}\ne 0(i=1,2,\cdots ,n)$,于是
$$({\beta }_1,{\beta }_2,\cdots ,{\beta }_n)=({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_n)B$$
即
$$Q=AB$$
其中
$$B=\left(\begin{array}{cccc}{b}_{11}& b_{12}& \cdots & b_{1n}\\ & b_{22}& \cdots & b_{2n}\\ & & \ddots & ⋮\\ & & & b_{nn}\end{array}\right)$$
是上三角矩阵$(b_{ii}\ne 0(i=1,2,\cdots ,n))$
显然$B$可逆，$R=B^{-1}$也是上三角矩阵
因为$Q$的各列标准正交，所以$Q$为正交矩阵，有$A=QR$

唯一性：
不妨设
$$A=QR=Q_1{R}_1$$
其中$Q,Q_1$都是正交矩阵，$R,R_1$都是上三角矩阵,
$$Q=Q_1{R}_1{R}^{-1}=Q_{1}D$$
$D=R_1{R}^{-1}$也是非奇异上三角矩阵，于是
$$I=Q^{T}Q=(Q_{1}D{)}^T(Q_{1}D)=D^{T}D$$
$$D=\left(\begin{array}{cccc}{d}_{11}& d_{12}& \cdots & d_{1n}\\ & d_{22}& \cdots & d_{2n}\\ & & \ddots & ⋮\\ & & & d_{nn}\end{array}\right)$$
代入比较，得
$$\begin{gathered} d_{11}^2=1,d_{12}=\cdots =d_{1n}=0 \\ {d}_{22}^2=1,d_{23}=\cdots =d_{2n}=0 \\ ⋮ \\ {d}_{nn}^2=1 \end{gathered}$$
从而
$\left|d_{ii}\right|=1$
即
$$D=diag(\pm 1,\pm 1,\cdots ,\pm 1)$$
所以$D$不仅是正交矩阵，而且还是对角线元素的绝对值全为1的对角矩阵
$$R_1=D{R}_1,Q_1=Q{D}^{-1}$$

当然，如果规定$R,R_1$对角线上的元素为正实数，则$D=I$,从而唯一分解

定理2

设$A$为$m\times n$的复矩阵$(m\ge n)$,且$n$个列向量线性无关，则$A$有分解式
$$A=UR$$
其中$U$是$m\times n$的复矩阵，且$U^{H}U=I$,$R$是$n$阶复非奇异上三角矩阵，且除去相差一个对角元素的模全为1的对角矩阵因子外，唯一分解

QR分解求法

吉文斯(Givens)方法

定理

任何非奇异矩阵可以通过左连乘初等旋转矩阵化为上三角矩阵

证明：
(1)
对实可逆矩阵$A=(a_{ij})$左乘初等旋转矩阵$R_{ij}$以后，只改变$A$的第$i$行和第$j$行元素
设
$$A^{\prime }=R_{ij}A$$
则
$$a_{ig}^{\prime }=c{a}_{ig}+s{a}_{jg},a_{jg}^{\prime }=-s{a}_{ig}+c{a}_{jg},a_{pg}^{\prime }=a_{pg}(p\ne i,j;g=1,2,\cdots ,n)$$
如果要使得$A^{\prime }$中的第$g_0$列的第$j$元素$a_{j{g}_0}^{\prime }=0$,那么只要$a_{i{g}_0}$和$a_{j{g}_0}$之一不为0，且取
$$s=\frac{a_{j{g}_0}}{\sqrt{a_{i{g}_0}^2+a_{j{g}_0}^2}},c=\frac{a_{i{g}_0}}{\sqrt{a_{i{g}_0}^2+a_{j{g}_0}^2}}$$
此时
$$a_{i{g}_0}^{\prime }=\sqrt{a_{i{g}_0}^2+a_{j{g}_0}^2}>0$$
也就是$A$的第$g_0$列的第$j$个元素化为0，第$g_0$列的第$i$个元素的变为正数，其余元素不变
(2)
假设$a_{11}\ne 0$,取$g_0=1$,连续左乘$R_{12},R_{13},\cdots ,R_{1n}$,使得第1列的第1个元素为正外，其余元素都被逐个化为0，即
$$\begin{array}{rl}{A}^{(1)}& =R_{1n}{R}_{1,n-1}\cdots R_{12}A\\ & =\left(\begin{array}{cccc}{a}_{11}^{(1)}& a_{12}^{(1)}& \cdots & a_{1n}^{(1)}\\ 0& a_{22}^{(1)}& \cdots & a_{2n}^{(1)}\\ ⋮& ⋮& & ⋮\\ 0& a_{n2}^{(1)}& \cdots & a_{nn}^{(1)}\end{array}\right)\end{array}$$
且$a_{11}^{(1)}>0$

如果$a_{1}1=0$,则$A$从 左乘$R_{1i_0}$开始，其中$i_0$是$a_{i1}\ne 0$的最小下标，因为$A$是可逆的，所以列向量不能为0，也就是说一定可以找到，此时$R_{1i_0}A$的第1列第1个元素为正
因为$A$是可逆的，所以右下角的子式非零，所以在$a_{22}^{(1)},a_{32}^{(1)},\cdots ,a_{n2}^{(1)}$中至少有一个不为0，此时同样可以认为$a_{22}^{(1)}\ne 0$，取$g_0=2$，连续左乘$R_{23},R_{24},\cdots ,R_{2n}$使$A^{(1)}$化为
$$\begin{array}{rl}{A}^{(2)}& =R_{2n}{R}_{2,n-1}\cdots R_{23}{A}^{(1)}\\ & =\left(\begin{array}{ccccc}{a}_{11}^{(1)}& a_{12}^{(1)}& a_{13}^{(1)}& \cdots & a_{1n}^{(1)}\\ 0& a_{22}^{(1)}& a_{23}^{(2)}& \cdots & a_{2n}^{(2)}\\ 0& 0& a_{33}^{(2)}& \cdots & a_{3n}^{(2)}\\ ⋮& ⋮& ⋮& & ⋮\\ 0& 0& a_{n3}^{(2)}& \cdots & a_{nn}^{(2)}\end{array}\right)\end{array}$$
且第一行元素不变，$a_{22}^{(2)}>0$
继续进行下去
$$\begin{array}{rl}{A}^{(n-1)}& =R_{n-1,n}\cdots R_{12}A\\ & =\left(\begin{array}{cccc}{a}_{11}^{(1)}& a_{12}^{(1)}& \cdots & a_{1n}^{(1)}\\ 0& a_{22}^{(2)}& \cdots & a_{2n}^{(2)}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_{nn}^{(n-1)}\end{array}\right)\end{array}$$
其中除了最后一个$a_{nn}^{(n-1)}$外，所有的对角线元素都是正的，显然$a_{nn}^{(n-1)}$的符号与$A$的行列式的符号一致

求法

由上面的定理，我们可以看出，利用初等旋转矩阵讲$A$化为上三角矩阵的过程实际上存在$A$的一个$QR$分解
$$R=A^{(n-1)}$$
$$Q=(R_{n-1}\cdots R_{12}{)}^{-1}=(R_{n-1}\cdots R_{12}{)}^T$$
每个$R_{ij}$都是正交矩阵，所以他们的乘积的逆矩阵$Q$也是正交矩阵，从而
$$A=QR$$

显然吉文斯方法需要$\frac{n(n-1)}{2}$个初等矩阵连乘，当$n$比较大的时候，工作量比较大，适合稀疏矩阵

豪斯霍尔德(Housholder)方法

定理

任何实的$n$阶矩阵$A$可用初等反射矩阵$H=I-2\omega {\omega }^T$化为上三角矩阵

证明：
$$A=({\alpha }_1^{(1)},{\alpha }_2^{(1)},\cdots ,{\alpha }_n^{(1)}$$
其中${\alpha }_i^{(1)}$是$A$的第$i$个列向量，因为${\alpha }_1^{(1)}\ne 0$

根据
$$\omega =\frac{\xi -\left|\xi \right|\zeta }{\left|\xi -\left|\xi \right|\zeta \right|}$$
构造一个单位向量${\omega }^{(1)}$,使得${\alpha }_1^{(1)}$与单位向量$e_1=(1,0,\cdots ,0{)}^T$同向.从而必然存在初等反射矩阵$H^{(1)}$,使得
$$H^{(1)}A=\left(\begin{array}{cc}\left|a_{11}^{(1)}\right|& \ast \\ 0& A_{n-1}\end{array}\right)$$
然后对矩阵$A_{n-1}$再用$n-1$阶的初等反射矩阵${\hat{H}}^{(2)}$,使得
$${\hat{H}}^{(2)}{A}_{n-1}=\left(\begin{array}{cc}\left|a_{22}^{(2)}\right|& \ast \\ 0& A_{n-2}\end{array}\right)$$
因此有
$$H^{(2)}=\left(\begin{array}{cc}1& 0^T\\ 0& {\hat{H}}^{(2)}\end{array}\right)$$
使得
$$H^{(2)}{H}^{(1)}A=\left(\begin{array}{ccc}\left|a_{11}^{(1)}\right|& & \ast \\ 0& \left|a_{22}^{(2)}\right|& \ast \\ 0& 0& \\ ⋮& ⋮& A_{n-2}\\ 0& 0& \end{array}\right)$$
下面我们证明$H^{(2)}$是初等反射矩阵
若${\hat{H}}^{(2)}=I_{n-1}-2\hat{\omega }{\hat{\omega }}^T$,其中$\hat{\omega }$是$n-1$维的单位向量
记
$$\omega =\left(\begin{array}{c}0\\ \hat{\omega }\end{array}\right)$$
显然$\omega$是$n$维的单位向量
$$H^{(2)}=I-2\omega {\omega }^T$$
因此$H^{(2)}$也是初等反射矩阵

继续进行下去，便能化为上三角矩阵
$$H^{(n-1)}\cdots H^{(1)}A=A^{(n)}$$
因为$A_{n-1},\cdots ,A_2$的第1列均不为零向量（否则与非奇异矛盾），所以这个过程可以执行到底

求法

由上述定理
$A=(H^{(n-1)}\cdots H^{(1)}{)}^{-1}{A}^{(n)}$,令
$$R=A^{(n)}$$
$$Q=(H^{(n-1)}\cdots H^{(1)}{)}^{-1}=(H^{(n-1)}\cdots H^{(1)}{)}^T$$
因为$H^{(i)}(i=1,2,\cdots ,n-1)$是正交矩阵，所以他们的乘积的逆矩阵$Q$也是正交矩阵，于是
$$A=QR$$

可以看出，豪斯霍尔德方法只要左乘$n-1$个初等矩阵，计算量大约是吉文斯方法的一半

吉文斯方法和豪斯霍尔德方法都可以推广到复矩阵
证明：（不会）