矩阵分解

所谓矩阵分解就是将矩阵分解成两三个标准矩阵的乘积
矩阵分解的目的在于

• 求解线性方程组
• 矩阵存储
• 矩阵重构以预测

矩阵分解的根本方法在于线性变换

矩阵分解的分类

1. 对角化分解：通过正交变换将矩阵对角化

   1. 奇异值分解SVD：针对一般矩阵的分解
      $A=U\Sigma V^H, 其中U，V为酉矩阵，\Sigma 为对角矩阵$A=UΣVH,其中U，V为酉矩阵，Σ为对角矩阵
   2. 特征值分解EVD（谱分解）：针对对称矩阵

   $A^HA=V\Sigma V^H$AHA=VΣVH

   3. CS分解:正交矩阵分块的同时对角化分解

2. 三角化分解：分解为正交矩阵和三角矩阵之积，或上三角矩阵与下三角矩阵

   1. Cholesky分解：针对对称正定矩阵

   $A=GG^T,其中G为下三角矩阵$A=GGT,其中G为下三角矩阵

   2. QR分解：针对一般矩阵

$A=QR，\\其中Q是正交矩阵，R是上三角矩阵$A=QR，其中Q是正交矩阵，R是上三角矩阵

​ 3. LU分解：针对非奇异矩阵
$A=LU \\ 其中L是下三角矩阵，U是上三角矩阵$A=LU其中L是下三角矩阵，U是上三角矩阵
3. 三角-对角化分解：将矩阵分解为三个矩阵的标准型（两个三角矩阵和一个对角矩阵）之积，或分解为对角矩阵和上三角矩阵之和

1. $LDM^T$LDMT分解：针对非对称矩阵

$A = LDM^T \\ 其中，L和M为单位下三角矩阵，D为对角矩阵$A=LDMT其中，L和M为单位下三角矩阵，D为对角矩阵

2. $LDL^T$LDLT分解：针对对称矩阵

$A = LDL^T$A=LDLT

3. Schur 分解：针对复矩阵

$Q^TAQ=D+N \\ 其中Q是酉矩阵，D是对角矩阵，N是严格上三角矩阵（对角线为0的上三角矩阵）$QTAQ=D+N其中Q是酉矩阵，D是对角矩阵，N是严格上三角矩阵（对角线为0的上三角矩阵）

4. 三对角化分解

   1. Householder分解

   $H^TAH=T,H=H_1H_2H_3...为Householder矩阵$HTAH=T,H=H1​H2​H3​...为Householder矩阵

对角化分解

CS分解

现今主要用于Quantum Compiling，这里不详细介绍
$Q = \begin{bmatrix} Q_{11} & Q_{12} \\ Q_{21} & Q_{22} \end{bmatrix}为正交矩阵，存在\\ \begin{bmatrix} U_{1} & 0 \\ 0 & U_{2} \end{bmatrix} \begin{bmatrix} Q_{11} & Q_{12} \\ Q_{21} & Q_{22} \end{bmatrix} \begin{bmatrix} V_{1} & 0 \\ 0 & V_{2} \end{bmatrix}= \begin{bmatrix} I_{k-j} & 0 & 0 \\ 0 & C & S \\ 0 & -S & C \end{bmatrix} \\ 其中U_1,U_2,V_1,V_2为正交矩阵，C,S为对角矩阵$Q=[Q11​Q21​​Q12​Q22​​]为正交矩阵，存在[U1​0​0U2​​][Q11​Q21​​Q12​Q22​​][V1​0​0V2​​]=⎣⎡​Ik−j​00​0C−S​0SC​⎦⎤​其中U1​,U2​,V1​,V2​为正交矩阵，C,S为对角矩阵

LU分解

定义

• 设$A\in R^{m*n}$A∈Rm∗n，将矩阵分解为A=LU，其中L为m*n单位下三角矩阵，U为A的阶梯形矩阵

