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

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

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

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

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

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

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

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

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

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

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

10、学习的是第15页，共90页2023/2/24第五章 线性方程组的直接解法16在编程计算时，最后的增广矩阵存放的元素是：在编程计算时，最后的增广矩阵存放的元素是：下面给出下面给出Gauss消去法的计算流程：消去法的计算流程：现在学习的是第16页，共90页2023/2/24第五章 线性方程组的直接解法17消元过程：消元过程：jk1，n 回代过程：回代过程：对于对于in1，n2，1，计算，计算k1，2，n1，ik1，k2，n对于对于执行计算执行计算置置现在学习的是第17页，共90页2023/2/24第五章 线性方程组的直接解法18消元条件：消元条件：回代条件：回代条件：消元法是将某行的若干倍加到另一

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

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

13、如下消去法求解如下方程组方程组现在学习的是第20页，共90页2023/2/24第五章 线性方程组的直接解法21此方程组具有四位有效数字的精确解为此方程组具有四位有效数字的精确解为x117.46，x245.76，x35.546 如果用顺序如果用顺序Gauss消去法求解，消元过程如下消去法求解，消元过程如下现在学习的是第21页，共90页2023/2/24第五章 线性方程组的直接解法22经回代求解得经回代求解得 x35.546，x2100.0，x1104.0和此方程组的精确解相比和此方程组的精确解相比x35.546，x245.76，x117.46有较大的误差。有较大的误差。对对于于此此例例，由由于于

14、顺顺序序Gauss消消去去法法中中的的主主元元素素绝绝对对值值非非常常小小，使使消消元元乘乘数数绝绝对对值值非非常常大大，计计算算过过程程中中出出现现大大数数吃吃掉掉小小数数现现象象，产产生生较较大大的的舍舍入入误误差差，最最终终导导致致计计算算所所求求得得的的两两个个解解 x1104.0 和和 x2100.0 已完全失真。已完全失真。为为避避免免这这种种现现象象发发生生，可可以以对对原原方方程程组组作作等等价价变变换换，再再利利用顺序用顺序Gauss消去法求解消去法求解。现在学习的是第22页，共90页2023/2/24第五章 线性方程组的直接解法23写出原方程组的增广矩阵：写出原方程组的增广

15、矩阵：针对第一列找出绝对值最大的元素，进行等价变换：针对第一列找出绝对值最大的元素，进行等价变换：现在学习的是第23页，共90页2023/2/24第五章 线性方程组的直接解法24求得方程的解为：求得方程的解为：x35.546，x245.76，x117.46精确解为：精确解为：x35.546，x245.76，x117.46 由此可见，第二种由此可见，第二种Gauss消去法的精度明显高于顺序消去法的精度明显高于顺序Gauss消去法，消去法，我们称它为我们称它为列主元列主元Gauss消去法消去法。列主元列主元Gauss消去法与消去法与顺序顺序Gauss消去法的不同之处在于：消去法的不同之处在于：后者

16、是按后者是按自然顺序自然顺序取主元素进行消元取主元素进行消元 前者在每步消元之前先前者在每步消元之前先选取主元素选取主元素然后再进行消元然后再进行消元 现在学习的是第24页，共90页2023/2/24第五章 线性方程组的直接解法25下面将列主元下面将列主元Gauss消去法的计算步骤叙述如下：消去法的计算步骤叙述如下：给给定定线线性性方方程程组组 Axb,记记A(1),b(1)A,b，列列主主元元Gauss消去法的具体过程如下：消去法的具体过程如下：1.首首先先在在增增广广矩矩阵阵A（1）,b（1）第第一一列列的的n个个元元素素中中选选取取绝绝对对值最大的一个作为主元素，并把此主元素所在的行与第

17、一行交换，即值最大的一个作为主元素，并把此主元素所在的行与第一行交换，即 2.其其次次进进行行第第一一步步消消元元得得到到增增广广矩矩阵阵A（2）,b（2），在在矩矩阵阵A（2）,b（2）第第二二列列的的后后 n1个个元元素素中中选选取取绝绝对对值值最最大大的的一一个个作作为主元素，并把此主元素所在的行与第二行交换，即为主元素，并把此主元素所在的行与第二行交换，即现在学习的是第25页，共90页2023/2/24第五章 线性方程组的直接解法26 3.再再进进行行第第二二步步消消元元得得到到增增广广矩矩阵阵A（3），b（3）。按按此此方方法法继继续续进进行行下下去去，经经过过n1步步选选主主元元和

