矩阵求逆的几种方法

在学习Hill算法的过程中,突然意识到自己对矩阵的很多东西都已经还给老师,于是打算把这个丢了快两年的东西重新捡起来学习一下

待定系数法

比较适用于低阶的矩阵,高阶矩阵计算量有亿点点大

没啥好说的,就是列个矩阵方程然后再分解为我们所熟知的方程格式

然后再求解

eg:

$\left[ \begin{matrix} 1 & 2 \\ -1 &-3 \end{matrix} \right]$的逆矩阵的求解

设逆矩阵为$\left[ \begin{matrix} a & b \\ c &d \end{matrix} \right]$

则$\left[ \begin{matrix} 1 & 2 \\ -2 &-3 \end{matrix} \right]\left[ \begin{matrix} a & b \\ c &d \end{matrix} \right]=\left[ \begin{matrix} 1 & 0 \\ 0 &1 \end{matrix} \right]$

即有

$\left[ \begin{matrix} a+2c & b+2d \\ -2a-3c &-2b-3d \end{matrix} \right]=\left[ \begin{matrix} 1 & 0 \\ 0 &1 \end{matrix} \right]$

可以得到以下方程

$a+2c=1$

$b+2d=0$

$-2a-3c=0$

$-2b-3d=1$

解得a=-3,b=-2,c=2,d=1

高斯消元法

这个应该是流传最广的求逆元版本,虽然我除了在考试手算中有所应用,目前还没有看到其他使用这个的地方

高斯消元法有两个细分:行变换与列变换,原理是一样的,一般用行变换。

高斯消元法先将矩阵A与单位矩阵I进行连接形成一个新的增广矩阵.

%E7%9F%A9%E9%98%B5%E6%B1%82%E9%80%86%E7%9A%84%E5%87%A0%E7%A7%8D%E6%96%B9%E6%B3%95%20121b63c332ea4e9b8e1a43957b6070ff/Untitled.png

eg:

$K=\left[ \begin{matrix} 2 & -1 & 0 \\ -1 &2 & -1 \\ 0 &-1& 2 \end{matrix} \right]$

接下来用高斯消元法来求K的逆矩阵

$\left[ \begin{matrix} K&I \end{matrix} \right]=\left[ \begin{matrix} 2 & -1 & 0 &1&0&0\\ -1 &2 & -1&0&1&0 \\ 0 &-1& 2&0&0&1 \end{matrix} \right]$→$\left[ \begin{matrix} 2 & -1 & 0 &1&0&0\\ 0 &3/2 & -1&1/2&1&0 \\ 0 &-1& 2&0&0&1 \end{matrix} \right]$→$\left[ \begin{matrix} 2 & -1 & 0 &1&0&0\\ 0 &3/2 & -1&1/2&1&0 \\ 0 &0& 4/3&1/3&2/3&1 \end{matrix} \right]$

K矩阵变成了上三角矩阵,接下来回代就可以分别求解出$K^{-1}$,如下

$\left[ \begin{matrix} 2 & -1 & 0 &1&0&0\\ 0 &3/2 & 0&3/4&3/2&3/4 \\ 0 &0& 4/3&1/3&2/3&1 \end{matrix} \right]$→$\left[ \begin{matrix} 2 & 0 & 0 &3/2&1&1/2\\ 0 &3/2 & 0&3/4&3/2&3/4 \\ 0 &0& 4/3&1/3&2/3&1 \end{matrix} \right]$→

$\left[ \begin{matrix} 1 & 0 & 0 &3/4&1/2&1/4\\ 0 &1 & 0&1/2&1&1/2 \\ 0 &0& 1&1/4&1/2&3/4 \end{matrix} \right]=$$\left[ \begin{matrix} I & K^{-1} \end{matrix} \right]$

求得逆矩阵$K^{-1}$

LU分解法

LU分解法实际上是高斯消元法的变种应用,这个方法更易于实现并行化。计算机基本用这种方法,面对大矩阵时有奇效。

LU分解即将一个矩阵分解为一个单位下三角矩阵和一个上三角矩阵的乘积。

需要注意的是,不是所有的矩阵都可以进行LU分解的

LU分解的前提

  1. 矩阵是方阵(LU分解主要是针对方阵);
  2. 矩阵是可逆的,也就是该矩阵是满秩矩阵,每一行都是独立向量;
  3. 消元过程中没有0主元出现,也就是消元过程中不能出现行交换的初等变换

LU分解求逆矩阵的流程

SVD分解法

即奇异值分解法(SingularValue Decomposition)

SVD分解可以对不是方阵的矩阵进行分解

SVD分解将矩阵A分解为三个矩阵的乘积,分别为正交矩阵U、对角矩阵W和正交矩阵的转置矩阵V

$A=UWV^T$

U是一个$mXm$的的矩阵,W是一个$mXn$的矩阵,且除了主对角线上的元素以外全为0.主对角线上的每个元素都被称为奇异值,V是一个$nXn$的矩阵

求逆即

$A^{-1}=VW^{-1}U^T$

如何得到$UWV^T$

