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

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

1、第5章 线性方程组的直接解法现在学习的是第1页，共92页2022/12/2第五章 线性方程组的直接解法2 在在科科学学计计算算中中，经经常常需需要要求求解解含含有有n n个个未未知知量量 的的n n个方程构成的线性方程组个方程构成的线性方程组方程组还可以用矩阵形式表示为方程组还可以用矩阵形式表示为:Ax=b (5.1)(5.1)现在学习的是第2页，共92页2022/12/2第五章 线性方程组的直接解法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

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

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

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

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

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

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

9、（5.1）等价的方程组）等价的方程组.现在学习的是第12页，共92页2022/12/2第五章 线性方程组的直接解法13对于等价方程组对于等价方程组进行回代求解，可以得到：进行回代求解，可以得到：现在学习的是第13页，共92页2022/12/2第五章 线性方程组的直接解法14首先写出增广矩阵首先写出增广矩阵于是，采用于是，采用Gauss消去法求解方程组消去法求解方程组(5.1)(5.1)现在学习的是第14页，共92页2022/12/2第五章 线性方程组的直接解法15然后进行消元，采用公式然后进行消元，采用公式最后进行回代得到方程组的解最后进行回代得到方程组的解得到相似增广矩阵得到相似增广矩阵（i

10、k+1，k+2，n）现在学习的是第15页，共92页2022/12/2第五章 线性方程组的直接解法16在编程计算时，最后的增广矩阵存放的元素是：在编程计算时，最后的增广矩阵存放的元素是：下面给出下面给出Gauss消去法的计算流程：消去法的计算流程：现在学习的是第16页，共92页2022/12/2第五章 线性方程组的直接解法17消元过程：消元过程：jk1，n 回代过程：回代过程：对于对于in1，n2，1，计算，计算k1，2，n1，ik1，k2，n对于对于执行计算执行计算令令现在学习的是第17页，共92页2022/12/2第五章 线性方程组的直接解法18消元条件：消元条件：回代条件：回代条件：消元法

11、是将某行的若干倍加到另一行消元法是将某行的若干倍加到另一行故故A的各阶顺序主子式的各阶顺序主子式Di(i=1n)不变不变，消元条件消元条件:回代条件回代条件:，现在学习的是第18页，共92页2022/12/2第五章 线性方程组的直接解法19用用Gauss消去法解方程组，应注意：消去法解方程组，应注意：1.适用条件：适用条件：原方程组系数矩阵的原方程组系数矩阵的各阶顺序主子各阶顺序主子 式式不等于零。不等于零。2.运算量小：运算量小：共有乘除法次数为共有乘除法次数为而而Gramer 法则的乘除法次数为法则的乘除法次数为:(n2-1)n！当当 n=20 时时现在学习的是第19页，共92页2022/

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

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

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

15、变变换换，再再利利用用顺序顺序Gauss消去法求解。消去法求解。现在学习的是第22页，共92页2022/12/2第五章 线性方程组的直接解法23四位十进制浮点数表示四位十进制浮点数表示消元因子消元因子105对阶处理对阶处理列主元列主元x1=2;x2=1现在学习的是第23页，共92页2022/12/2第五章 线性方程组的直接解法24写出原方程组的增广矩阵：写出原方程组的增广矩阵：针对第一列找出绝对值最大的元素，进行等价变换：针对第一列找出绝对值最大的元素，进行等价变换：现在学习的是第24页，共92页2022/12/2第五章 线性方程组的直接解法25求得方程的解为：求得方程的解为：x35.546，

16、x245.76，x117.46精确解为：精确解为：x35.546，x245.76，x117.46 由此可见，第二种由此可见，第二种Gauss消去法的精度明显高于顺序消去法的精度明显高于顺序Gauss消去法，消去法，我们称它为我们称它为列主元列主元Gauss消去法消去法。列主元列主元Gauss消去法与消去法与顺序顺序Gauss消去法的不同之处在于：消去法的不同之处在于：后者是按后者是按自然顺序自然顺序取主元素进行消元取主元素进行消元 前者在每步消元之前先前者在每步消元之前先选取主元素选取主元素然后再进行消元然后再进行消元 现在学习的是第25页，共92页2022/12/2第五章 线性方程组的直接解

