南京航空航天大学《数值分析》课件-第3章

1、第第3 3章章 线性方程组的数值线性方程组的数值解法解法2022年5月21日星期六2第第3 3章章 线性方程组的数值解法线性方程组的数值解法3.1 3.1 高斯消去法高斯消去法3.2 3.2 矩阵三角分解法矩阵三角分解法3.3 3.3 平方根法平方根法3.4 3.4 向量和矩阵的范数向量和矩阵的范数3.5 3.5 方程组的形态和误差分析方程组的形态和误差分析3.6 3.6 迭代法迭代法3.7 3.7 迭代法的收敛性（选）迭代法的收敛性（选）312125020 xxxx123515xx411 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba

2、xa xa xb写成写成 Ax=b，其中，其中1112111212222212,nnnnnnnnaaaxbaaaxbxaaaxbAbn个未知量个未知量n个方程的个方程的11,2,nijjija xbin或简写成或简写成5xAb1,2,ikDxinD若若，即，即|A|0，则该，则该。此时，可以此时，可以求解求解11121121222212ninnnnnniaabaDaabaaaba 111212122212nnnnnnaaaaaaDaaa61,2,ikDxinD11121121222212ninnnnnniaabaDaabaaaba 111212122212nnnnnnaaaaaaDaaa1!1

3、11nn nSnnnnn 每个行列式的乘积项行列式每个乘积项的乘法次数！7：: 假定计算过程没有舍入误差的情况下，假定计算过程没有舍入误差的情况下，。经过有限步运算就能求得精确解的方法，经过有限步运算就能求得精确解的方法，但实际计算中由于舍入误差的影响，这类方法也但实际计算中由于舍入误差的影响，这类方法也只能求得近似解；例如：只能求得近似解；例如：等。等。构造适当的向量序列，构造适当的向量序列，。例如：。例如：等。等。8：上三：上三 角形方程组角形方程组 ，得，得 3211,0,1xxx11 11221122222nnnnnnnnu xu xu xyu xu xyu xy45610233771

4、232334561023377xxxxxx91121237=72+3=24+5+6=10 xxxxxx1231,0,1xxx7723245610101223345423377xxxxx3211,0,1xxx4504233771111 1122122223321,111,1,nnnnnnnn nnnu xu xdu xu xduxuxduxd11121222321,11,1nnnnnnnnuuduuduudud121231,0,1xxx11223774+642+33xxxxx7746423313顺序高斯消去法按方程和未知量的自然顺序进行。顺序高斯消去法按方程和未知量的自然顺序进行。：用逐次消去未

5、知数的方法：用逐次消去未知数的方法进行求解。求解分成两步进行求解。求解分成两步14顺序高斯消去法顺序高斯消去法: 。1 不作行交换。不作行交换。2 用不等于零的数乘某行，加至另一行。用不等于零的数乘某行，加至另一行。151231231232+43+262+25xxxxxxxxx1231231232+426+46 224+45 2xxxxxxxxx212323232+405+3803+36xxxxxxx 式5312323232+40+358 50+2xxxxxxx 式式式式1612323232+40+358 50+2xxxxxxx 式1232332+40+358 500252 5xxxxxx得到

6、得到123111xxA(2)的主元分别为的主元分别为 2，2.5，0.6 det A=det A(2) =22.50.6=3 22112.51.50.6A11121222nnnnaaaaaaA 1122detnnaaaAA181112111212222212,nnnnnnnnaaaxbaaaxbxaaaxbAbxAb11121121222212nnnnnnnaaabaaabaaabB增广矩阵19 111111121111111212222111112nnnnnnnaaabaaabaaabB增广矩阵11121121222212nnnnnnnaaabaaabaaabB增广

7、矩阵主方程20 111111121111111212222111112nnnnnnnaaabaaabaaabB增广矩阵 111111121111111111111111122122121111221212111111111111111121211111111nnnnnnnnnnnaaabaaaaaaabbaaaaaaaaaabbaaaB 110,1,2,iain设 111121aa 11111naa21 111111121111111111111111122122121111221212111111111111111121211111111nnnnnnnnnnnaaabaaaaaaabbaaa

8、aaaaaaabbaaaB 121111111121111111,2,3,ijijjiiiiaaaaai jnabbba22 1111111211222222222222nnnnnnaaabaabaabB增广矩阵 121111111121111111,2,3,ijijjiiiiaaaaai jnabbba23 111111112111222222222knknkkkkkkknkkkknknnnaaaabaaabaabaabB 增广矩阵 11,1,kkkkkkijijkjkikkkkkkkiikkikaaaaai jknabbba 0,1,kikaik kn 设 kkkknkaa24 11111

