矩阵分解及计算

矩阵分解

满秩分解

满秩分解的形式：
$$A=BC$$
满秩分解定理：设$m\times n$矩阵$A$的秩为r，存在$m\times r$矩阵$B$和$r\times n$矩阵$C$使得 $A=BC$，并且rank($B$)=rank($C$)。

分解步骤：

1. 初等变换法，将原来矩阵写为：
   $$(A|I)$$
   然后将A变换为一个行阶梯形，右侧的单位阵就会变换为一个初等矩阵。

   然后根据去掉A中全为0的行，同时相应的去掉I变换后相应的列，就构成了一个行满秩和列满秩矩阵，其中A变换后应当作为行满秩($C$)放在右边，I变换后做处理的矩阵作为列满秩($B$)放在左边。

   

去掉B最后一行

由P求可逆阵对应去最后一列，最后得到

2. 利用下三角矩阵变换

   与法1同理，只不过写成下三角形式，不需要进行行变换过程，只是一个矩阵乘法的过程。

   首先化去第一列，使得第一个元素不为0，其余都为0，此时对应的下三角矩阵$L_1$应当第一列第一个元素为1，剩下为行变换操作的系数。同理继续化去第二列，使得满足阶梯型，获得$L_2$，直至到满足阶梯型。

   其次将所有的下三角矩阵相乘，并去逆矩阵。

   那么下三角矩阵就作为左侧的列满秩，得到的行阶梯型作为右边的行满秩（需要去除对应的0行以及相应的列）。

   注意如果一开始以0打头，那么先需要做一个交换然后再进行后续操作，即第一个元素绝对不能为0。

   

   此处由于0元素在第一列第一个，需要做一个行交换。

   

   然后再使用下三角进行转换求解。

   

三角分解

1. LU分解

   LU的分解形式为：
   $$A=\left(\begin{array}{cccc}\ast & 0& 0& 0\\ \ast & \ast & 0& 0\\ \ast & \ast & \ast & 0\\ \ast & \ast & \ast & \ast \end{array}\right)\left(\begin{array}{cccc}\ast & \ast & \ast & \ast \\ 0& \ast & \ast & \ast \\ 0& 0& \ast & \ast \\ 0& 0& 0& \ast \end{array}\right)$$
   能够LU分解的充要条件是$A$的所有顺序主子是均非0。

   分解步骤与满秩分解相同，构造多个下三角矩阵，然后计算到下三角，和上三角，但是不需要去0行。

   我们看满秩分解的

   

   此时第一行不进行行变换得到的结果其实就是一个三角分解。

2. LDU分解

   相比于LU分解，只是将形式改变为
   $$A=\left(\begin{array}{cccc}\ast & 0& 0& 0\\ \ast & \ast & 0& 0\\ \ast & \ast & \ast & 0\\ \ast & \ast & \ast & \ast \end{array}\right)\left(\begin{array}{cccc}\ast & 0& 0& 0\\ 0& \ast & 0& 0\\ 0& 0& \ast & 0\\ 0& 0& 0& \ast \end{array}\right)\left(\begin{array}{cccc}1& \ast & \ast & \ast \\ 0& 1& \ast & \ast \\ 0& 0& 1& \ast \\ 0& 0& 0& 1\end{array}\right)$$
   在LU分解的基础上提取出上三角矩阵对角线的元素，上三角矩阵中除对角线外的元素除以该行的第一个非0元素。

QR分解

QR分解将形式为
$$A=Q\left(\begin{array}{cccc}\ast & \ast & \ast & \ast \\ 0& \ast & \ast & \ast \\ 0& 0& \ast & \ast \\ 0& 0& 0& \ast \end{array}\right)$$
其中Q是一个正交矩阵。

分解步骤：

假设$A$为一个$3\times 3$的矩阵，记为$({\alpha }_1,{\alpha }_2,{\alpha }_3)$。

1. 对${\alpha }_1,{\alpha }_2,{\alpha }_3$进行正交化，有：
   $$\begin{gathered} {\beta }_1={\alpha }_1 \\ {\beta }_2={\alpha }_2-k_{21}{\beta }_1 \\ {\beta }_3={\alpha }_3-k_{31}{\beta }_1-k_{3_2}{\beta }_2 \end{gathered}$$
   其中$k_{21}=\frac{<{\alpha }_2,{\beta }_1>}{<{\beta }_1,{\beta }_1>}$,$k_{31}=\frac{<{\alpha }_3,{\beta }_1>}{<{\beta }_1,{\beta }_1>}$,$k_{32}=\frac{<{\alpha }_3,{\beta }_2>}{<{\beta }_2,{\beta }_2>}$

2. 单位化，得到矩阵$Q:Q=(\frac{{\beta }_1}{\Vert {\beta }_1\Vert },\frac{{\beta }_2}{\Vert {\beta }_2\Vert },\frac{{\beta }_3}{\Vert {\beta }_3\Vert })$

   1、2两步实际上是进行了施密特正交化。

3. 得到R矩阵
   $$R=\left(\begin{array}{ccc}\Vert {\beta }_1\Vert & & \\ & \Vert {\beta }_2\Vert & \\ & & \Vert {\beta }_3\Vert \end{array}\right)\left(\begin{array}{ccc}1& k_{21}& k_{31}\\ & 1& k_{32}\\ & & 1\end{array}\right)$$

4. $A=QR$

奇异值分解

奇异值分解形式为
$$A=U\left(\begin{array}{cc}\sum & 0\\ 0& 0\end{array}\right)V^H$$
其中$\sum =diag({\sigma }_1,\cdots ,{\sigma }_r)$

分解步骤：

假设A为$m\times n$，那么奇异值分解就应该为$m\times m$、$m\times n$、$n\times n$

1. 首先求$A^{H}A$，并求出对应的特征值${\lambda }_i$,${\lambda }_i$开方，按照大小排序，得到${\sigma }_i$，从而构造$\sum$矩阵，然后补零，就可以构造出 $\left(\begin{array}{cc}\sum & 0\\ 0& 0\end{array}\right)$
2. 解出特征之${\lambda }_i$对应$A^{H}A$的特征向量${\xi }_i$，并进行单位化,得到$v_i$，从构造出矩阵$V=\left(\begin{array}{c}{v}_1,\cdots ,v_n\end{array}\right)$
3. 根据奇异值分解，进行变换，得到$U_1=AV{\left(\begin{array}{cc}\sum & 0\\ 0& 0\end{array}\right)}^{-1}$，此时得到的$U_1$矩阵为$m\times r$,需要进行扩充。
4. 我们构造一个$U_2$$(r\times n)$矩阵，使得$U_1^H{U}_2=0$
5. 最后将$U_1$与$U_2$拼接，得到$U$
6. 最后得到SVD$A=U\left(\begin{array}{cc}\sum & 0\\ 0& 0\end{array}\right)V^H$

考点

1. 满秩分解
2. 奇异值分解和QR分解选其一

参考

矩阵论-戴华

【矩阵论】Chapter 6—矩阵分解知识点总结复习（附Python实现）