17、法26下面将列主元下面将列主元Gauss消去法的计算步骤叙述如下：消去法的计算步骤叙述如下：给给定定线线性性方方程程组组 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/12/2第五章 线性方程组的直接解法27 3.再再进进行行第第二二步步消消元元得得到到增增广广矩矩阵阵A（3），b（3）。按按此此方方法法继继续续进进行行下下去去，经经过过n1步步选选主主元元和和消消元元运运算算，得得到到增增广广矩矩阵阵A（n），b（n），它对应的方程组，它对应的方程组A（n）xb（n）是一个是一个与原方程组等价与原方程组等价的上三角形方程组，可进行回代求解。的上三角形方程组，可进行回代求解。容容易易证

19、证明明，只只要要det（A）0，列列主主元元Gauss消消去去法法就就可可以以顺利完成，即不会出现顺利完成，即不会出现主元素为零主元素为零或者或者绝对值太小绝对值太小的情形出现。的情形出现。下面给出列主元下面给出列主元Gauss消去法的计算流程：消去法的计算流程：现在学习的是第27页，共92页2022/12/2第五章 线性方程组的直接解法28列主元列主元GaussGauss消去算法消去算法 用列主元用列主元Gauss消去法求解线性方程组消去法求解线性方程组Axb 输入：输入：A（aij），），b（b1，bn）T，维数，维数n输出：方程组解输出：方程组解x1，xn，或方程组无解信息，或方程组无解

20、信息1 1：对于对于k1，2，n1，循环执行步循环执行步2 2到步到步5 52 2：按列选主元素按列选主元素 aik，即确定下标，即确定下标 i 使使3 3：若若aik0，输出，输出 no unique solution，停机，停机4 4：若若ik，换行，换行现在学习的是第28页，共92页2022/12/2第五章 线性方程组的直接解法295 5：消元计算，对于：消元计算，对于ik1，n，计算计算 6 6：若：若 ann 0 输出输出 no unigue solution，停机，停机7 7：回代求解：回代求解 8 8：输出：输出 x1，x2，xn现在学习的是第29页，共92页2022/12/2第

21、五章 线性方程组的直接解法30 由于这两种方法的精度差不多，且全主元由于这两种方法的精度差不多，且全主元Gauss消去法程序设消去法程序设计复杂占用机器时间较多，实际应用中一般采用列主元计复杂占用机器时间较多，实际应用中一般采用列主元Gauss消去消去法，它既简单又能保证计算精度。法，它既简单又能保证计算精度。有时候在消元过程中可以在系数矩阵所有元素中选择绝对值最大有时候在消元过程中可以在系数矩阵所有元素中选择绝对值最大的元素作为主元素（换行换列），这样的的元素作为主元素（换行换列），这样的Gauss消去法和叫做消去法和叫做全主元全主元Gauss消去法消去法。无回代的列主元消去法：无回代的列主

22、元消去法：高斯高斯约当消去法约当消去法（初等变换法求逆矩阵（初等变换法求逆矩阵的规范算法），计算量大约是的规范算法），计算量大约是n3/2次乘除法次乘除法。现在学习的是第30页，共92页2022/12/2第五章 线性方程组的直接解法312 2 直接三角分解方法直接三角分解方法一一、Gauss消去法的矩阵运算消去法的矩阵运算 从从1中中讨讨论论可可知知，Gauss消消去去法法的的消消元元过过程程是是将将增增广广矩矩阵阵A,bA（1）,b（1）逐步约化为矩阵逐步约化为矩阵A（n）,b（n）。现在说明，在消元过程中，系数矩阵现在说明，在消元过程中，系数矩阵AA（1）是如何经矩阵是如何经矩阵运算约化为

