数值分析——线性方程组直接解法

1、2022-4-23第五章 线性方程组的直接解法1第五章第五章 线性方程组的直接解法线性方程组的直接解法1 Gauss1 Gauss消去法消去法 1.1 1.1 顺序顺序GaussGauss消去法消去法 1.2 1.2 列主元列主元GaussGauss消去法消去法 2 2 直接三角分解方法直接三角分解方法 2.1 Gauss 2.1 Gauss消去法的矩阵运算消去法的矩阵运算 2.2 Doolittle2.2 Doolittle分解法分解法 2.3 2.3 平方根法平方根法 2.4 2.4 追赶法追赶法 2022-4-23第五章 线性方程组的直接解法2 在科学计算中，经常需要求解含有在科学计算中

2、，经常需要求解含有n n个未知量个未知量 的的n n个方程构成的线性方程组个方程构成的线性方程组方程组还可以用矩阵形式表示为方程组还可以用矩阵形式表示为: : Ax=b nnnnnnnnbbbbxxxxaaaaaaaaaA2121212222111211, nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111(7.1)(7.1)2022-4-23第五章 线性方程组的直接解法3 根据根据 GramerGramer（克莱姆）法则，求解方程组（克莱姆）法则，求解方程组（7.17.1）时，）时，要计算大量的行列式，所需乘法次数大约为要计算大量的行列式，

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

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

5、用直接方法一般也只能求得方程组的近似值。本章我直接方法一般也只能求得方程组的近似值。本章我们将给出直接解法的若干算法。们将给出直接解法的若干算法。2022-4-23第五章 线性方程组的直接解法51 Gauss1 Gauss消去消去法法 GaussGauss（高斯）消去法是一种规则化的加减消元法（高斯）消去法是一种规则化的加减消元法 基基 本本 思思 想想 通过逐次消元计算把需求解的线性方程组转化成通过逐次消元计算把需求解的线性方程组转化成上三角形方程组，也就是把线性方程组的系数矩阵转上三角形方程组，也就是把线性方程组的系数矩阵转化为上三角矩阵，从而使一般线性方程组的求解转化化为上三角矩阵，从而

6、使一般线性方程组的求解转化为等价（同解）的上三角形方程组的求解。为等价（同解）的上三角形方程组的求解。 GaussGauss消去法由消元和回代两个过程组成，先讨论消去法由消元和回代两个过程组成，先讨论一个具体的线性方程组的一个具体的线性方程组的求解。求解。 2022-4-23第五章 线性方程组的直接解法6一、顺序一、顺序GaussGauss消消去法去法 15233322242321321321xxxxxxxxx 48822422423232321xxxxxxx 8122242242332321xxxxxx323 x612 x321 x 188022402242 152333212242,bA

