基于QR分解迭代求解方阵特征值和特征向量( 二 ) _矩阵

引理2：若 A ∈ R m × n A\in \ R^{m\times n} A∈Rm×n是一个列满秩矩阵，则 A A A总可以通过上述初代变换分解为 A = Q R A=QR A=QR的形式，其中 Q Q Q是一个列正交矩阵， R R R是一个非奇异上三角矩阵。
以上引理的证明不再赘述，可以查阅有关线性代数资料。有了上述的铺垫，就可以给出初等变换法计算QR分解的过程：
step1:求出正定对称矩阵 A T A A^TA ATA
step2:对 A T A A^TA ATA同时进行上述初等行、列变换，得到对角矩阵且主对角线上的元素全部为正实数。又由于”对矩阵做初等行变换等价于用相应的初等矩阵左乘该矩阵，对矩阵做初等列变换等价于用相应的初等矩阵右乘该矩阵“，故而存在下三角矩阵 B B B和上三角矩阵 B T B^T BT(显然可逆)，使得 B T ( A T A ) B = d i a g ( d 1 , d 2 , ? , d n ) ( d i ≥ 0 ) B^T(A^TA)B=diag(d_1,d_2,\cdots ,d_n)(d_i\geq 0) BT(ATA)B=diag(d1?,d2?,?,dn?)(di?≥0)
step3:设 C = d i a g ( d 1 , d 2 , ? , d n ) C=diag(\sqrt d_1,\sqrt d_2,\cdots,\sqrt d_n) C=diag(d?1?,d?2?,?,d?n?)，则 C ? 1 [ B T ( A T A ) B ] C ? 1 = ( A B C ? 1 ) T ( A B C ? 1 ) = I C^{-1}[B^T(A^TA)B]C^{-1}=(ABC^{-1})^T(ABC^{-1})=I C?1[BT(ATA)B]C?1=(ABC?1)T(ABC?1)=I,其中 I I I为单位阵
step4:令 Q = A B C ? 1 Q=ABC^{-1} Q=ABC?1， Q Q Q是一个列正交矩阵， R = C B ? 1 R=CB^{-1} R=CB?1是一个非奇异的上三角矩阵，得出QR分解式
看完上述步骤，如果感觉还是难以理解，我们再进行更加形象化的描述。假设矩阵 A ∈ R m × n A\in \ R^{m\times n} A∈Rm×n如下：
( a 11 a 12 ? a 1 n a 21 a 22 ? a 2 n ? ? ? ? a m 1 a m 2 ? a m n ) \begin{} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{} ??????a11?a21??am1??a12?a22??am2???????a1n?a2n??amn????????
那么 A T A ∈ R n × n A^TA\in \ R^{n\times n} ATA∈Rn×n是一个对称正定矩阵：
( a 11 a 12 ? a 1 n a 12 a 22 ? a 2 n ? ? ? ? a 1 n a 2 n ? a n n ) \begin{} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{12} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1n} & a_{2n} & \cdots & a_{nn} \\ \end{} ??????a11?a12??a1n??a12?a22??a2n???????a1n?a2n??ann????????
【基于QR分解迭代求解方阵特征值和特征向量】我们在上述 A T A A^TA ATA的下方拼接一个单位阵，就得到了：
( a 11 a 12 ? a 1 n a 12 a 22 ? a 2 n ? ? ? ? a 1 n a 2 n ? a n n 1 0 ? 0 0 1 ? 0 ? ? ? ? 0 0 ? 1 ) \begin{} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{12} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1n} & a_{2n} & \cdots & a_{nn} \\ \hline 1 & 0 &\cdots &0\\0 & 1& \cdots &0\\ \vdots & \vdots &\ddots &\vdots \\ 0& 0&\cdots &1\\ \end{} ???????????????a11?a12??a1n?10?0?a12?a22??a2n?01?0??????????a1n?a2n??ann?00?1?????????????????
进行上述的初等行列变换，将上方的 A T A A^TA ATA化成对角矩阵如下：
( d 1 0 ? 0 0 d 2 ? 0 ? ? ? ? 0 0 ? d n b 11 b 12 ? b 1 n b 21 b 22 ? b 2 n ? ? ? ? b n 1 b n 2 ? b n n ) \begin{}d_1 & 0 & \cdots & 0 \\0 & d_2 & \cdots & 0 \\\vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & d_n \\\hline b_{11} & b_{12} &\cdots & b_{1n}\\b_{21} & b_{22}& \cdots &b_{2n}\\\vdots & \vdots &\ddots &\vdots \\ b_{n1}& b_{n2}&\cdots &b_{nn}\\\end{} ???????????????d1?0?0b11?b21??bn1??0d2??0b12?b22??bn2???????????00?dn?b1n?b2n??bnn??????????????????
将上方对角阵对角元开方后记作 C C C，下面的方阵记为 B B B然后我们就可以得到 Q = A B C ? 1 Q=ABC^{-1} Q=ABC?1， R = C B ? 1 R=CB^{-1} R=CB?1.

文章插图
好的，现在我们已经完完全全了解了初等变换法求QR分解的完整过程啦！下面有了QR分解和迭代思路，特征值问题便可以迎刃而解。
四、C++实现
初等变换法QR分解的代码如下：