18、和消消元元运运算算，得得到到增增广广矩矩阵阵A（n），b（n），它对应的方程组，它对应的方程组A（n）xb（n）是一个是一个与原方程组等价与原方程组等价的上三角形方程组，可进行回代求解。的上三角形方程组，可进行回代求解。容容易易证证明明，只只要要det（A）0，列列主主元元Gauss消消去去法法就就可可以以顺顺利利完完成，即不会出现成，即不会出现主元素为零主元素为零或者或者绝对值太小绝对值太小的情形出现。的情形出现。下面给出列主元下面给出列主元Gauss消去法的计算流程：消去法的计算流程：现在学习的是第26页，共90页2023/2/24第五章 线性方程组的直接解法27列主元列主元GaussGa

19、uss消去算法消去算法 用列主元用列主元Gauss消去法求解线性方程组消去法求解线性方程组Axb 输入：输入：A（aij），），b（b1，bn）T，维数，维数n输出：方程组解输出：方程组解x1，xn，或方程组无解信息，或方程组无解信息1 1：对于对于k1，2，n1，循环执行步循环执行步2 2到步到步5 52 2：按列选主元素按列选主元素 aik，即确定下标，即确定下标 i 使使3 3：若若aik0，输出，输出 no unique solution，停机，停机4 4：若若ik，换行，换行现在学习的是第27页，共90页2023/2/24第五章 线性方程组的直接解法285 5：消元计算，对于：消元计

20、算，对于ik1，n，计算计算 6 6：若：若 ann 0 输出输出 no unigue solution，停机，停机7 7：回代求解：回代求解 8 8：输出：输出 x1，x2，xn现在学习的是第28页，共90页2023/2/24第五章 线性方程组的直接解法29 由于这两种方法的精度差不多，且全主元由于这两种方法的精度差不多，且全主元Gauss消去法程序设消去法程序设计复杂占用机器时间较多，实际应用中一般采用列主元计复杂占用机器时间较多，实际应用中一般采用列主元Gauss消去消去法，它既简单又能保证计算精度。法，它既简单又能保证计算精度。有时候在消元过程中可以在系数矩阵所有元素中选择绝对值最有时

21、候在消元过程中可以在系数矩阵所有元素中选择绝对值最大的元素作为主元素（换行换列），这样的大的元素作为主元素（换行换列），这样的Gauss消去法和叫做消去法和叫做全全主元主元Gauss消去法消去法。无回代的列主元消去法：无回代的列主元消去法：高斯高斯约当消去法约当消去法（初等变换法求（初等变换法求逆矩阵的规范算法），计算量大约是高斯法的逆矩阵的规范算法），计算量大约是高斯法的3倍。倍。现在学习的是第29页，共90页2023/2/24第五章 线性方程组的直接解法302 2 直接三角分解方法直接三角分解方法一一、Gauss消去法的矩阵运算消去法的矩阵运算 从从1中中讨讨论论可可知知，Gauss消消去

22、去法法的的消消元元过过程程是是将将增增广广矩矩阵阵A,bA（1）,b（1）逐步约化为矩阵逐步约化为矩阵A（n）,b（n）。现在说明，在消元过程中，系数矩阵现在说明，在消元过程中，系数矩阵AA（1）是如何经矩阵运是如何经矩阵运算约化为上三角矩阵算约化为上三角矩阵A（n）,即即 用矩阵运算的观点来看，消元的每一步计算等价于用一个用矩阵运算的观点来看，消元的每一步计算等价于用一个单位下三角矩阵单位下三角矩阵左乘前一步约化得到的矩阵。左乘前一步约化得到的矩阵。现在学习的是第30页，共90页2023/2/24第五章 线性方程组的直接解法31若若 ，令，令 ，i2，3，n，得到下三角矩阵得到下三角矩阵施行

