第5章 线性方程组的直接解法优秀课件.ppt

《第5章 线性方程组的直接解法优秀课件.ppt》由会员分享，可在线阅读，更多相关《第5章 线性方程组的直接解法优秀课件.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章 线性方程组的直接解法第1页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法2 在在科科学学计计算算中中，经经常常需需要要求求解解含含有有n n个个未未知知量量 的的n n个方程构成的线性方程组个方程构成的线性方程组方程组还可以用矩阵形式表示为方程组还可以用矩阵形式表示为:Ax=b (5.1)(5.1)第2页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法3 根据根据 Gramer（克莱姆）法则，求解方程组（克莱姆）法则，求解方程组（5.15.1）时，要计）时，要计算大量的行列式，所需乘法次数大约为算大量的行列式，所需乘法次数大约为 当当 n 较大时较大时

2、,这个计算量是惊人的。例这个计算量是惊人的。例 如，当如，当 n=20 时，时，约需乘法次数为约需乘法次数为 N=9.71020 若系数矩阵若系数矩阵A A非奇异，即非奇异，即 det(A)0,则方程组有惟一解则方程组有惟一解 x=(x1,x2,xn)T.如果用每秒一亿次的计算机来计算，需要三十万年如果用每秒一亿次的计算机来计算，需要三十万年(10950(10950万万天天)时间。可见时间。可见Gramer法则不是一种实用的方法。法则不是一种实用的方法。因此，必须构造出适合于计算机使用的因此，必须构造出适合于计算机使用的线性方程组线性方程组求解方法。求解方法。N=(n+1)n!(n-1)=(n

3、2-1)n!第3页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法4 直直接接方方法法的的特特点点是是:如如果果不不考考虑虑计计算算过过程程中中的的舍舍入入误误差差，运运用用此此类类方方法法经经过过有有限限次次算算术术运运算算就就能能求求出线性方程组的精确解出线性方程组的精确解。求求解解线线性性方方程程组组的的数数值值方方法法可可分分为为两两大大类类：直直接接方方法法和和迭迭代代方方法法。本本章章讨讨论论直直接接方方法法，迭迭代代方方法法将将在下一章中讨论。在下一章中讨论。需要指出，由于实际计算中舍入误差的存在，需要指出，由于实际计算中舍入误差的存在，用直接方法一般也只能求得方

4、程组的近似值。本章用直接方法一般也只能求得方程组的近似值。本章我们将给出我们将给出直接解法的若干算法直接解法的若干算法。第4页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法5假设系数行列式不为零，则解存在惟一，可用克莱姆法则求解假设系数行列式不为零，则解存在惟一，可用克莱姆法则求解两类解法两类解法直接法直接法：不计舍入误差，通过有限次算术运算求得精确解：不计舍入误差，通过有限次算术运算求得精确解迭代法迭代法：设计迭代公式，反复进行，无限次求得精确解：设计迭代公式，反复进行，无限次求得精确解克莱姆法则克莱姆法则计算量太大，不实用；计算量太大，不实用；高斯消元法高斯消元法直接法直

5、接法 迭代法迭代法第5页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法61 Gauss消去法消去法 Gauss（高斯）消去法是一种高斯）消去法是一种规则化规则化的加减消元法的加减消元法 基本思想基本思想 通通过过逐逐次次消消元元计计算算把把需需求求解解的的线线性性方方程程组组转转化化成成上上三三角角形形方方程程组组，也也就就是是把把线线性性方方程程组组的的系系数数矩矩阵阵转转化化为为上上三三角角矩矩阵阵，从从而而使使一一般般线线性性方方程程组组的的求求解解转化为转化为等价（同解）等价（同解）的上三角形方程组的求解。的上三角形方程组的求解。Gauss消去法由消去法由消元消元和和

6、回代回代两个过程组成，先讨论两个过程组成，先讨论一个具体的线性方程组的一个具体的线性方程组的求解。求解。中国古籍九章算术，成书于约公元前中国古籍九章算术，成书于约公元前250年年 第6页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法7一、顺序一、顺序Gauss消去法消去法例例1.用用Gauss消去法解方程组消去法解方程组用增广矩阵进行进算用增广矩阵进行进算上三角形上三角形方程组方程组消元过程消元过程回代过程回代过程第7页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法8这样，对于方程组这样，对于方程组(5.1)我们用增广矩阵表示，并给出我们用增广矩阵表示，并给

7、出Gauss消去法的消去法的具体算法具体算法。或者或者 Ax=b 第8页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法9顺序顺序Gauss消去法的消元过程可表述如下：消去法的消元过程可表述如下：第一步，设第一步，设 a11(1)0，将第一列中，将第一列中a11(1)以下的各元素消成零以下的各元素消成零乘以矩阵乘以矩阵A（1），b（1）的的第第一行一行再加到再加到第第i 行行，得到矩阵，得到矩阵 (i2，3，n)即依次用即依次用消元因子消元因子(行乘数行乘数)第9页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法10其中其中 第二步第二步，设设 a22(2)0

8、，将第二列，将第二列a22(2)以下各元素消成零，以下各元素消成零，（i3，4，n）即依次用即依次用乘以矩阵乘以矩阵A（2），b（2）的第二行再加到第的第二行再加到第i行，得到矩阵行，得到矩阵第10页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法11其中其中 如此继续消元下去直到如此继续消元下去直到第第n1步步结束后，得到矩阵结束后，得到矩阵第11页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法12增广矩阵增广矩阵A（n），b（n）对应如下上三角形方程组对应如下上三角形方程组 这是与原线性方程组（这是与原线性方程组（5.1）等价的方程组）等价的方程组.第12

9、页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法13对于等价方程组对于等价方程组进行回代求解，可以得到：进行回代求解，可以得到：第13页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法14首先写出增广矩阵首先写出增广矩阵于是，采用于是，采用Gauss消去法求解方程组消去法求解方程组(5.1)(5.1)第14页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法15然后进行消元，采用公式然后进行消元，采用公式最后进行回代得到方程组的解最后进行回代得到方程组的解得到相似增广矩阵得到相似增广矩阵（ik+1，k+2，n）第15页，本讲稿共92页2022/1

10、0/25第五章 线性方程组的直接解法16在编程计算时，最后的增广矩阵存放的元素是：在编程计算时，最后的增广矩阵存放的元素是：下面给出下面给出Gauss消去法的计算流程：消去法的计算流程：第16页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法17消元过程：消元过程：jk1，n 回代过程：回代过程：对于对于in1，n2，1，计算，计算k1，2，n1，ik1，k2，n对于对于执行计算执行计算令令第17页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法18消元条件：消元条件：回代条件：回代条件：消元法是将某行的若干倍加到另一行消元法是将某行的若干倍加到另一行故故A的各

11、阶顺序主子式的各阶顺序主子式Di(i=1n)不变不变，消元条件消元条件:回代条件回代条件:，第18页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法19用用Gauss消去法解方程组，应注意：消去法解方程组，应注意：1.适用条件：适用条件：原方程组系数矩阵的原方程组系数矩阵的各阶顺序主子各阶顺序主子 式式不等于零。不等于零。2.运算量小：运算量小：共有乘除法次数为共有乘除法次数为而而Gramer 法则的乘除法次数为法则的乘除法次数为:(n2-1)n！当当 n=20 时时第19页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法20二二 列主元列主元Gauss消去法消

12、去法 顺序顺序Gauss消去法计算过程中的消去法计算过程中的 akk(k)称为主元素，在第称为主元素，在第k步消元时要用它作除数步消元时要用它作除数,则可能会出现以下几种情况：则可能会出现以下几种情况：若出现若出现 akk(k)0，消元过程就不能进行下去。，消元过程就不能进行下去。akk(k)0，消去过程能够进行，但若消去过程能够进行，但若|akk(k)|过小，也会造成过小，也会造成舍入误差积累很大导致计算解的精度下降。舍入误差积累很大导致计算解的精度下降。例例5-2 在四位十进制的限制下，用顺序在四位十进制的限制下，用顺序Gauss消去法求解如下方程消去法求解如下方程组组第20页，本讲稿共9

13、2页2022/10/25第五章 线性方程组的直接解法21此方程组具有四位有效数字的精确解为此方程组具有四位有效数字的精确解为x117.46，x245.76，x35.546 如果用顺序如果用顺序Gauss消去法求解，消元过程如下消去法求解，消元过程如下_消元因子消元因子83.33;2667004.200被被“吃掉吃掉”-44540被被“吃掉吃掉”消元因子消元因子-14670000第21页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法22经回代求解得经回代求解得 x35.546，x2100.0，x1104.0和此方程组的精确解相比和此方程组的精确解相比x35.546，x245.7

14、6，x117.46有较大的误差。有较大的误差。此此例例是是由由于于顺顺序序Gauss消消去去法法中中的的主主元元素素绝绝对对值值非非常常小小，使使消消元元因因子子绝绝对对值值非非常常大大，某某些些数数也也变变得得很很大大，计计算算过过程程中中出出现现“大大数数吃吃掉掉小小数数”现现象象，产产生生较较大大的的舍舍入入误误差差，最最终终导导致致计计算算所所求求得得的的两个解两个解 x1104.0 和和 x2100.0 完全失真。完全失真。为为避避免免这这种种现现象象发发生生，可可以以对对原原方方程程组组作作等等价价变变换换，再再利利用用顺顺序序Gauss消去法求解。消去法求解。第22页，本讲稿共9

15、2页2022/10/25第五章 线性方程组的直接解法23四位十进制浮点数表示四位十进制浮点数表示消元因子消元因子105对阶处理对阶处理列主元列主元x1=2;x2=1第23页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法24写出原方程组的增广矩阵：写出原方程组的增广矩阵：针对第一列找出绝对值最大的元素，进行等价变换：针对第一列找出绝对值最大的元素，进行等价变换：第24页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法25求得方程的解为：求得方程的解为：x35.546，x245.76，x117.46精确解为：精确解为：x35.546，x245.76，x117.46

16、 由此可见，第二种由此可见，第二种Gauss消去法的精度明显高于顺序消去法的精度明显高于顺序Gauss消去法，我们消去法，我们称它为称它为列主元列主元Gauss消去法消去法。列主元列主元Gauss消去法与消去法与顺序顺序Gauss消去法的不同之处在于：消去法的不同之处在于：后者是按后者是按自然顺序自然顺序取主元素进行消元取主元素进行消元 前者在每步消元之前先前者在每步消元之前先选取主元素选取主元素然后再进行消元然后再进行消元 第25页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法26下面将列主元下面将列主元Gauss消去法的计算步骤叙述如下：消去法的计算步骤叙述如下：给给定定

17、线线性性方方程程组组 Axb,记记A(1),b(1)A,b，列列主主元元Gauss消去法的具体过程如下：消去法的具体过程如下：1.首首先先在在增增广广矩矩阵阵A（1）,b（1）第第一一列列的的n个个元元素素中中选选取取绝绝对对值值最最大大的的一一个个作作为为主主元元素素，并并把把此此主主元元素素所所在在的的行行与与第第一一行行交交换换，即即 2.其其次次进进行行第第一一步步消消元元得得到到增增广广矩矩阵阵A（2）,b（2），在在矩矩阵阵A（2）,b（2）第第二二列列的的后后 n1个个元元素素中中选选取取绝绝对对值值最最大大的的一一个个作作为为主元素，并把此主元素所在的行与第二行交换，即主元素，

18、并把此主元素所在的行与第二行交换，即第26页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法27 3.再再进进行行第第二二步步消消元元得得到到增增广广矩矩阵阵A（3），b（3）。按按此此方方法法继继续续进进行行下下去去，经经过过n1步步选选主主元元和和消消元元运运算算，得得到到增增广广矩矩阵阵A（n），b（n），它对应的方程组，它对应的方程组A（n）xb（n）是一个是一个与原方程组等价与原方程组等价的上三角形方程组，可进行回代求解。的上三角形方程组，可进行回代求解。容容易易证证明明，只只要要det（A）0，列列主主元元Gauss消消去去法法就就可可以以顺利完成，即不会出现顺利完

19、成，即不会出现主元素为零主元素为零或者或者绝对值太小绝对值太小的情形出现。的情形出现。下面给出列主元下面给出列主元Gauss消去法的计算流程：消去法的计算流程：第27页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法28列主元列主元GaussGauss消去算法消去算法 用列主元用列主元Gauss消去法求解线性方程组消去法求解线性方程组Axb 输入：输入：A（aij），），b（b1，bn）T，维数，维数n输出：方程组解输出：方程组解x1，xn，或方程组无解信息，或方程组无解信息1 1：对于对于k1，2，n1，循环执行步循环执行步2 2到步到步5 52 2：按列选主元素按列选主元素

20、 aik，即确定下标，即确定下标 i 使使3 3：若若aik0，输出，输出 no unique solution，停机，停机4 4：若若ik，换行，换行第28页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法295 5：消元计算，对于：消元计算，对于ik1，n，计算计算 6 6：若：若 ann 0 输出输出 no unigue solution，停机，停机7 7：回代求解：回代求解 8 8：输出：输出 x1，x2，xn第29页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法30 由于这两种方法的精度差不多，且全主元由于这两种方法的精度差不多，且全主元Gauss消

21、去法程序设计复消去法程序设计复杂占用机器时间较多，实际应用中一般采用列主元杂占用机器时间较多，实际应用中一般采用列主元Gauss消去法，它消去法，它既简单又能保证计算精度。既简单又能保证计算精度。有时候在消元过程中可以在系数矩阵所有元素中选择绝对有时候在消元过程中可以在系数矩阵所有元素中选择绝对值最大的元素作为主元素（换行换列），这样的值最大的元素作为主元素（换行换列），这样的Gauss消去法消去法和叫做和叫做全主元全主元Gauss消去法消去法。无回代的列主元消去法：无回代的列主元消去法：高斯高斯约当消去法约当消去法（初等变换法（初等变换法求逆矩阵的规范算法），计算量大约是求逆矩阵的规范算法）

22、，计算量大约是n3/2次乘除法次乘除法。第30页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法312 2 直接三角分解方法直接三角分解方法一一、Gauss消去法的矩阵运算消去法的矩阵运算 从从1中中讨讨论论可可知知，Gauss消消去去法法的的消消元元过过程程是是将将增增广广矩矩阵阵A,bA（1）,b（1）逐步约化为矩阵逐步约化为矩阵A（n）,b（n）。现在说明，在消元过程中，系数矩阵现在说明，在消元过程中，系数矩阵AA（1）是如何经矩阵运是如何经矩阵运算约化为上三角矩阵算约化为上三角矩阵A（n）,即即 用矩阵运算的观点来看，消元的每一步计算等价于用一个用矩阵运算的观点来看，消

23、元的每一步计算等价于用一个单单位下三角矩阵位下三角矩阵左乘前一步约化得到的矩阵。左乘前一步约化得到的矩阵。第31页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法32若若 ，令，令 ，i2，3，n，得到下三角矩阵得到下三角矩阵施行第一步消元，我们得到施行第一步消元，我们得到第32页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法33若若 ，令，令 ，i2，3，n，则有，则有 施行第二步消元，我们得到施行第二步消元，我们得到初等行变初等行变换换第33页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法34如此下去，直至施行第如此下去，直至施行第n1步

24、消元，得到步消元，得到 初等行变初等行变换换第34页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法35 由此可见，在顺序由此可见，在顺序Gauss消去法的过程中，系数矩阵消去法的过程中，系数矩阵AA（1）经过一系列经过一系列单位下三角矩阵单位下三角矩阵的左乘运算约化为上三角矩阵的左乘运算约化为上三角矩阵A（n），即，即 这时这时由由得得令令第35页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法36容易验证容易验证 则则从从顺顺序序Gauss消消去去法法的的矩矩阵阵运运算算表表示示式式可可知知，系系数数矩矩阵阵A可可分分解解为为一个单位下三角矩阵一个单位下三角

25、矩阵L和一个上三角矩阵和一个上三角矩阵U的乘积，即的乘积，即其中其中第36页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法37 第一个方程组的系数矩阵为第一个方程组的系数矩阵为下三角矩阵下三角矩阵，第二个方程组的系，第二个方程组的系数矩阵为数矩阵为上三角矩阵上三角矩阵，两个方程组都非常容易求解，具体求解，两个方程组都非常容易求解，具体求解结果如下：结果如下：我们将我们将A=LU 称为称为矩阵矩阵A的三角分解的三角分解,这时线性方程组为：这时线性方程组为：令令则有则有高斯消元法的实质是把高斯消元法的实质是把A分解为两个三角矩阵乘积分解为两个三角矩阵乘积第37页，本讲稿共92页2

26、022/10/25第五章 线性方程组的直接解法38对于对于由由解得解得第38页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法39对于对于由由求得求得第39页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法40可以看出对于方程组可以看出对于方程组：只要对系数矩阵作了三角分解只要对系数矩阵作了三角分解：由这个简单的计算过程可知，系数矩阵的三角分解很关键，由这个简单的计算过程可知，系数矩阵的三角分解很关键，如何进行如何进行三角分解更容易三角分解更容易？下面介绍几种方法。？下面介绍几种方法。通过如下两组公式很容易求解通过如下两组公式很容易求解：第40页，本讲稿共92页

27、2022/10/25第五章 线性方程组的直接解法41二、二、Doolittle分解法分解法 前已述及，若在顺序前已述及，若在顺序Gauss消去法的过程中，每步消去法的过程中，每步消元的主元素消元的主元素 akk(k)0，则矩阵，则矩阵A A可分解为可分解为ALU，L为为单位下三角矩阵单位下三角矩阵，U为为上三角矩阵上三角矩阵，此分解称为，此分解称为A的的 Doolittle（杜利特尔）分解。已经证明主元杜利特尔）分解。已经证明主元akk(k)0的的充要条件充要条件是是A的各阶顺序主子式不为零，于是有的各阶顺序主子式不为零，于是有如下定理。如下定理。定定理理5.1 5.1 设设n阶阶方方阵阵A的

28、的各各阶阶顺顺序序主主子子式式不不为为零零，则则存存在在惟惟一一单单位位下下三三角角矩矩阵阵L和和上上三三角角矩矩阵阵U使使ALU。下面介绍矩阵三角分解的下面介绍矩阵三角分解的Doolittle分解方法。分解方法。（前（前n-1阶即可）阶即可）第41页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法42根据根据 A=LU 有等式成立：有等式成立：比较等式两端比较等式两端对应元素对应元素，有，有第42页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法43先固定先固定i按行求按行求再固定再固定j按列求按列求第43页，本讲稿共92页2022/10/25第五章 线性方程

29、组的直接解法44于是，对于矩阵的三角分解：于是，对于矩阵的三角分解：可按照以下公式进行：可按照以下公式进行：对于对于 i=2,3,，n,计算计算（5.2）（5.3）（5.4）用计算公式用计算公式(5.3)、(5.4)对矩阵对矩阵A作的分解作的分解(5.2)称作称作Doolittle分解分解。第44页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法45按框先横后竖按框先横后竖计算元素计算元素第一步第一步第二步第二步第第 n步步第45页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法46下面，我们对具体矩阵进行下面，我们对具体矩阵进行Doolittle 三角分解。三

30、角分解。为了表示和存储方便，可以将分解后的两个矩阵用一为了表示和存储方便，可以将分解后的两个矩阵用一个矩阵表示个矩阵表示第46页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法47例例5-3 5-3 利用利用Doolittle三角分解法分解矩阵三角分解法分解矩阵解：分解时用到如下公式解：分解时用到如下公式1234111261237624624第47页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法481234111261237624624可以写成：可以写成：这时，矩阵的三角分解这时，矩阵的三角分解第48页，本讲稿共92页2022/10/25第五章 线性方程组的直

31、接解法49如果我们要求解方程组如果我们要求解方程组则由则由得到得到第49页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法50由由解得解得再由再由求得方程组的解：求得方程组的解：第50页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法51（5.5）如下的计算公式如下的计算公式(5.3)、(5.4)与与(5.5)就是求解方程组就是求解方程组Axb 的的 Doolittle 三角分解法三角分解法（紧凑格式法）（紧凑格式法）,包括包括分解分解和和回代回代两步。两步。（5.3）（5.4）关于具体求解过程可以按下面例子的方法进行。关于具体求解过程可以按下面例子的方法进行。

32、与高斯消去法计算与高斯消去法计算量相同，精度高量相同，精度高第51页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法52例例5-4 利用利用Doolittle三角分解方法解线性方程三角分解方法解线性方程解解:进行三角分解进行三角分解ALU，按照公式按照公式(5.5)可以对增广可以对增广 矩阵矩阵A,b作三角分解作三角分解:1 2 3 -2-3 2 2-3-13317第52页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法53得到得到1 2 3 -2-3 2 2-3-13317这时，相应的方程组为：这时，相应的方程组为：x135x28，第53页，本讲稿共92页20

33、22/10/25第五章 线性方程组的直接解法54例例5-5 利用利用Doolittle三角分解方法解线性方程组三角分解方法解线性方程组解：对增广矩阵进行三角分解解：对增广矩阵进行三角分解1 2 3 -4 -2-3 2 42-3133322-4-117-16等价方程组通过分解式容易写出为：等价方程组通过分解式容易写出为：第54页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法551 2 3 -4 -2-3 2 42-3133322-4-117-16解得解得LU分解的意义：按分解的意义：按A的性质作不同分解，得到不同的直接三角分解法的性质作不同分解，得到不同的直接三角分解法第55页

34、，本讲稿共92页2022/10/25第五章 线性方程组的直接解法56三、平方根法三、平方根法 实际应用中，常见一类非常重要的线性方程组实际应用中，常见一类非常重要的线性方程组Axb，其中，其中A为为对称正定矩阵对称正定矩阵，即，即A是对称的且对任何非零向量是对称的且对任何非零向量 x 都有都有xTAx0 0。本节将对这类方程组导出更有效的三角分解求解方法，称之为本节将对这类方程组导出更有效的三角分解求解方法，称之为平平方根法方根法。设设A为为对对称称正正定定矩矩阵阵，那那么么A的的所所有有顺顺序序主主子子式式均均大大于于零零，根根据定理据定理5.15.1，存在惟一三角分解，存在惟一三角分解AL

35、U，即，即第56页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法57 记记 Ak（1kn）为）为A的的 k 阶顺序主子阵，则阶顺序主子阵，则det（Ak）为）为A的的k阶阶顺序主子式顺序主子式(记为记为Dk)。由上式，利用矩阵分块运算规则，容易验证。由上式，利用矩阵分块运算规则，容易验证 D1=u11，Dk u11 u22 ukk=Dk-1ukk (k1)那么由那么由Dk0，可知，可知 ukk0，k1，2，n 这时，将上面的矩阵表示为：这时，将上面的矩阵表示为：第57页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法58即：即：A=LDU1 ，其中，其中 DU

36、1=U，U1=D-1U。第58页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法59单位下三角阵单位下三角阵当当AAT为对称矩阵时，根据为对称矩阵时，根据 ALDU1,得到得到ATU1T D LT=U1T(D LT)再根据矩阵三角分解的唯一性再根据矩阵三角分解的唯一性,可知可知 U1 T L。于是。于是ALDLT 对称阵分解对称阵分解则有则有令令上三角阵上三角阵第59页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法60 如果对称正定矩阵如果对称正定矩阵A具有如下分解具有如下分解 AGGT，其中，其中G为下三角矩为下三角矩阵，则称其为阵，则称其为对称正定矩阵的对

37、称正定矩阵的 Cholesky（乔列斯基）分解。（乔列斯基）分解。(定定理理5.3)为表示方便，可以记为表示方便，可以记 给定对称正定方程组给定对称正定方程组 Axb，对，对 A 进行进行 Cholesky分解分解ALLT，则原方程组等价于，则原方程组等价于 LLTxb平方根分解平方根分解第60页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法61Lyb；LTx y由此解得原方程组的解由此解得原方程组的解x，这就是求解方程组的，这就是求解方程组的平方根法平方根法（利用对称利用对称正定矩阵的正定矩阵的Choleskey分解求解正定方程组的方法）分解求解正定方程组的方法）下下面面，

38、我我们们通通过过比比较较矩矩阵阵的的对对应应元元素素给给出出对对称称正正定定矩矩阵阵的的平平方方根分解法根分解法。已知。已知即：即：LLTxb，等价于等价于第61页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法62比较对应元素：比较对应元素：第62页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法63当当 i=j 时时当当 j i 时时固定固定j按列求按列求第63页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法64于是，根据计算公式于是，根据计算公式可以对对称正定矩阵进行平方根分解可以对对称正定矩阵进行平方根分解l11 l21 l22 l31

39、 l32 l33 ln1 ln2 ln3 lnn 第64页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法65按列计算元按列计算元素素平方根法不必选主元，精度高，稳定性好，是最有效算法之一。平方根法不必选主元，精度高，稳定性好，是最有效算法之一。第65页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法66 关关于于方方程程组组 Ax=b,如如果果对对系系数数矩矩阵阵进进行行了了平平方方根根分分解解 ALLT，则将方程组化为：，则将方程组化为：Lyb,LTxy解得解得第66页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法67 于是，关于系数矩阵是

40、对称正定矩阵的线性方程组于是，关于系数矩阵是对称正定矩阵的线性方程组Ax=b的求解，的求解，分两步进行：分两步进行：第一步：系数矩阵的第一步：系数矩阵的平方根分解平方根分解第二步：解等价方程组第二步：解等价方程组第67页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法68例例5-6 用平方根法求解对称正定方程组用平方根法求解对称正定方程组 解解:首先进行首先进行A 的的Cholesky 分解分解 ALLT2-0.50.521.512-0.50.521.51第68页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法69得得 y12，y23.5，y31 得得 x11，

41、x21，x31 求解求解Lyb:再求解再求解 LTxy:第69页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法70关于对称正定方程组关于对称正定方程组 也可以用一般的三角分解法求解，这时由也可以用一般的三角分解法求解，这时由 4 -1 1 4-0.250.254370.7511求得求得 x11，x21，x31 第70页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法71改进平方根法改进平方根法：利用对称矩阵分解利用对称矩阵分解A=LDLT求解系数矩阵为对求解系数矩阵为对称的线性方程组称的线性方程组Ax=b的方法的方法.（避免开方运算）（避免开方运算）（对角加载

42、）（对角加载）第71页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法72固定i按行算第72页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法73四、追赶法四、追赶法 追追赶赶法法是是专专门门用用于于求求解解三三对对角角方方程程组组的的。这这类类方方程程组组经经常常出出现现于于用用差差分分方方法法或或有有限限元元方方法法求求解解二二阶阶常常微微分分方方程程边边值值问问题题、热热传传导导问问题题及及三三次次样样条条函函数数插插值值等等问问题题，三三对对角角方方程程组组Axf 的的系系数数矩矩阵具有如下形式：阵具有如下形式：设设A为一个三对角矩阵，那么它的顺序主子式

43、均不为一个三对角矩阵，那么它的顺序主子式均不为零的一个充分条件是：为零的一个充分条件是：第73页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法74在此条件下，可对在此条件下，可对A进行三角分解，设进行三角分解，设比较矩阵的对应元素，根据矩阵乘法规则，可得到比较矩阵的对应元素，根据矩阵乘法规则，可得到 按行对按行对角占优角占优下三角下三角单位上三角单位上三角Crout分解分解第74页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法75可以证明可以证明第75页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法76于是，由以上结果：于是，由以上结果：分

44、别得到：分别得到：也就是说也就是说,用这一组公式可以对三对角矩阵进行三用这一组公式可以对三对角矩阵进行三角分解：角分解：第76页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法77对对于于三三对对角角方方程程组组Axf，设设A的的三三角角分分解解为为ALU，则则原原方方程程组组等价于等价于Lyf，Uxy LUxf，即，即 第77页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法78由由Lyf，即，即解得解得解得解得由由Uxy，即，即第78页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法79解三对角矩阵方程组解三对角矩阵方程组 Ax=f 的的追赶

45、法追赶法为：为：第79页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法80例例5-7 用追赶法求解三对角方程组用追赶法求解三对角方程组 解解:首先进行系数矩阵的三角分解首先进行系数矩阵的三角分解 第80页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法81第81页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法82求解方程组求解方程组Lyf，即，即 得得 到到 y11/2，y21/3，y31/4，y41 再求解方程组再求解方程组 Uxy，即，即 得得 到到 x11，x21，x31，x41 第82页，本讲稿共92页2022/10/25第五章 线性

46、方程组的直接解法83 当三对角矩阵当三对角矩阵A满足对角占优条件时，追赶法是数值稳定的。满足对角占优条件时，追赶法是数值稳定的。追赶法具有计算程序简单，存贮少，计算量小的优点。追赶法具有计算程序简单，存贮少，计算量小的优点。计算量仅为计算量仅为O(n)解解三三对对角角方方程程组组Axf 的的追追赶赶法法，用用四四个个一一维维数数组组存存放放方方程程组数据组数据 ai，bi，ci，fi ,fi常数项。常数项。输入输入 方程组数据方程组数据 ai，bi，ci，fi，n输出输出 计算解计算解x（x1，x2，xn）T根据以下算法编写程序根据以下算法编写程序第83页，本讲稿共92页2022/10/25第

47、五章 线性方程组的直接解法841 2 对于对于i1，2，n1，计算，计算3 4 5 输出输出 x1，x2，xn 第84页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法85五、三角分解方法的优点五、三角分解方法的优点 此时，在完成并存贮矩阵此时，在完成并存贮矩阵L和和U后，右端项改变一次仅需增加后，右端项改变一次仅需增加 n2 次运算。次运算。1.当需要求解具有同系数矩阵的一系列方程组当需要求解具有同系数矩阵的一系列方程组 Axbi，i1，2，m 时，可节省计算量时，可节省计算量。U y=biL x=yi=1,2,m 首先对系数矩阵作三角分解首先对系数矩阵作三角分解 ALU，再

48、求解方程组化为：再求解方程组化为：第85页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法862.可用来求可逆矩阵可用来求可逆矩阵 A 的逆矩阵的逆矩阵 A1推得推得 A Xk e k，k1，2，n令令 A-1=(X1 X2 Xn ),E=(e1 e2 en)A(X1 X2 Xn )=(e1 e2 en)则由则由 AA-1=E 得到得到如果如果 A=LU,则有则有UYk e k L Xk Y kk1，2，n解出解出 Xk，k1，2，n，便可求得逆矩阵便可求得逆矩阵第86页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法873.可用来求矩阵可用来求矩阵 A 的行列

49、式的行列式如果对矩阵如果对矩阵 A 作了三角分解作了三角分解 A=LU：则可以求得行列式的值为则可以求得行列式的值为第87页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法88第五章第五章 总总 结结 1.解线性方程组解线性方程组Gauss消去法的计算程序如何实现？可以进行消去法的计算程序如何实现？可以进行Gauss消去法的条件是什么？消去法的条件是什么？2.解线性方程组列主元解线性方程组列主元Gauss消去法的计算程序如何实现？可消去法的计算程序如何实现？可以进行列主元以进行列主元Gauss消去法的条件是什么？消去法的条件是什么？3.解线性方程组的解线性方程组的Doolitt

50、le三角分解法如何进行三角分解法如何进行?可以进分解可以进分解的条件是什么？的条件是什么？4.解对称正定矩阵方程组的平方根解对称正定矩阵方程组的平方根(Cholesky)解法如何进行解法如何进行?5.如何实现解三对角矩阵方程组的追赶法的计算程序如何实现解三对角矩阵方程组的追赶法的计算程序?如如何用该算法进行三次样条函数的构造？何用该算法进行三次样条函数的构造？第88页，本讲稿共92页2022/10/25第五章 线性方程组的直接解法89第5章 习题习题5-1 利用利用Gauss消去法解下列方程组消去法解下列方程组Axb，其中，其中（1）（2）第89页，本讲稿共92页2022/10/25第五章 线