9、1112111222222222knknnkkkkkknknnnnnaaaabaaabaababB 增广矩阵 111,2,1,1,kkkkkkijijkjkikkkkkkkiikkikaaaaakni jknabbba25 111111112111222222222knknnkkkkkknknnnnnaaaabaaabaababB 增广矩阵 nnnnnnbxa 1,1,2,1niiiijjj iiiiiba xxina 26 111,2,1,1,kkkkkkijijkjkikkkkkkkiikkikknaaaaai jknabbba 1,1,2,1niiiijjnj innininniiba

10、xbxxinaa 27,1,i jkn 否是ijijikkjaaaa1,ikkkikaaaikn ，iiikkbbab1?kn1,2,1in nnnnbba1niiijjiij ibba ba 28111212122212nnnnnnaaaaaaaaaA111212122212kkkkkkkaaaaaaaaaA29111212122212kkkkkkkaaaaaaaaaA111212122212kkkkkkkkaaaaaaDaaaA 1111112122222kkkkkaaaaaa 121122kkka aa3031111212122212kkkkkkkkaaaaaaDaaaA 1111112

11、122222kkkkkaaaaaa 121122kkka aa 0,1,2,iiiain321,1,2,niiijjj iaain3334 111111121111111111111111122122121111221212111111111111111121211111111nnnnnnnnnnnaaabaaaaaaabbaaaaaaaaaabbaaaB 121111111121111111,2,3,ijijjiiiiaaaaai jnabbba35 11111111111121nnijijijjij iaaaaaa 121111111,2,3,ijijjiaaaai jna， 121111

12、11221nnijijjjjij ij iaaaaa 1111111221nnijjjjij ij iaaaa 111111111111111nijijij iaaaaaa36 111111111nijijij iaaaa 121111111,2,3,ijijjiaaaai jna， 11111122211nijjj inijjjij iaaaaa 111111111111111nijijij iaaaaaa 11111111iiiiaaaa 11111111iiiiaaaa 2iia 222nijiijj iaa 0,1,2,iiiain37 第i步 乘法次数 除法次数 1 2(1)n 1n

13、 2 2(2)n 2n 1n 1 1 合计 (1)(21)6n nn (1)2n n 38213n n 12n n12n n2213n nn33nn 较大时39顺序高斯消去法顺序高斯消去法当主元当主元 时无法进行；时无法进行；当主元当主元 ，但是，但是 很小，将严重影响计很小，将严重影响计算结果的精度。算结果的精度。 0kkka 0kkka kkka21213xxx方程组01 1113B增广矩阵40：避免用绝对值小的元素，作：避免用绝对值小的元素，作除数。除数。每次消元前选取一列中绝对值最大的元素每次消元前选取一列中绝对值最大的元素作为主元素。用这个主元素作除数，这样便可以作为主元素。用这个主

14、元素作除数，这样便可以减少舍入误差。减少舍入误差。，不增加求解过程的，不增加求解过程的运算量，而大大减小误差。运算量，而大大减小误差。41 111111112111222222222knknkkkkkkknkkkknknnnaaaabaaabaabaabB 增广矩阵 ,1,kikaik kn ,krkrak n42 257324111105558220555B 1354157324422B123123123354157324422xxxxxxxxx 5732354144223 54 5573282205554111105554312 3573282205550022B101x573282205

15、55411110555 257324111105558220555B44 列主元消去法中列主元消去法中： 121122det1mnnna aa A列主元法的消元列主元法的消元过程过程 其中，其中，m为消元过程中为消元过程中。 1354157324422B行交换行交换28det152165 A例如，例如，有，有 3573282205550022B45,1,i jkn 否是ijijikkjaaa a1,ikikkkaaaikn ，iikikbbba1?kn1,2,1in nnnnbba1niiijjiij ibba ba 46否是?inikda?dd,1,jk kn ljtaljkjaakkdal

16、k?ikadli否是是否?lk是kjatltblkbbkbt否47 1,2,kkkakn 111111122=nniiiiaaa严严格格对对角角占占优优：ijjiaa对对称称矩矩阵阵： 112maxii na 111a48 11122=nnkkkiikiiaaa严严格格对对角角占占优优：ijjiaa对对称称矩矩阵阵： 222a 121111111,2,3,iijijjaaaai jna 112111121111111111,2,3,iiijijjjijjiaaaaaaaai jnaa kkka49：当消元过程进行到第当消元过程进行到第k步时，从右下角步时，从右下角n-k+1阶子阶子阵中选择阵中