23、第一步消元，我们得到施行第一步消元，我们得到现在学习的是第31页，共90页2023/2/24第五章 线性方程组的直接解法32若若 ，令，令 ，i2，3，n，则有，则有 施行第二步消元，我们得到施行第二步消元，我们得到初等行变初等行变换换现在学习的是第32页，共90页2023/2/24第五章 线性方程组的直接解法33如此下去，直至施行第如此下去，直至施行第n1步消元，得到步消元，得到 初等行变初等行变换换现在学习的是第33页，共90页2023/2/24第五章 线性方程组的直接解法34 由此可见，在顺序由此可见，在顺序Gauss消去法的过程中，系数矩阵消去法的过程中，系数矩阵AA（1）经经过一系列

24、过一系列单位下三角矩阵单位下三角矩阵的左乘运算约化为上三角矩阵的左乘运算约化为上三角矩阵A（n），即，即 这时这时由由得得令令现在学习的是第34页，共90页2023/2/24第五章 线性方程组的直接解法35容易验证容易验证 则则从从顺顺序序Gauss消消去去法法的的矩矩阵阵运运算算表表示示式式可可知知，系系数数矩矩阵阵A可可分分解为一个单位下三角矩阵解为一个单位下三角矩阵L和一个上三角矩阵和一个上三角矩阵U的乘积，即的乘积，即其中其中现在学习的是第35页，共90页2023/2/24第五章 线性方程组的直接解法36 第一个方程组的系数矩阵为第一个方程组的系数矩阵为下三角矩阵下三角矩阵，第二个方程

25、组的系，第二个方程组的系数矩阵为数矩阵为上三角矩阵上三角矩阵，两个方程组都非常容易求解，具体求解结，两个方程组都非常容易求解，具体求解结果如下：果如下：我们将我们将A=LU 称为称为矩阵矩阵A的三角分解的三角分解,这时线性方程组为：这时线性方程组为：令令则有则有高斯消元法与矩阵的因式分解有关高斯消元法与矩阵的因式分解有关现在学习的是第36页，共90页2023/2/24第五章 线性方程组的直接解法37对于对于由由解得解得现在学习的是第37页，共90页2023/2/24第五章 线性方程组的直接解法38对于对于由由求得求得现在学习的是第38页，共90页2023/2/24第五章 线性方程组的直接解法3

26、9可以看出对于方程组可以看出对于方程组：只要对系数矩阵作了三角分解只要对系数矩阵作了三角分解：由这个简单的计算过程可知，系数矩阵的三角分解很关键，由这个简单的计算过程可知，系数矩阵的三角分解很关键，如何如何进行三角分解更容易进行三角分解更容易？下面介绍几种方法。？下面介绍几种方法。通过如下两组公式很容易求解通过如下两组公式很容易求解：现在学习的是第39页，共90页2023/2/24第五章 线性方程组的直接解法40二、二、Doolittle分解法分解法 前已述及，若在顺序前已述及，若在顺序Gauss消去法的过程中，每步消元消去法的过程中，每步消元的主元素的主元素 akk(k)0，则矩阵，则矩阵A

27、 A可分解为可分解为ALU，L为为单位下单位下三角矩阵三角矩阵，U为为上三角矩阵上三角矩阵，此分解称为，此分解称为A的的 Doolittle（杜利特尔）分解。可以证明当杜利特尔）分解。可以证明当akk(k)0的的充要条件充要条件是是A的各阶顺序主子式不为零，于是有如下定理。的各阶顺序主子式不为零，于是有如下定理。定定理理5.1 5.1 设设n阶阶方方阵阵A的的各各阶阶顺顺序序主主子子式式不不为为零零，则则存在存在惟一惟一单位下三角矩阵单位下三角矩阵L和和上三角矩阵上三角矩阵U使使ALU。下面介绍矩阵三角分解的下面介绍矩阵三角分解的Doolittle分解方法。分解方法。现在学习的是第40页，共9

