线性方程组数值解(第四、五章2011)

1、江西理工大学理学院江西理工大学理学院实际问题中的线性方程组分类：按系数矩阵中零元素的个数：稠密线性方程组稀疏线性方程组按未知量的个数：高阶线性方程组(如1000)低阶线性方程组按系数矩阵的形状对称正定方程组三角形方程组三对角占优方程组(80%)第四章第四章 解线性方程组的直接法解线性方程组的直接法.,)(,) 1 . 4() 1 . 4(22112222212111212111常数向量为方程组的未知向量和分别是方程组的系数矩阵其中其矩阵形式为阶线性方程组本章研究的对象是bXaAbAXbxaxaxabxaxaxabxaxaxanijnnnnnnnnnnnxxx21nbbb21.,.,作简要介绍并

2、对误差分析直接法本章讨论几种较实用的方程组精确解的方法经过有限步运算能求得就是在不计舍入误差时所谓直接法4.1 Gauss消去法消去法4.1.1 Gauss顺序消去法顺序消去法 高斯高斯(Gauss)消去法实质是消元法消去法实质是消元法,它的基本做法是把方程它的基本做法是把方程组组(4.1)转化成一个等价的三角方程组转化成一个等价的三角方程组nnnnnnnngxbgxbxbgxbxbxb）（4.22222211212111.,.11为回代这个过程称逐个求出然后这个过程称为消元xxxnn4.1.1.1 高斯消去法的计算过程高斯消去法的计算过程 为了符号统一为了符号统一,把方程组把方程组(4.1)

3、改写成下面形式改写成下面形式其中用矩阵表示为)3 .4()3 .4()1()1()1()1(2)1(21)1(1)1(2)1(22)1(221)1(21)1(1)1(12)1(121)1(11bXAbxaxaxabxaxaxabxaxaxannnnnnnnnn)1()1(2)1(1)1()1()1(2)1(1)1(2)1(22)1(22)1(1)1(12)1(11)1(,nnnnnnnbbbbaaaaaaaaaA其中用矩阵表示为方程组等价的即得与式等等倍方程减去第一个方程的第三个倍个方程的用第二个方程减去第一若)4 . 4()4 . 4() 3 . 4(.,/,/, 0)2()2()2()2(

4、2)2(2)2(3)2(32)2(32)2(2)2(22)2(22)1(1)1(12)1(121)1(11)1(11)1(31)1(11)1(21)1(11bXAbxaxabxaxabxaxabxaxaxaaaaaannnnnnnnnnn的等价方程组得倍方程的个方程减去第二个中第若类似地则令)4 . 4(,/)4 . 4(, 0,), 3, 2(/,000)2(22)2(2)2(22)1(11)1()2()1(11)1()2()1(11)1(11)2()2(2)1(1)2(2)2(3)2(2)2(3)2(33)2(32)2(2)2(23)2(22)1(1)1(13)1(12)1(11)2(aa

5、iabmbbamaaniaambbbbaaaaaaaaaaaaaAiiiijiijijiinnnnnnnnnji, 3, 2,)5 . 4(其中用矩阵表示为)6 . 4()6 . 4()3()3()3()3(3)3(3)3(3)3(33)3(33)2(2)2(23)2(232)2(22)1(1)1(13)1(132)1(121)1(11bXAbxaxabxaxabxaxaxabxaxaxaxannnnnnnnnnn)3()2(2)1(1)3()3()3(3)3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)3(,00000nnnnnnnbbbbaaaaaaaa

6、aaaA方程组即得等价的三角步经过去上述步骤可继续进行下若则令,1, 0), 4, 3(/)3(33)2(22)2()3()2(22)2()3()2(22)2(22nabmbbamaaniaamiiijiijijiinji, 4, 3,)7 .4()8 . 4()8 . 4()()()()()3(3)3(33)3(33)2(2)2(23)2(232)2(22)1(1)1(13)1(132)1(121)1(11nnnnnnnnnnnnnnbXAbxabxaxabxaxaxabxaxaxaxa用矩阵表示为)()2(2)1(1)()()3(3)3(33)2(2)2(23)2(22)1(1)1(13)