• 如果$A\in R^{n*n}$A∈Rn∗n非奇异，并且其LU存在的话，则A的LU分解是唯一的，且$det(A)=u_{11}u_{22}……u_{nn}$det(A)=u11​u22​……unn​

  证明
  若否，设$A=L_1U_2=L_2U_2$A=L1​U2​=L2​U2​是非奇异矩阵的两个LU分解，则$L_1U_2=L_2U_2$L1​U2​=L2​U2​
  易证，上三角矩阵和上三角矩阵的乘积还是上三角矩阵
  由于 $L_2^{-1}L_1$L2−1​L1​是下三角矩阵，$U_2U_1^{-1}$U2​U1−1​是上三角矩阵所以若$L_1U_1=L_2U_2$L1​U1​=L2​U2​，L，U均为单位矩阵，则$L_1=L_2,U_1=U_2$L1​=L2​,U1​=U2​，所以分解唯一。

求解方程

求解线性方程组Ax=b时，将A进行 LU分解，LUx=b，令y=Ux,方程组变为Ly=b，解得y，再求解Ux=y。由于L，U为特殊矩阵，这两个方程都可以用回代法轻松求解。

1. 分解A=LU
2. 用前向回代法求解下三角矩阵方程Ly=b
3. 用后向回代法求解下三角矩阵方程Ux=y

• 对于AX=B也可同样求解

分解方法

1. 方法一

• 将A初等变换$E_1E_2...E_k​$E1​E2​...Ek​​为阶梯形矩阵U

• 对单位矩阵I进行行初等变换$E^{-1}_kE^{-1}_{k-1}...E^{-1}_{1}$Ek−1​Ek−1−1​...E1−1​为L，即$L=E^{-1}_1E^{-1}_{2}...E^{-1}_{k}$L=E1−1​E2−1​...Ek−1​

  注： 初等矩阵的逆矩阵：

  • 行交换：行交换
  • 某行乘以一个倍数：除以这个倍数
  • 某行乘以一个倍数加到另一行：乘上这个数的相反数加到另一行

2. 方法二
   可以利用方法一中步骤1 将A 变换为阶梯型矩阵U 过程中的有关矩阵$A, A_1, A_2, U​$A,A1​,A2​,U​ 的主元列构造单位下三角矩阵L。注：这里的$A_i​$Ai​​是将前i列全部变换为主元下全部元素为0的矩阵
   具体方法是：
   （1）取出A 的第一个主元所在的列（不失一般性，假定为第1 列），将其归一化（第
   一个元素为1）后，作为L 的第一列。
   （2）取出$A_{i−1}​$Ai−1​​ 的第i 个主元及下面的同列元素构成的部分组成一个(n − i) × 1 向量，
   将其归一化后，作为L 的第i 列的下半部分，其中，i = 2, 3, · · · , n。

Cholesky 分解

定义

设$A = [a_{ij}] ∈ R^{n×n}$A=[aij​]∈Rn×n是对称正定矩阵，$A = GG^T$A=GGT 称为矩阵A 的Cholesky 分解，且分解是唯一的，其中$G ∈ R^{n×n}$G∈Rn×n是一个具有正的对角线元素的下三角矩阵，即
$G=\begin{bmatrix}g_{11}\\g_{21}&g_{22}\\.&.&.\\g_{n1} & g_{n2}&...&g_{nn}\end{bmatrix}$G=⎣⎢⎢⎡​g11​g21​.gn1​​g22​.gn2​​....​gnn​​⎦⎥⎥⎤​

逐列求解矩阵G