28、0页2023/2/24第五章 线性方程组的直接解法41根据根据 A=LU 有等式成立：有等式成立：比较等式两端比较等式两端对应元素对应元素，有，有现在学习的是第41页，共90页2023/2/24第五章 线性方程组的直接解法42先固定先固定i按行求按行求再固定再固定j按列求按列求现在学习的是第42页，共90页2023/2/24第五章 线性方程组的直接解法43于是，对于矩阵的三角分解：于是，对于矩阵的三角分解：可按照以下公式进行：可按照以下公式进行：对于对于 i=2,3,，n,计算计算（5.2）（5.3）（5.4）用计算公式用计算公式(5.3)、(5.4)对矩阵对矩阵A作的分解作的分解(5.2)称

29、作称作Doolittle分解。分解。现在学习的是第43页，共90页2023/2/24第五章 线性方程组的直接解法44 按框先横后按框先横后竖计算元素竖计算元素第一步第一步第二步第二步第第 n步步现在学习的是第44页，共90页2023/2/24第五章 线性方程组的直接解法45下面，我们对具体矩阵进行下面，我们对具体矩阵进行Doolittle 三角分解。三角分解。为了表示和存储方便，可以将分解后的两个矩阵用一为了表示和存储方便，可以将分解后的两个矩阵用一个矩阵表示个矩阵表示现在学习的是第45页，共90页2023/2/24第五章 线性方程组的直接解法46例例5-3 5-3 利用利用Doolittle

30、三角分解法分解矩阵三角分解法分解矩阵解：分解时用到如下公式解：分解时用到如下公式1234111261237624624现在学习的是第46页，共90页2023/2/24第五章 线性方程组的直接解法471234111261237624624可以写成：可以写成：这时，矩阵的三角分解这时，矩阵的三角分解现在学习的是第47页，共90页2023/2/24第五章 线性方程组的直接解法48如果我们要求解方程组如果我们要求解方程组则由则由得到得到现在学习的是第48页，共90页2023/2/24第五章 线性方程组的直接解法49由由解得解得再由再由求得方程组的解：求得方程组的解：现在学习的是第49页，共90页202

31、3/2/24第五章 线性方程组的直接解法50（5.5）如下的计算公式如下的计算公式(5.3)、(5.4)与与(5.5)就是求解方程组就是求解方程组Axb 的的 Doolittle 三角分解法三角分解法（紧凑格式法）（紧凑格式法）,包括包括分解分解和和回代回代两步。两步。（5.3）（5.4）关于具体求解过程可以按下面例子的方法进行。关于具体求解过程可以按下面例子的方法进行。与高斯消去法计与高斯消去法计算量基本相同算量基本相同现在学习的是第50页，共90页2023/2/24第五章 线性方程组的直接解法51例例5-4 利用利用Doolittle三角分解方法解线性方程三角分解方法解线性方程解解:进行三

32、角分解进行三角分解ALU，按照公式按照公式(5.5)可以对增广可以对增广 矩阵矩阵A,b作三角分解作三角分解:1 2 3 -2-3 2 2-3-13317现在学习的是第51页，共90页2023/2/24第五章 线性方程组的直接解法52得到得到1 2 3 -2-3 2 2-3-13317这时，相应的方程组为：这时，相应的方程组为：x135x28，现在学习的是第52页，共90页2023/2/24第五章 线性方程组的直接解法53例例5-5 利用利用Doolittle三角分解方法解线性方程组三角分解方法解线性方程组解：对增广矩阵进行三角分解解：对增广矩阵进行三角分解1 2 3 -4 -2-3 2 42

33、-3133322-4-117-16等价方程组通过分解式容易写出为：等价方程组通过分解式容易写出为：现在学习的是第53页，共90页2023/2/24第五章 线性方程组的直接解法541 2 3 -4 -2-3 2 42-3133322-4-117-16解得解得LU分解的意义：根据分解的意义：根据A的性质作不同的分解，得到不同的直接法的性质作不同的分解，得到不同的直接法现在学习的是第54页，共90页2023/2/24第五章 线性方程组的直接解法55三、平方根法三、平方根法 在实际应用中，常见一类非常重要的线性方程组在实际应用中，常见一类非常重要的线性方程组Axb，其，其中中A A为为对称正定矩阵对称