23、上三角矩阵运算约化为上三角矩阵A（n）,即即 用矩阵运算的观点来看，消元的每一步计算等价于用一用矩阵运算的观点来看，消元的每一步计算等价于用一个个单位下三角矩阵单位下三角矩阵左乘前一步约化得到的矩阵。左乘前一步约化得到的矩阵。现在学习的是第31页，共92页2022/12/2第五章 线性方程组的直接解法32若若 ，令，令 ，i2，3，n，得到下三角矩阵得到下三角矩阵施行第一步消元，我们得到施行第一步消元，我们得到现在学习的是第32页，共92页2022/12/2第五章 线性方程组的直接解法33若若 ，令，令 ，i2，3，n，则有，则有 施行第二步消元，我们得到施行第二步消元，我们得到初等行变初等行

24、变换换现在学习的是第33页，共92页2022/12/2第五章 线性方程组的直接解法34如此下去，直至施行第如此下去，直至施行第n1步消元，得到步消元，得到 初等行变初等行变换换现在学习的是第34页，共92页2022/12/2第五章 线性方程组的直接解法35 由此可见，在顺序由此可见，在顺序Gauss消去法的过程中，系数矩阵消去法的过程中，系数矩阵AA（1）经过一系列经过一系列单位下三角矩阵单位下三角矩阵的左乘运算约化为上三角矩阵的左乘运算约化为上三角矩阵A（n），即，即 这时这时由由得得令令现在学习的是第35页，共92页2022/12/2第五章 线性方程组的直接解法36容易验证容易验证 则则从

25、从顺顺序序Gauss消消去去法法的的矩矩阵阵运运算算表表示示式式可可知知，系系数数矩矩阵阵A可分解为一个单位下三角矩阵可分解为一个单位下三角矩阵L和一个上三角矩阵和一个上三角矩阵U的乘积，即的乘积，即其中其中现在学习的是第36页，共92页2022/12/2第五章 线性方程组的直接解法37 第一个方程组的系数矩阵为第一个方程组的系数矩阵为下三角矩阵下三角矩阵，第二个方程组的系，第二个方程组的系数矩阵为数矩阵为上三角矩阵上三角矩阵，两个方程组都非常容易求解，具体求解结果，两个方程组都非常容易求解，具体求解结果如下：如下：我们将我们将A=LU 称为称为矩阵矩阵A的三角分解的三角分解,这时线性方程组为

26、：这时线性方程组为：令令则有则有高斯消元法的实质是把高斯消元法的实质是把A分解为两个三角矩阵乘积分解为两个三角矩阵乘积现在学习的是第37页，共92页2022/12/2第五章 线性方程组的直接解法38对于对于由由解得解得现在学习的是第38页，共92页2022/12/2第五章 线性方程组的直接解法39对于对于由由求得求得现在学习的是第39页，共92页2022/12/2第五章 线性方程组的直接解法40可以看出对于方程组可以看出对于方程组：只要对系数矩阵作了三角分解只要对系数矩阵作了三角分解：由这个简单的计算过程可知，系数矩阵的三角分解很关键，由这个简单的计算过程可知，系数矩阵的三角分解很关键，如何如

27、何进行三角分解更容易进行三角分解更容易？下面介绍几种方法。？下面介绍几种方法。通过如下两组公式很容易求解通过如下两组公式很容易求解：现在学习的是第40页，共92页2022/12/2第五章 线性方程组的直接解法41二、二、Doolittle分解法分解法 前已述及，若在顺序前已述及，若在顺序Gauss消去法的过程中，每步消消去法的过程中，每步消元的主元素元的主元素 akk(k)0，则矩阵，则矩阵A A可分解为可分解为ALU，L为为单单位下三角矩阵位下三角矩阵，U为为上三角矩阵上三角矩阵，此分解称为，此分解称为A的的 Doolittle（杜利特尔）分解。已经证明主元杜利特尔）分解。已经证明主元akk

28、(k)0的的充充要条件要条件是是A的各阶顺序主子式不为零，于是有如下定理。的各阶顺序主子式不为零，于是有如下定理。定定理理5.1 5.1 设设n阶阶方方阵阵A的的各各阶阶顺顺序序主主子子式式不不为为零零，则存在则存在惟一惟一单位下三角矩阵单位下三角矩阵L和和上三角矩阵上三角矩阵U使使ALU。下面介绍矩阵三角分解的下面介绍矩阵三角分解的Doolittle分解方法。分解方法。（前（前n-1阶即可）阶即可）现在学习的是第41页，共92页2022/12/2第五章 线性方程组的直接解法42根据根据 A=LU 有等式成立：有等式成立：比较等式两端比较等式两端对应元素对应元素，有，有现在学习的是第42页，共

