1、2.Gauss2.Gauss消元法消元法 (一)高斯消去法的求解过程高斯消去法的求解过程,可大致分为两个阶段可大致分为两个阶段:首先首先,把原把原方程组化为上三角形方程组方程组化为上三角形方程组,称之为称之为“消去消去”过程过程;然后然后,用逆次序用逆次序逐一求出三角方程组逐一求出三角方程组(原方程组的等价方程组原方程组的等价方程组)的解的解,并称之为并称之为“回回代代”过程过程.,.,下面分别写出下面分别写出“消去消去”和和“回代回代”两个过程的计算步两个过程的计算步骤骤.消去过程消去过程:第一步第一步:设设a a1111 0,0,取取 做做(消去第消去第i i个方程组的个方程组的x x1
2、1)m mi1i1 第一个方程第一个方程+第第i i个方程个方程 i=2,3,i=2,3,n n则第则第i i个方程变为个方程变为1111aamii)1()1(2)1(1)1(21inbxaxaxainii可得第一步消元后的方程组为可得第一步消元后的方程组为)1()1(2)1(2)1(2)1(22)1(22)0(1)0(12)0(121)0(11nnnnnnnnnbxaxabxaxabxaxaxai,j=2,3,niiijijiiijiijijbbaabmbbamaa)0()0()0(11)0()1()0(11)0()1(,i,j=2,3,n第二步第二步:设设 ,取取 做做(消去第消去第i i
3、个个方程组的方程组的x x2 2,i=3,4,i=3,4,n)n)m mi2i2 第二个方程第二个方程+第第i i个方程个方程 i=3,4,i=3,4,n n类似可得第二步消元后的方程组为类似可得第二步消元后的方程组为0)1(22a)1(22)1(22aamii)2()2(3)2(3)2(3)2(33)2(33)1(2)1(22)1(22)0(1)0(12)0(121)0(11nnnnnnnnnnnbxaxabxaxabxaxabxaxaxanjibmbbamaaiiijiijij,.,4,3,)1(22)1()2()1(22)1()2(第第k k步步:设设 ,取取 做做(消去第消去第i i个
4、个方程组的方程组的x xk k,i,i=k+1,k+2,=k+1,k+2,n),n)m mikik 第第k k个方程个方程+第第i i个方程个方程 i=i=k+1,k+2k+1,k+2,n n类似可得第类似可得第k步消元后的方程组为步消元后的方程组为0)1(kkka)1()1(kkkkikikaam)()(1)(1)(1)(11)(11)1(2)1(22)1(22)0(1)0(12)0(121)0(11knnknnkkknkknknkkkkknnnnbxaxabxaxabxaxabxaxaxankkjibmbbamaakkikkikikkjikkijkij,.,2,1,)1()1()()1()
5、1()(继续下去到第继续下去到第n-1步消元步消元,可将线性方程组化为如下上三角方程可将线性方程组化为如下上三角方程组组:nkkjibmbbamaaaamnkkkbabxabxaxabxaxaxakkikkikikkjikkijkijkkkkikikkikijnnnnnnnnnn,.,2,1,/1,3,21)1()1()()1()1()()1()1()()()1()1()1(2)1(22)1(2211212111，对计算公式为次消元后的系数，表示第的上标和其中 高斯消元法高斯消元法 /*Gaussian Elimination*/思思路路首先将首先将A化为上三角阵化为上三角阵 /*upper-
6、triangular matrix*/，再回代求解再回代求解 /*backward substitution*/。=1 Gaussian Elimination The Method消元消元记记,)()1()1(nnijaAA )1()1(1)1(.nbbbbStep 1：设设 ，计算因子，计算因子0)1(11 a).,2(/)1(11)1(11niaamii 将增广矩阵将增广矩阵/*augmented matrix*/第第 i 行行 mi1 第第1 1行行，得到得到)1(1)1(1)1(12)1(11.baaan)2(A)2(b).,2,()1(11)1()2()1(11)1()2(njib
7、mbbamaaiiijiijij 其中其中Step k：设设 ，计算因子，计算因子且计算且计算0)(kkka).,1(/)()(nkiaamkkkkikik ).,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij 共进行共进行？步步n 1 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa回代回代)()(/nnnnnnabx 0)(nnnaWhat if?No unique solution exists.)1.,1()(1)()(niaxabxiiinijjiijiii0)(ii
8、iaWhat if?Then we must find the smallest integer k i with ,and interchange the k-th row with the i-th row.0)(ikiaWhat if we cant find such k?No unique solution exists.定理定理 若若A的所有的所有顺序主子式顺序主子式/*determinant of leading principal submatrices*/均不为均不为0，则高斯消元无需换行即可，则高斯消元无需换行即可进行到底，得到唯一解。进行到底，得到唯一解。iiiiiaaa
9、aA.)det(1111 事实上，只要事实上，只要 A 非奇异，即非奇异，即 A 1 存在，则可通过逐存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出次消元及行交换，将方程组化为三角形方程组，求出唯一解。唯一解。1 Gaussian Elimination The Method6239432632321321321xxxxxxxxxGauss 消元发求解方程组用例下面给出例题。为具体认识这种方法，完成第一步消元得。个方程）第个方程）做（第解3,21(i11/1/21/2/01,3111313111212111imaamaamani1,1,11131263261)123()23(1
10、3/3333263211/1/,01032632321321323332321)1(22)1(3232)1(223232321xxxxxxxxxxxxxxxaamaxxxxxxx故说求解为回代求得完成第二步消元得3.3.高斯选主元素消去法高斯选主元素消去法例例1:考虑如下线性方程组的考虑如下线性方程组的Gauss消元法消元法 求解性求解性 2x2=1 2x1+3x2=2解解:因为因为a11=0,故此题不能用故此题不能用Gauss消元法求解消元法求解,但交换但交换方程组的顺序后方程组的顺序后,就可就可用用Gauss消元法求解了消元法求解了.选主元素的必要性。选主元素的必要性。例例2：单精度解方程
11、组单精度解方程组 211021219xxxx/*精确解为精确解为 和和 */.1000.00.1101191 x8个个.8999.99.0212 xx8个个用用Gaussian Elimination计算：计算：911212110/aam999212210101010.0.011 ma8个个92121012 mb 9991010011100,112 xx小主元小主元/*Small pivot element*/可能导致计可能导致计算失败。算失败。1 Gaussian Elimination Pivoting Strategies0.0001x1+x2=1 x1+x2=2 假设假设求解是在四位浮
12、点十进求解是在四位浮点十进制数的计算机上进行制数的计算机上进行0.1000 10-3 x1+0.1000 101 x2=0.1000 1010.1000 101 x1 +0.1000 101 x2=0.2000 101 解解:本题的计算机机内形式为本题的计算机机内形式为 因为因为a11=0.0001 0,故可用故可用Gauss消元法求解消元法求解,进行第一次消元时有进行第一次消元时有a22(1)=0.1000 101-104 0.1000 101 (m21=a21/a11=1/0.0001=104)=0.00001 105-0.1000 105 (对阶计算对阶计算)=0.0000-0.1000
13、 105=-0.1000 105,得三角方程组得三角方程组 0.1000 10-3 x1+0.1000 101 x2=0.1000 101 -0.1000 105 x2=-0.1000 105 回代解得x2=1 ,x1=0 严重失真!(因为本题的准确解为因为本题的准确解为x1=10000/9999,x2=9998/9999例例4 4 用高斯消去法解方程组用高斯消去法解方程组 9.07.0103.0212111xxxx要求用具有舍入的要求用具有舍入的1010位浮点数进行计算。位浮点数进行计算。精确到精确到1010位真解：位真解：Tx)7000000000.0,2000000000.0(*9.01
14、17.01103.0),(11bA解法解法1 1（高斯消去法）（高斯消去法）消元：消元：121121103333333333.0103.01 m12103333333333.011 1舍去或着舍去或着说被说被“吃吃”9.0舍去或着说被舍去或着说被“吃吃”12103333333333.07.09.0 07.01103.01112103333333333.0 12102333333333.0 计算解：计算解：。0000000000.07000000000.012xx 显然显然,计算解与真解相差太大计算解与真解相差太大,11)1(11103.0 a原原因因是是用用很很小小的的数数作除数，作除数，使得
15、舍入误差太大，从而计算结果不可靠。使得舍入误差太大，从而计算结果不可靠。解法解法2 用行变换的高斯消去法用行变换的高斯消去法.消元：消元：7.01103.09.0111112rr)103.01103.0(111121 m 7.0109.011。2000000000.07000000000.012xx计算解计算解:7.0103.09.0211121xxxx 9.07.0103.0212111xxxx 该结果较好。例子说明，在采用高斯消去法解方程组时，应该结果较好。例子说明，在采用高斯消去法解方程组时，应 。对一般系数矩阵，最好保持乘数。对一般系数矩阵，最好保持乘数)(kkka元元素素避避免免采采
16、用用绝绝对对值值很很小小主主1|ikm，因此在高斯消去法中引进选主元素技巧。，因此在高斯消去法中引进选主元素技巧。9.0117.01103.0),(11bA完全主元素消去法完全主元素消去法一一 选主元消元法：选主元消元法：。，0|max|1111 ijnjnijiaa11jxx 与与注注意意调调换换，设设bxA，nnRA 为非奇异矩阵，为非奇异矩阵，)1.4(第一步：第一步：。元元素素仍仍记记为为且且两两未未知知量量，并并作作记记录录，iijbabA,使使,11ji选选主主元元：)1(行行元元素素，行行与与第第第第交交换换时时即即当当交交换换行行列列111),(,1,)2(ibAi（3 3）消
17、元计算：）消元计算：，),3,2(1111niaamii ，),3,2(1111niamaii ib列列元元素素。列列与与第第第第交交换换时时当当111),(,1jbAj 1 ia),3,2(11nibmbii 在在A中选取绝对值最大的元素作为主元素，即确定中选取绝对值最大的元素作为主元素，即确定 第第k 步：重复进行，设已完成第步：重复进行，设已完成第1 1步步第第k-1 的选主元，使的选主元，使 A，增广阵。增广阵。b A，约化为约化为:b nnnnkkknkknkkbaabaababaaabAbA222111211)()(,第第k步的步骤：步的步骤：。步步选选主主元元区区域域方方框框为为
18、第第1,2,1 nkk使使选选主主元元：即即确确定定,)1(kkji0max ijnjknikjiaakk，行行元元素素，行行与与第第第第交交换换时时即即当当交交换换行行列列kkkkikbAki),(,)2()()(（3 3）消元计算：）消元计算：),1(nkiaamkkikik ),1,(nkjiamakjikij ib列列元元素素。列列与与第第第第交交换换时时当当kkkkjkbAkj),(,)()(ija),1(nkibmbkiki 二二 回代求解回代求解：调调换换后后的的次次序序。则则是是未未知知数数其其中中nnxxxyyy,2121 )1,2,1(/)(/1niayabyabyiini
19、jjijiinnnn工作量大。工作量大。nnnnnnbbbyyyaaaaaa212122211211经过上述过程，方程组约化为：经过上述过程，方程组约化为：。该该方方法法数数值值稳稳定定)1(kim缺点：缺点：优点：优点：改进方法：改进方法：。且此时且此时1 kim列主元消去法，列主元消去法，设已完成第设已完成第1步步第第k-1步计算，得到与原方程步计算，得到与原方程组组等价的方程组等价的方程组，其中，其中)()(kkbxA )()()()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11)()(,nnknnknkkknknkkknnkkbaabaabaabaaabA方框
20、内为第方框内为第k步选主元素区域。步选主元素区域。列主元素消去法列主元素消去法 以下步骤类似完全选主元素消去法。以下步骤类似完全选主元素消去法。例：例：211111091,112 xx 110211 11102119 列主元法没有全主元法稳定。列主元法没有全主元法稳定。0,112 xx例：例：2111010199 99991010010101注意：这两个方程组注意：这两个方程组在数学上在数学上严格等价严格等价。标度化列主元消去法标度化列主元消去法/*Scaled Partial Pivoting*/对每一行计算对每一行计算 。为省时间，。为省时间，si 只在初始时计只在初始时计算一次。以后每一
21、步考虑子列算一次。以后每一步考虑子列 中中 最大的最大的 aik 为主元。为主元。|max1ijnjias nkkkaa.iiksa稳定性介于列主元法和全主元法之间。稳定性介于列主元法和全主元法之间。1 Gaussian Elimination Pivoting Strategies 列主元基本思想列主元基本思想 用高斯消去法求解线性方程组时用高斯消去法求解线性方程组时,应避免小的主元应避免小的主元.在实际计算在实际计算中中,进行第进行第k k步消去前步消去前,应该在第应该在第k k列元素列元素a aikik (i=k,(i=k,n),n)中找出绝大中找出绝大值最大者值最大者,例如例如 a =
22、max a a =max a 再把第再把第p p个方程与第个方程与第k k个方程组进行交换个方程组进行交换,使使a apkpk(k-1)(k-1)成为主元成为主元.我们称我们称这个过程为这个过程为选主元选主元.由于只在第由于只在第k k列元素中选主元列元素中选主元,通常也称为通常也称为按列按列选主元选主元(或称或称部分选主元部分选主元).如果在第如果在第k k步消去前步消去前,在第在第k k个方程到第个方程到第n n个方程所有的个方程所有的x xk k到到x xn n的的系数系数a (i=k,a (i=k,n;j=k,n;j=k,n),n)中中,找出绝对值最大者找出绝对值最大者,例如例如 a
23、=maxa a =maxa 再交换第再交换第k,pk,p两个方程和第两个方程和第k,qk,q两个未知量的次序两个未知量的次序,使使a a 成为主元成为主元.称这个过程为称这个过程为完全选主元完全选主元.不论是哪种方式选出主元不论是哪种方式选出主元,而后再按上面介绍的计算步骤进行而后再按上面介绍的计算步骤进行消去的计算消去的计算,一般都称为一般都称为选主元的高斯消去法选主元的高斯消去法.在实际计算中在实际计算中,常用常用按列选主元的高斯消去法按列选主元的高斯消去法.(k-1)(k-1)pk(k-1)ikkin(k-1)pq(k-1)ijki,jn(k-1)ij(k-1)pq例例4.2.5，4.2
24、.6（P78）例例1 用列主元消去法解方程组用列主元消去法解方程组解解 第一次消元对第一次消元对 因列主元素为因列主元素为a31(1),故先作行变换故先作行变换r2_r3,然后进行消元计算可得然后进行消元计算可得 第二次消元对第二次消元对A(2)|b(2),因列主元素为因列主元素为a32(2),故先作行变换故先作行变换r2_r3,然后进行然后进行消元计算可得消元计算可得 由此回代由此回代,得得x=(1.9272,-0.69841,0.90038)T与精确解与精确解 x=(1.9273,-0.69850,0.90042)T相比较是比较准确的相比较是比较准确的.-0.002x1+2x2+2x3 =
25、0.4 x1+0.78125x2 =1.38163.996x1+5.5625x2+4x3=7.4178 -0.002 2 2 0.4 A(1)|b(1)=1 0.78125 0 1.3816 3.996 5.5625 4 7.4178 3.996 5.5625 4 7.4178 A(2)|b(2)=0 -0.61077 -1.0010 -0.47471 0 2.0029 2.0020 0.40371 3.996 5.5625 4 7.4178A(3)|b(3)=0 2.0029 2.0020 0.40371 0 0 -0.39050 -0.35160例例1 用列主元素消去法解方程组用列主元素消
26、去法解方程组 分析：分析：由精确解看出有两位有效数字，因此，用由精确解看出有两位有效数字，因此，用4 4位浮点数进位浮点数进 021313222226321321321xxxxxxxxx。精精确确解解：)0.5,8.3,6.2(321 xxx 012113333.06667.022226,bA)1667.0,3333.0(3121 mm 3334.0333.1667.10667.13333.00001.00222632rr 667.13333.00001.003334.0333.1667.102226解解 ：消元：消元：)00005999.06667.10001.0(32 m 667.1333
27、3.0003334.0333.16667.1022263334.000005999.0667.1 舍去或着说被舍去或着说被“吃吃”行计算。行计算。回代计算解：回代计算解：602.2801.3003.5123xxx高斯选主元消去法的步骤：高斯选主元消去法的步骤：667.13333.0003334.0333.16667.102226bA，注注：该解若取两位有效数字，则与真解完全相同。该解若取两位有效数字，则与真解完全相同。优点：优点：数值稳定。数值稳定。修正方法：修正方法：消元消元；回代回代。列主元高斯列主元高斯-约当（约当（Gauss-Jordam）消去法。）消去法。缺点：缺点：既消元；又回代。
28、既消元；又回代。列主元高斯列主元高斯约当（约当（Gauss JordanJordan)消去法消去法 假设假设G-J消去法已完成第消去法已完成第1 1步第步第k-1步，得到与原方程组等价步，得到与原方程组等价，)()()()()(,1)(,1)(1)(1)(11knnknkkknkkkknkknkknkkkaaaaaaaaA第第k步计算步骤：步计算步骤：,)()()(1)(knkkkkbbbb的方程组的方程组 ，其中，其中)()(kkbxA（1）按列选主元：按列选主元：使使即即确确定定ki；iknikkiaak max,行行元元素素；行行与与第第第第时时，交交换换当当kkikbAki),(（2
29、2）换行：换行：消元：消元：（3 3）消元计算：消元计算：（3 3）消元计算：消元计算：，且且),2,1(/kiniaamkkikik ，且且 nkjkiniamaakjikijij,1,2,1。且且),2,1(kinibmbbkikii ，kkkkam/1 （4 4）计算主行（主元素所在行）计算主行（主元素所在行）)(),1,(kkkjkjkkkjkjaaankkjmaa 有有则则均均已已完完成成即即上上述述过过程程完完成成后后,2,1,nk nnnnbbbbAbA111,21)1()1(步步。),2,1(nibxii 计算解：计算解：kkkkmbb（1）按列选主元：按列选主元：使使即即确确
30、定定ki；iknikkiaak max,行行元元素素；行行与与第第第第时时，交交换换当当kkikbAki),(（2 2）换行：换行：消元：消元：说明说明：次次乘乘除除法法。计计算算量量较较大大，大大约约是是)2/(3nO因此，可以用来求逆矩阵。因此，可以用来求逆矩阵。如果用列主元如果用列主元G-JG-J消去法将（消去法将（A，I）为为非非奇奇异异矩矩阵阵，设设nnRA 。则则TA 1不用回代，将不用回代，将A化为单位矩阵，则解为常数项列。化为单位矩阵，则解为常数项列。定理定理9 9 （列主元高斯（列主元高斯约当法求逆约当法求逆矩矩阵）阵）化为（化为（I，T），），。解解即即消消去去法法bAxb
31、xAJG1 优点优点：缺点缺点：约约当当消消去去法法。时时，一一般般不不用用高高斯斯在在解解方方程程组组 bxA因为计算量太大，但是在解多个方程组而它们的系数矩阵相同时，因为计算量太大，但是在解多个方程组而它们的系数矩阵相同时，则则有有了了矩矩阵阵的的逆逆矩矩阵阵用用此此方方法法，即即是是求求系系数数bAxAA111,该方法与高等代数中求逆矩阵方法的不同之处是有选主该方法与高等代数中求逆矩阵方法的不同之处是有选主注注：元，实际上元，实际上选选主元就是交换两行的位置，仍是初等变换，在一般的主元就是交换两行的位置，仍是初等变换，在一般的求逆矩阵方法中也有交换两行元素。求逆矩阵方法中也有交换两行元素
32、。例例4.2.8、4.2.9（P81）例例6 用列主元用列主元G-J消去法求消去法求。的的逆逆矩矩阵阵1653542321 AA 100653010542001321),(IA 001321010542100653解：解：31rr 131r 3/10113/103/21013/203/10023/5131323121 mm，13123132rrrr 3/10113/103/21013/20100653 2132 m 02/112/10012/302/31022/502/101 2123523rrr 2321rr 02/112/1003/21013/203/10023/51 02/112/100
33、12/302/31022/502/101 2123523rrr 012100133010231001 3323123rrrrr，)(1 AI。所所以以 0121332311A 2321rr 02/112/1003/21013/203/10023/51u 理解理解 完全主元素消去法完全主元素消去法u 会用会用列主元素消去法列主元素消去法解方程组；解方程组；P98 4.3、4.5、4.6（改为用（改为用列主高斯约当法解）列主高斯约当法解）作业作业:列主元素消去法列主元素消去法列主元高斯列主元高斯约当（约当（Gauss Jordan)消去法消去法会用会用列主元高斯列主元高斯约当（约当（Gauss J
34、ordan)消去法求矩阵的逆矩消去法求矩阵的逆矩阵。阵。高斯消去法的计算量分析 高斯消去法的乘除总运算高斯消去法的乘除总运算(由于计算机作乘除运算所需时间远大由于计算机作乘除运算所需时间远大于作加减运算所需时间于作加减运算所需时间,故我们只讨论乘除运算量故我们只讨论乘除运算量)分析为分析为消元次数消元次数k k 消元乘法次数消元乘法次数 消元除法次数消元除法次数 回代乘除法总次数回代乘除法总次数 1 n(n-1)n-11 n(n-1)n-1 2 (n-1)(n-2)n-2 2 (n-1)(n-2)n-2 .k (n-k+1)(n-k)n-k k (n-k+1)(n-k)n-k .n-1 2 n
35、-1 2*1 1 n(n+1)/21 1 n(n+1)/2 故高斯消去法的计算量为故高斯消去法的计算量为 N=n(nN=n(n2 2-1)/3+n(n-1)/2+n(n+1)/2=n-1)/3+n(n-1)/2+n(n+1)/2=n3 3/3+n/3+n2 2-n/3-n/3当当 N N 充分大时为充分大时为 n n3 3/3/3 运算量运算量/*Amount of Computation*/1 Gaussian Elimination Amount of Computation由于计算机中乘除由于计算机中乘除/*multiplications/divisions*/运算的时运算的时间远远超过
36、加减间远远超过加减/*additions/subtractions*/运算的时间，故运算的时间，故估计某种算法的运算量时，往往只估计估计某种算法的运算量时，往往只估计乘除的次数乘除的次数，而且通，而且通常以乘除次数常以乘除次数的的最高次幂最高次幂为运算量的为运算量的数量级数量级。Gaussian Elimination:Step k：设设 ，计算因子，计算因子且计算且计算0)(kkka).,1(/)()(nkiaamkkkkikik ).,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij 共进行共进行n 1步步 )()2(2)1(121)()2(
37、2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa)()(/nnnnnnabx )1.,1()(1)()(niaxabxiiinijjiijiii(n k)次次(n k)2 次次(n k)次次(n k)(n k+2)次次nnnknknnk6523)2)(2311 消元乘除次数：消元乘除次数：1 次次(n i+1)次次22)1(1211nninni 回代乘除次数：回代乘除次数：Gaussian Elimination 的总乘除次数为的总乘除次数为 ，运算量为，运算量为 级。级。nnn31323 33n1 Gaussian Elimination Amount of
38、 Computation Complete Pivoting:比比 Gaussian Elimination多出多出 比较，保证稳定，但费时。比较，保证稳定，但费时。33nO Partial Pivoting:比比 Gaussian Elimination只多出只多出 比较，略省时，但不保比较，略省时，但不保证稳定。证稳定。32nO Scaled Partial Pivoting:比比 Gaussian Elimination多出多出 除法和除法和 比较，比列主比较，比列主元法稳定。但若逐次计算元法稳定。但若逐次计算 si(k)，则比全主元法还慢。，则比全主元法还慢。)(2nO 32nO Ga
39、uss-Jordan Method:运算量约为运算量约为 。故通常只用于求逆矩阵，而不用于解方。故通常只用于求逆矩阵，而不用于解方程组。求逆矩阵即程组。求逆矩阵即 。23nO 1|AIIA况。使求解出现解失真的情程有时不能进行到底而单的特点，但其消元过法的基础，具有计算简的基本方法，它是直接消元法是解线性方程组的事。是一件很简单个未知量的线性方程组算机解含有从这个表可以看出用计回代消元的函数）代时间（作为阵按秒计算得消元及回矩那么下表给出，对满的为用在一次运算上的时间假设对某计算机来说，上。在简约成三角形的形式大时，主要的工作量花而当Gaussnnsnp1005.70.50001000075.
40、100000.510000085.000505.010:,151 方法的特点方法的特点 由具体计算结果可知由具体计算结果可知,全主元素法的精度优于主元素法全主元素法的精度优于主元素法,这是由于全主这是由于全主元素是在全体系数中选主元元素是在全体系数中选主元,故它对控制舍入误差十分有效故它对控制舍入误差十分有效.但全主元素法在但全主元素法在计算过程中计算过程中,需同时作行与列的互换需同时作行与列的互换,因而程序比较复杂因而程序比较复杂,计算时间较长计算时间较长.列主列主元素法的精度虽稍低于全主元素法元素法的精度虽稍低于全主元素法,但其计算简单工作量大为减少但其计算简单工作量大为减少,且计算经且计
41、算经验与理论分析均表明验与理论分析均表明,它与全主元素法同样具有良好的数值稳定性它与全主元素法同样具有良好的数值稳定性,列主元素列主元素法是求解中小型稠密性方程组的最好方法之一法是求解中小型稠密性方程组的最好方法之一.选主元消去法选主元消去法(包括解线性方程组的所有直接的方法包括解线性方程组的所有直接的方法)比较适用于中比较适用于中小型方程组小型方程组.对高阶方程组对高阶方程组,即使奇数矩阵是稀疏的即使奇数矩阵是稀疏的,但在计算中很难保持稀但在计算中很难保持稀疏性疏性,因而有存储量大，程序复杂等不足因而有存储量大，程序复杂等不足,所幸的是这一缺点可用迭代法解决所幸的是这一缺点可用迭代法解决.另
42、外另外,高斯选主元消去法还可技巧性的解决一些特殊线性方程组高斯选主元消去法还可技巧性的解决一些特殊线性方程组 由于误差的影响由于误差的影响,计算过程中可能出现一些坏现象计算过程中可能出现一些坏现象,要尽可能防止要尽可能防止,表现表现在求解线性方程组的消元法比较上在求解线性方程组的消元法比较上,则应该注意要简化运算则应该注意要简化运算,减小运算次数减小运算次数,提高效率提高效率;提高数值稳定性等提高数值稳定性等.假定我们能把矩阵假定我们能把矩阵A写成下列两个矩阵相乘的形式：写成下列两个矩阵相乘的形式：A=LU 其中其中L为下三角矩阵，为下三角矩阵，U为上三角矩阵。这样我们可以把为上三角矩阵。这样
43、我们可以把线性方程组线性方程组 Ax=b写成写成 Ax=（LU)x=L(U x)=b Ly=b令令 U x=y,则原线性方程组则原线性方程组 Ax=b Ux=y于是可于是可首先求解向量首先求解向量y使使 Ly=b然后求解然后求解 Ux=y,从而求解线性方程组从而求解线性方程组 Ax=b的目的的目的.LU分解法的基本思想分解法的基本思想内容内容:LU分解分解.关键词关键词:LU分解分解:将系数矩阵将系数矩阵A转变成等价两个矩阵转变成等价两个矩阵L和和U的乘积的乘积,其中其中L和和U分别是下三角和上三角分别是下三角和上三角矩阵矩阵,而且要求而且要求L的对角元素都是的对角元素都是1.紧凑格式紧凑格式
44、:由于可以把由于可以把L和和U两个矩阵压缩到一两个矩阵压缩到一个数组中个数组中,而且还可以存储在原来的系数矩阵而且还可以存储在原来的系数矩阵A的数组中的数组中.这种这种LU分解分解表示表示常被称为紧凑格式常被称为紧凑格式.定义定义1 1 LUA 叫叫A的三角（因子）分解，其中的三角（因子）分解，其中 是是L是上三角。是上三角。U下三角下三角,L为单位下三角阵（对角元全为为单位下三角阵（对角元全为1 1），），U为上三角阵，则称为上三角阵，则称LUA 为为DoolittleDoolittle分解分解;L若若 是下三角，是下三角，U 是单位上三角，则称是单位上三角，则称LUA 定理定理1 n1 n
45、阶阵阶阵)2(nA 有唯一有唯一DoolittleDoolittle分解分解(CroutCrout）A 的前的前n-1n-1个顺序主子式不为个顺序主子式不为0 0.（证略）（证略）三角分解不唯一三角分解不唯一,为此引入为此引入定义定义2 2 若若 为为CroutCrout分解。分解。为什么要讨论三角分解？若在消元法进行前能实为什么要讨论三角分解？若在消元法进行前能实 现三角分解现三角分解LUA ，则则 bxLUbAx)(上三角方程组）上三角方程组）下三角方程组）下三角方程组）(yUxbLy 容易回代求解容易回代求解回代求解很容易，如回代求解很容易，如 2,1)1,-n(k n),2,3,(k
46、1 1111111212121222111 kknkjjkjkknnnnkjjkjkkkknnnnnnuxubxuyxylblylbybbbyyyllllll练练习习：由由LU=A及对及对L和和U的要求可以得到分解的计算的要求可以得到分解的计算公式根据下式公式根据下式(Doolittle分解分解)：1 l21 1 l31 l32 1 ln1 ln2 lnn-1 1 u11 u12 u13 u1n u22 u23 u2n un-1n u(n-1)n unn=aannL Un1an3 a11 a12 a13 a1na21 a22 a23 a2na31 a32 a33 a3n an2 Aijjjji
47、iiiijiauuullllULj000,0,1,213211第j个分量第i个分量nkjikkjikkjikijulula1,max1根据矩阵乘法及相等的定义根据矩阵乘法及相等的定义,有有 niulululanjuulululainkkkikkikijjnkkkjkkjkj,2,2,11111111111111111111得公式 u1j=a1j j=1,2,n li1=ai1/u11 i=2,3,niiikkijknkikkijkkijkjiijikkjiknkikkjikkjkijululululauulululajiji111111111,有时当1iil),3,2(),1(),1,(),3
48、,2(),2,1(1111111111nknkiauulalnkkjaulauniualnjauDoolittleikkkkmmkimikikkjkmmjkmkjkjiijj 分解公式分解公式在计算机程序中常常用这种方法解线性代数方程组。在计算机程序中常常用这种方法解线性代数方程组。它的优点是存储量很省。它的优点是存储量很省。L和和U中的三角零元素都不中的三角零元素都不必存储，就是必存储，就是U的对角元素也因为都是的对角元素也因为都是1没有必要再没有必要再记录在程序中，这样只用一个记录在程序中，这样只用一个n阶方阵就可以把阶方阵就可以把L和和U贮存起来。即：贮存起来。即：下三角（不包括对角元）
49、存储下三角（不包括对角元）存储L各元各元素素 而上三角存储而上三角存储U的元素。的元素。再考察公式再考察公式S会发现会发现A中任一元素中任一元素aij只在计算只在计算lij（ji)中用到一次以后就不再出现了，因而完全中用到一次以后就不再出现了，因而完全可以利用原始数组可以利用原始数组A的单元，一个个逐次贮存的单元，一个个逐次贮存L或或U中中的相应元素，即：的相应元素，即：a11 a12 a13 a1n u11 u12 u13 u1n a21 a22 a23 a2n l21 u22 u23 u2n a31 a32 a33 a3n l31 l32 u33 u3n an1 an2 an3 ann l
50、n1 ln2 ln3 unn.(1)(3)(5)(2n-1)(2)(4)(6)(2n)采用采用LU分解有如下特点：分解有如下特点：（1）LU分解与右端向量无关。先分解，后分解与右端向量无关。先分解，后回代。一般说来，分解的运算次数正比于回代。一般说来，分解的运算次数正比于n回代求解正比与回代求解正比与n。求。求 遇到多次回代时，分遇到多次回代时，分解的工作不必重新做。这样节省计算时间。解的工作不必重新做。这样节省计算时间。（2）分解按步进行，前边分解得到的信息）分解按步进行，前边分解得到的信息为后边所用。为后边所用。（3）A阵的存储空间可利用，节省存储阵的存储空间可利用，节省存储。32例例1
