《数值分析——线性方程组直接解法.ppt》由会员分享，可在线阅读，更多相关《数值分析——线性方程组直接解法.ppt（89页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章 线性方程组的直接解法线性方程组的直接解法1 Gauss1 Gauss消去法消去法 1.1 1.1 顺序顺序GaussGauss消去法消去法 1.2 1.2 列主元列主元GaussGauss消去法消去法 2 2 直接三角分解方法直接三角分解方法 2.1 Gauss2.1 Gauss消去法的矩阵运算消去法的矩阵运算 2.2 Doolittle2.2 Doolittle分解法分解法 2.3 2.3 平方根法平方根法 2.4 2.4 追赶法追赶法 在在科科学学计计算算中中，经经常常需需要要求求解解含含有有n n个个未未知知量量 的的n n个方程构成的线性方程组个方程构成的线性方程组方程组
2、还可以用矩阵形式表示为方程组还可以用矩阵形式表示为:Ax=b (7.1)(7.1)12/12/20222第五章 线性方程组的直接解法 根据根据 GramerGramer（克莱姆）法则，求解方程组（克莱姆）法则，求解方程组（7.17.1）时，）时，要计算大量的行列式，所需乘法次数大约为要计算大量的行列式，所需乘法次数大约为 当当 n n 较大时较大时,这个计算量是惊人的。例这个计算量是惊人的。例 如，当如，当 n=20 时，约需乘法次数为时，约需乘法次数为 N=9.71020 若系数矩阵若系数矩阵A A非奇异，即非奇异，即 det(A)0,则方程组有则方程组有惟一解惟一解 x=(x1,x2,xn
3、)T.如果用每秒一亿次的计算机来计算，需要三十万年时如果用每秒一亿次的计算机来计算，需要三十万年时间。可见间。可见GramerGramer法则不是一种实用的方法。法则不是一种实用的方法。因此，必须构造出适合于计算机使用的线性方程组的求因此，必须构造出适合于计算机使用的线性方程组的求解方法。解方法。N=(n2-1)n!12/12/20223第五章 线性方程组的直接解法 直直接接方方法法的的特特点点是是，如如果果不不考考虑虑计计算算过过程程中中的的舍舍入入误误差差，运运用用此此类类方方法法经经过过有有限限次次算算术术运运算算就就能能求求出出线性方程组的精确解。线性方程组的精确解。求求解解线线性性方
4、方程程组组的的数数值值方方法法可可分分为为两两大大类类：直直接接方方法法和和迭迭代代方方法法。本本章章讨讨论论直直接接方方法法，迭迭代代方方法法将将在在下一章中讨论。下一章中讨论。需要指出，由于实际计算中舍入误差的存在，用需要指出，由于实际计算中舍入误差的存在，用直接方法一般也只能求得方程组的近似值。本章我们直接方法一般也只能求得方程组的近似值。本章我们将给出直接解法的若干算法。将给出直接解法的若干算法。12/12/20224第五章 线性方程组的直接解法1 Gauss消去消去法法 GaussGauss（高斯）消去法是一种规则化的加减消元法高斯）消去法是一种规则化的加减消元法 基基 本本 思思
5、想想 通通过过逐逐次次消消元元计计算算把把需需求求解解的的线线性性方方程程组组转转化化成成上上三三角角形形方方程程组组，也也就就是是把把线线性性方方程程组组的的系系数数矩矩阵阵转转化化为为上上三三角角矩矩阵阵，从从而而使使一一般般线线性性方方程程组组的的求求解解转转化化为等价（同解）的上三角形方程组的求解。为等价（同解）的上三角形方程组的求解。GaussGauss消去法由消元和回代两个过程组成，先讨论消去法由消元和回代两个过程组成，先讨论一个具体的线性方程组的一个具体的线性方程组的求解。求解。12/12/20225第五章 线性方程组的直接解法一、顺序一、顺序Gauss消消去法去法例例7.1.用
6、用Gauss消去法解方程组消去法解方程组用增广矩阵进行进算用增广矩阵进行进算12/12/20226第五章 线性方程组的直接解法这样，对于方程组这样，对于方程组(7.1)我们用增广矩阵表示，并给出我们用增广矩阵表示，并给出gauss消去法的具体算法消去法的具体算法或者或者 Ax=b 12/12/20227第五章 线性方程组的直接解法顺序顺序Gauss消去法的消元过程可表述如下：消去法的消元过程可表述如下：第一步，设第一步，设 a11(1)0 ，将第一列将第一列a11(1)以下各元素消成零以下各元素消成零乘以矩阵乘以矩阵A（1），b（1）的第的第一行再加到第一行再加到第i 行，得到矩阵行，得到矩阵
7、 (i2，3，n)即依次用即依次用12/12/20228第五章 线性方程组的直接解法其中其中 第二步第二步，设设 a22(2)0 ，将第二列将第二列a22(2)以下各元素消成零，以下各元素消成零，（i3，4，n）即依次用即依次用乘以矩阵乘以矩阵A（2），b（2）的第二行再加到第的第二行再加到第i行，得到矩阵行，得到矩阵12/12/20229第五章 线性方程组的直接解法其中其中 如此继续消元下去第如此继续消元下去第n1步结束后，得到矩阵步结束后，得到矩阵12/12/202210第五章 线性方程组的直接解法增广矩阵增广矩阵A（n），b（n）对应如下上三角形方程组对应如下上三角形方程组 这是与原线性
8、方程组（这是与原线性方程组（7.1）等价的方程组）等价的方程组.12/12/202211第五章 线性方程组的直接解法对于等价方程组对于等价方程组进行回代求解，可以得到：进行回代求解，可以得到：12/12/202212第五章 线性方程组的直接解法首先写出增广矩阵首先写出增广矩阵于是，采用于是，采用Gauss消去法求解方程组消去法求解方程组(7.1)(7.1)12/12/202213第五章 线性方程组的直接解法然后进行消元，采用公式然后进行消元，采用公式最后进行回代得到方程组的解最后进行回代得到方程组的解得到相似增广矩阵得到相似增广矩阵（ik+1，k+2，n）12/12/202214第五章 线性方
9、程组的直接解法在编程计算时，最后的增广矩阵存放的元素是：在编程计算时，最后的增广矩阵存放的元素是：下面给出下面给出Gauss消去法的计算流程：消去法的计算流程：12/12/202215第五章 线性方程组的直接解法消元过程：消元过程：jk1，n 回代过程：回代过程：对于对于in1，n2，1，计算计算k1，2，n1，ik1，k2，n对于对于执行计算执行计算置置12/12/202216第五章 线性方程组的直接解法算法算法 Gauss(A,a,b,n,x)1.消元消元 For k=1,2,n-1 1.1 if akk=0,stop;1.2 For i=k+1,k+2,n 1.2.1 l ik=aik/
10、akk=aik 1.2.2 For j=k+1，k+2,n ai j-aik ak j=aij 1.2.3 bi-aik bk=bi 2.回代回代2.1 bn/an=xn;2.2 For i=n-1,n-2,2,1 2.2.1 bk=S 2.2.2 For j=k+1，k+2,n S akj xj=S 2.2.3 S/akk=xk a1 1 a1 2 a13 a1 n b1a2 1 a2 2 a23 a2 n b2a3 1 a3 2 a33 a3 n b3an 1 an 2 an3 an n bnl21 l31 l41.l n1 a22 a23 .a2n b2 l32 l42.l n2.a33
11、 .a 3n b3l43.l n3 a1 1 a1 2 a13 .a1 n b1a 4n b4.ann bn 12/12/202217第五章 线性方程组的直接解法用用Gauss消去法解方程组，应注意：消去法解方程组，应注意：1.适用条件：适用条件：原方程组系数矩阵的各阶顺序主子原方程组系数矩阵的各阶顺序主子 式不等于零。式不等于零。2.运算量小：运算量小：共有乘除法次数为共有乘除法次数为而而Gramer 法则的乘除法次数为法则的乘除法次数为:(n2-1)n！当当 n=20 时时12/12/202218第五章 线性方程组的直接解法二二 列主元列主元Gauss消消去法去法 顺序顺序Gauss消去法
12、计算过程中的消去法计算过程中的 akk(k)称为主元素，在称为主元素，在第第k步消元时要用它作除数步消元时要用它作除数,则可能会出现以下几种情况则可能会出现以下几种情况若出现若出现 akk(k)0，消元过程就不能进行下去。消元过程就不能进行下去。akk(k)0，消去过程能够进行，但若消去过程能够进行，但若|akk(k)|过小，也会过小，也会造成舍入误差积累很大导致计算解的精度下降。造成舍入误差积累很大导致计算解的精度下降。例例7-2 在四位十进制的限制下，试用顺序在四位十进制的限制下，试用顺序Gauss消去法消去法求解如下方程组求解如下方程组12/12/202219第五章 线性方程组的直接解法
13、此方程组具有四位有效数字的精确解为此方程组具有四位有效数字的精确解为x117.46，x245.76，x35.546 解解 用顺序用顺序Gauss消去法求解，消元过程如下消去法求解，消元过程如下12/12/202220第五章 线性方程组的直接解法经回代求解得经回代求解得 x35.546，x2100.0，x1104.0和此方程组的精确解相比和此方程组的精确解相比x35.546，x245.76，x117.46有较大的误差。有较大的误差。对对于于此此例例，由由于于顺顺序序Gauss消消去去法法中中的的主主元元素素绝绝对对值值非非常常小小，使使消消元元乘乘数数绝绝对对值值非非常常大大，计计算算过过程程中
14、中出出现现大大数数吃吃掉掉小小数数现现象象，产产生生较较大大的的舍舍入入误误差差，最最终终导导致致计计算算解解 x1104.0 和和 x2100.0 已完全失真。已完全失真。为为避避免免这这种种现现象象发发生生，可可以以对对原原方方程程组组作作等等价价变变换换，再再利用顺序利用顺序Gauss消去法求解消去法求解。12/12/202221第五章 线性方程组的直接解法写出原方程组的增广矩阵：写出原方程组的增广矩阵：针对第一列找出绝对值最大的元素，进行等价变换：针对第一列找出绝对值最大的元素，进行等价变换：12/12/202222第五章 线性方程组的直接解法求得方程的解为：求得方程的解为：x35.5
15、46，x245.76，x117.46精确解为：精确解为：x35.546，x245.76，x117.46 由此可见，第二种由此可见，第二种Gauss消去法的精度明显高于顺序消去法的精度明显高于顺序Gauss消消去法，我们称它为列主元去法，我们称它为列主元Gauss消去法。消去法。列主元列主元Gauss消去法与顺序消去法与顺序Gauss消去法的不同之处在于：消去法的不同之处在于：后者是按自然顺序取主元素进行消元后者是按自然顺序取主元素进行消元 前者在每步消元之前先选取主元素然后再进行消元前者在每步消元之前先选取主元素然后再进行消元 12/12/202223第五章 线性方程组的直接解法下面将列主元下
16、面将列主元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个个元元素素中中选选取取绝绝对对值
17、值最最大大的的一个作为主元素，并把此主元素所在的行与第二行交换，即一个作为主元素，并把此主元素所在的行与第二行交换，即12/12/202224第五章 线性方程组的直接解法 3.再再进进行行第第二二步步消消元元得得到到增增广广矩矩阵阵A（3），b（3）。按按此此方方法法继继续续进进行行下下去去，经经过过n1步步选选主主元元和和消消元元运运算算，得得到到增增广矩阵广矩阵A（n），b（n），它对应的方程组它对应的方程组A（n）xb（n）是一个与原方程组等价的上三角形方程组，可进行回代求是一个与原方程组等价的上三角形方程组，可进行回代求解。解。容容易易证证明明，只只要要det（A）0，列列主主元元Ga
18、uss消消去去法法就就可可以以顺顺利利完完成成，即即不不会会出出现现主主元元素素为为零零或或者者绝绝对对值值太太小小的的情情形出现。形出现。下面给出列主元下面给出列主元Gauss消去法的计算流程：消去法的计算流程：12/12/202225第五章 线性方程组的直接解法列主元列主元GaussGauss消去算法消去算法 用列主元用列主元Gauss消去法求解线性方程组消去法求解线性方程组Axb 输入输入 A（aij），），b（b1，bn）T，维数维数n n输出输出 方程组解方程组解x x1 1，x xn n，或方程组无解信息或方程组无解信息1 1：对于对于k k1 1，2 2，n n1 1，循环执行步
19、循环执行步2 2到步到步5 52 2：按列选主元素按列选主元素 a aikik ，即确定下标即确定下标 I I 使使3 3：若若a aikik0 0，输出输出 no unique solution，停机停机4 4：若若i ik k，换行换行12/12/202226第五章 线性方程组的直接解法5 5：消元计算，对于：消元计算，对于i ik k1 1，n n，计算计算 6 6：若：若 ann 0 输出输出 no unigue solution，停机停机7 7：回代求解：回代求解 8 8：输出：输出 x x1 1，x x2 2，x xn n12/12/202227第五章 线性方程组的直接解法 由于这
20、两种方法的精度差不多，且全主元由于这两种方法的精度差不多，且全主元Gauss消去法消去法程序设计复杂占用机器时间较多，实际应用中一般采用列程序设计复杂占用机器时间较多，实际应用中一般采用列主元主元Gauss消去法，它既简单又能保证计算精度。消去法，它既简单又能保证计算精度。有时候在消元过程中可以在系数矩阵所有元素中选择绝有时候在消元过程中可以在系数矩阵所有元素中选择绝对值最大的元素作为主元素，这样的对值最大的元素作为主元素，这样的Gauss消去法叫做全主消去法叫做全主元元Gauss消去法。消去法。12/12/202228第五章 线性方程组的直接解法2 2 直接三角分解方法直接三角分解方法一一、
21、Gauss消去法的矩阵运消去法的矩阵运算算 从从1中中讨讨论论可可知知，顺顺序序Gauss消消去去法法的的消消元元过过程程是是将将增增广广矩矩阵阵A，bA（1），b（1）逐逐步步约约化化为为矩矩阵阵A（n），b（n）。现在说明，在消元过程中，系数矩阵现在说明，在消元过程中，系数矩阵AA（1）是如是如何经矩阵运算约化为上三角矩阵何经矩阵运算约化为上三角矩阵A（n）。即即 用矩阵运算的观点来看，消元的每一步计算等价用矩阵运算的观点来看，消元的每一步计算等价于用一个单位下三角矩阵左乘前一步约化得到的矩阵。于用一个单位下三角矩阵左乘前一步约化得到的矩阵。12/12/202229第五章 线性方程组的直接
22、解法若若 ，令，令 ，i2，3，n，得到下三角矩阵得到下三角矩阵施行第一步消元，我们得到施行第一步消元，我们得到12/12/202230第五章 线性方程组的直接解法若若 ，令，令 ，i2，3，n，则有则有 施行第二步消元，我们得到施行第二步消元，我们得到12/12/202231第五章 线性方程组的直接解法如此下去，施行第如此下去，施行第n1步消元，得到步消元，得到 12/12/202232第五章 线性方程组的直接解法 由此可见，在顺序由此可见，在顺序Gauss消去法的过程中，系数矩阵消去法的过程中，系数矩阵AA（1）经过一系列单位下三角矩阵的左乘运算约化为上三角矩经过一系列单位下三角矩阵的左乘
23、运算约化为上三角矩阵阵A（n），即即 这时这时由由得得令令12/12/202233第五章 线性方程组的直接解法容易验证容易验证 则则从从顺顺序序Gauss消消去去法法的的矩矩阵阵运运算算表表示示式式可可知知，系系数数矩矩阵阵A可可分分解解为为一一个个单单位位下下三三角角矩矩阵阵L和和一一个个上上三三角角矩矩阵阵U的的乘乘积积，即即其中其中12/12/202234第五章 线性方程组的直接解法第一个方程组的系数矩阵为下三角矩阵，第二个方程组的系第一个方程组的系数矩阵为下三角矩阵，第二个方程组的系数矩阵为上三角矩阵，两个方程组都非常容易求解，具体求数矩阵为上三角矩阵，两个方程组都非常容易求解，具体求
24、解结果如下：解结果如下：我们将我们将A=LU 称为矩阵称为矩阵A的三角分解的三角分解,这时线性方程组为：这时线性方程组为：令令则有则有12/12/202235第五章 线性方程组的直接解法对于对于由由解得解得12/12/202236第五章 线性方程组的直接解法对于对于由由求得求得12/12/202237第五章 线性方程组的直接解法可以看出对于方程组可以看出对于方程组：只要对系数矩阵作了三角分解只要对系数矩阵作了三角分解：由这个简单的计算过程可知，系数矩阵的三角分解很关键，由这个简单的计算过程可知，系数矩阵的三角分解很关键，如何进行三角分解更容易？下面介绍几种方法。如何进行三角分解更容易？下面介绍
25、几种方法。通过如下两组公式很容易求解通过如下两组公式很容易求解：12/12/202238第五章 线性方程组的直接解法二、二、Doolittle分解法分解法 前已述及，若在顺序前已述及，若在顺序Gauss消去法的过程中，每步消去法的过程中，每步消元的主元素消元的主元素 akk(k)0，则矩阵则矩阵A A可分解为可分解为ALU，L L为单位下三角矩阵，为单位下三角矩阵，U为上三角矩阵，此分解称为为上三角矩阵，此分解称为A A的的 Doolittle（杜利特尔）分解。可以证明杜利特尔）分解。可以证明akk(k)0的充要的充要条件是条件是A A的各阶顺序主子式不为零，于是有如下定理。的各阶顺序主子式不
26、为零，于是有如下定理。定定理理7.1 7.1 设设n阶阶方方阵阵A的的各各阶阶顺顺序序主主子子式式不不为为零零，则则存存在在惟惟一一单单位位下下三三角角矩矩阵阵L和和上上三三角角矩矩阵阵U使使ALU。下面介绍矩阵三角分解的下面介绍矩阵三角分解的Doolittle分解方法。分解方法。12/12/202239第五章 线性方程组的直接解法根据根据 A=LU 有等式成立：有等式成立：比较等式两端对应元素，有比较等式两端对应元素，有12/12/202240第五章 线性方程组的直接解法nnii12/12/202241第五章 线性方程组的直接解法可以解得可以解得：当当 i=1 时时 当当 j=1 时时 当当
27、 i 1 时时 当当 j 1 时时 12/12/202242第五章 线性方程组的直接解法于是，对于矩阵的三角分解：于是，对于矩阵的三角分解：可按照以下公式进行：可按照以下公式进行：对于对于 i=2,3,，n,计算计算（7.2）（7.3）（7.4）用计算公式用计算公式(7.3)、(7.4)对矩阵对矩阵A A作的分解作的分解(7.2),称作称作Doolittle分解。分解。12/12/202243第五章 线性方程组的直接解法下面，我们对具体矩阵进行下面，我们对具体矩阵进行Doolittle 三角分解。三角分解。为了表示和存储方便，可以将分解后的两个矩阵用一为了表示和存储方便，可以将分解后的两个矩阵
28、用一个矩阵表示个矩阵表示12/12/202244第五章 线性方程组的直接解法例例7-3 7-3 利用利用Doolittle三角分解法分解矩阵三角分解法分解矩阵解：分解时用到如下公式解：分解时用到如下公式123411126123762462412/12/202245第五章 线性方程组的直接解法1234111261237624624可以写成：可以写成：这时，矩阵的三角分解这时，矩阵的三角分解12/12/202246第五章 线性方程组的直接解法如果我们要求解方程组如果我们要求解方程组则由则由得到得到12/12/202247第五章 线性方程组的直接解法由由解得解得再由再由求得方程组的解：求得方程组的解
29、：12/12/202248第五章 线性方程组的直接解法（7.5）如下的计算公式如下的计算公式(7.3)、(7.4)与与(7.5)就是求解方程组就是求解方程组Axb 的的 Doolittle 三角分解方法三角分解方法,包括分解和回代两步包括分解和回代两步。（7.3）（7.4）关于具体求解过程可以按下面例子的方法进行。关于具体求解过程可以按下面例子的方法进行。12/12/202249第五章 线性方程组的直接解法例例7-4 利用利用Doolittle三角分解方法解线三角分解方法解线性方程性方程解解:进行三角分解进行三角分解ALU，按照公式按照公式(7.5)可以对增广可以对增广 矩阵矩阵A,b作三角分
30、解作三角分解:1 2 3 -2-3 2 2-3-1331712/12/202250第五章 线性方程组的直接解法得到得到1 2 3 -2-3 2 2-3-13317这时，相应的方程组为：这时，相应的方程组为：x135x28，12/12/202251第五章 线性方程组的直接解法例例7-5 利用利用Doolittle三角分解方法解线性三角分解方法解线性方程组方程组解：对增广矩阵进行三角分解解：对增广矩阵进行三角分解1 2 3 -4 -2-3 2 42-3133322-4-117-16等价方程组通过分解式容易写出为：等价方程组通过分解式容易写出为：12/12/202252第五章 线性方程组的直接解法1
31、 2 3 -4 -2-3 2 42-3133322-4-117-16解得解得12/12/202253第五章 线性方程组的直接解法三、平方根法三、平方根法 在实际应用中，常见一类非常重要的线性方程组在实际应用中，常见一类非常重要的线性方程组Axb，其中其中A A为对称正定矩阵，即为对称正定矩阵，即A A是对称的且对任何非零向量是对称的且对任何非零向量 x x 都有都有xTAx0 0。本节将对这类方程组导出更有效地三角分本节将对这类方程组导出更有效地三角分解求解方法，称之为解求解方法，称之为平方根法平方根法。设设A A为为对对称称正正定定矩矩阵阵，那那么么A A的的所所有有顺顺序序主主子子式式均均
32、大大于于零零，根据定理根据定理7.17.1，存在惟一三角分解，存在惟一三角分解A ALULU，即即12/12/202254第五章 线性方程组的直接解法 记记 Ak（1kn）为）为A的的 k 阶顺序主子阵，则阶顺序主子阵，则det（Ak）为为A的的k阶顺序主子式。由上式，利用矩阵分块运算规则，阶顺序主子式。由上式，利用矩阵分块运算规则，容易验证容易验证 det（Ak）u11 u22 ukk那么由那么由 det（Ak）0，可知可知 ukk0，k1，2，n 这时，将上面的矩阵表示为：这时，将上面的矩阵表示为：12/12/202255第五章 线性方程组的直接解法即：即：A=LDM ，其中其中 DM=U
33、，M=D-1U。12/12/202256第五章 线性方程组的直接解法当当AAT为对称矩阵时，根据为对称矩阵时，根据 ALDM,得到得到ATMT D LT再根据矩阵三角分解的唯一性再根据矩阵三角分解的唯一性,可知可知 MLT。于是于是ALDLT则有则有令令12/12/202257第五章 线性方程组的直接解法 如果对称正定矩阵如果对称正定矩阵A具有如下分解具有如下分解 AGGT，其中其中G为为下三角矩阵，则称其为下三角矩阵，则称其为对称正定矩阵的对称正定矩阵的 Cholesky（乔（乔列斯列斯基）分解。基）分解。为表示方便，可以记为表示方便，可以记 给定对称正定方程组给定对称正定方程组 Axb，对
34、对 A 进行进行 Cholesky分解分解ALLT，则原方程组等价于则原方程组等价于 LLTxb12/12/202258第五章 线性方程组的直接解法Lyb LTx y解此方程组即可得到原方程组的解解此方程组即可得到原方程组的解x ，这就是求解方程组这就是求解方程组的平方根法。的平方根法。下下面面，我我们们通通过过比比较较矩矩阵阵的的对对应应元元素素给给出出对对称称正正定定矩矩阵阵的的平方根分解法。已知平方根分解法。已知即：即：LLTxb，等价于等价于12/12/202259第五章 线性方程组的直接解法比较对应元素：比较对应元素：12/12/202260第五章 线性方程组的直接解法当当 i=j
35、时时当当 j i 时时解得解得12/12/202261第五章 线性方程组的直接解法于是，根据计算公式于是，根据计算公式可以对对称正定矩阵进行平方根分解可以对对称正定矩阵进行平方根分解l11 l21 l22 l31 l32 l33 ln1 ln2 ln3 lnn 12/12/202262第五章 线性方程组的直接解法 关关于于方方程程组组 Ax=b,如如果果对对系系数数矩矩阵阵进进行行了了平平方方根根分分解解 ALLT，则将方程组化为：则将方程组化为：Lyb,LTxy解得解得12/12/202263第五章 线性方程组的直接解法 于是，关于系数矩阵是对称正定矩阵的线性方程组于是，关于系数矩阵是对称正
36、定矩阵的线性方程组Ax=b的求解，分两步进行：的求解，分两步进行：第一步：系数矩阵的平方根分解第一步：系数矩阵的平方根分解第二步：解等价方程组第二步：解等价方程组12/12/202264第五章 线性方程组的直接解法例例7-6 用平方根法求解对称正定方程组用平方根法求解对称正定方程组 解解:首先进行首先进行A 的的Cholesky 分解分解 ALLT2-0.50.521.512-0.50.521.5112/12/202265第五章 线性方程组的直接解法得得 y12，y23.5，y31 得得 x11，x21，x31 求解求解Lyb:再求解再求解 LTxy:12/12/202266第五章 线性方程组
37、的直接解法关于对称正定方程组关于对称正定方程组 也可以用一般的三角分解法求解，这时由也可以用一般的三角分解法求解，这时由 4 -1 1 4-0.250.254370.7511求得求得 x11，x21，x31 12/12/202267第五章 线性方程组的直接解法四、追赶法四、追赶法 追追赶赶法法是是专专门门用用于于求求解解三三对对角角方方程程组组的的。这这类类方方程程组组经经常常出出现现于于用用差差分分方方法法或或有有限限元元方方法法求求解解二二阶阶常常微微分分方方程程边边值值问问题题、热热传传导导问问题题及及三三次次样样条条函函数数插插值值等等问问题题，三三对对角角方方程程组组AxAxb b的
38、的系系数数矩矩阵阵具具有如下形式：有如下形式：设设A A为一个三对角矩阵，那么它的顺序主子式均不为一个三对角矩阵，那么它的顺序主子式均不为零的一个充分条件是：为零的一个充分条件是：12/12/202268第五章 线性方程组的直接解法在此条件下，可对在此条件下，可对A进行三角分解，设进行三角分解，设比较矩阵的对应元素，根据矩阵乘法规则，可得到比较矩阵的对应元素，根据矩阵乘法规则，可得到 12/12/202269第五章 线性方程组的直接解法i-1列列i 行行第第3列列12/12/202270第五章 线性方程组的直接解法i-1列列i-1行行第第3列列12/12/202271第五章 线性方程组的直接解
39、法i-1列列第第3列列i-1行行i-1列列12/12/202272第五章 线性方程组的直接解法于是，由以上结果：于是，由以上结果：分别得到：分别得到：也就是说也就是说,用这一组公式可以对三对角矩阵进行三角用这一组公式可以对三对角矩阵进行三角分解：分解：12/12/202273第五章 线性方程组的直接解法对对于于三三对对角角方方程程组组Axb，设设A的的三三角角分分解解为为ALU，则则原原方方程组等价于程组等价于Lyb，Uxy 12/12/202274第五章 线性方程组的直接解法由由Lyb，即即解得解得解得解得由由Uxy，即即12/12/202275第五章 线性方程组的直接解法于是，对于三对角矩
40、阵方程组于是，对于三对角矩阵方程组 Ax=b，如下的两组公如下的两组公式便构成了构成了解三对角方程组的追赶法：式便构成了构成了解三对角方程组的追赶法：12/12/202276第五章 线性方程组的直接解法例例7-7 用追赶法求解三对角方程组用追赶法求解三对角方程组 解解:首先进行系数矩阵的三角分解首先进行系数矩阵的三角分解 12/12/202277第五章 线性方程组的直接解法12/12/202278第五章 线性方程组的直接解法求解方程组求解方程组Lyy，即即 得得 到到 y11/2，y21/3，y31/4，y41 再求解方程组再求解方程组 Uxy，即即 得得 到到 x11，x21，x31，x41
41、 12/12/202279第五章 线性方程组的直接解法 当三对角矩阵当三对角矩阵A满足对角占优条件时，追赶法是数值稳满足对角占优条件时，追赶法是数值稳定的。定的。追赶法具有计算程序简单，存贮少，计算量小的优点。追赶法具有计算程序简单，存贮少，计算量小的优点。解解三三对对角角方方程程组组Axb的的追追赶赶法法，用用四四个个一一维维数数组组存存放放方程组数据方程组数据 ai，bi，ci，di ,di常数项。常数项。输入输入 方程组数据方程组数据 ai，bi，ci，di，n输出输出 计算解计算解x（x1，x2，xn）T根据以下算法编写程序根据以下算法编写程序12/12/202280第五章 线性方程组
42、的直接解法1 2 对于对于i1，2，n1，计算计算3 4 5 输出输出 x1，x2，xn 12/12/202281第五章 线性方程组的直接解法五、三角分解方法的五、三角分解方法的优点优点 此时，在完成并存贮矩阵此时，在完成并存贮矩阵L和和U后，右端项第改变一次仅后，右端项第改变一次仅需增加需增加 n2 次运算。次运算。1.当需要求解具有同系数矩阵的一系列方程组当需要求解具有同系数矩阵的一系列方程组 Axbi，i1，2，m 时，可大节省计算量时，可大节省计算量。U y=biL x=yi=1,2,m 首先对系数矩阵作三角分解首先对系数矩阵作三角分解 ALU，再再求解方程组化求解方程组化为：为：12
43、/12/202282第五章 线性方程组的直接解法2.可以用以求可逆矩阵可以用以求可逆矩阵 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，便可求得逆矩阵便可求得逆矩阵12/12/202283第五章 线性方程组的直接解法3.可以用以求矩阵可以用以求矩阵 A 的行列式的行列式如果对矩阵如果对矩阵 A 作了三角分解作了三角分解 A=LU：则则可
44、以求得行列式的值为可以求得行列式的值为12/12/202284第五章 线性方程组的直接解法第七章第七章 总总 结结 1.解线性方程组解线性方程组Gauss消去法的计算程序如何实现？可消去法的计算程序如何实现？可以进行以进行Gauss消去法的条件是什么？消去法的条件是什么？2.解线性方程组列主元解线性方程组列主元Gauss消去法的计算程序如何实消去法的计算程序如何实现？可以进行列主元现？可以进行列主元Gauss消去法的条件是什么？消去法的条件是什么？3.解线性方程组的解线性方程组的Doolittle三角分解法如何进行三角分解法如何进行?可以可以进分解的条件是什么？进分解的条件是什么？4.解对称正
45、定矩阵方程组的平方根解对称正定矩阵方程组的平方根(Cholesky)解法如解法如何进行何进行?5.如何实现解三对角矩阵方程组的追赶法的计算程序如何实现解三对角矩阵方程组的追赶法的计算程序?如何用该算法进行三次样条函数的构造？如何用该算法进行三次样条函数的构造？12/12/202285第五章 线性方程组的直接解法第7章 习题习题7-1 利用利用Gauss消去法解下列方程组消去法解下列方程组Axb，其中其中（1）（2）12/12/202286第五章 线性方程组的直接解法7-2 利用列主元利用列主元Gauss消去法解下列方程组消去法解下列方程组Axb，其中其中 7-3 对下列矩阵对下列矩阵A进行进行
46、LU分解，并求解方程组分解，并求解方程组Axb，其中其中 12/12/202287第五章 线性方程组的直接解法7-4 对下列矩阵对下列矩阵A进行进行LU分解分解 7-5 对矩阵对矩阵A进行进行LLT分解，并求解方程组分解，并求解方程组Axb，其中其中 12/12/202288第五章 线性方程组的直接解法 7-6 证明：用列主元证明：用列主元Gauss消去法求解方程组消去法求解方程组Axb相当于用相当于用Gauss消去法求解方程组消去法求解方程组PAxPb，其中其中P是一个行排列矩阵，它是一些初等行变换矩阵的乘是一个行排列矩阵，它是一些初等行变换矩阵的乘积矩阵。积矩阵。7-7 用追赶法求解方程组用追赶法求解方程组 12/12/202289第五章 线性方程组的直接解法