29、92页2022/12/2第五章 线性方程组的直接解法43先固定先固定i按行求按行求再固定再固定j按列求按列求现在学习的是第43页，共92页2022/12/2第五章 线性方程组的直接解法44于是，对于矩阵的三角分解：于是，对于矩阵的三角分解：可按照以下公式进行：可按照以下公式进行：对于对于 i=2,3,，n,计算计算（5.2）（5.3）（5.4）用计算公式用计算公式(5.3)、(5.4)对矩阵对矩阵A作的分解作的分解(5.2)称作称作Doolittle分解分解。现在学习的是第44页，共92页2022/12/2第五章 线性方程组的直接解法45按框先横后竖按框先横后竖计算元素计算元素第一步第一步第二

30、步第二步第第 n步步现在学习的是第45页，共92页2022/12/2第五章 线性方程组的直接解法46下面，我们对具体矩阵进行下面，我们对具体矩阵进行Doolittle 三角分解。三角分解。为了表示和存储方便，可以将分解后的两个矩阵用一为了表示和存储方便，可以将分解后的两个矩阵用一个矩阵表示个矩阵表示现在学习的是第46页，共92页2022/12/2第五章 线性方程组的直接解法47例例5-3 5-3 利用利用Doolittle三角分解法分解矩阵三角分解法分解矩阵解：分解时用到如下公式解：分解时用到如下公式1234111261237624624现在学习的是第47页，共92页2022/12/2第五章

31、线性方程组的直接解法481234111261237624624可以写成：可以写成：这时，矩阵的三角分解这时，矩阵的三角分解现在学习的是第48页，共92页2022/12/2第五章 线性方程组的直接解法49如果我们要求解方程组如果我们要求解方程组则由则由得到得到现在学习的是第49页，共92页2022/12/2第五章 线性方程组的直接解法50由由解得解得再由再由求得方程组的解：求得方程组的解：现在学习的是第50页，共92页2022/12/2第五章 线性方程组的直接解法51（5.5）如下的计算公式如下的计算公式(5.3)、(5.4)与与(5.5)就是求解方程组就是求解方程组Axb 的的 Doolitt

32、le 三角分解法三角分解法（紧凑格式法）（紧凑格式法）,包括包括分解分解和和回代回代两步。两步。（5.3）（5.4）关于具体求解过程可以按下面例子的方法进行。关于具体求解过程可以按下面例子的方法进行。与高斯消去法计算量与高斯消去法计算量相同，精度高相同，精度高现在学习的是第51页，共92页2022/12/2第五章 线性方程组的直接解法52例例5-4 利用利用Doolittle三角分解方法解线性方程三角分解方法解线性方程解解:进行三角分解进行三角分解ALU，按照公式按照公式(5.5)可以对增广可以对增广 矩阵矩阵A,b作三角分解作三角分解:1 2 3 -2-3 2 2-3-13317现在学习的是

33、第52页，共92页2022/12/2第五章 线性方程组的直接解法53得到得到1 2 3 -2-3 2 2-3-13317这时，相应的方程组为：这时，相应的方程组为：x135x28，现在学习的是第53页，共92页2022/12/2第五章 线性方程组的直接解法54例例5-5 利用利用Doolittle三角分解方法解线性方程组三角分解方法解线性方程组解：对增广矩阵进行三角分解解：对增广矩阵进行三角分解1 2 3 -4 -2-3 2 42-3133322-4-117-16等价方程组通过分解式容易写出为：等价方程组通过分解式容易写出为：现在学习的是第54页，共92页2022/12/2第五章 线性方程组的

