线性代数 --- LU分解（Gauss消元法的矩阵表示）

2023-11-03

Gauss消元法等价于把系数矩阵A分解成两个三角矩阵L和U的乘法

首先，LU分解实际上就是用矩阵的形式来记录的高斯消元的过程。其中，对矩阵A进行高斯消元后的结果为矩阵U，是LU分解后的两个三角矩阵中其中之一。U是一个上三角矩阵，U就是上三角矩阵upper triangle的首字母的大写。

高斯消元的每一步都可以用一个基本消元矩阵E表示。而所有的E都可以收录在一个矩阵当中，我这里叫他Z矩阵。Z矩阵就是集所有基本消元矩阵E于一身的消元矩阵，令Z左乘A就能一次性完成高斯消元的全部过程得到ZA=U。而，要想把消元后的矩阵U还原成原始矩阵A，就需要用到另外一个三角矩阵，即，下三角矩阵L，取Lower triangle的首字母，使得LU=A，完成了对高斯消元的换原。

本文分共分5个部分，其中最重要的就是前两个部分，第一部分：高斯消元过程（这包含了矩阵U和矩阵Z）和第二部分：消元的逆过程（这包含了矩阵L）。

Tips:对于高斯消元不熟悉的同学可以看看我的另一篇文章，我详细了介绍了基本消元矩阵E，（在这篇文章中看，我还会对E做一些说明）他让我们从矩阵的角度去看待高斯消元法。

线性代数 --- 线性代数中的一些特殊矩阵（被广泛用于高斯消元法的消元矩阵E）

高斯消元过程

Part I: 消元矩阵Z，让Ax=b变成Ux=c

现有如下方程组Ax=b:

对该矩阵进行高斯消元共需三步：

消除非零主元2下面的元素

（i）第二行减去第一行的2倍，得到新的第二行（消除了4）

（ii）第三行减去第一行的-1倍，得到了新的第三行（消去了-2）

消除非零主元1下面的元素

（iii）用新的第三行减去新的第二行的-3倍，(消去了3)

得到全新的Ux=c，如下：

注意，在矩阵U中，主对角线下面的元素全部为0，我们称这种矩阵U为上三角矩阵（Upper triangular）。同时，等式右端的b也变成了c。也就是说，A和b，经过了上面提到的三步（i）,（ii）,（iii)，分别变成了U和c。

又因为，根据我们前面提到的基本消元矩阵E。也就是，上述所提到的三步，都可以通过矩阵的方式实现。用基本消元矩阵Eij重新表示如下(注：Eij表示消去矩阵中的第i行第j列的元素)：

（i）第二行减去第一行的2倍，等于用消元矩阵E21乘以A。

（ii）第三行减去第一行的-1倍，等于用消元矩阵E31乘以A。

（iii）用新的第三行减去新的第二行的-3倍，等于用消元矩阵E31乘以A。

Eij，表示用第i行的方程减去第j行方程乘以一定倍数，也可以说Eij等于消除A中指定的元素A(i,j)。基本消元矩阵都是下三角矩阵，其主对角线上的元素都是1。

我们按照高斯消元的顺序，把A变成了U，有：

同时，我们对原方程的右端b也进行了同样的操作得到c，有：

如果矩阵很大，消元步骤很多，那么就会有很多个消元矩阵E按照消元的顺序相乘最终乘以A。根据矩阵乘法的结合律，我们可以先求出所有的E的乘积Z矩阵，有：

$\large E_{32}E_{31}E_{21}A=(E_{32}E_{31}E_{21})A=ZA$

其中，Z等于：

$\LARGE E_{32}E_{31}E_{21}=\begin{bmatrix} 1 &0 &0 \\ -2& 1&0 \\ -5& 3 &1 \end{bmatrix}=Z$

现在我们来重新观察一下前面的三个基本消元矩阵E，请注意我用红色方框所匡的数，正好等于Eij消元过程中，第j行所乘的负数倍。这是消元矩阵的一个重要的性质。

此外，我们还要注意消元矩阵E的积Z矩阵，他也是一个下三角矩阵，且对角线上的值全是1。需要注意的是，用我红色方框所标记的值-5，和消元过程中对应位置所乘的倍数-1不对等。这和接下来我们将要看到的L矩阵在此处的值形成强烈的对比。同时，我们还会看到，我们不能简单的通过记录下来的消元过程中每一步所乘的倍数，直接写出消元矩阵的积，Z矩阵。但是，我们可以根据每一步所乘的倍数，直接写出L，它和对应位置的乘数是一一对应的。

高斯消元的逆过程

Part II: 还原矩阵L，让Ux=c回到Ax=b

在前面的讨论中，我学会了用一连串的消元矩阵的乘积Z矩阵乘以A，达到消元的目的。即:

$\large E_{32}E_{31}E_{21}A=(E_{32}E_{31}E_{21})A=ZA=U$

那么请问，经过高斯消元后的U，怎么回到原始矩阵A？就好像是，前面我们已经有了傅里叶正变换，现在我们要求傅里叶反变换。