17、选择max(akj,ajk, j=k,n) 作为主元作为主元 ，实，实现过程既要进行现过程既要进行，也要进行，也要进行。 kkka50前面学习的前面学习的都包含都包含 和和 两个过程。两个过程。当消元过程稍加改变，就可以使系数矩阵变为当消元过程稍加改变，就可以使系数矩阵变为，这时就，这时就了，了，Dxb 111222kkkaaaD51：在高斯消去法的消元过程中，消元时在高斯消去法的消元过程中，消元时，最后系数矩阵化为，最后系数矩阵化为。这种算。这种算法法只有消元只有消元，没有回代没有回代。 52 11831151233151116BB 3183115717310618622660077B 41

18、83012714006622660077B 5180018714006622660077B11x 22x 33x 17 718 227122 53 25100101020013B 5180018714006622660077B11x 22x 33x 54 24100101020013B 11831151233151116BB在在归一化归一化消元完成后消元完成后 5532n56-1nAAI111-1121,nnnnnxxxxAx xx12100010,0001nnIe eeiiAxe 25100101020013BnAI1nIA57111210110A 1111100210010110001BB

19、 2111100012210021101B 3101110012210003321B 410001 31 301001 32 300112 31 3B101 31 301 32 312 31 3AAnI1AnI第第3 3章章 线性方程组的数值线性方程组的数值解法解法2022年5月21日星期六59第第3 3章章 线性方程组的数值解法线性方程组的数值解法3.1 3.1 高斯消去法高斯消去法3.2 3.2 矩阵三角分解法矩阵三角分解法3.3 3.3 平方根法平方根法3.4 3.4 向量和矩阵的范数向量和矩阵的范数3.5 3.5 方程组的形态和误差分析方程组的形态和误差分析3.6 3.6 迭代法迭代法

20、3.7 3.7 迭代法的收敛性（选）迭代法的收敛性（选）60矩阵三角分解法是高斯消去法的变形方法。矩阵三角分解法是高斯消去法的变形方法。高斯消去法解线性方程组高斯消去法解线性方程组 ，然后，然后 。这些。这些过程可以通过过程可以通过来实现。来实现。高斯消去法用高斯消去法用来描述时，是对系数矩阵分解来描述时，是对系数矩阵分解成为一个上三角矩阵和一个下三角矩阵的乘积，即成为一个上三角矩阵和一个下三角矩阵的乘积，即。61则对系数矩阵则对系数矩阵进行进行等价于用等价于用，在对方程组第，在对方程组第1次消次消元后，有。元后，有。 121121M AAM bb62则对系数矩阵则对系数矩阵进行进行等价于用等

21、价于用，在对方程组第，在对方程组第1次消次消元后，有。元后，有。 121121M AAM bb为下三角矩阵为下三角矩阵211311100001000= 1000100nlllM 11,2,3,kkkikikalkina63在对方程组在对方程组后，有后，有 11kkkkkkM AAM bb1,2,100000010000001000=0010000100001000kkkkkn klllM 1,1 ,2,3,kkkikkikalknina64记，记， ，L是是下下三角矩阵，三角矩阵， 是上三是上三角矩阵。角矩阵。是对是对k=1到到n-1进行的，因此有进行的，因此有 11211121nnnnMM

22、M AAMM M bb 1121nnLMM MUA这样，这样， 1111nL AUL bb nALUbLb6566这里这里A的的有有2种，种，。例如例如：2341A一般地，任取与一般地，任取与AD，则对，则对LU分解分解有，有，1111ALUAL DDULDD ULU10232305/3 10232105 I67杜里特尔分解杜里特尔分解(Doolittle)克洛特分解克洛特分解(Crout)111212122212111nnnnnnuuuluullu 111212122212111nnnnnnluullulll 68111212122212111nnnnnnuuuluullu ALU0,1,2

23、,iiuin691122ALUL U112121L LU U70设设 讨论讨论a 取何值时，取何值时，矩阵矩阵A可作可作LU分解。分解。1221aA当当A的顺序主子式不为零时，矩阵的顺序主子式不为零时，矩阵A有有LU分解分解 所以，有所以，有10a 12 20a 1a 3a 111212122212kkkkkkkkaaaaaaAkDaaaA矩阵 的第 阶顺序主子式710110AA是非奇异矩阵，假设存在是非奇异矩阵，假设存在LU分解分解 比较等式比较等式，有，有0110=1010bdbdacabadc 01bab两式显然矛盾，所以该非奇异矩阵两式显然矛盾，所以该非奇异矩阵A不存在这样的不存在这样