34、直接解法551 2 3 -4 -2-3 2 42-3133322-4-117-16解得解得LU分解的意义：按分解的意义：按A的性质作不同分解，得到不同的直接三角分解法的性质作不同分解，得到不同的直接三角分解法现在学习的是第55页，共92页2022/12/2第五章 线性方程组的直接解法56三、平方根法三、平方根法 实际应用中，常见一类非常重要的线性方程组实际应用中，常见一类非常重要的线性方程组Axb，其中，其中A为为对称正定矩阵对称正定矩阵，即，即A是对称的且对任何非零向量是对称的且对任何非零向量 x 都有都有xTAx0 0。本节将对这类方程组导出更有效的三角分解求解方法，称之本节将对这类方程组

35、导出更有效的三角分解求解方法，称之为为平方根法平方根法。设设A为为对对称称正正定定矩矩阵阵，那那么么A的的所所有有顺顺序序主主子子式式均均大大于于零零，根据定理根据定理5.15.1，存在惟一三角分解，存在惟一三角分解ALU，即，即现在学习的是第56页，共92页2022/12/2第五章 线性方程组的直接解法57 记记 Ak（1kn）为）为A的的 k 阶顺序主子阵，则阶顺序主子阵，则det（Ak）为）为A的的k阶顺序主子式阶顺序主子式(记为记为Dk)。由上式，利用矩阵分块运算规则，容易验。由上式，利用矩阵分块运算规则，容易验证证 D1=u11，Dk u11 u22 ukk=Dk-1ukk (k1)

36、那么由那么由Dk0，可知，可知 ukk0，k1，2，n 这时，将上面的矩阵表示为：这时，将上面的矩阵表示为：现在学习的是第57页，共92页2022/12/2第五章 线性方程组的直接解法58即：即：A=LDU1 ，其中，其中 DU1=U，U1=D-1U。现在学习的是第58页，共92页2022/12/2第五章 线性方程组的直接解法59单位下三角阵单位下三角阵当当AAT为对称矩阵时，根据为对称矩阵时，根据 ALDU1,得到得到ATU1T D LT=U1T(D LT)再根据矩阵三角分解的唯一性再根据矩阵三角分解的唯一性,可知可知 U1 T L。于是。于是ALDLT 对称阵分解对称阵分解则有则有令令上三

37、角阵上三角阵现在学习的是第59页，共92页2022/12/2第五章 线性方程组的直接解法60 如果对称正定矩阵如果对称正定矩阵A具有如下分解具有如下分解 AGGT，其中，其中G为下三角为下三角矩阵，则称其为矩阵，则称其为对称正定矩阵的对称正定矩阵的 Cholesky（乔列斯基）分解。（乔列斯基）分解。(定理定理5.3)为表示方便，可以记为表示方便，可以记 给定对称正定方程组给定对称正定方程组 Axb，对，对 A 进行进行 Cholesky分解分解ALLT，则原方程组等价于，则原方程组等价于 LLTxb平方根分解平方根分解现在学习的是第60页，共92页2022/12/2第五章 线性方程组的直接解

38、法61Lyb；LTx y由此解得原方程组的解由此解得原方程组的解x，这就是求解方程组的，这就是求解方程组的平方根法平方根法（利用对称利用对称正定矩阵的正定矩阵的Choleskey分解求解正定方程组的方法）分解求解正定方程组的方法）下下面面，我我们们通通过过比比较较矩矩阵阵的的对对应应元元素素给给出出对对称称正正定定矩矩阵阵的的平平方方根分解法根分解法。已知。已知即：即：LLTxb，等价于等价于现在学习的是第61页，共92页2022/12/2第五章 线性方程组的直接解法62比较对应元素：比较对应元素：现在学习的是第62页，共92页2022/12/2第五章 线性方程组的直接解法63当当 i=j 时

39、时当当 j i 时时固定固定j按列求按列求现在学习的是第63页，共92页2022/12/2第五章 线性方程组的直接解法64于是，根据计算公式于是，根据计算公式可以对对称正定矩阵进行平方根分解可以对对称正定矩阵进行平方根分解l11 l21 l22 l31 l32 l33 ln1 ln2 ln3 lnn 现在学习的是第64页，共92页2022/12/2第五章 线性方程组的直接解法65按列计算按列计算元素元素平方根法不必选主元，精度高，稳定性好，是最有效算法之一。平方根法不必选主元，精度高，稳定性好，是最有效算法之一。现在学习的是第65页，共92页2022/12/2第五章 线性方程组的直接解法66