我们先从单一步骤的还原开始，比如说，E21通过让A的第二行减去第一行的两倍，实现了消除A中的元素A(2,1)，即消去了A矩阵中的4：

$\large E_{21}A=X$

要想还原这个步骤，也就是把矩阵X变成A，只需让矩阵X中的第二行加上第一行的两倍就行了。如果我们把这个还原的操作用矩阵来表示，并且称这个还原矩阵为R（取英文中还原的单词resume之意），R矩阵如下：

$\large R=\begin{bmatrix} 1&0 &0 \\ 2& 1 &0 \\ 0& 0 &1 \end{bmatrix}$

现在我们用R乘以X（左乘）试试看：

可见，还原矩阵R左乘X的结果和A一样。实现了对E21的还原。刚才，我们为了把X还原到A，只计算了R*X。如果我们对前面的消元过程 $E_{21}A=X$ ，两边同时乘以还原矩阵R，就会看到如下等式，这说明，还原矩阵R有可能是消元矩阵E21的逆矩阵：

$\large RE_{21}A=RX=A$

根据逆矩阵的定义，如果 $\large AB=BA=I$ ，那么B就是A的逆矩阵记作 $\large A^{-1}$ 。现在，先看RE21的计算结果。

可见， R*E21的结果等于单位矩阵I。如果E21*R的结果也是单位矩阵I的话，就能证明R就是E21的逆矩阵。

根据上面的计算结果，我们可以得出一个非常重要的结论：前面我们所反复提到的还原矩阵R，实际上就是 $\large E_{21}$ 的逆矩阵 $\large E{_{21}}^{-1}$ ，即：

请注意，消元矩阵E的逆矩阵 $E^{-1}$ 相遇对于E，只不过是改变了元素E(i,j)的符号。

根据基本消元矩阵E的这一特性，我们能够很快的求出另外两个消元矩阵E31和E32的逆。

现在，我们已经知道了可以还原高斯消元全部过程的三个还原矩阵， $E{_{21}}^{-1}$ ， $E{_{31}}^{-1}$ ， $E{_{32}}^{-1}$ 。那么我们究竟应该如何使用这三个还原矩阵呢？还有就是怎么把这三个矩阵合成一个矩阵，类似于上面的消元矩阵Z，让我们只需一步就能还原高斯消元的全过程，直接把U变回到A？

对整个高斯消元的还原过程，我们应该按照依次按照相反的顺序完成，我们把A变成U时，最后一步（E32），应该是还原操作时的第一步，而对A进行高斯消元中的第一步，在还原时，反倒应该是最后一步。这叫后进先出。现在我们用矩阵的方式把还原过程写出来：

为了证明，我们把前面的消元等式U=ZA

$\large E_{32}E_{31}E_{21}A=(E_{32}E_{31}E_{21})A=ZA=U$

代入上面的还原等式得右边，得（我们把下式记作等式a）：

$A=E{_{21}}^{-1}E{_{31}}^{-1}E{_{32}}^{-1}U=E{_{21}}^{-1}E{_{31}}^{-1}E{_{32}}^{-1}ZA=E{_{21}}^{-1}E{_{31}}^{-1}E{_{32}}^{-1}E_{32}E_{31}E_{21}A$

又因为：

$E{_{32}}^{-1}E_{32}=I$

等式a的右边可化简为：

$E{_{21}}^{-1}E{_{31}}^{-1}E{_{32}}^{-1}E_{32}E_{31}E_{21}A=E{_{21}}^{-1}E{_{31}}^{-1}IE_{31}E_{21}A=E{_{21}}^{-1}E{_{31}}^{-1}E_{31}E_{21}A$

依此类推，等式a中的所有消元矩阵和他的逆矩阵都会相互抵消，最终把U变回了A。如果说，我们在前面把几个消元矩阵E的乘积定义为消元矩阵Z，这里我们也相应的把几个消元矩阵的逆的乘积定义为L，最终得到举世闻名的LU分解式，即：

正如一连串的消元矩阵的积Z矩阵可以一次性完成对A的全部消元一样，即ZA=U。同样，也存在一个矩阵L等于一连串的消元矩阵的逆的积，可以一次性完成对U的还原，即LU=A。也就是说前面我们提到的Z矩阵，就是L的逆矩阵。

$\large A=LU=L(ZA)=IA=A\Rightarrow Z=L^{-1}$

下面我们用两组方法来证明：

1，z*L=L*z=I（根据逆矩阵的定义）

2，Z的逆矩阵等于L（对Z求逆，这个方法不严格，因为求逆会有精度误差）

让我们再仔细审视一下矩阵L，同样，L也是一个三角矩阵，且主对角线上的元素都是1，与消元矩阵的积Z矩阵（现在我们知道Z矩阵就是L的逆）不同的是，L中主对角线下面的元素正好是消元过程中，每一步所乘的倍数，2，-1，-3。

$\large L=\begin{bmatrix} 1 &0 &0 \\ 2& 1 &0 \\ -1& -3 &1 \end{bmatrix}$