34、正定矩阵，即，即A是对称的且对任何非零向量是对称的且对任何非零向量 x 都有都有xTAx0 0。本节将对这类方程组导出更有效地三角分解求解方法，称之为。本节将对这类方程组导出更有效地三角分解求解方法，称之为平方根法平方根法。设设A为为对对称称正正定定矩矩阵阵，那那么么A的的所所有有顺顺序序主主子子式式均均大大于于零零，根根据定理据定理5.15.1，存在惟一三角分解，存在惟一三角分解ALU，即，即现在学习的是第55页，共90页2023/2/24第五章 线性方程组的直接解法56 记记 Ak（1kn）为）为A的的 k 阶顺序主子阵，则阶顺序主子阵，则det（Ak）为）为A的的k阶顺序主子式。由上式，

35、利用矩阵分块运算规则，容易验证阶顺序主子式。由上式，利用矩阵分块运算规则，容易验证 det（Ak）u11 u22 ukk那么由那么由 det（Ak）0，可知，可知 ukk0，k1，2，n 这时，将上面的矩阵表示为：这时，将上面的矩阵表示为：现在学习的是第56页，共90页2023/2/24第五章 线性方程组的直接解法57即：即：A=LDM ，其中其中 DM=U，M=D-1U。现在学习的是第57页，共90页2023/2/24第五章 线性方程组的直接解法58当当AAT为对称矩阵时，根据为对称矩阵时，根据 ALDM,得到得到ATMT D LT再根据矩阵三角分解的唯一性再根据矩阵三角分解的唯一性,可知可

36、知 MLT。于是。于是ALDLT则有则有令令现在学习的是第58页，共90页2023/2/24第五章 线性方程组的直接解法59 如果对称正定矩阵如果对称正定矩阵A具有如下分解具有如下分解 AGGT，其中，其中G为下三为下三角矩阵，则称其为角矩阵，则称其为对称正定矩阵的对称正定矩阵的 Cholesky（乔列斯基）分解。（乔列斯基）分解。为表示方便，可以记为表示方便，可以记 给定对称正定方程组给定对称正定方程组 Axb，对，对 A 进行进行 Cholesky分解分解ALLT，则原方程组等价于，则原方程组等价于 LLTxb现在学习的是第59页，共90页2023/2/24第五章 线性方程组的直接解法60

37、Lyb LTx y解此方程组即可得到原方程组的解解此方程组即可得到原方程组的解x ，这就是求解方程组的这就是求解方程组的平方平方根法根法。下下面面，我我们们通通过过比比较较矩矩阵阵的的对对应应元元素素给给出出对对称称正正定定矩矩阵阵的的平平方方根根分解法分解法。已知。已知即：即：LLTxb，等价于等价于现在学习的是第60页，共90页2023/2/24第五章 线性方程组的直接解法61比较对应元素：比较对应元素：现在学习的是第61页，共90页2023/2/24第五章 线性方程组的直接解法62当当 i=j 时时当当 j i 时时解得解得现在学习的是第62页，共90页2023/2/24第五章 线性方程

38、组的直接解法63于是，根据计算公式于是，根据计算公式可以对对称正定矩阵进行平方根分解可以对对称正定矩阵进行平方根分解l11 l21 l22 l31 l32 l33 ln1 ln2 ln3 lnn 现在学习的是第63页，共90页2023/2/24第五章 线性方程组的直接解法64 关关于于方方程程组组 Ax=b,如如果果对对系系数数矩矩阵阵进进行行了了平平方方根根分分解解 ALLT，则将方程组化为：，则将方程组化为：Lyb,LTxy解得解得现在学习的是第64页，共90页2023/2/24第五章 线性方程组的直接解法65 于是，关于系数矩阵是对称正定矩阵的线性方程组于是，关于系数矩阵是对称正定矩阵的