40、关关于于方方程程组组 Ax=b,如如果果对对系系数数矩矩阵阵进进行行了了平平方方根根分分解解 ALLT，则将方程组化为：，则将方程组化为：Lyb,LTxy解得解得现在学习的是第66页，共92页2022/12/2第五章 线性方程组的直接解法67 于是，关于系数矩阵是对称正定矩阵的线性方程组于是，关于系数矩阵是对称正定矩阵的线性方程组Ax=b的求解，的求解，分两步进行：分两步进行：第一步：系数矩阵的第一步：系数矩阵的平方根分解平方根分解第二步：解等价方程组第二步：解等价方程组现在学习的是第67页，共92页2022/12/2第五章 线性方程组的直接解法68例例5-6 用平方根法求解对称正定方程组用平

41、方根法求解对称正定方程组 解解:首先进行首先进行A 的的Cholesky 分解分解 ALLT2-0.50.521.512-0.50.521.51现在学习的是第68页，共92页2022/12/2第五章 线性方程组的直接解法69得得 y12，y23.5，y31 得得 x11，x21，x31 求解求解Lyb:再求解再求解 LTxy:现在学习的是第69页，共92页2022/12/2第五章 线性方程组的直接解法70关于对称正定方程组关于对称正定方程组 也可以用一般的三角分解法求解，这时由也可以用一般的三角分解法求解，这时由 4 -1 1 4-0.250.254370.7511求得求得 x11，x21，x

42、31 现在学习的是第70页，共92页2022/12/2第五章 线性方程组的直接解法71改进平方根法改进平方根法：利用对称矩阵分解利用对称矩阵分解A=LDLT求解系数矩阵为对称的求解系数矩阵为对称的线性方程组线性方程组Ax=b的方法的方法.（避免开方运算）（避免开方运算）（对角加载）（对角加载）现在学习的是第71页，共92页2022/12/2第五章 线性方程组的直接解法72固定i按行算现在学习的是第72页，共92页2022/12/2第五章 线性方程组的直接解法73四、追赶法四、追赶法 追追赶赶法法是是专专门门用用于于求求解解三三对对角角方方程程组组的的。这这类类方方程程组组经经常常出出现现于于用

43、用差差分分方方法法或或有有限限元元方方法法求求解解二二阶阶常常微微分分方方程程边边值值问问题题、热热传传导导问问题题及及三三次次样样条条函函数数插插值值等等问问题题，三三对角方程组对角方程组Axf 的系数矩阵具有如下形式：的系数矩阵具有如下形式：设设A为一个三对角矩阵，那么它的顺序主子式均不为零为一个三对角矩阵，那么它的顺序主子式均不为零的一个充分条件是：的一个充分条件是：现在学习的是第73页，共92页2022/12/2第五章 线性方程组的直接解法74在此条件下，可对在此条件下，可对A进行三角分解，设进行三角分解，设比较矩阵的对应元素，根据矩阵乘法规则，可得到比较矩阵的对应元素，根据矩阵乘法规

44、则，可得到 按行对按行对角占优角占优下三角下三角单位上三角单位上三角Crout分解分解现在学习的是第74页，共92页2022/12/2第五章 线性方程组的直接解法75可以证明可以证明现在学习的是第75页，共92页2022/12/2第五章 线性方程组的直接解法76于是，由以上结果：于是，由以上结果：分别得到：分别得到：也就是说也就是说,用这一组公式可以对三对角矩阵进行三角分用这一组公式可以对三对角矩阵进行三角分解：解：现在学习的是第76页，共92页2022/12/2第五章 线性方程组的直接解法77对对于于三三对对角角方方程程组组Axf，设设A的的三三角角分分解解为为ALU，则则原原方方程程组组等

