矩阵的QR分解

矩阵的QR分解

GramSchmidt

设存在 B = { x 1 , x 2 , … , x n } \mathcal{B}=\left\{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}\right\} B={x1​,x2​,…,xn​}在施密特正交化过程中

1. $q_1=\frac{x_1}{||x_1||}$
2. $q_k=\frac{x_k-{\sum }_{i=1}^{k-1}⟨q_i,x_k⟩u_i}{||x_k-{\sum }_{i=1}^{k-1}⟨q_i,x_k⟩u_i||}$

对于任意一个矩阵 A m × n = { a 1 ∣ a 2 ∣ … ∣ a n } A_{m\times n}=\{a_1|a_2|\dots|a_n\} Am×n​={a1​∣a2​∣…∣an​}，其行向量线性无关，则存在$A=QR$，其 Q m × n = { q 1 ∣ q 2 ∣ … ∣ q n } Q_{m\times n}=\{q_1|q_2|\dots|q_n\} Qm×n​={q1​∣q2​∣…∣qn​}矩阵是$R(A)$的一组正交基，$R_{m\times m}$是一个上三角矩阵，则
$$\mathbf{R}=\left(\begin{array}{ccccc}{\nu }_1& {\mathbf{q}}_1^{\ast }{\mathbf{a}}_2& {\mathbf{q}}_1^{\ast }{\mathbf{a}}_3& \cdots & {\mathbf{q}}_1^{\ast }{\mathbf{a}}_n\\ 0& {\nu }_2& {\mathbf{q}}_2^{\ast }{\mathbf{a}}_3& \cdots & {\mathbf{q}}_2^{\ast }{\mathbf{a}}_n\\ 0& 0& {\nu }_3& \cdots & {\mathbf{q}}_3^{\ast }{\mathbf{a}}_n\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & {\nu }_n\end{array}\right)$$
其中$v_1=||a_1||,v_k=||a_k-{\sum }_{i=1}^{k-1}<q_i,a_k>q_i||\text{for k>1}$

Householder

酉矩阵：一个复数矩阵$U_{n\times n}$它的行或列构成一个$C^n$的正交基，其中$U^{\ast }U=I，||Ux|{|}_2=||x|{|}_2$

对于非0向量$U\in C^{n\times 1}$ ，则$U$的正交投影是$P_u=\frac{U{U}^{\ast }}{U^{\ast }U}$，其垂直方向的投影是$P_{u\perp }=I-\frac{U{U}^{\ast }}{U^{\ast }U}$

初等反射（ householder 变换）

其中对于$u^{\perp }$ 的初等反射为 $R=I-2\frac{U{U}^{\ast }}{U^{\ast }U}$

对于矩阵${\mathbf{A}}_{m\times n}=[{\mathbf{A}}_{\ast 1}|{\mathbf{A}}_{\ast 2}|\cdots |{\mathbf{A}}_{\ast n}]$

构建基本反射$R=I-2\frac{U{U}^{\ast }}{U^{\ast }U}$，其中$u=A_{\ast 1}\pm \mu ||A_{\ast 1}||e_1,\mu =\{\begin{array}{cc}1& \text{if }{x}_1\text{ is real},\\ x_1/|x_1|& \text{if }{x}_1\text{ is not real},\end{array}$

根据householder变换可得${\mathbf{R}}_1{\mathbf{A}}_{\ast 1}=\mp \mu \Vert {\mathbf{A}}_{\ast 1}\Vert {\mathbf{e}}_1=(t_{11},0,\cdots ,0{)}^T$

所以${\mathbf{R}}_1\mathbf{A}=[{\mathbf{R}}_1{\mathbf{A}}_{\ast 1}|{\mathbf{R}}_1{\mathbf{A}}_{\ast 2}|\cdots |{\mathbf{R}}_1{\mathbf{A}}_{\ast n}]=(\begin{array}{cc}{t}_{11}& {\mathbf{t}}_1^T\\ 0& {\mathbf{A}}_2\end{array})$，其中$A_2$ 是一个$(m-1\times n-1)$的矩阵

若同时对$A_2$矩阵进行操作可以得到一个上三角矩阵$(m=n)$，即$PA=T$，其中$P$矩阵为elementary reflector矩阵的乘积，$T$矩阵为上梯形

Givens 旋转

对于正交矩阵$P$形式如上，表示在平面$(i,j)$上旋转，其中$s^2+c^2=1$

对于向量 X = { x 1 , x 2 … , x n } T X=\{x_1,x_2\dots,x_n\}^T X={x1​,x2​…,xn​}T， P i j X = { x 1 , x 2 , … , c x i + s x j , … , − s x i + c x j , … , x n } T P_{ij}X=\{x_1,x_2,\dots,cx_i+sx_j,\dots,-sx_i+cx_j,\dots,x_n\}^T Pij​X={x1​,x2​,…,cxi​+sxj​,…,−sxi​+cxj​,…,xn​}T，易知旋转矩阵乘某一个向量，其只有在该旋转平面上的值发生改变，若存在：
$$c=\frac{x_i}{\sqrt{x_i^2+x_j^2}},s=\frac{x_j}{\sqrt{x_i^2+x_j^2}}$$
则 P i j X = { x 1 , x 2 , … , x i 2 + x j 2 , … , 0 , … , x n } T P_{ij}X=\{x_1,x_2,\dots,\sqrt{x_i^2+x_j^2},\dots,0,\dots,x_n\}^T Pij​X={x1​,x2​,…,xi2​+xj2​ ​,…,0,…,xn​}T

由此可以实现消去向量的第j个值，即存在：
$${\mathbf{P}}_{12}\mathbf{x}=\left(\begin{array}{c}\sqrt{x_1^2+x_2^2}\\ 0\\ x_3\\ x_4\\ ⋮\\ x_n\end{array}\right),{\mathbf{P}}_{13}{\mathbf{P}}_{12}\mathbf{x}=\left(\begin{array}{c}\sqrt{x_1^2+x_2^2+x_3^2}\\ 0\\ x_4\\ ⋮\\ x_n\end{array}\right),\dots ,{\mathbf{P}}_{1n}\cdots {\mathbf{P}}_{13}{\mathbf{P}}_{12}\mathbf{x}=\left(\begin{array}{c}\Vert \mathbf{x}\Vert \\ 0\\ 0\\ ⋮\\ 0\end{array}\right).$$

若$A$矩阵是非奇异矩阵，则可以利用householder、givens以及Gram-schmidt来产生一个正交矩阵$Q$以及一个上三角矩阵$R$其对角线上全为正数，可以得到形如$A=QR$的形式