24、的LU分解。分解。7211121112122222111211221222121212111rinrinnrrrrrirnniiiriiinnnnnnnnrninnaaaaaaaaaauuuaaaaaluuaaaaalluaaaaa 1111 11,1,2,2,3,jjjjaujnal ujn111111,1,2,2,3,jjjjuajnlaujn7311121112122222111211221222121212111rinrinnrrrrrirnniiiriiinnnnnnnnrninnaaaaaaaaaauuuaaaaaluuaaaaalluaaaaa 221 1221 12222,2,

25、3,3,4,jjjjjjal uujnal ul ujn2221 1221 1222,2,3,3,4,jjjjjjual ujnlal uujn7411121112122222111211221222121212111rinrinnrrrrrirnniiiriiinnnnnnnnrninnaaaaaaaaaauuuaaaaaluuaaaaalluaaaaa 1111,1,1,2,rrjrkkjrjkrjrjkkrjrrrkal uujr rnal ul ujrrn1111,1,1,2,rrjrjrkkjkrjrjrjkkrrrkual ujr rnlal uujrrn7511111212112

26、1212222313132322332nnnnnnnnnnauauaualaaualalauauu1111,1,1,2,rrjrjrkkjkrjrjrjkkrrrkual ujr rnlal uujrrn76223477245A1112132122233132332231477 =12451uuuluulluA77111213212223313233122314771245uuuluullu112u122u133u21 112142l ul21 12222273l uuu21 13232371l uuu31 113121l ul 31 1232223242l ul ul31 133223333

27、356l ul uuu2231223477 =21312451216A11223336u u uA78223477245A 2222334273712142562231223477 =21312451216A11223336u u uA79212431615A121221133217A80158412293A115841193021117 A8122342491648246461651 100A122341126122216323521-36A828311212212111nnnnyblybllyb 111211122222nnnnnnuuuxyuuxyuxy112112211,2,3,iij

28、jiijybl yybl yybin1111,2,3,iiiijjjybybl yin1,1,2,1nnnnniiijjiij ixyuxyu xuinn 33n84123123123223347712457xxxxxxxxx 1112132122233132332231477 =12451uuuluulluA85111213212223313233122314771245uuuluullu112u122u133u21 112142l ul21 12222273l uuu21 13232371l uuu31 113121l ul 31 1232223242l ul ul31 133223333

29、356l ul uuu2231223477 =21312451216A86122321311216LU12313:2111217yyyLyb317b112233223:316xyxyxyUxy123356yyy y123221xxx x871111,1,1,1,2,rrjrjrkkjkrjrjrjkkrrrkual ujr rnlal uujrrn1112111212222211121122122212121212111rinrinnrrrrrirnniiiriiinnnnnrninrninnaaaaaaaaaauuuaaaaaluuaaaaallaaaababbbb 1,12,1,1nnnn

30、nnuuuu1,11,1,11,1nn nnn nnabaubuyLL88 111112121111212122222231313232333232nnnnnnnnnnnnauauaubyalaaubyalalaubyaubyu1111,1,1,2,1rrjrjrkkjkrjrjrjkkrrrkual ujr rlal uujrrnn89123123123223347712457xxxxxxxxx 111213121222323132333223314771 =124571uuuyluuylluyB90111213121222323132333122331477112457uuuyluuyll

31、uy112u122u133u21 112142l ul21 12222273l uuu21 13232371l uuu31 113121l ul 31 1232223242l ul ul31 133223333356l ul uuu223316U13y 2112215l yyy 3113223376ll yyyy 356y 221 Uxyx91123422341249161482463361651 10029xxxx111213141212223242313233343414243444122341124916114824633161651 10029uuuuyluuuylluuyllluyB

32、112u122u133u11y 144u211l222u236u20y 2412u312l322l336u31y 3431u413l425l432l434y 4434u 921234223412612063113434xxxxUyx112u122u133u11y 144u211l222u236u20y 2412u312l322l336u31y 3431u413l425l432l434y 4434u 12343951xxxx93111122211A111213111213212223212223313233313233111111122112111uuuyyyluuyyylluyyy941112