45、等价于价于Lyf，Uxy LUxf，即，即 现在学习的是第77页，共92页2022/12/2第五章 线性方程组的直接解法78由由Lyf，即，即解得解得解得解得由由Uxy，即，即现在学习的是第78页，共92页2022/12/2第五章 线性方程组的直接解法79解三对角矩阵方程组解三对角矩阵方程组 Ax=f 的的追赶法追赶法为：为：现在学习的是第79页，共92页2022/12/2第五章 线性方程组的直接解法80例例5-7 用追赶法求解三对角方程组用追赶法求解三对角方程组 解解:首先进行系数矩阵的三角分解首先进行系数矩阵的三角分解 现在学习的是第80页，共92页2022/12/2第五章 线性方程组的直

46、接解法81现在学习的是第81页，共92页2022/12/2第五章 线性方程组的直接解法82求解方程组求解方程组Lyf，即，即 得得 到到 y11/2，y21/3，y31/4，y41 再求解方程组再求解方程组 Uxy，即，即 得得 到到 x11，x21，x31，x41 现在学习的是第82页，共92页2022/12/2第五章 线性方程组的直接解法83 当三对角矩阵当三对角矩阵A满足对角占优条件时，追赶法是数值稳定的。满足对角占优条件时，追赶法是数值稳定的。追赶法具有计算程序简单，存贮少，计算量小的优点。追赶法具有计算程序简单，存贮少，计算量小的优点。计算量仅为计算量仅为O(n)解解三三对对角角方方

47、程程组组Axf 的的追追赶赶法法，用用四四个个一一维维数数组组存存放放方方程程组组数据数据 ai，bi，ci，fi ,fi常数项。常数项。输入输入 方程组数据方程组数据 ai，bi，ci，fi，n输出输出 计算解计算解x（x1，x2，xn）T根据以下算法编写程序根据以下算法编写程序现在学习的是第83页，共92页2022/12/2第五章 线性方程组的直接解法841 2 对于对于i1，2，n1，计算，计算3 4 5 输出输出 x1，x2，xn 现在学习的是第84页，共92页2022/12/2第五章 线性方程组的直接解法85五、三角分解方法的优点五、三角分解方法的优点 此时，在完成并存贮矩阵此时，在

48、完成并存贮矩阵L和和U后，右端项改变一次仅需增加后，右端项改变一次仅需增加 n2 次运算。次运算。1.当需要求解具有同系数矩阵的一系列方程组当需要求解具有同系数矩阵的一系列方程组 Axbi，i1，2，m 时，可节省计算量时，可节省计算量。U y=biL x=yi=1,2,m 首先对系数矩阵作三角分解首先对系数矩阵作三角分解 ALU，再求解方程组化为：再求解方程组化为：现在学习的是第85页，共92页2022/12/2第五章 线性方程组的直接解法862.可用来求可逆矩阵可用来求可逆矩阵 A 的逆矩阵的逆矩阵 A1推得推得 A Xk e k，k1，2，n令令 A-1=(X1 X2 Xn ),E=(e

49、1 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/12/2第五章 线性方程组的直接解法873.可用来求矩阵可用来求矩阵 A 的行列式的行列式如果对矩阵如果对矩阵 A 作了三角分解作了三角分解 A=LU：则可以求得行列式的值为则可以求得行列式的值为现在学习的是第87页，共92页2022/12/2第五章 线性方程组的直接解法88第五章第五章 总总 结结 1.解线性方程组解线性方程组Gau

50、ss消去法的计算程序如何实现？可以消去法的计算程序如何实现？可以进行进行Gauss消去法的条件是什么？消去法的条件是什么？2.解线性方程组列主元解线性方程组列主元Gauss消去法的计算程序如何实现？可以消去法的计算程序如何实现？可以进行列主元进行列主元Gauss消去法的条件是什么？消去法的条件是什么？3.解线性方程组的解线性方程组的Doolittle三角分解法如何进行三角分解法如何进行?可以进分解的条可以进分解的条件是什么？件是什么？4.解对称正定矩阵方程组的平方根解对称正定矩阵方程组的平方根(Cholesky)解法如何解法如何进行进行?5.如何实现解三对角矩阵方程组的追赶法的计算程序如何实现