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

这篇具有很好参考价值的文章主要介绍了线性代数 --- LU分解(Gauss消元法的矩阵表示)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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:

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

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

(i)第二行减去第一行的2倍,得到新的第二行(消除了4)

(ii)第三行减去第一行的-1倍,得到了新的第三行(消去了-2)

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

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

得到全新的Ux=c,如下:

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

         

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

(i)第二行减去第一行的2倍,等于用消元矩阵E21乘以A。

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

 (ii)第三行减去第一行的-1倍,等于用消元矩阵E31乘以A。

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

其中,Z等于:

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法


高斯消元的逆过程

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

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

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

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

 现在我们用R乘以X(左乘)试试看:

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法 矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

 矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

 代入上面的还原等式得右边,得(我们把下式记作等式a):

 又因为:

等式a的右边可化简为:

         

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法  

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

1,z*L=L*z=I(根据逆矩阵的定义)

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

注意: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分解的应用       

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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


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

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

(记作式2) 

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

证明:

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法


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

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

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

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法


补充:

下面是我的一些关于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.

矩阵的lu分解,Linear Algebra,线性代数,矩阵,LU分解,高斯消元,算法

 (配图与本文无关)

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

到了这里,关于线性代数 --- LU分解(Gauss消元法的矩阵表示)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • MIT - 线性代数-LU_LDU分解|单位矩阵

    U为消元结果(行变换),L为行变换矩阵的逆矩阵 D为主元(Pivot)A的主对角线元素,在这里为2、3,U为对D做列变换使其得到LU中的U 为什么要写成A=LU而不是E21A=U呢?因为A=LU中L只包含行变换信息,E21A=U还有额外的数字 2×2 2 3×3 3×2=6 4×4 4×3×2=24 结论:单位矩阵的逆=转置矩阵(

    2024年01月23日
    浏览(46)
  • 线性代数——高斯消元 学习笔记

    消元法 消元法是将方程组中的一方程的未知数用含有另一未知数的代数式表示,并将其带入到另一方程中,这就消去了一未知数,得到一解;或将方程组中的一方程倍乘某个常数加到另外一方程中去,也可达到消去一未知数的目的。消元法主要用于二元一次方程组的求解。

    2024年02月08日
    浏览(37)
  • 线性代数笔记2--矩阵消元

    0. 简介 矩阵消元 1. 消元过程 实例方程组 { x + 2 y + z = 2 3 x + 8 y + z = 12 4 y + z = 2 begin{cases} x+2y+z=2\\\\ 3x+8y+z=12\\\\ 4y+z=2 end{cases} ⎩ ⎨ ⎧ ​ x + 2 y + z = 2 3 x + 8 y + z = 12 4 y + z = 2 ​ 矩阵化 A = [ 1 2 1 3 8 1 0 4 1 ] X = [ x y z ] A= begin{bmatrix} 1 2 1 \\\\ 3 8 1 \\\\ 0 4 1 end{bmatrix} \\\\ X= begin{bmatrix} x\\\\

    2024年02月22日
    浏览(42)
  • 【数值计算方法】Gauss消元法及其Python/C实现

       Gauss消元法 ,也称为高斯消元法或高斯-约当消元法,是一种用于 求解线性方程组的数值方法 。它是由德国数学家卡尔·弗里德里希·高斯在18世纪末发展起来的。   Gauss消元法的基本思想是通过一系列的行变换将线性方程组转化为一个上三角形的方程组,然后通过回代

    2024年02月06日
    浏览(43)
  • 2.2 消元法的概念

    消元法 (elimination)是一个求解线性方程组的系统性方法。下面是使用消元法求解一个 2 × 2 2times2 2 × 2 线性方程组的例子。消元之前,两个方程都有 x x x 和 y y y ,消元后,第一个未知数 x x x 将从第二个方程消失: 新的方程 8 y = 8 8y=8 8 y = 8 能够直接得到 y = 1 y=1 y = 1 ,再将

    2024年02月08日
    浏览(34)
  • 线性代数-Python-04:线性系统+高斯消元的实现

    2.1 Matrix 2.2 Vector 2.3 线性系统

    2024年02月03日
    浏览(47)
  • Matlab | Lab4——用LU 分解法、 Jacobi 迭代、 Gauss-Seidel 迭代 解线性病态方程组(系数矩阵为Hilbert矩阵)

    考虑线性方程组Hx=b,其中H为n阶Hilbert矩阵,即 通过先给 定解 (例如取x的各个分量为1),再计算出右端向量b的办法给出一个精确解已知的问题. (1)分别编写Doolittle LU 分解法、 Jacobi 迭代、 Gauss-Seidel 迭代的一般程序; (2) 取阶数n=6,分别用 LU 分解法、 Jacobi 迭代、 Gauss-S

    2024年02月11日
    浏览(40)
  • [Eigen中文文档] 线性代数与分解

    文档总目录 英文原文(Linear algebra and decomposition) 本节说明如何求解线性系统,计算各种分解,如 LU 、 QR 、 SVD 、 特征分解 …… 求解基本线性系统 问题 :有一个方程组,写成矩阵方程如下: A x = b Ax = b A x = b 其中 A A A 和 b b b 是矩阵(作为一种特殊情况, b b b 也可以是一个

    2024年02月07日
    浏览(41)
  • 数值线性代数:奇异值分解SVD

    本文记录计算矩阵奇异值分解SVD的原理与流程。 注1:限于研究水平,分析难免不当,欢迎批评指正。 设列满秩矩阵,若的特征值为,则称为矩阵的奇异值。 设,则存在正交矩阵与,使得 其中,,,即为矩阵的奇异值。 考虑下述两种情形: 情形1: 其中, 由此可以看出,

    2024年02月15日
    浏览(51)
  • 线性代数中的矩阵分解与稀疏处理

    线性代数是计算机科学、数学、物理等多个领域的基础知识之一,其中矩阵分解和稀疏处理是线性代数中非常重要的两个方面。矩阵分解是指将一个矩阵分解为多个较小的矩阵的过程,这有助于我们更好地理解和解决问题。稀疏处理是指处理那些主要由零组成的矩阵的方法,

    2024年04月15日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包