矩阵的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}$是一个上三角矩阵，则
R = ( ν 1 q 1 ∗ a 2 q 1 ∗ a 3 ⋯ q 1 ∗ a n 0 ν 2 q 2 ∗ a 3 ⋯ q 2 ∗ a n 0 0 ν 3 ⋯ q 3 ∗ a n ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ ν n ) \mathbf{R}=

R= ​ν1​00⋮0​q1∗​a2​ν2​0⋮0​q1∗​a3​q2∗​a3​ν3​⋮0​⋯⋯⋯⋱⋯​q1∗​an​q2∗​an​q3∗​an​⋮νn​​ ​
其中$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 ∗ 1 ± μ ∣ ∣ A ∗ 1 ∣ ∣ e 1 , μ = { 1 if  x 1  is real , x 1 / ∣ x 1 ∣ if  x 1  is not real , u=A_{*1}\pm\mu||A_{*1}||e_1,\quad\left.\mu=\left\{

\right.\right. u=A∗1​±μ∣∣A∗1​∣∣e1​,μ={1x1​/∣x1​∣​if x1​ is real,if x1​ is not real,​

根据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$

所以 R 1 A = [ R 1 A ∗ 1 ∣ R 1 A ∗ 2 ∣ ⋯ ∣ R 1 A ∗ n ] = ( t 11 t 1 T 0 A 2 ) \left.\mathbf{R}_1\mathbf{A}=[\mathbf{R}_1\mathbf{A}_{*1}|\mathbf{R}_1\mathbf{A}_{*2}|\cdots|\mathbf{R}_1\mathbf{A}_{*n}]=\left(

\right.\right) R1​A=[R1​A∗1​∣R1​A∗2​∣⋯∣R1​A∗n​]=(t11​0​t1T​A2​​)，其中$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个值，即存在：
P 12 x = ( x 1 2 + x 2 2 0 x 3 x 4 ⋮ x n ) ,   P 13 P 12 x = ( x 1 2 + x 2 2 + x 3 2 0 x 4 ⋮ x n ) ,   … ,   P 1 n ⋯ P 13 P 12 x = ( ∥ x ∥ 0 0 ⋮ 0 ) . \mathbf P_{12}\mathbf x=

,~\mathbf P_{13}\mathbf P_{12}\mathbf x=,~\ldots,~\mathbf P_{1n}\cdots\mathbf P_{13}\mathbf P_{12}\mathbf x=. P12​x= ​x12​+x22​ ​0x3​x4​⋮xn​​ ​, P13​P12​x= ​x12​+x22​+x32​ ​0x4​⋮xn​​ ​, …, P1n​⋯P13​P12​x= ​∥x∥00⋮0​ ​.

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