33、13111213212223212223313233313233111111122112111uuuyyyluuyyylluyyy111u121u131u 111y120y211l221u231u 211y 221y312l 323l332u315y323y 130y230y331y123111112iiiiixxxUyx1121311115yyy y1222322013yyyy1323333001yyy y95123111112iiiiixxxUyx1121311115yyy y2122232013yyyy3132333001yyy y112131121.52.5xxxx122232210.

34、51.5xxx x132333300.50.5xxxx11232101.50.50.52.51.50.5Axxx9611112222211111nnnnnnnnnbcxfabcxfabcxfabxfAxf971111222221111111nnnnnnnnbcluabcluabclab ALU981111222221111111nnnnnnnnbcluabcluabclab ,2,3,iiain11lb,1,2,1jjjl ucjn111,1,2,1jjjjaulbjn99,2,3,iiain11lb,1,2,1jjjl ucjn111,1,2,1jjjjaulbjn11lb,1,2,1jjj

35、cujnl111,1,2,1jjjjlbaujn11220:inllululALU1000,1,2,ilin0,1,2,ilin0,1,2,ilin101110bc0,0,2,3,1iiiiibaca cin且0nnba1111222221111111nnnnnnnnbcluabcluabclabA10211bc,2,3,1iiibacinnnba1111222221111111nnnnnnnnbcluabcaluabcalab 103ALUL UxfAxfUxyLyfLyf首先求解方程组：1111222221111111nnnnnnnnbcluabcaluabcalabALUAxf11122

36、22nnnnlyfalyfalyf104Lyf首先求解方程组：1111,2,3,iiiiil yfa yl yfin1112222nnnnlyfalyfalyf1111,2,3,iiiiiyflyfa ylinUxy然后求解方程组：111221111nnnxyuxyuxy1051,1,2,1nniiiixyxu xyin1,1,2,1nniiiixyxyu xinUxy然后求解方程组：111221111nnnxyuxyuxyLyfUxy106123421313212420355xxxx12l 11 2u 25 2l 24 5u 312 5l 35 6u 415 2l11223342111132

37、1224213351lululul107123421313212420355xxxx215 2212 535 2L11 214 515 61ULyf首先求解方程组：12342315 21212 5035 25yyyy1083 215 61yLyf首先求解方程组：12342315 21212 5035 25yyyyUxy然后求解方程组：123411 23 214 5115 65 611xxxx1092101xUxy然后求解方程组：123411 23 214 5115 65 611xxxx第第3 3章章 线性方程组的数值线性方程组的数值解法解法2022年5月21日星期六111112113xBx+

38、f 1,0,1,kkkxBx+ f limkkxxAxb114xBx+ f 1,0,1,kkkxBx+ f limkkxx115xBx+ f 1,0,1,kkkxBx+ fMN xb11xMNxM bxBx+ f11BMNfM b116xxAxbxBx+ f BIAfbxIA xb1171112111212222212,nnnnnnnnaaaxbaaaxbxaaaxbAb11121222121200+0nnnnnnaaaaaaaaaAMN11811121222121200+0nnnnnnaaaaaaaaaAMNAxMN xb11xM bMNx 111kkxM bMNx119 111111121

39、1111111221222222211112000kknkknkknnnnnnnnnxxbaaaabaaaaxxbaaaaxx 111kkxM bMNx 1111nkkiiiiiiijjjj ixbaaa x 111nkkiiiiijjjj ixaba x120max?iixy是否是否0?,1,.,iiain是否111,2,niiiiijjjj iyaba xin121例例3-27： 用雅可比迭代法求解方程组用雅可比迭代法求解方程组 1231231231023210152510 xxxxxxxxx解：解： 从从3个方程分离出个方程分离出1232133120.20.10.30.20.11.50.

40、20.42xxxxxxxxx构造雅可比迭代公式构造雅可比迭代公式 1123121313120.20.10.30.20.11.50,1,0.20.42kkkkkkkkkxxxxxxkxxx122(0)00,0,0Tx(1)10.3x(1)21.5x(1)32x 1123121313120.20.10.30.20.11.50,1,0.20.42kkkkkkkkkxxxxxxkxxxk012345 x1(k)00.30.800.91800.97160.9894 x2(k)01.51.761.92601.97001.9897 x3(k)02.02.662.86402.95402.9823 1,2,3Tx精确解：123迭代收敛时，新值迭代收敛时，新值xi(k+1) 比老值比老值xi(k) 更准确更准确，而在，而在中中，第，第k+1次迭代只用