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 nnnnnnnnbbbbxxxxaaaaaaaaaA2121212222111211,nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111(1)(1)引入引入 根据根据 GramerGramer（克莱姆）法则，求解方程组（克莱姆）法则，求解方程组（1 1）时，要计）时，要计算大量的行列式，所需乘法次数大约为算大量的行列式，所需乘法次数大约为 当当 n n 较大时较大时,这个计算量是惊人的。例这个计算量是惊人的。例 如，当如，当 n=20 时，时，约需乘法次数为约需乘法次数为 N=9.71020 若系数矩阵
3、若系数矩阵A A非奇异，即非奇异，即 det(A)0，则方程组有惟一解则方程组有惟一解 x=(x1,x2,xn)T.如果用每秒一亿次的计算机来计算，需要三十万年时间。如果用每秒一亿次的计算机来计算，需要三十万年时间。可见可见GramerGramer法则不是一种实用的方法。法则不是一种实用的方法。因此，必须构造出适合于计算机使用的线性方程组的求解因此，必须构造出适合于计算机使用的线性方程组的求解方法。方法。N=(n2-1)n!引入引入 直接方法的特点是，如果不考虑计算过程中的舍入误直接方法的特点是，如果不考虑计算过程中的舍入误差，运用此类方法经过有限次算术运算就能求出线性方程差，运用此类方法经过
4、有限次算术运算就能求出线性方程组的精确解。组的精确解。求解线性方程组的数值方法可分为两大类：直接方法和求解线性方程组的数值方法可分为两大类：直接方法和迭代方法。本章讨论直接方法，迭代方法将在下一章中讨论。迭代方法。本章讨论直接方法，迭代方法将在下一章中讨论。需要指出，由于实际计算中舍入误差的存在，用直接方需要指出，由于实际计算中舍入误差的存在，用直接方法一般也只能求得方程组的近似值。法一般也只能求得方程组的近似值。1 Gauss消去法 GaussGauss（高斯）消去法是一种规则化的加减消元法高斯）消去法是一种规则化的加减消元法 通过逐次消元计算把需求解的线性方程组转化成上三角通过逐次消元计算
5、把需求解的线性方程组转化成上三角形方程组，也就是把线性方程组的系数矩阵转化为上三角矩形方程组，也就是把线性方程组的系数矩阵转化为上三角矩阵，从而使一般线性方程组的求解转化为等价（同解）的上阵，从而使一般线性方程组的求解转化为等价（同解）的上三角形方程组的求解。三角形方程组的求解。GaussGauss消去法由消元和回代两个过程组成，先讨论一个具体消去法由消元和回代两个过程组成，先讨论一个具体的线性方程组的的线性方程组的求解。求解。一、顺序一、顺序Gauss消去法消去法 15233322242321321321xxxxxxxxx 48822422423232321xxxxxxx 812224224
6、2332321xxxxxx323 x612 x321 x 188022402242 152333212242,bA 81200224022423/2,6/1,32123 xxx例例1.用用Gauss消去法解方程组消去法解方程组用增广矩阵进行进算用增广矩阵进行进算一、顺序一、顺序Gauss消去法消去法 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111或者或者 Ax=b 我们用增广矩阵表示，并给出我们用增广矩阵表示，并给出gaussgauss消去法的具体算法消去法的具体算法 )1()1()1(3)1(2)1(1)1(3)1(3)1(33)1(3
7、2)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消去法消去法 )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第一步，设第一步，设 a11(1)0 ，将第一列将第一列a11(1)以下各元素消成零以下各元素消成零乘以矩阵乘以矩阵A（1
8、），b（1）的第的第一行再加到第一行再加到第i 行，得到矩阵行，得到矩阵 (i2，3，n)1(11)1(11aalii 即依次用即依次用一、顺序一、顺序Gauss消去法消去法其中其中 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行，得到矩阵行，得到矩阵 )2()2()2(3)2(2)2(3)2(3)2(
9、33)2(32)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11)2()2(000,nnnnnnnnbaaabaaabaaabaaaabA一、顺序一、顺序Gauss消去法消去法niblbbnjialaaiiijiijij,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)2()2(00000,nnnnnnnbaabaabaaabaaaab
10、A一、顺序一、顺序Gauss消去法消去法增广矩阵增广矩阵A（n），b（n）对应如下上三角形方程组对应如下上三角形方程组 )()()2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnbxabxaxabxaxaxa这是与原线性方程组（这是与原线性方程组（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一、顺序一、顺序Gauss消去法消去法对于等价方程组对于等价方程组 )()()1(1)1(1
11、1)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 L算法算法 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=a
12、ik 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 .a 3
13、n b3l43.l n3 a1 1 a1 2 a13 .a1 n b1a 4n b4.ann bn 一、顺序一、顺序Gauss消去法消去法用用Gauss消去法解方程组，应注意：消去法解方程组，应注意：1.适用条件：适用条件：原方程组系数矩阵的各阶顺序主子原方程组系数矩阵的各阶顺序主子 式不等于零。式不等于零。2.运算量小：运算量小：共有乘除法次数为共有乘除法次数为 )3(312)1(231233nnnnnnnn 而而Gramer 法则的乘除法次数为法则的乘除法次数为:(n2-1)n！当当 n=20 时时202107.9!)1(nnN3060)3(3123 nnnN二 列主元Gauss消去法 顺
14、序顺序Gauss消去法计算过程中的消去法计算过程中的 akk(k)称为主元素，在称为主元素，在第第k步消元时要用它作除数步消元时要用它作除数,则可能会出现以下几种情况则可能会出现以下几种情况若出现若出现 akk(k)0，消元过程就不能进行下去。消元过程就不能进行下去。akk(k)0，消去过程能够进行，但若消去过程能够进行，但若|akk(k)|过小，也会造过小，也会造成舍入误差积累很大导致计算解的精度下降。成舍入误差积累很大导致计算解的精度下降。例例2 在四位十进制的限制下，试用顺序在四位十进制的限制下，试用顺序Gauss消去法求解消去法求解如下方程组如下方程组 9812.4120032001.
15、1291.58334.06781.0167.001.0012.0321321321xxxxxxxxx二 列主元Gauss消去法此方程组具有四位有效数字的精确解为此方程组具有四位有效数字的精确解为x117.46，x245.76，x35.546 解解 用顺序用顺序Gauss消去法求解，消元过程如下消去法求解，消元过程如下 0.981200.41200320010.12910.58334.0000.16781.01670.00100.00120.0 231017981044541467041.44010.8101000.006781.01670.00100.00120.0 5531065171011
16、750041.44010.8101000.006781.01670.00100.00120.0二 列主元Gauss消去法经回代求解得经回代求解得 x35.546，x2100.0，x1104.0和此方程组的精确解相比和此方程组的精确解相比x35.546，x245.76，x117.46有较大的误差。有较大的误差。对于此例，由于顺序对于此例，由于顺序Gauss消去法中的主元素绝对值非常消去法中的主元素绝对值非常小，使消元乘数绝对值非常大，计算过程中出现大数吃掉小数小，使消元乘数绝对值非常大，计算过程中出现大数吃掉小数现象，产生较大的舍入误差，最终导致计算解现象，产生较大的舍入误差，最终导致计算解 x
17、1104.0 和和 x2100.0 已完全失真。已完全失真。为避免这种现象发生，为避免这种现象发生，可以对原方程组作等价变换，再利可以对原方程组作等价变换，再利用顺序用顺序Gauss消去法求解。消去法求解。0.981200.41200320010.12910.58334.0000.16781.01670.00100.00120.0 6781.01670.00100.00120.010.12910.58334.0000.10.981200.412003200写出原方程组的增广矩阵：写出原方程组的增广矩阵：针对第一列找出绝对值最大的元素，进行等价变换：针对第一列找出绝对值最大的元素，进行等价变换：
18、644.01670.0105500.0079.11909.54584.000.981200.4120032002 5329.00961.00079.11909.54584.000.981200.412003200求得方程的解为：求得方程的解为：x35.546，x245.76，x117.46精确解为：精确解为：x35.546，x245.76，x117.46 由此可见，第二种由此可见，第二种Gauss消去法的精度明显高于顺序消去法的精度明显高于顺序Gauss消消去法，我们称它为列主元去法，我们称它为列主元Gauss消去法。消去法。列主元列主元Gauss消去法与顺序消去法与顺序Gauss消去法的不同
19、之处在于：消去法的不同之处在于：后者是按自然顺序取主元素进行消元后者是按自然顺序取主元素进行消元 前者在每步消元之前先选取主元素然后再进行消元前者在每步消元之前先选取主元素然后再进行消元 下面将列主元下面将列主元Gauss消去法的计算步骤叙述如下：消去法的计算步骤叙述如下：给定线性方程组给定线性方程组 Axb,记记A（1）,b（1）A,b，列主元列主元Gauss消去法的具体过程如下：消去法的具体过程如下：1.首先在增广矩阵首先在增广矩阵A（1）,b（1）第一列的第一列的n个元素中选取绝个元素中选取绝对值最大的一个作为主元素，并把此主元素所在的行与第一对值最大的一个作为主元素，并把此主元素所在的
20、行与第一行交换，即行交换，即,max)1(11)1(1inikaa 2.其次进行第一步消元得到增广矩阵其次进行第一步消元得到增广矩阵A（2）,b（2），在矩在矩阵阵A（2）,b（2）第二列的后第二列的后 n1个元素中选取绝对值最大的个元素中选取绝对值最大的一个作为主元素，并把此主元素所在的行与第二行交换，即一个作为主元素，并把此主元素所在的行与第二行交换，即,max)2(22)2(2inikaa )1(1)1()1(1)1(,bbaakjkj)2(2)2()2(2)2(,bbaakjkj 3.再进行第二步消元得到增广矩阵再进行第二步消元得到增广矩阵A（3），b（3）。按此按此方法继续进行下去，
21、经过方法继续进行下去，经过n1步选主元和消元运算，得到增步选主元和消元运算，得到增广矩阵广矩阵A（n），b（n），它对应的方程组它对应的方程组A（n）xb（n）是一个与原方程组等价的上三角形方程组，可进行回代求是一个与原方程组等价的上三角形方程组，可进行回代求解。解。容易证明，只要容易证明，只要det（A）0，列主元列主元Gauss消去法就可消去法就可以顺利完成，即不会出现主元素为零或者绝对值太小的情以顺利完成，即不会出现主元素为零或者绝对值太小的情形出现。形出现。下面给出列主元下面给出列主元Gauss消去法的计算流程：消去法的计算流程：列主元列主元GaussGauss消去算法消去算法 用列主
22、元用列主元Gauss消去法求解线性方程组消去法求解线性方程组Axb 输入输入 A（aij），），b（b1，bn）T，维数维数n n输出输出 方程组解方程组解x x1 1，x xn n，或方程组无解信息或方程组无解信息1 1：对于对于k1，2，n1，循环执行步循环执行步2到步到步52 2：按列选主元素按列选主元素 a aikik ，即确定下标即确定下标 I I 使使jknjkikaa max3 3：若若a aikik0 0，输出输出 no unique solution，停机停机nkjaaijkj,ikbb4 4：若若i ik k，换行换行5 5：消元计算，对于：消元计算，对于i ik k1 1
23、，n n，计算计算 kkikikaal/nkjalaakjikikik,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 n二 列主元Gauss消去法 由于这两种方法的精度差不多，且全主元由于这两种方法的精度差不多，且全主元Gauss消去法程序设消去法程序设计复杂占用机器时间较多，实际应用中一般采用列主元计复杂占用机器时间较多，实际应用中一般采用列主元Gauss消去消去法，它既简单又能保证计算精度。法，它既简单又能保证计算精度。有时候在消元过程中可以在系数矩阵所有元素中选择绝对值最大有时候在消元过程中可以在系数矩阵所有元素中选择绝对值最大的元素作为主元素，这样的的元素作为主元素，这样的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(,nnnnnnnnnbaaaabaaaabaaaabaaaabAThankYou!