39、线性方程组Ax=b的求解，的求解，分两步进行：分两步进行：第一步：系数矩阵的平方根分解第一步：系数矩阵的平方根分解第二步：解等价方程组第二步：解等价方程组现在学习的是第65页，共90页2023/2/24第五章 线性方程组的直接解法66例例5-6 用平方根法求解对称正定方程组用平方根法求解对称正定方程组 解解:首先进行首先进行A 的的Cholesky 分解分解 ALLT2-0.50.521.512-0.50.521.51现在学习的是第66页，共90页2023/2/24第五章 线性方程组的直接解法67得得 y12，y23.5，y31 得得 x11，x21，x31 求解求解Lyb:再求解再求解 LT

40、xy:现在学习的是第67页，共90页2023/2/24第五章 线性方程组的直接解法68关于对称正定方程组关于对称正定方程组 也可以用一般的三角分解法求解，这时由也可以用一般的三角分解法求解，这时由 4 -1 1 4-0.250.254370.7511求得求得 x11，x21，x31 现在学习的是第68页，共90页2023/2/24第五章 线性方程组的直接解法69四、追赶法四、追赶法 追追赶赶法法是是专专门门用用于于求求解解三三对对角角方方程程组组的的。这这类类方方程程组组经经常常出出现现于于用用差差分分方方法法或或有有限限元元方方法法求求解解二二阶阶常常微微分分方方程程边边值值问问题题、热热传

41、传导导问问题题及及三三次次样样条条函函数数插插值值等等问问题题，三对角方程组三对角方程组AxAxb b的系数矩阵具有如下形式：的系数矩阵具有如下形式：设设A A为一个三对角矩阵，那么它的顺序主子式均不为零为一个三对角矩阵，那么它的顺序主子式均不为零的一个充分条件是：的一个充分条件是：现在学习的是第69页，共90页2023/2/24第五章 线性方程组的直接解法70在此条件下，可对在此条件下，可对A进行三角分解，设进行三角分解，设比较矩阵的对应元素，根据矩阵乘法规则，可得到比较矩阵的对应元素，根据矩阵乘法规则，可得到 现在学习的是第70页，共90页2023/2/24第五章 线性方程组的直接解法71

42、i-1列列i 行行第第3列列现在学习的是第71页，共90页2023/2/24第五章 线性方程组的直接解法72i-1列列i-1行行第第3列列现在学习的是第72页，共90页2023/2/24第五章 线性方程组的直接解法73i-1列列第第3列列i-1行行i-1列列现在学习的是第73页，共90页2023/2/24第五章 线性方程组的直接解法74于是，由以上结果：于是，由以上结果：分别得到：分别得到：也就是说也就是说,用这一组公式可以对三对角矩阵进行三角分解：用这一组公式可以对三对角矩阵进行三角分解：现在学习的是第74页，共90页2023/2/24第五章 线性方程组的直接解法75对对于于三三对对角角方方

43、程程组组Axb，设设A的的三三角角分分解解为为ALU，则则原原方方程程组组等等价于价于Lyb，Uxy 现在学习的是第75页，共90页2023/2/24第五章 线性方程组的直接解法76由由Lyb，即即解得解得解得解得由由Uxy，即即现在学习的是第76页，共90页2023/2/24第五章 线性方程组的直接解法77于是，对于三对角矩阵方程组于是，对于三对角矩阵方程组 Ax=b，如下的两组公式便如下的两组公式便构成了构成了解三对角方程组的追赶法：构成了构成了解三对角方程组的追赶法：现在学习的是第77页，共90页2023/2/24第五章 线性方程组的直接解法78例例5-7 用追赶法求解三对角方程组用追赶

44、法求解三对角方程组 解解:首先进行系数矩阵的三角分解首先进行系数矩阵的三角分解 现在学习的是第78页，共90页2023/2/24第五章 线性方程组的直接解法79现在学习的是第79页，共90页2023/2/24第五章 线性方程组的直接解法80求解方程组求解方程组Lyy，即，即 得得 到到 y11/2，y21/3，y31/4，y41 再求解方程组再求解方程组 Uxy，即，即 得得 到到 x11，x21，x31，x41 现在学习的是第80页，共90页2023/2/24第五章 线性方程组的直接解法81 当三对角矩阵当三对角矩阵A满足对角占优条件时，追赶法是数值稳定满足对角占优条件时，追赶法是数值稳定的