7、1(12)1(11)(,000000nnnnnnnnnnbbbbaaaaaaaaaaA式为消元过程元素的计算公程矩阵的过程称为消元过把系数矩阵化为上三角.)9 . 4(nikjabmbbaabbamaaaaaanjkibbaakijkkikkikkkkkkikkikikkjikkijkkjkkkkikkijkijkikikijkij10)/()/(,)1()()()()()()()1()()()()()()()1()()1()()1(njknik1,1)(1)()()()(211)()(/ )(/,), 2, 1(,/,)8 . 4(),8 . 4(iiijnijiijiiinnnnnninn

8、nnnnnnnnaxabxabxnixxxxxxbx其计算公式为叫回代过程这一过程依次求得全部变量式子可求出代入倒数第三个把可求出子把它代入倒数第二个式得最后一个式子从方程组有了等价的三角方程组1, 2, 1nni)10. 4(4.1.1.2 高斯消去法的运算量高斯消去法的运算量(只计算乘除法只计算乘除法)nknnkknnnnnn12) 1(3) 1(.,)2() 1(,2,) 1(,1共需次需做乘法个系数消去第二列的次需做乘法个系数消去第一列的nnnNNNnnkNnnnNnnknknk3131),1(26523),1(2,23211223111的运算量为所以高斯消去法数为回代过程所需的乘除次

9、除次数为消元过程所需的乘要做的除法运算次数为次乘法4.1.2 Gauss列主元消去法列主元消去法而中止溢出作除数计算机将因若它为称为主元数用到的除个倍数步求第高斯消去法消元过程中,”0“, 0,/,)()()(kkkkkkkikaaaknk10001. 02,0001. 0, 0, 1100001000010001. 0,.9999/9998,9999/10000210001. 01 . 4.,2121122211212121xxxxxxxxxxxxxxxx变为下交换一先将方程组的两个方程为了避免这种情况入误差剧增造成的使舍作除数这是因为用与精确解相差甚远回代得得消去第二个方程的求解的计算机上

10、用高斯消元字若在尾数为三位十进数的精确解为方程组例或产生较大的误差计算.|max|) 11, 2, 1)2(.,) 1 (.1 . 4.,.,),(,.1, 112,)()()(, 1)(122211paanknbAnknkkkpaaaakkxxxxxxiknikpkkpkknkkkkkkk保存主元所在的行标按列选主元做对阶数常数列向量输入系数矩阵列主元高斯消去法算法全主元高斯消去法则称为列中选主元行在步若在消去过程的第主元高斯消去法元的高斯消去法称为列这种选主两行则交换设绝对值最大的数为中选主元列在第步可在消去过程的第为避免出现小主元结果和精确解非常接近回代得得消去第二个方程的6557710

11、46232 . 4.1, 1,/ )3(, 1, 1,) 13 , 2 , 1()5., 1/)4.,)3.;, 0|)2321213211xxxxxxxxbXnniababxnkibmbbnkjiamaanknkiaamkpkpanijiijijiikikiikjikijijkkikikpk解方程组用列主元高斯消去法求例中存于常数项解回代消元计算两行交换若否则顺序进行计算停止则系数矩阵奇异若2/5|52/5010/61|610/107|07100,6|5154|6237|07102, 1105,10, 3max,6|5157|07104|623|:312121为化消元行交换第选主元表示计算过

