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.
(配图与本文无关)文章来源:https://www.toymoban.com/news/detail-782182.html
版权声明:所有的笔记,可能来自很多不同的网站和说明,在此没法一一列出,如有侵权,请告知,立即删除。欢迎大家转载,但是,如果有人引用或者COPY我的文章,必须在你的文章中注明你所使用的图片或者文字来自于我的文章,否则,侵权必究。 ----松下J27文章来源地址https://www.toymoban.com/news/detail-782182.html
到了这里,关于线性代数 --- LU分解(Gauss消元法的矩阵表示)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!