45、。的。追赶法具有计算程序简单，存贮少，计算量小的优点。追赶法具有计算程序简单，存贮少，计算量小的优点。解解三三对对角角方方程程组组Axb的的追追赶赶法法，用用四四个个一一维维数数组组存存放放方方程程组组数数据据 ai，bi，ci，di ,di常数项。常数项。输入输入 方程组数据方程组数据 ai，bi，ci，di，n输出输出 计算解计算解x（x1，x2，xn）T根据以下算法编写程序根据以下算法编写程序现在学习的是第81页，共90页2023/2/24第五章 线性方程组的直接解法821 2 对于对于i1，2，n1，计算，计算3 4 5 输出输出 x1，x2，xn 现在学习的是第82页，共90页202

46、3/2/24第五章 线性方程组的直接解法83五、三角分解方法的优点五、三角分解方法的优点 此时，在完成并存贮矩阵此时，在完成并存贮矩阵L和和U后，右端项第改变一次仅需增后，右端项第改变一次仅需增加加 n2 次运算。次运算。1.当需要求解具有同系数矩阵的一系列方程组当需要求解具有同系数矩阵的一系列方程组 Axbi，i1，2，m 时，可大节省计算量时，可大节省计算量。U y=biL x=yi=1,2,m 首先对系数矩阵作三角分解首先对系数矩阵作三角分解 ALU，再求解方程组化为：再求解方程组化为：现在学习的是第83页，共90页2023/2/24第五章 线性方程组的直接解法842.可以用以求可逆矩阵

47、可以用以求可逆矩阵 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，便可求得逆矩阵便可求得逆矩阵现在学习的是第84页，共90页2023/2/24第五章 线性方程组的直接解法853.可以用以求矩阵可以用以求矩阵 A 的行列式的行列式如果对矩阵如果对矩阵 A 作了三角分解作了三角分解 A=LU：则可以求得行列式的值为则可以求得行列式的值为现在

48、学习的是第85页，共90页2023/2/24第五章 线性方程组的直接解法86第五章第五章 总总 结结 1.解线性方程组解线性方程组Gauss消去法的计算程序如何实现？可以消去法的计算程序如何实现？可以进行进行Gauss消去法的条件是什么？消去法的条件是什么？2.解线性方程组列主元解线性方程组列主元Gauss消去法的计算程序如何实现？可以消去法的计算程序如何实现？可以进行列主元进行列主元Gauss消去法的条件是什么？消去法的条件是什么？3.解线性方程组的解线性方程组的Doolittle三角分解法如何进行三角分解法如何进行?可以进分解的条可以进分解的条件是什么？件是什么？4.解对称正定矩阵方程组的

49、平方根解对称正定矩阵方程组的平方根(Cholesky)解法如何进行解法如何进行?5.如何实现解三对角矩阵方程组的追赶法的计算程序如何实现解三对角矩阵方程组的追赶法的计算程序?如何用该如何用该算法进行三次样条函数的构造？算法进行三次样条函数的构造？现在学习的是第86页，共90页2023/2/24第五章 线性方程组的直接解法87第5章 习题习题5-1 利用利用Gauss消去法解下列方程组消去法解下列方程组Axb，其中，其中（1）（2）现在学习的是第87页，共90页2023/2/24第五章 线性方程组的直接解法885-2 利用列主元利用列主元Gauss消去法解下列方程组消去法解下列方程组Axb，其中

50、其中 5-3 对下列矩阵对下列矩阵A进行进行LU分解，并求解方程组分解，并求解方程组Axb，其中其中 现在学习的是第88页，共90页2023/2/24第五章 线性方程组的直接解法895-4 对下列矩阵对下列矩阵A进行进行LU分解分解 5-5 对矩阵对矩阵A进行进行LLT分解，并求解方程组分解，并求解方程组Axb，其，其中中 现在学习的是第89页，共90页2023/2/24第五章 线性方程组的直接解法90 5-6 证明：用列主元证明：用列主元Gauss消去法求解方程组消去法求解方程组Axb相当于用相当于用Gauss消去法求解方程组消去法求解方程组PAxPb，其中，其中P是是一个行排列矩阵，它是一