12、程用增广矩阵解aaabATXxxxaa) 1, 1, 0(010/)1()7(7(1)2/5/() 152/5(1.5/31|5/31002/5|52/507|07100,10/61|610/102/5|52/507|07103, 22/52/5|,10/1max|1232323所以回代得增广矩阵这就是上三角方程组的为化消元行交换第选主元4.2 三角分解法三角分解法4.2.1 Doolittle分解法分解法 求解线性方程组的三角分解法求解线性方程组的三角分解法,源于高斯消去法的矩阵形式源于高斯消去法的矩阵形式. 从矩阵的角度看从矩阵的角度看,把式把式(4.3)化为式化为式(4.4),相当于系数

13、矩阵和相当于系数矩阵和常数列向量左乘初等矩阵常数列向量左乘初等矩阵列向量左乘初等矩阵相当于系数矩阵和常数化为式把式即),6 . 4()4 . 4(,1001011)1(1)2()1(1)2(131211bMbAMAmmmMn)11. 4(.),1(,1,10010101)1(1221)()1(1221)()2(2)3()2(2)3(2322由式三角阵其逆的乘积也是单位下也是单位下三角矩阵其逆的下三角矩阵对角元为为单位下三角矩阵其中得步经过即innnnnnnMbMMMMbAMMMMAnbMbAMAmmM)11. 4(设可惟一分解为矩阵时为的所有顺序主子式都不当分解的乘积叫做和上三角矩阵下三角矩阵

14、分解为单位即将系数矩阵是上三角矩阵是单位下三角矩阵其中则令.,0.,)1()(111211)(111211)1(LUAAALUULAULLUAAUMMMLAMMMAnnnn)12. 4(nnnnnnuuuuuuUlllllL2221121121323121,1111LUAULniuxuyxuyxYUXniylbybybLYbLYYUXbLUXnikiikikiinnnnikkikii由于矩阵与系数矩阵如何分解成问题得再解得解则令这时方程组可写为:1, 1/ )(/, 3, 2.,11111)13. 4()14. 4(nkkjikijnjiula1),2 , 1,(:根据矩阵的乘法有.), 3

15、, 2(/;), 2 , 1(:)(0)(01:111111的第一列元素得的第一行元素得从而可得注意到LniualUnjaujiujilliijjijijii的要确定列元素的前行元素的前现设已求出UrLrU,1,1nrnriuulalnriulululanrriulaunrriuululalkrlrLrrkrrkrikirirnkrkrrirkrikkrikirrkkirkririnkrkrikirkkirkrirrrk, 2:)16. 4(), 1(/ )(), 1()15. 4(), 1,(), 1,(,1,)(0.1111111111其中于是同理有于是则有由于列元素的第行元素及第可以引进

16、步分解时在进行第步的分解已完成若分解元可采用列主为避免这种情况产生较大的误差入误差的积累计算会引起舍的绝对值很小时当分解时直接进行与用高斯消去法相同为分解解方程组的计算量用所需乘除次数为解次数为所需乘除解所需乘除次数为分解讨论,1.,.,2.3131).(21),(21),(311:23321232231kkLUuLU、nnnNNNNLUnnNYUXnnNbLYnnNLUA、kk列元素的第行元素和的第计算两行的交换并记录选主元计算做对和阶输入矩阵分解算法如下列主元分解这种分解称为列主元步分解再进行第两行的交换令kLkUniaakpApSSnkkiaulaSnknALULUkkpASSnkkiu

17、laSpikiinikpkmikmkimikiinikpkmmkimiki)4., 2, 1,) 3.|,|max|)2., 1,) 1, 2, 1)2(.) 1 (:.,|max|, 1,1111623523/)2(4(/ )(1312/2/22/4/322:7135427743223 . 4,1, 1/2332133133332212313232132123231221222211313111212113121132111ululauuulalulauulauualualuuuLUxxxLUAULnkiaulaunkiaaauSlkkkimikmkikiikkkikkkiik分解先把系数矩

18、阵进行解分解求解方程组用例中存放在和分解后)(,.,2 . 2 . 42, 2, 16, 5, 3613322,121121321321计算按列不难得出计算公式的元素算用直接分解的办法来计这种分解是惟一的当限定对角元为正时使矩阵存在一个非奇异下三角是正定矩阵时当平方根法一改进的平方根法平方根法得再解得解LLLALA、xxxYUXyyybLYULT设设nnnnnaaaaaa11222111AnnnnllllllL21222111将 直接利用矩阵乘法,得:TLLA 2332322313322322131321131312222212211212121111,lllallllallallallala

19、则可由上式逐行求出矩阵则可由上式逐行求出矩阵L的元素的元素:31222111llll计算公式为计算公式为:2111211211111)() 1, 3 , 2 , 1(/ )(iiikiiiijkjjjkikijijlalijlllalal这时将原方程的解化为求解两个三角方程组的解这时将原方程的解化为求解两个三角方程组的解:yxLbLyT ,:得bLy ), 3 , 2(/ )(111111nilylbylbyiiikkikii由由由由:得yxLT) 1 , 2, 1(/ )(1nnilxlyxlyxnikiikikiinnnn73536/ )(3/23/3/3/2/3)17. 4(:73512

20、030223234 . 4.3213332312221112322313333222131323222122221131311121211111321yyyllllllllallllallallallalalxxxCholesky解得由式解组利用平方根法求解方程例分解法平方根法也叫.,.,),(6112/13/13/1,6/1, 3/523123321321333222312111321称为改进的平方根法用开方的分解法可得一种不是对角矩阵是单位下三角矩阵其中分解为把为避免开方运算次开方但需要计算量减少一半分解比高斯消去法分解矩阵的计算量为得再由得DLLDLAAn、LUnOnxxxyyyxxxl

21、lllllyyyT 二、改进的平方根法。二、改进的平方根法。 定理：若线性方程组定理：若线性方程组AX=b的系数矩阵的系数矩阵A为为n阶对称阵阶对称阵,且且A的的各阶顺序主子式都不等于零各阶顺序主子式都不等于零,则可将则可将A惟一分解为惟一分解为A=LDLT,其中其中L为单位下三角阵，为单位下三角阵，D为对角阵，写成矩阵形式为为对角阵，写成矩阵形式为:1111112121212121212222111211nnnnnnnnnnnllldddlllaaaaaaaaa根据矩阵乘法根据矩阵乘法,对对i=1,2, n有有:.,6,:, 2, 1:,) 1, 2, 1(,3111111112而且无需开方

22、运算上式所需的计算量约为容易看出有对于则上式可整理如下引进辅助量为了避免重复计算nltaddtlltatnidltijddllaldladikikikiiijijijjkjkikijijjijijjkjkjkikijijkjkikiii1,2, 1ij.:)2(:,) 1 (:,11111的解此即方程组中的求未知数计算中的求未知数求解下三角方程组令的解的步骤如下再求解方程分解以后的求得bAXxldyxdyxXXDLYylbybyYbLYXDLYbAXLDLAknikkiiiinnnTkikiiTTik), 2, 1(ni) 1, 2, 1( ni:175. 0,25. 0, 3, 1:34,2

23、5. 0, 1:24:1.,:25. 15 . 375. 25 . 075. 225. 464:3232313133323232131312131323231312121222121212121111321321321因此分解故有等于零的各阶顺序方子式都不且阶对称阵为阵满足可知此方程组的系数矩解方程组用改进的平方根法求解例ltltaddtldtlltatatiltaddtlatiadiLDLAnAxxxxxxxxxT112:2, 1, 1:1, 1, 6:175. 0125. 025. 01144175. 025. 0125. 013312211113322223332321313312122

24、11xxlxldyxxldyxdyxYXDLylylbyylbybybLYLDLATT即原方程组的解为得代入式的解为代入式nnnnnnndbadcbadcbadcbadcb111133332222111.阵为三对角方程组的增广矩程组最适用的追赶法nnnnlalalalal1133221nnnyyuyuyuyu1111111332211可得对三对角方解法用于三对角方程组将高斯消去法或三角分追赶法,3 . 2 . 4若A满足:1.|b1|c1|02.|bi|=|ai|+|ci|,(aici不等于0)3.|bn|an|0则可以证明A是非奇异的，且A的各顺序主子式不为01, 1), 2(/ )(/,1

25、1111111111nixuyxyxnilyadyuabllculdybliiiinniiiiiiiiiiii回代得得比较两边相应的元素)19. 4()20. 4( 上述方法称为追赶法上述方法称为追赶法,其中分解的过程叫追其中分解的过程叫追,回代的过程叫赶回代的过程叫赶.追赶法所需乘除次数为追赶法所需乘除次数为5n-4,比高斯消去法和三角分解法少的多比高斯消去法和三角分解法少的多. 实际遇到的方程组实际遇到的方程组,系数矩阵往往对角占优系数矩阵往往对角占优,不选主元就可顺不选主元就可顺利稳定地进行利稳定地进行.5/3)2/5/()2/112(/ )(, 2/52/113, 2/1/2/1/,

26、2)19. 4(111121101221112131112122112111131125 . 421222122211111111433221143214321lyadyuabllculdyblyyuyuyullllxxxx得由解设用追赶法求解方程组例0, 1, 1, 2)20. 4 (213735153521212113725312512012211121311121234xxxx得由式于是4.3 线性方程组数值求解的误差分析线性方程组数值求解的误差分析 前面介绍了求解线性方程组的各种方法，但从数值计算的前面介绍了求解线性方程组的各种方法，但从数值计算的角度看，除介绍算法外，还要进行误差分析

27、。而向量范数角度看，除介绍算法外，还要进行误差分析。而向量范数、矩、矩阵范数及矩阵的条件数在误差分析中是十分重要的，本节先介阵范数及矩阵的条件数在误差分析中是十分重要的，本节先介绍向量范数、矩阵范数及矩阵的条件数。绍向量范数、矩阵范数及矩阵的条件数。 4.3.1 向量范数向量范数向量范数是向量范数是n维实空间维实空间Rn中长度概念的推广中长度概念的推广。.|. |,:) 3(. |:)2(. 00, 0|:) 1 (:|,|,1 . 4的范数为向量则称有对所有三角不等式有和对所有齐次性时当且仅当有对所有正定性若具有性质对应一非负实数任一向量定义XXYXYXRYXXaaXRaRXX，XXRXXR

28、Xnnnn:4|3| |,4| |,2| |,1max|304) 3(21|10| 3|4|2| 1 |:.2 ,1) 3 , 4, 2 , 1 (6 . 4.,.2 ,1|max|,222221211222212211向量范数的基本性质解范数范数和范数的求例分量个的是其中范数范数和范数分别称为几种常用的范数有中在XXXXnXxxxxXxxxXxxxXRTnininnn)21. 4(. 00, 0|:) 1 (:|,|,2 . 4.,2 . 3 . 4. 0|lim.)3(.|,|.)2(.,|.) 1 ()()(21A，AARAARAXXXXXMXXmMmRXXnxxxXnnnnkkkrsr

29、nsrn时当且仅当有对所有正定性质若具有性对应一非负实数任一矩阵定义可定义矩阵的范数类似于向量范数的定义矩阵范数等价于收敛于向量向量序列范数收敛性使得数则存在常上任意两种范数为和设等价性函数元连续的是其分量向量的范数连续性. 1)2(.|,|:|) 1 (:.| ,)4(|,:) 3(. |:)2(EXXAAXAABAABRBABABARBAAaaARaRAnnnnnn单位矩阵范数为向量范数其中相容性质矩阵范数常用的几个性的范数为矩阵则称对所有有对所有三角不等式有和对所有齐次性|)|1 (1|)(|,1|)3(1BBEBEB且可逆时|)(|)|1 (|)(|)(|)()(|)()(|1.0|)

30、|1 (|)(|0|0,0)(,:111111BEBBBEBEBBEBEBEBEEBEXBXBXBXXBXXXBEXXBEBE因为可逆所以矛盾有非零解则方程组不可逆若证明|)|1 (1|)(|1BBE所以.,2,2 ,1 ,.,)(|max|)()(|2|max|)(1112111在理论证明时常用到它范数有一些很好的性质但范数比较复杂范数计算简单范数和这三种范数中的谱半径称为矩阵的绝对值最大的特征值表示矩阵其中行范数范数范数列范数范数三种常用的矩阵范数为AAAAAAaAAAAaATTTnjijniTniijnj)22. 4(特征方程为解求设例范数矩阵范数为一个常用且易于计算的此外2010101

31、03043)2(1|7)43(|),2|1max(|6)4|2(|),31max(|:| ,| ,| ,|,43217 .4)|(|.,22221211,2/12AAAAAAAAAAaAFTFFnjiijF01003020101010|2AAIT1167.512515|,125152A于是特征值为4.3.3 线性方程组固有性态与条件数线性方程组固有性态与条件数 一个线性方程组一个线性方程组AX=b是由它的系数矩阵是由它的系数矩阵A和常数向量和常数向量b确确定的。在实际问题中，定的。在实际问题中，A和和b中的数据是带有误差的，现在研究中的数据是带有误差的，现在研究A和和b受到微小扰动后对解有何影

32、响？受到微小扰动后对解有何影响？0001. 20001. 12,)0001. 2, 2(,. 0, 220001. 128 . 42121212121xxxxbbxxxxxxT方程组变为变为一微小变化若方程组右端常数项有的精确解为线性方程组例1, 121xx其解为 常数项的第二个分量的微小变化，引起了方程组解的巨大常数项的第二个分量的微小变化，引起了方程组解的巨大变化，这样的方程组称为病态方程组，矩阵变化，这样的方程组称为病态方程组，矩阵A称为病态矩阵。称为病态矩阵。 应该注意，矩阵的应该注意，矩阵的“病态病态”性质是矩阵本身固有的性态，性质是矩阵本身固有的性态，下面我们希望找出刻画矩阵下面我

33、们希望找出刻画矩阵“病态病态”性质的量。性质的量。 (1).设有非奇异方程组设有非奇异方程组AX=b，其精确解为，其精确解为X，b受到扰动受到扰动b b，从而相应的解，从而相应的解X有扰动有扰动X，即，即|:|:)(111XAbbAXbAbAXbAXbXAbAXbbXXA得由两边取范数得由.|,|, 0|, 0|111倍误差的端项相对解的相对误差不超过右有扰动时右端项此式表明从而则若以上两式相乘得AAkbbbAAXXAbXbAAbX)23.4(XAAAXAAEAAAAAAXAXAAbXXAAXXAAb)()(,.)(,1|,)()()(,).2(111此时也可逆时所以当可逆因为即有扰动从而相应

34、的解有微小扰动是精确的现假定.)(|)(3 . 4.|.,.|)(,|1|1|,|1|)(|)(|,1111111111111的条件数或方程组称为矩阵数定义的条件数称为方程组我们把会很大则扰动对解的影响可能很大而会很大则对解的影响不不大若倍系数矩阵相对误差的不超过近似解的相对误差有扰动时系数矩阵此式表明得并利用两边取范数bAXAAAAcondbAXAAkkkAAkAAAAAAAAAAAAAXXAAAAAEAAAvvv)24. 4(minmax2minmax221211111)(:2)()()()3(1)()2()() 1 (:AcondAAAAAAAAAcondAAAAcondAAAAcond

35、TT为对称阵时有特别当条件数的条件数的条件数的常用的条件数有)()()(1)(),(,)2()()(, )()(,1)() 1 (:22221AUcondUAcondAcondUcondEUUUAcondAcondAcondAcondAcondT则单位阵即为正交阵若条件数的性质AAAcondAAAcondXXbbAcondXX)(1)(:)24. 4()(:)23. 4(,可表示成而式可表示成式引入条件数后)()(1)(,AAbbAAAcondAcondXXbAb则有扰动和若同时考虑 由以上讨论可知，条件数很大（由以上讨论可知，条件数很大（cond（A）1）的方程）的方程组为病态方程组，条件数

36、很小的方程组为良态方程组。组为病态方程组，条件数很小的方程组为良态方程组。21010,9 . 4.140004|)(20001|0001. 2|1110001. 110000,0001. 1111,8 . 4,21525111111111xxxxAAAcondAAAA考察方程组的性态求方程组的条件数例程组所以该方程组为病态方中例例如.,)2(.) 1 (.,.,1100003|)(1101101102,110101max|10111,101max|111011011|,1110115得出的解变化很大将系数稍加变化相差悬殊系数矩阵的元素数量级表示方程组病态下列条件可能计

37、算若方程组的条件数不易实际应用中该方程组是病态方程组所以解AAAcondAAAAAA采用平衡措施后例如值最大的元素除以该行绝对就是将系数矩阵的各行所谓平衡措施迭代改善等如平衡措施或采用其他处理方法计算可采用双精度字长进行程组对于病态不太严重的方很差所得的解也可能即使算法是稳定的对于病态方程组主元数量级相差悬殊采用选主元技术时线性相关系数矩阵的行或列近似差较远算出的解与期望的解相1100003)(,11101,1).,(,.,.,)5(.)4(.)3(5.AcondA111105A通过事前误差估计实际上是一种前面介绍的误差估计称为迭代改善逐渐接近真正解的方法使得新解这样反复解再修改再求修改量仍是

38、近似解所得解满足使求修改量为求更好的近似解即先求近似解所谓迭代改善方程组变成良态的了, ,.,.,)(,. 2., 4)(, 2|, 2|101111101|155*1XXXXrXAbXAXXXrXAbXAbXXAXXXXAcondAAAAA1|, 6 .13|) 1 . 1, 5 . 4, 6 .13, 2 . 9(,)9 .30, 1 .33, 9 .22, 1 .32(,) 1, 1, 1, 1 (31332332109579106856577871010. 4”.“.,.4321XXXXbbbbXxxxxTTT得有扰动的解再解方程组有扰动现在的精确解为方程组例事后误差估计这就是所谓的然

39、后再作误差分析也可先上机求解当条件数难以计算时计算条件数来估计误差6 .1316 .13|XX. 6 .136 .13331 . 04488|)(|4488)(33|1 . 0|估计相对误差也是实际相对误差为bbAcondXXAcondbb 第五章第五章 线性方程组的迭代法线性方程组的迭代法 第四章介绍的直接法是通过有限步运算后得到方程组的解第四章介绍的直接法是通过有限步运算后得到方程组的解,当系数矩阵当系数矩阵A为非奇异的低阶稠密矩阵时，直接法是有效的为非奇异的低阶稠密矩阵时，直接法是有效的.但但在实际计算中在实际计算中,常会遇到大型稀疏矩阵（常会遇到大型稀疏矩阵（A的阶数很大，但零元的阶数

40、很大，但零元数很多）数很多）.迭代法是求解大型稀疏矩阵方程组的有效方法。迭代法是求解大型稀疏矩阵方程组的有效方法。 迭代法的基本思想是构造一个向量序列迭代法的基本思想是构造一个向量序列X(k),使其收使其收敛于方程组敛于方程组AX=b的精确解的精确解.因此因此,对迭代法来说对迭代法来说,一般一般有以下几个问题有以下几个问题: (1) 如何构造迭代序列如何构造迭代序列? (2) 构造的序列在什么情况下收敛构造的序列在什么情况下收敛? (3) 如果收敛如果收敛,收敛速度如何收敛速度如何? (4) 近似解的误差估计近似解的误差估计.5.1 Jacobi迭代法迭代法nnnnnnnnnnnnniinnn

41、nnnnnnnaxaxaxabxaxaxaxabxaxaxaxabxabAXbxaxaxabxaxaxabxaxaxa/)(/)(/)(, 0112211222323121221113132121122112222212111212111方程组可改写成假设其矩阵形式为设有方程组) 1 . 5()2 . 5()3 . 5().(.,/ )(/ )(/ )(,.,)3 . 5(,),(,)3 . 5(,),(*)()()(11)(22)(11)1(22)(2)(323)(1212)1(211)(1)(313)(2121)1(1)2()1()1(2)1(1)1()0()0(2)0(1)0(迭代法代法

42、这种迭代法称为简单迭就是方程组的解则收敛于若序列时当可得一向量序列这样迭代格式为一般地如此继续下去量右端得向把它代入式记为新向量右端可得一代入式选取初始向量JacobiXXXkXaxaxaxabxaxaxaxabxaxaxaxabxXxxxXxxxXkknnknnnknknnknknnkkkknnkkkTnTn)4 . 5(.; 2,1,)4(. 4,|)3(./ )(, 2, 1)2(. 1.,) 1 (1 . 5)0()0(1)0()0(否则输出失败信息转若否则转停止计算输出若计算对令代次数容许最大迭容许误差初始向量维数常数向量输入矩阵迭代法算法XXkkNkXXaxabxnikNXnbAJ

43、acobinijjiijijii5.2 Seidel迭代法迭代法即得迭代格式使用时再计算后若计算出不使用时计算用简单迭代法,)1()1(2)1(1)1(1)1()1()1()(kikkkikikkkkxxxxxxXX15/ )3230(8/ )12(20/ )3224(:3015321282432201 . 5./ )(/ )(/ )(213312321321321321)1(11)1(22)1(11)1(22)(2)(323)1(1212)1(211)(1)(313)(2121)1(1xxxxxxxxxxxxxxxxxxSeidelJacobiSeidelaxaxaxabxaxaxaxabx

44、axaxaxabxnnknnnknknnknknnkkkknnkkk方程组变形为解迭代法求解线性方程组迭代法和用例迭代法这种方法称为)5 . 5(容许最大容许误差初始向量维数常数向量输入矩阵迭代法算法迭代得取迭代格式为），迭代得取迭代格式为,) 1 (2 . 5)125368111. 2,138409760.01,76735807. 0()0, 0, 0(15/ )3230(8/ )12(20/ )3224()2(125368111. 2138409760.01,76735807. 0()0, 0, 0(15/ )3230(8/ )12(20/ )3224() 1 ()0()9()8()1(2

45、)1(1)1(3)(3)1(1)1(2)(3)(2)1(1)13()12()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1XnbASeidelXXXxxxxxxxxxSeidelXXXxxxxxxxxxJacobiTTkkkkkkkkkTTkkkkkkkkk.; 2,1,)4(. 4,|)3(/ )(1, 3, 2/ )(/ )()2(. 1.)0()0(11)0(11111)0(2111否则输出失败信息转若否则转停止计算输出若计算令迭代次数XXkkNkXXaxabxniaxaxabxaxabxkNnnjnjnjnniijnijijjijijiijnjj5.3 松弛法松弛法-SOR

46、法法 松弛法是松弛法是Seidel迭代法的加速迭代法的加速,迭代格式为迭代格式为:TknnnknnnknknnknkknnkkkkknnkkkXxxxxxxxxxxxxxxxxSORSeidelSeidelRalaxationOverSuccessiveSORxaxaxaxabxxaxaxaxabxxaxaxaxabx) 1, 1, 1, 1(141414142 . 5.1.)(.,)1 (/ )()1 (/ )()1 (/ )(4321432143214321)()1(11)1(22)1(11)1()(222)(2)(323)1(1212)1(2)(111)(1)(313)(2121)1(1

47、它的精确解为法解方程组用例迭代法是松弛法的特例迭代法时为法这种迭代称为松弛法或叫做松弛因子其中)6 . 5(. 1,) 1 (3 . 5.,)99999912. 0,99999953. 0,00000310. 1,99999646. 0(, 3 . 1,)0, 0, 0(4/ )41 (4/ )41 (4/ )41 (4/ )41 (:)0()11()0()(4)1(3)1(2)1(1)(4)1(4)(4)(3)1(2)1(1)(3)1(3)(4)(3)(2)1(1)(2)1(2)(4)(3)(2)(1)(1)1(1kNXnbAXXxxxxxxxxxxxxxxxxxxxxxxxxTTkkkkk

48、kkkkkkkkkkkkkkkkkkk令容许最大迭代次数容许误差松弛因子初始向维数常数向量输入矩阵松弛法算法果则可能达不到加速的效好但若选择得不加速会使迭代法的收敛大大松弛因子选择得好得取迭代格式为解.; 2,1,)4(. 4,|)3()1 (/ )() 1, 3, 2()1 (/ )()1 (/ )()2()0()0()0(11)0()0(111)0(111)0(2111否则输出失败信息转若否则转停止计算输出若计算XXkkNkXXxaxabxnixaxaxabxxaxabxnnnjnjnjnniiijnijijjijijiijnjj5.4 迭代法的一般形式与收敛性迭代法的一般形式与收敛性)5

49、 . 5()()()4 . 5(000000.,.)()1(1)1(1)(1)1()(1)1()(1)1(211221212211bFXEXDXbDXADIXbXADDXbXFEDXaaaFaaaEaaaDkkkkkkkkknnnnnn可表示为而式（即或可表示为则式令向量表示把迭代公式用矩阵一)7 . 5(bEDfFEDMSeidelbDfADIMJacobifMXXbXFDEDXXbFXEXDXbFXEDXbFXEXDXkkkkkkkkkkkkk1111)()1()(1)1()()()1(1)1()(1)1()()1()1()(,)(),()(,)1()()1 ()6 .5()(迭代法对迭代法对简单迭代法可以统一写成下面形式以上几种迭代格式即可表示为式即或)8 . 5()9 . 5()10. 5