$\begin{bmatrix}a_{11}&...&...&a_{1n}\\a_{21}&a_{22}&...\\...&...&...\\a_{n1} & a_{n2}&...&a_{nn}\end{bmatrix}=\begin{bmatrix}g_{11}\\g_{21}&g_{22}\\.&.&.\\g_{n1} & g_{n2}&...&g_{nn}\end{bmatrix}\begin{bmatrix}g_{11}&g_{12}&...&g_{n1}\\0&g_{22}\\.&.&.\\0 &0&...&g_{nn}\end{bmatrix}$⎣⎢⎢⎡​a11​a21​...an1​​...a22​...an2​​............​a1n​ann​​⎦⎥⎥⎤​=⎣⎢⎢⎡​g11​g21​.gn1​​g22​.gn2​​....​gnn​​⎦⎥⎥⎤​⎣⎢⎢⎡​g11​0.0​g12​g22​.0​.......​gn1​gnn​​⎦⎥⎥⎤​

• 求解第一列：

  • 比较两边关系，易得$g_{11}=\sqrt{a_{11}}$g11​=a11​​
  • $a_{1i}=g_{11}g_{i1}, \therefore g_{i1}=\frac{a{i1}}{\sqrt{a_{11}}}​$a1i​=g11​gi1​,∴gi1​=a11​​ai1​​(i=1,2,…n)得到G的第一列的元素

• 递推关系求解其余列：

  这里表示由前j-1列求第j列

  • 先求对角线上元素

  $由G的第j行乘上G^T第j列等于a_{jj}可得\\g_{jj} = a_{jj}-\Sigma^{i-1}_{k=1}g^2_{ik}$由G的第j行乘上GT第j列等于ajj​可得gjj​=ajj​−Σk=1i−1​gik2​

  • 求第j列其余元素$g_{ij}​$gij​​，i>j

$a_{ij} =∑^j_{k=1}g_{jk}g_{ik}\\ g_{jj}g_{ij} = a_{ij} −∑^{j-1}_{k=1}g_{jk}g_{ik} = v(i) \space j>1\\ 由G的第j行乘上G^T第i列等于a_{ji}可得\\ a_{ji}=\Sigma^j_{k=1}g_{jk}g_{ik}\\ \therefore g_{ij}=\frac{a_{ji}-\Sigma^{j-1}_{k=1}g_{jk}g_{ik}}{g_{jj}}$aij​=k=1∑j​gjk​gik​gjj​gij​=aij​−k=1∑j−1​gjk​gik​=v(i) j>1由G的第j行乘上GT第i列等于aji​可得aji​=Σk=1j​gjk​gik​∴gij​=gjj​aji​−Σk=1j−1​gjk​gik​​

用于求解方程

$Ax=b\\ G^{-1}Ax=G^{-1}b\\ G^Tx=h,h=G^{-1}b$Ax=bG−1Ax=G−1bGTx=h,h=G−1b
由于G是上三角矩阵，所以方程可用回代法轻松解出

QR 分解

定义

若$A\in R^{m\times n}$A∈Rm×n，且m>=n，则存在列正交矩阵$Q\in R^{m\times m}$Q∈Rm×m和上三角矩阵$R\in R^{m\times n}$R∈Rm×n使得A=QR

• 引理

  若A和B是任意两个$m\times n$m×n矩阵，则$A^HA=B^HB$AHA=BHB，当且仅当存在一个$m\times m$m×m酉矩阵Q使得QA=B

分解方法

1、Gram-Schmidt法QR正交分解

• 将向量$a_1$a1​标准正交化，结果去作$q_1$q1​
  $\begin{cases} R_{11}&=&\lVert a_1 \rVert \\ q_1 &=& \frac{q_1}{R_{11}} \end{cases}${R11​q1​​==​∥a1​∥R11​q1​​​
• 从$a_2$a2​中除去与$a_1$a1​平行的分量，再进行标准正交化，并将结果取作$q_2$q2​则有

$\begin{cases} R_{12}&=&q_1^Ha_2 \\ R_{22}&=&\lVert a_2-q_1R_{12} \\ q_2 &=& (a_2-q_1R_{12})/R_{22} \end{cases}$⎩⎪⎨⎪⎧​R12​R22​q2​​===​q1H​a2​∥a2​−q1​R12​(a2​−q1​R12​)/R22​​