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矩阵，有：

其中，Z等于：

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

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

---

高斯消元的逆过程

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

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

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

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

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

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

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

        根据逆矩阵的定义， 如果，那么B就是A的逆矩阵记作。现在，先看RE21的计算结果。

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

         根据上面的计算结果，我们可以得出一个非常重要的结论：前面我们所反复提到的还原矩阵R，实际上就是的逆矩阵，即：

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

 

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

 

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

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

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

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

 又因为：

等式a的右边可化简为：

         

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

  

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

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

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

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

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

        还记得吗，每个消元矩阵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。

对方程组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.

 （配图与本文无关）

版权声明：所有的笔记，可能来自很多不同的网站和说明，在此没法一一列出，如有侵权，请告知，立即删除。欢迎大家转载，但是，如果有人引用或者COPY我的文章，必须在你的文章中注明你所使用的图片或者文字来自于我的文章，否则，侵权必究。 ----松下J27​