我们先将A和A的转置做矩阵乘法,那么会得到m*m的一个方阵$AA^T$,既然$AA^T$是方阵,所以可以进行特征分解可以得到

%E7%9F%A9%E9%98%B5%E6%B1%82%E9%80%86%E7%9A%84%E5%87%A0%E7%A7%8D%E6%96%B9%E6%B3%95%20121b63c332ea4e9b8e1a43957b6070ff/Untitled%202.png

可以得到矩阵 [公式] 的n个特征值和对应的n个特征向量v了。将 [公式] 的所有特征向量张成一个n×n的矩阵V,于是我们就得到了矩阵V,我们把V中的每个特征向量叫做A的右奇异向量。

同理我们可以特征分解到特征值和特征向量满足下式

%E7%9F%A9%E9%98%B5%E6%B1%82%E9%80%86%E7%9A%84%E5%87%A0%E7%A7%8D%E6%96%B9%E6%B3%95%20121b63c332ea4e9b8e1a43957b6070ff/Untitled%203.png

同理,[公式] 的所有特征向量张成一个m×m的矩阵U,这就是U矩阵了,U矩阵里的每个特征向量叫做A的左奇异向量

现在就差W矩阵了

因为有

$A=UWV^T=>AV=UWVTV=>AV=UW=>Av_i=\sigma_iu_i=>\sigma_i=Av_i/u_i$

通过这个我们可以求得每个奇异值的值,进而可以求奇异值矩阵W

下面补充对于为什么$A^TA$的特征向量组成的就是我们SVD中的V矩阵,而$AA^T$的特征向量组成的就是我们SVD中的U矩阵

下面以V矩阵的证明为例子

$A=UWV^T=>A^T=VWU^T=>A^TA=VWU^TUWV^T=VW^2V^T$

得证

SVD例题

对A=$\left[ \begin{matrix} 0 & 1 \\ 1 &1 \\ 1&0 \end{matrix} \right]$

先求$A^TA$和$AA^T$

$A^TA=\left[ \begin{matrix} 0 & 1 & 1 \\ 1 &1 & 0 \end{matrix} \right]\left[ \begin{matrix} 0 & 1 \\ 1 &1 \\ 1&0 \end{matrix} \right]=\left[ \begin{matrix} 2 & 1 \\ 1 &2 \end{matrix} \right]$

$AA^T=\left[ \begin{matrix} 0 & 1 \\ 1 &1 \\1&0 \end{matrix} \right]\left[ \begin{matrix} 0 & 1&1 \\ 1 &1&0 \end{matrix} \right]=\left[ \begin{matrix} 1 & 1&0 \\ 1 &2&1\\0&1&1 \end{matrix} \right]$

进而求得$A^TA$的特征值和特征向量

$\lambda_1=3;v_1=\left[ \begin{matrix} 1/\sqrt2 \\ 1 &2&1\\0&1&1 \end{matrix} \right]$ $\lambda_2=1;v_2=\left[ \begin{matrix} -1/\sqrt2 \\ 1/\sqrt2 \end{matrix} \right]$

接着求$AA^T$的特征值和特征向量

$\lambda_1=3;u_1=\left[ \begin{matrix} 1/\sqrt6 \\ 2/\sqrt6\\1/\sqrt6 \end{matrix} \right]$ $\lambda_2=1;u_2=\left[ \begin{matrix} 1/\sqrt2 \\ 0\\-1/\sqrt2 \end{matrix} \right]$ $\lambda_3=0;u_3=\left[ \begin{matrix} 1/\sqrt3 \\ -1/\sqrt3\\1/\sqrt3 \end{matrix} \right]$

通过$Av_i=\sigma_iu_i,i=1,2$求奇异值

$\left[ \begin{matrix} 0&1 \\ 1&1\\1&0 \end{matrix} \right]\left[ \begin{matrix} 1\sqrt2 \\ 1\sqrt2 \end{matrix} \right]=\sigma_1\left[ \begin{matrix} 1/\sqrt6 \\ 2/\sqrt6\\1/\sqrt6 \end{matrix} \right]=>\sigma_1=\sqrt3$

$\left[ \begin{matrix} 0&1 \\ 1&1\\1&0 \end{matrix} \right]\left[ \begin{matrix} -1\sqrt2 \\ 1\sqrt2 \end{matrix} \right]=\sigma_2\left[ \begin{matrix} 1/\sqrt2 \\ 0\\-1/\sqrt2 \end{matrix} \right]=>\sigma_2=1$

也可以用 [公式] 直接求出奇异值为 [公式] 和1.

最终完成svd分解为

$A=UWV^T=\left[ \begin{matrix} 1/\sqrt6 & 1\sqrt2&1/\sqrt3 \\ 2/\sqrt6&0&-1/\sqrt3\\1/\sqrt6&-1/\sqrt2&1/\sqrt3 \end{matrix} \right]\left[ \begin{matrix} \sqrt3&0 \\ 0&1\\0&0 \end{matrix} \right]\left[ \begin{matrix} 1/\sqrt2&1/\sqrt2 \\ -1/\sqrt2&1/\sqrt2 \end{matrix} \right]$