还记得吗，每个消元矩阵Eij中(i，j)处所保存的，正好是消元过程中每一步所乘的负倍数。而且，消元矩阵的积Z矩阵的主对角线下面的值并不全是消元步骤中的倍数，如下：

注意：Z矩阵中的-5不是消元中的倍数。

这样看来，我们不能通过每个消元矩阵Eij中(i，j)处的值，直接写出消元矩阵的积Z矩阵。但是，我们可以通过每个消元矩阵的逆矩阵中(i，j)处的值，直接写出还原矩阵的积L矩阵。大家可以回去自己比对一下。By the way,L不仅把U还原成了A，同时也可以把c还原成了b，即Lc=b。

前面提到的后进先出的还原顺序，对于任何阶数的矩阵都适用，每一步所乘的倍数，都毫无改变的出现在L的相应位置上。

我们可以把上面讨论的做一个小结：

只要在消元的过程中，不存在主元为0的情况（这里我们先不考虑换行后主元不为0的情形）。我们可以把对矩阵A的Gauss消元过程用矩阵的形式表示成A=LU，其中L是一个下三角矩阵，L的主对角线上的元素全是1，主对角线下面(i,j)处的元素是消元过程中每一步所乘的倍数。U是一个上三角矩阵，是Gauss消元的结果。他的主对角线上的元素是主元。

LU分解是唯一的！这一点很重要哦！

Part III: LU分解的应用

现在我们回到最开始的方程组：

当A可以被分解成LU的形式后，原方程组Ax=b的求解，就变成了对LUx=b的求解，进一步，如果我们把Ux看成一个整体，并令Ux=y，则LUx=b变成了Ly=b。

$\LARGE Ax=b\Leftrightarrow L(Ux)=b\Leftrightarrow \begin{matrix} Ly=b\\ Ux=y \end{matrix}$

对方程组Ly=b，用正向代入法，求得y向量。对方程组Ux=y，用反向代入法，求解x如下：

最终，求得Ax=b的解x=(-1,2,1)。(注意这里要倒着往前看，最底下的是x1，最先求得的是x3。)

Part VI: LU分解相对于高斯若尔当消元法的优势

我们有了A的LU分解以后，如果换了原方程Ax=b中的右端b。我们就不需要对新的方程组进行第二次LU分解了，但如果你是用传统的高斯若尔当消元法来求解的话，则需要从头开始，再来一遍。

这里我们举个例子，首先维持原始方程中的A不变，而去改变b，注意，A不变则A的LU分解就不变。现在，我们把原始方程组中右端的值换成b'=(8，11，3)，我们要求解的x为u',v',w'。

（记作式2）

按照我们之前说的求解步骤，我们先用正向代入法求解Ly=b'，其中b'=(8,11,3)，我们求得y=(8,-5,-4)。(把下图中的c替换成y即可)

这里我们会看到一个非常有趣的现象。我们说求解Ax=b，经过高斯消元后，实际上就是求解Ux=c。如果说我们对上面的新方程组，式2，进行高斯消元的话，我们会惊奇的发现，他最终得到新右端向量c，就是我们前面求出来的y。

证明：

根据我们前面学到的知识，消元矩阵的积Z矩阵乘以Ax=b的左右两边，得到Ux=c，而Z实际上就是还原矩阵L的逆矩阵。我们已知L，我们用他的逆矩阵来乘以这个新的b'，其实也就是对Ax=b'进行高斯消元，看看这个结果和上面我们用正向代入法求出来的结果是不是一样的。

可以看到，如果我们对新的方程组Ax=b'重新进行高斯消元，所得到的右端c(Ux=c)，和我们用LU分解法的L，所联立的方程组Ly=b'的解y，是一模一样的。

接下来的就和原来的一样，用反向回代法去计算Ux=y，最终求得解x。

这和我用matlab求得的结果一致。

Part V: A=LDU ，对称的LU三角矩阵分解

LU分解在形状上会存在一定的不对称性，U的主对角线上全是主元，而L的主对角线上全是1。我们可以对U加以改造，使得A的LU分解看起来更为对称。方法是把U中对角线上的主元分离成一个单独的对角矩阵D，使得：

这样一来，A的LU分解，就从A=LU变成了A=LDU。下面我们举个例子：

补充：

下面是我的一些关于LU分解学习的个人笔记，供参考：

1，

线性代数 --- LU分解 - 风格A（个人笔记扫描版）_松下J27的博客-CSDN博客https://blog.csdn.net/daduzimama/article/details/1205239782，

线性代数 --- LU分解 - 风格B（个人笔记扫描版）_松下J27的博客-CSDN博客LU分解 - 风格B（个人笔记扫描版）https://blog.csdn.net/daduzimama/article/details/120524090

（全文完）

作者 --- 松下J27

格言摘抄：

不要用别人的错误来惩罚自己。（无名氏）

参考文献（鸣谢）：

1，《Introduction to Linear Algebra》,5th Edition - Gilbert Strang

2，线性代数及其应用，侯自新，南开大学出版社，1990.

（配图与本文无关）

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)