7、81200224022423/ 2, 6/ 1, 32123 xxx例例7.1. 用用Gauss消去法解方程组消去法解方程组用增广矩阵进行进算用增广矩阵进行进算2022-4-23第五章 线性方程组的直接解法7这样，对于方程组这样，对于方程组 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111(7.1)我们用增广矩阵表示，并给出我们用增广矩阵表示，并给出gauss消去法的具体算法消去法的具体算法 )1()1()1(3)1(2)1(1)1(3)1(3)1(33)1(32)1(31)1(2)1(2)1(23)1(22)1(21)1(1)1(1)1(

8、13)1(12)1(11)1()1(,nnnnnnnnnbaaaabaaaabaaaabaaaabAbA或者或者 Ax=b 2022-4-23第五章 线性方程组的直接解法8 )1()1()1(3)1(2)1(1)1(3)1(3)1(33)1(32)1(31)1(2)1(2)1(23)1(22)1(21)1(1)1(1)1(13)1(12)1(11)1()1(,nnnnnnnnnbaaaabaaaabaaaabaaaabAbA顺序顺序Gauss消去法的消元过程可表述如下：消去法的消元过程可表述如下： 第一步，设第一步，设 a11(1) 0 ，将第一列，将第一列a11(1)以下各元素消成零以下各元

9、素消成零乘以矩阵乘以矩阵A（1），b（1）的第的第一行再加到第一行再加到第i 行，得到矩阵行，得到矩阵 (i2，3，n)1(11)1(11aalii 即依次用即依次用2022-4-23第五章 线性方程组的直接解法9其中其中 niblbbnjialaaiiijiijij,3,2,3,2,)1(11)1()2()1(11)1()2( 第二步第二步，设设 a22(2) 0 ，将第二列，将第二列a22(2)以下各元素消成零，以下各元素消成零，)2(22)2(22aalii （i3，4，n） 即依次用即依次用乘以矩阵乘以矩阵A（2），b（2）的第二行再加到第的第二行再加到第i行，得到矩阵行，得到矩阵 )

10、2()2()2(3)2(2)2(3)2(3)2(33)2(32)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11)2()2(000,nnnnnnnnbaaabaaabaaabaaaabA2022-4-23第五章 线性方程组的直接解法10niblbbnjialaaiiijiijij, 4 , 3, 4 , 3,)2(22)2()3()2(22)2()3( 其中其中 如此继续消元下去第如此继续消元下去第n1步结束后，得到矩阵步结束后，得到矩阵 )3()3()3(3)3(3)3(3)3(33)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(

11、11)2()2(00000,nnnnnnnbaabaabaaabaaaabA2022-4-23第五章 线性方程组的直接解法11增广矩阵增广矩阵A（n），b（n）对应如下上三角形方程组对应如下上三角形方程组 )()()2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnbxabxaxabxaxaxa这是与原线性方程组（这是与原线性方程组（7.1）等价的方程组）等价的方程组. )()()3(3)3(3)3(33)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11)()(000000,nnnnnnnnnnbabaabaaabaaaabA

12、2022-4-23第五章 线性方程组的直接解法12对于等价方程组对于等价方程组 )()()1(1)1(11)1(11)2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnnnnnnnnnnnbxabxaxabxaxabxaxaxa进行回代求解，可以得到：进行回代求解，可以得到：)()(nnnnnnabx ( )( )( )11,1,2,1nkkkkjjkj kkkbaxkna L L ( )( )( )( )1122( )1kkkkkkkkkkkkknnkkkxbaxaxaxaL L2022-4-23第五章 线性方程组的直接解法13首先写出增广矩阵首先写出增广

13、矩阵于是，采用于是，采用Gauss消去法求解方程组消去法求解方程组 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111(7.1)(7.1) )1()1()1(3)1(2)1(1)1(3)1(3)1(33)1(32)1(31)1(2)1(2)1(23)1(22)1(21)1(1)1(1)1(13)1(12)1(11)1()1(,nnnnnnnnnbaaaabaaaabaaaabaaaabAbA2022-4-23第五章 线性方程组的直接解法14nkkiblbbnkkjialaakkikkikikkjikkijkij,2,1,2,1,)()()1(

14、)()()1( 然后进行消元，采用公式然后进行消元，采用公式最后进行回代得到方程组的解最后进行回代得到方程组的解得到相似增广矩阵得到相似增广矩阵)()(kkkkikikaal （ik+1，k+2，n） )()()3(3)3(3)3(33)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11)()(000000,nnnnnnnnnnbabaabaaabaaaabA2022-4-23第五章 线性方程组的直接解法15)()(nnnnnnabx 在编程计算时，最后的增广矩阵存放的元素是：在编程计算时，最后的增广矩阵存放的元素是： )()(321)3(3)3(3)1(3332

15、31)2(2)2(2)2(23)2(2221)1(1)1(1)1(13)1(12)1(11nnnnnnnnnnnballlbaallbaaalbaaaa下面给出下面给出Gauss消去法的计算流程：消去法的计算流程：( )( )( )11,1,2,1nkkkkkjjkj kkkxbaxkna L L2022-4-23第五章 线性方程组的直接解法16消元过程：消元过程： )()(kkkkikikaal ,)()()1(kkjikkijkijalaa jk1，n kkikkikiblbb )()1(回代过程：回代过程： 对于对于in1，n2，1，计算，计算)(1)()(iiinijjiijiiiax

16、abx k1，2，n1，ik1，k2，n对于对于执行计算执行计算)()(/nnnnnnabx 置置2022-4-23第五章 线性方程组的直接解法17算法算法 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 /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

17、,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 . a 3n b3l43 .l n3 a1 1 a1 2 a13 . a1 n b1a 4n b4. . .ann bn 2022-4-23第五章 线性方程组的直接解法18用用Gau

18、ss消去法解方程组，应注意：消去法解方程组，应注意：1. 适用条件：适用条件： 原方程组系数矩阵的各阶顺序主子原方程组系数矩阵的各阶顺序主子 式不等于零。式不等于零。2 . 运算量小：运算量小：共有乘除法次数为共有乘除法次数为 )3(312) 1(231233nnnnnnnn 而而Gramer 法则的乘除法次数为法则的乘除法次数为: (n2 -1) n！当当 n=20 时时202107 .9!)1( nnN3060)3(3123 nnnN2022-4-23第五章 线性方程组的直接解法19二二 列主元列主元GaussGauss消消去法去法 顺序顺序Gauss消去法计算过程中的消去法计算过程中的

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

20、6781. 0167. 001. 0012. 0321321321xxxxxxxxx2022-4-23第五章 线性方程组的直接解法20此方程组具有四位有效数字的精确解为此方程组具有四位有效数字的精确解为x117.46，x245.76，x35.546 解解 用顺序用顺序Gauss消去法求解，消元过程如下消去法求解，消元过程如下 0 .981200. 41200320010.12910. 58334. 0000. 16781. 01670. 00100. 00120. 0 231017981044541467041.44010. 8101000. 006781. 01670. 00100. 001

21、20. 0 5531065171011750041.44010. 8101000. 006781. 01670. 00100. 00120. 02022-4-23第五章 线性方程组的直接解法21经回代求解得经回代求解得 x35.546，x2100.0，x1104.0和此方程组的精确解相比和此方程组的精确解相比x35.546 ，x245.76， x117.46有较大的误差。有较大的误差。 对于此例，由于顺序对于此例，由于顺序Gauss消去法中的主元素绝对值非消去法中的主元素绝对值非常小，使消元乘数绝对值非常大，计算过程中出现大数吃掉常小，使消元乘数绝对值非常大，计算过程中出现大数吃掉小数现象，产

22、生较大的舍入误差，最终导致计算解小数现象，产生较大的舍入误差，最终导致计算解 x1104.0 和和 x2100.0 已完全失真。已完全失真。 为避免这种现象发生，为避免这种现象发生，可以对原方程组作等价变换，再可以对原方程组作等价变换，再利用顺序利用顺序Gauss消去法求解消去法求解。2022-4-23第五章 线性方程组的直接解法22 0 .981200. 41200320010.12910. 58334. 0000. 16781. 01670. 00100. 00120. 0 6781. 01670. 00100. 00120. 010.12910. 58334. 0000. 10 .981

23、200. 412003200写出原方程组的增广矩阵：写出原方程组的增广矩阵：针对第一列找出绝对值最大的元素，进行等价变换：针对第一列找出绝对值最大的元素，进行等价变换： 644. 01670. 0105500. 0079.11909. 54584. 000 .981200. 41200320022022-4-23第五章 线性方程组的直接解法23 5329. 00961. 00079.11909. 54584. 000 .981200. 412003200求得方程的解为：求得方程的解为：x35.546，x245.76，x117.46精确解为：精确解为： x35.546 ，x245.76， x11

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

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

26、把此主元素所在的行与第二行交换，即一个作为主元素，并把此主元素所在的行与第二行交换，即,max)2(22)2(2inikaa )1(1)1()1(1)1(,bbaakjkj)2(2)2()2(2)2(,bbaakjkj2022-4-23第五章 线性方程组的直接解法25 3. 再进行第二步消元得到增广矩阵再进行第二步消元得到增广矩阵A（3），b（3）。按此。按此方法继续进行下去，经过方法继续进行下去，经过n1步选主元和消元运算，得到增步选主元和消元运算，得到增广矩阵广矩阵A（n），b（n），它对应的方程组，它对应的方程组A（n）xb（n）是一个与原方程组等价的上三角形方程组，可进行回代求是一个与

27、原方程组等价的上三角形方程组，可进行回代求解。解。 容易证明，只要容易证明，只要det（A）0，列主元，列主元Gauss消去法就可消去法就可以顺利完成，即不会出现主元素为零或者绝对值太小的情以顺利完成，即不会出现主元素为零或者绝对值太小的情形出现。形出现。 下面给出列主元下面给出列主元Gauss消去法的计算流程：消去法的计算流程：2022-4-23第五章 线性方程组的直接解法26列主元列主元GaussGauss消去算法消去算法 用列主元用列主元Gauss消去法求解线性方程组消去法求解线性方程组Axb 输入输入 A（aij），），b（b1，bn）T，维数，维数n n输出输出 方程组解方程组解x

28、x1 1，x xn n，或方程组无解信息，或方程组无解信息1 1： 对于对于k k1 1，2 2，n n1 1，循环执行步，循环执行步2 2到步到步5 52 2： 按列选主元素按列选主元素 a aik ik ，即确定下标，即确定下标 I I 使使jknjkikaa max3 3： 若若a aikik0 0，输出，输出 no unique solution，停机，停机nkjaaijkj, ikbb4 4： 若若i ik k，换行，换行2022-4-23第五章 线性方程组的直接解法275 5：消元计算，对于：消元计算，对于i ik k1 1，n n，计算，计算 kkikikaal/nkjalaak

29、jikikik, 1, kikiiblbb 6 6：若：若 ann 0 输出输出 no unigue solution，停机，停机7 7：回代求解：回代求解 nnnnabx/1 ,2,1,11 nixabiaxnijjijiii8 8：输出：输出 x x1 1，x x2 2，x xn n2022-4-23第五章 线性方程组的直接解法28 由于这两种方法的精度差不多，且全主元由于这两种方法的精度差不多，且全主元Gauss消去法消去法程序设计复杂占用机器时间较多，实际应用中一般采用列程序设计复杂占用机器时间较多，实际应用中一般采用列主元主元Gauss消去法，它既简单又能保证计算精度。消去法，它既简

30、单又能保证计算精度。 有时候在消元过程中可以在系数矩阵所有元素中选择绝有时候在消元过程中可以在系数矩阵所有元素中选择绝对值最大的元素作为主元素，这样的对值最大的元素作为主元素，这样的Gauss消去法叫做全主消去法叫做全主元元Gauss消去法。消去法。 )1()1()1(3)1(2)1(1)1(3)1(3)1(33)1(32)1(31)1(2)1(2)1(23)1(22)1(21)1(1)1(1)1(13)1(12)1(11)1()1(,nnnnnnnnnbaaaabaaaabaaaabaaaabA2022-4-23第五章 线性方程组的直接解法292 2 直接三角分解方法直接三角分解方法一一 、

31、 GaussGauss消去法的矩阵运消去法的矩阵运算算 从从1中讨论可知，顺序中讨论可知，顺序Gauss消去法的消元过程消去法的消元过程是将增广矩阵是将增广矩阵A，bA（1），b（1）逐步约化为矩阵逐步约化为矩阵A（n），b（n）。 现在说明，在消元过程中，系数矩阵现在说明，在消元过程中，系数矩阵AA（1）是是如何经矩阵运算约化为上三角矩阵如何经矩阵运算约化为上三角矩阵A（n）。即。即 用矩阵运算的观点来看，消元的每一步计算等价用矩阵运算的观点来看，消元的每一步计算等价于用一个单位下三角矩阵左乘前一步约化得到的矩阵。于用一个单位下三角矩阵左乘前一步约化得到的矩阵。 )1()1(2)1(1)1(

32、2)1(22)1(21)1(1)1(12)1(11)1(nnnnnnaaaaaaaaaA )1()1(2)1(22)1(1)1(12)1(11)(000nnnnnaaaaaaA?2022-4-23第五章 线性方程组的直接解法30 )1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11)1(nnnnnnaaaaaaaaaA若若 ，令，令 ， i2，3，n，0)1(11 a)1(11)1(11/ aalii 得到下三角矩阵得到下三角矩阵 1001011131211nlllL施行第一步消元，我们得到施行第一步消元，我们得到2022-4-23第五章 线性方程组的直接解法31 )

33、2()2(2)2(2)2(22)1(1)1(12)1(11)1(1)2(00nnnnnaaaaaaaALA若若 ，令，令 ，i2，3，n，则有，则有 0)2(22 a)2(22)2(22/ aalii 10101012322nllL施行第二步消元，我们得到施行第二步消元，我们得到2022-4-23第五章 线性方程组的直接解法32 )3()3(3)3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)2(2)3(00000nnnnnnaaaaaaaaaaaALA如此下去，施行第如此下去，施行第n1步消元，得到步消元，得到 )2()2(2)2(22)1(1)1(12)

34、1(11)1(1)(nnnnnnnaaaaaaALA2022-4-23第五章 线性方程组的直接解法33 由此可见，在顺序由此可见，在顺序Gauss消去法的过程中，系数矩阵消去法的过程中，系数矩阵AA（1）经过一系列单位下三角矩阵的左乘运算约化为上三角经过一系列单位下三角矩阵的左乘运算约化为上三角矩阵矩阵A（n），即，即 )1(1)( nnnALA这时这时)2(21 nnnALLALLLLnn1221 )(111211nnALLLA 11111nkkkkllL由由 111111nkkkkllL得得)(111211,nnAULLLL 令令2022-4-23第五章 线性方程组的直接解法34容易验证容

35、易验证 1111121323121111211nnnnnllllllLLLL 则从顺序则从顺序Gauss消去法的矩阵运算表示式可知，系数矩阵消去法的矩阵运算表示式可知，系数矩阵A可分解为一个单位下三角矩阵可分解为一个单位下三角矩阵L和一个上三角矩阵和一个上三角矩阵U的乘积，的乘积，即即LUALLLAnn )(111211 )2()2(2)2(22)1(1)1(12)1(11)(nnnnnaaaaaaAU其中其中 nnnnuuuuuu222112112022-4-23第五章 线性方程组的直接解法35第一个方程组的系数矩阵为下三角矩阵，第二个方程组的系第一个方程组的系数矩阵为下三角矩阵，第二个方程

36、组的系数矩阵为上三角矩阵，两个方程组都非常容易求解，具体求数矩阵为上三角矩阵，两个方程组都非常容易求解，具体求解结果如下：解结果如下：我们将我们将A=LU 称为矩阵称为矩阵A的三角分解的三角分解,这时线性方程组为：这时线性方程组为：bAX bLUX 令令YUX 则有则有 YUXbLY2022-4-23第五章 线性方程组的直接解法36bLY 对于对于 nnnnnnbbbbyyyyllllll3213211213231211111由由 nkylbybykiikikk, 3 , 2,1111解得解得2022-4-23第五章 线性方程组的直接解法37YUX 对于对于 nnnnnnyyyxxxuuuuu

37、u212122211211由由 1 , 2, 1,/1nniuxuyxuyxiinijjijiinnnn求得求得2022-4-23第五章 线性方程组的直接解法38bAX 可以看出对于方程组可以看出对于方程组： 只要对系数矩阵作了三角分解只要对系数矩阵作了三角分解： LUA 由这个简单的计算过程可知，系数矩阵的三角分解很关键，由这个简单的计算过程可知，系数矩阵的三角分解很关键，如何进行三角分解更容易？下面介绍几种方法。如何进行三角分解更容易？下面介绍几种方法。 nkylbybykiikikk,3,2,1111 1 , 2, 1,/1nniuxuyxuyxiinijjijiinnnn通过如下两组公

38、式很容易求解通过如下两组公式很容易求解： 2022-4-23第五章 线性方程组的直接解法39二、二、Doolittle分解法分解法 前已述及，若在顺序前已述及，若在顺序Gauss消去法的过程中，每步消去法的过程中，每步消元的主元素消元的主元素 akk(k)0，则矩阵，则矩阵A A可分解为可分解为ALU，L L为单位下三角矩阵，为单位下三角矩阵，U为上三角矩阵，此分解称为为上三角矩阵，此分解称为A A的的 Doolittle（杜利特尔）分解。可以证明杜利特尔）分解。可以证明akk(k) 0的充要的充要条件是条件是A A的各阶顺序主子式不为零，于是有如下定理。的各阶顺序主子式不为零，于是有如下定理

39、。 定理定理7.1 7.1 设设n阶方阵阶方阵A的各阶顺序主子式不为零，的各阶顺序主子式不为零，则存在惟一单位下三角矩阵则存在惟一单位下三角矩阵L和上三角矩阵和上三角矩阵U使使ALU。下面介绍矩阵三角分解的下面介绍矩阵三角分解的Doolittle分解方法。分解方法。LUA 2022-4-23第五章 线性方程组的直接解法40 nnnnnnaaaaaaaaa212222111211 nnnnuuuuuu22211211 1111321323121nnnllllll根据根据 A=LU 有等式成立：有等式成立：比较等式两端对应元素，有比较等式两端对应元素，有 ija)001(121 i iiilll

40、00121jjjjjjuuuu2022-4-23第五章 线性方程组的直接解法41 ija)001(121 i iiilll 00121jjjjjjuuuujijii ijijiuululul 112211ji ji jjijjjijjijiulululul 112211 nnii2022-4-23第五章 线性方程组的直接解法42可以解得可以解得：,11jjau ,1111ualii 当当 i=1 时时 当当 j=1 时时 nj, 2 , 1 ni, 3 , 2 当当 i 1 时时 niij, 1, 11ikkjikijijulau当当 j 1 时时 njji, 2, 1 jiululululj

41、iuulululajjijjjijjijiijjiiijijiij112211112211jjjkkjikijijuulal/ )(11 2022-4-23第五章 线性方程组的直接解法43于是，对于矩阵的三角分解：于是，对于矩阵的三角分解：可按照以下公式进行：可按照以下公式进行： niualnjauiijj,3,2,/,2,1,111111 nnnnnnaaaaaaaaa212222111211 nnnnuuuuuu22211211 1111321323121nnnllllll nikulaulniijulauimmikmkiiikiimmjimijij,1),(1,1,1111对于对于 i=

42、2,3, ，n, 计算计算（7.2）（7.3）（7.4）用计算公式用计算公式(7.3)、(7.4)对矩阵对矩阵A A作的分解作的分解(7.2),称作称作Doolittle分解。分解。2022-4-23第五章 线性方程组的直接解法44 nnnnnnaaaaaaaaa212222111211 nnnnuuuuuu22211211 1111321323121nnnllllll下面，我们对具体矩阵进行下面，我们对具体矩阵进行Doolittle 三角分解。三角分解。为了表示和存储方便，可以将分解后的两个矩阵用一为了表示和存储方便，可以将分解后的两个矩阵用一个矩阵表示个矩阵表示 nnnnnnaaaaaaa

43、aa212222111211 nnnnnnulluuluuu2122221112112022-4-23第五章 线性方程组的直接解法45例例7-3 7-3 利用利用DoolittleDoolittle三角分解法分解矩阵三角分解法分解矩阵解：分解时用到如下公式解：分解时用到如下公式 niualnjauiijj,3,2,/,2,1,111111 25681161642781169414321A 1234111261237624624 11ikkjikijijulauniij, 1, njji, 2, 1 jjjkkjikijijuulal/ )(11 2022-4-23第五章 线性方程组的直接解法4

44、6 25681161642781169414321A 1234111261237624624可以写成：可以写成：这时，矩阵的三角分解这时，矩阵的三角分解 25681161642781169414321A 25681161642781169414321A 1671013100110001 24000246001262043212022-4-23第五章 线性方程组的直接解法47如果我们要求解方程组如果我们要求解方程组 19044102256811616427811694143214321xxxx则由则由 25681161642781169414321 1671013100110001 240002

45、4600126204321得到得到 1904410216710131001100014321yyyy 432143212400024600126204321yyyyxxxx2022-4-23第五章 线性方程组的直接解法48由由 1904410216710131001100014321yyyy解得解得 2418824321yyyy再由再由 432143212400024600126204321yyyyxxxx 24188224000246001262043214321xxxx求得方程组的解：求得方程组的解：14 x13 x12 x11 x2022-4-23第五章 线性方程组的直接解法49 1 ,

46、2,1,/,3,2,11111nniuxuyxuyxnkylbybyiinijjijiinnnnkiikikk（7.5） 如下的计算公式如下的计算公式(7.3)、(7.4)与与(7.5)就是求解方程组就是求解方程组Axb 的的 Doolittle 三角分解方法三角分解方法,包括分解和回代两步。包括分解和回代两步。 niualnjauiijj,3,2,/,2,1,111111（7.3） nikulaulniijulauimmikmkiiikiimmjimijij,1),(1,1,1111（7.4）关于具体求解过程可以按下面例子的方法进行。关于具体求解过程可以按下面例子的方法进行。 2022-4-

47、23第五章 线性方程组的直接解法50例例7-4 7-4 利用利用DoolittleDoolittle三角分解方法解线三角分解方法解线性方程性方程 105201021243321321xxx解解: 进行三角分解进行三角分解ALU，按照公式按照公式(7.5)可以对增广可以对增广 矩阵矩阵A,b作三角分解作三角分解: 100102512432321 1 2 3 -2-3 2 2 -3-133172022-4-23第五章 线性方程组的直接解法51 1712300320321321xxx得到得到,3173 x 100102512432321 1 2 3 -2-3 2 2 -3-13317这时，相应的方程

48、组为：这时，相应的方程组为：x135x28，2022-4-23第五章 线性方程组的直接解法52例例7-5 7-5 利用利用DoolittleDoolittle三角分解方法解线性三角分解方法解线性方程组方程组 710521391443010213124343214321xxxx解：对增广矩阵进行三角分解解：对增广矩阵进行三角分解 71391441030102513124324321 1 2 3 -4 -2-3 2 42-3133322-4-117-16等价方程组通过分解式容易写出为：等价方程组通过分解式容易写出为：2022-4-23第五章 线性方程组的直接解法53 1 2 3 -4 -2-3 2

49、 42-3133322-4-117-16 16171240002300132043214321xxxx解得解得, 44 x, 33 x, 22 x, 11 x2022-4-23第五章 线性方程组的直接解法54三、平方根法三、平方根法 在实际应用中，常见一类非常重要的线性方程组在实际应用中，常见一类非常重要的线性方程组Axb，其中其中A A为对称正定矩阵，即为对称正定矩阵，即A A是对称的且对任何非零向量是对称的且对任何非零向量 x x 都有都有xTAx0 0。本节将对这类方程组导出更有效地三角分解。本节将对这类方程组导出更有效地三角分解求解方法，称之为求解方法，称之为平方根法平方根法。 设设A

50、 A为对称正定矩阵，那么为对称正定矩阵，那么A A的所有顺序主子式均大于的所有顺序主子式均大于零，根据定理零，根据定理7.17.1，存在惟一三角分解，存在惟一三角分解A ALULU，即，即 nnnnnnnnnuuuuuuuuuullllllA33322322113121112132312111112022-4-23第五章 线性方程组的直接解法55 nnnnnnnnnuuuuuuuuuullllllA3332232211312111213231211111 记记 Ak（1kn）为）为A的的 k 阶顺序主子阵，则阶顺序主子阵，则det（Ak）为为A的的k阶顺序主子式。由上式，利用矩阵分块运算规则，

51、阶顺序主子式。由上式，利用矩阵分块运算规则，容易验证容易验证 det（Ak）u11 u22 ukk那么由那么由 det（Ak）0，可知，可知 ukk0，k1，2，n 这时，将上面的矩阵表示为：这时，将上面的矩阵表示为：2022-4-23第五章 线性方程组的直接解法56 nnnnnnnnnuuuuuuuuuullllllA3332232211312111213231211111 1111111133322222311111131112332211121323121uuuuuuuuuuuunnnnnnnnnuuuullllllLDM 即：即： A=LDM ，其中其中 DM=U， M=D-1U。20

52、22-4-23第五章 线性方程组的直接解法57当当AAT为对称矩阵时，根据为对称矩阵时，根据 ALDM, 得到得到ATMT D LT再根据矩阵三角分解的唯一性再根据矩阵三角分解的唯一性,可知可知 MLT。于是。于是ALDLT则有则有TLDLDA2121 ),diag(221121nnuuuD 21LDG 令令TLDLD)(2121 TGG nnnnnnnnnnngggggggggggggggggggg3332232211312111213332312221112022-4-23第五章 线性方程组的直接解法58 如果对称正定矩阵如果对称正定矩阵A具有如下分解具有如下分解 AGGT，其中，其中G为

53、为下三角矩阵，则称其为下三角矩阵，则称其为对称正定矩阵的对称正定矩阵的 Cholesky（乔列斯（乔列斯基）分解。基）分解。 为表示方便，可以记为表示方便，可以记TLLA nnnnnnnnnnnllllllllllllllllllll333223221131211121333231222111 给定对称正定方程组给定对称正定方程组 Axb，对，对 A 进行进行 Cholesky分解分解ALLT，则原方程组等价于，则原方程组等价于 LLTxb2022-4-23第五章 线性方程组的直接解法59Lyb LTx y解此方程组即可得到原方程组的解解此方程组即可得到原方程组的解x ，这就是求解方程组这就是

54、求解方程组的平方根法。的平方根法。 下面，我们通过比较矩阵的对应元素给出对称正定矩阵的下面，我们通过比较矩阵的对应元素给出对称正定矩阵的平方根分解法。已知平方根分解法。已知即：即： LLTxb，等价于等价于 nnnnnnnnnnnllllllllllllllllllll333223221131211121333231222111 nnnnnnaaaaaaaaa2122221112112022-4-23第五章 线性方程组的直接解法60 ija比较对应元素：比较对应元素： nnnnnnnnnnnllllllllllllllllllll333223221131211121333231222111 n

55、nnnnnaaaaaaaaa212222111211 0021jjjjlll 0,0,21iiiilll2022-4-23第五章 线性方程组的直接解法61 ija当当 i = j 时时 0021jjjjlll 0,0,21iiiilll22221jjjjjjllla 当当 j i 时时jjijjijiijlllllla 2211解得解得njlaljkjkjjjj,2, 1,)(21112 njilllaljjjkjkikijij, 2 , 1,/ )(11 2022-4-23第五章 线性方程组的直接解法62 于是，根据计算公式于是，根据计算公式njlaljkjkjjjj,2, 1,)(2111

56、2 可以对对称正定矩阵进行平方根分解可以对对称正定矩阵进行平方根分解 nnnnnnaaaaaaaaa212222111211l11 njilllaljjjkjkikijij, 2 , 1,/ )(11 l21 l22 l31 l32 l33 ln1 ln2 ln3 lnn nnnnnllllllllll3332322213121112022-4-23第五章 线性方程组的直接解法63 关于方程组关于方程组 Ax=b , 如果对系数矩阵进行了平方根分解如果对系数矩阵进行了平方根分解 ALLT，则将方程组化为：，则将方程组化为： Lyb , LTxynjlylbyjjjkkjkjj, 2 , 1,1

57、1 1 , 1,1 nnjlylyxjjnjkkkjjj nnnnnnnbbbbyyyyllllllllll321321321333231222111 nnnnnnnyyyyxxxxllllllllll321321333232221312111解得解得2022-4-23第五章 线性方程组的直接解法64 于是，关于系数矩阵是对称正定矩阵的线性方程组于是，关于系数矩阵是对称正定矩阵的线性方程组Ax=b的求解，分两步进行：的求解，分两步进行：第一步：系数矩阵的平方根分解第一步：系数矩阵的平方根分解njlaljkjkjjjj,2, 1,)(21112 njjilllaljjjkjkikijij, 1,

58、/ )(11 第二步：解等价方程组第二步：解等价方程组njlylbyjjjkkjkjj,2,1,11 1 ,1,1 nnjlylyxjjnjkkkjjj2022-4-23第五章 线性方程组的直接解法65例例7-6 用平方根法求解对称正定方程组用平方根法求解对称正定方程组 25. 7645 . 375. 2175. 225. 41114321xxx解解: 首先进行首先进行A 的的Cholesky 分解分解 ALLTnjlaljkjkjjjj,2, 1,)(21112 njjilllaljjjkjkikijij, 1,/ )(11 2-0.50.521.51 2-0.50.521.512022-4

59、-23第五章 线性方程组的直接解法66得得 y12，y23.5 ，y31 得得 x11，x21，x31 25. 76415 . 15 . 0025 . 0002321yyy 15 . 321005 . 1205 . 05 . 02321xxx求解求解Lyb:再求解再求解 LTxy:2022-4-23第五章 线性方程组的直接解法67 25. 7645 . 375. 2175. 225. 41114321xxx关于对称正定方程组关于对称正定方程组 也可以用一般的三角分解法求解，这时由也可以用一般的三角分解法求解，这时由 4 -1 1 4-0.250.254370.7511求得求得 x11，x21，

60、x31 25. 75 . 375. 21675. 225. 4141142022-4-23第五章 线性方程组的直接解法68四、追赶法四、追赶法 追赶法是专门用于求解三对角方程组的。这类追赶法是专门用于求解三对角方程组的。这类方程组经常出现于用差分方法或有限元方法求解二方程组经常出现于用差分方法或有限元方法求解二阶常微分方程边值问题、热传导问题及三次样条函阶常微分方程边值问题、热传导问题及三次样条函数插值等问题，三对角方程组数插值等问题，三对角方程组AxAxb b的系数矩阵具的系数矩阵具有如下形式：有如下形式： nnnbacbacbacbA13322211 设设A A为一个三对角矩阵，那么它的顺