數(shù)值計(jì)算方法解線性方程組的數(shù)值解法PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 數(shù)值計(jì)算方法解線性方程組的數(shù)值解法數(shù)值計(jì)算方法解線性方程組的數(shù)值解法 2 第1頁/共53頁 3 第2頁/共53頁 4 nnnnnn nn nn bxaxaxa bxaxaxa bxaxaxa . . . . 2211 22222121 11212111 第3頁/共53頁 5 nnij n n n a aaa aaa aaa )(A n2n1n 22221 12111 T n T n bbbxxxbx 2121 , 第4頁/共53頁 6 代替所得。列用的第是 ，其中 ，法則： biAA AD ni D D xGramer i ii i i )det(0A)det(D ,.,2 , 1

2、第5頁/共53頁 7 ) 3(122 )2(54 ) 1 (6 321 32 321 xxx xx xxx 第6頁/共53頁 8 )4(114 )2( 54 ) 1 (6 32 32 321 xx xx xxx 第7頁/共53頁 9 )5(62 )2(5 ) 1 (6 3 32 321 x xx xxx 第8頁/共53頁 10 nil bxlxlxl bxlxl bxl ii nnnnnn ,.,2 , 1, 0 . . 2211 2222121 1111 其中， 第9頁/共53頁 11 1 1 2212122 11 1 1 /)( . /)( n i nnininn lxlbx lxlbx

3、l b x 該法稱為向前代入法。 即ni lxlbx lbx ii i j jijii ,.,3 , 2 / )( / : 1 1 1111 第10頁/共53頁 12 ;/ )( ; 11 ; 0 nto2i3 /2 ; ), 2 , 1, 2 , 1(,1 1111 iiii jij iij lsbx xlss doitojFor s doFor lbx ijnibl 、 、 、賦初值 第11頁/共53頁 13 nnnn lll ll l L Lbx 21 2221 11 (1)其中式可簡寫成， 第12頁/共53頁 14 ,.,n,iu bxu . bxu.xu bxu.xuxu ii nn

4、nn nn nn 210 )2( 22222 11212111 其中， 第13頁/共53頁 15 12,.1 1 ,ni )/uxu(bx /ubx ii n ij jijii nnnn 第14頁/共53頁 16 nn n n u uu uuu U Ubx 222 11211 (2)其中式可簡寫成， 第15頁/共53頁 17 0 ii a T n nnn n n i i i bbbbb aa aa aaa ni a a l n a a . . . . . AA ,.,3 , 2, .,32ii)( )2()2( 2 )1( 1 )2()1( )2()2( 2 )2( 2 )2( 22 )1(

5、1 )1( 11 )1( 11 )2(1 )1( 11 )1( 1 1 )1( 11 )1( 1 ）（ 令 ），行（第第一行 第16頁/共53頁 18 ),.,2;,.,2( )1( 11 )1( 1 )1( 1)1( )1( 11 )1()2( njni a aa a alaa ji ij jiijij ),.,2(. )1( 1 )1( 11 )1( 1 )1( 1 )1( 1 )1()2( nib a a b lbbb i i iii 第17頁/共53頁 19 )( )( )2( 2 )1( 1 )()( )()( )2( 2 )2( 22 )1( 1 )1( 12 )1( 11 )()

6、( . . . . . . . . | k n k k k nn k nk k kn k kk n n kk b b b b aa aa aa aaa bA 第18頁/共53頁 20 nkjnkialaa k kjik k ij k ij ,.,1;,.,1 )()()1( ， 則有 ，令1,.,2 , 1,.,1 )( )( nknki a a l k k k ik ik nkiblbb k kik k i k i ,.,1 )()()1( ， 第19頁/共53頁 21 )( )( )2( 2 )1( 1 )( )()( )2( 2 )2( 22 )1( 1 )1( 12 )1( 11 )(

7、)( . . . . . . . . n n k k n nn k kn k kk n n nn b b b b a aa aa aaa bA 第20頁/共53頁 22 ) 1,.,2 , 1( ,.,1 ,.,1 / )()()1( )()()1( )()( nk nkj nki lbbb alaa aal ik k k k i k i k kjik k ij k ij k kk k ikik 第21頁/共53頁 23 )( )( )2( 2 )1( 1 )( )()( )2( 2 )2( 22 )1( 1 )1( 12 )1( 11 )( )()n( . . . . . . . . )(

8、| A n n k k n nn k kn k kk n n n n b b b b a aa aa aaa n Ab bx 其中 得到 第22頁/共53頁 24 ) 1,.,1(/ ).( / A )( 1 )()( )()( )()( niaxabx abx i ii n ij j i ij i ii n nn n n nn bx 回代法 再解 第23頁/共53頁 25 ；做對(duì) ； ； 做對(duì) 機(jī)；輸出算法失敗信息，停 做對(duì) 輸入： kjikijij kikii kkikikik kk iij alaankj blbb aala nki a nk nibnjia ,.,3 2 /1 ,.,)

9、2 thenif) ,.,)( ),.,(),.,() 1 ( 0 0 0 1 1 01 1212 2121 第24頁/共53頁 26 )det(),.,()( .)(det) 3 / )( ,.,)2 /) 1 else,thenif)( AAnix aaaA axabxb ni abxb a i nn ii n ij jijiii nnnnn nn 的行列式的值系數(shù)矩陣輸出：方程組的解 ； ； 做對(duì) ； 做并停機(jī)輸出算法失敗信息 214 121 03 2211 1 第25頁/共53頁 27 第26頁/共53頁 28 次除法。即做kn ),.,1i (/: )()( nkaalk k kk

10、k ikik 步第 : ) 1)( )1()( 故總的消元計(jì)算量為 次乘法需由 knknAA kk 1 1 )52)(1( 6 1 )1)()( n k nnnknknkn ) 1( 2 1 )()( nnbXA nn 回代時(shí)乘除運(yùn)算量為解 ) 13( 3 1 2 nnnN即總計(jì)算量為 第27頁/共53頁 29 nka k kk ,.,2 , 1, 0 )( 高斯順序消去法要求 0.)det( )()2( 22 )1( 11 n nn aaaA有： .也就是此算法的缺點(diǎn) ., , 00: )( )()( 即數(shù)值不穩(wěn)定做除數(shù)易產(chǎn)生解的失真用此時(shí) 很小，但若即使 k kk k kk k kk a

11、aa 第28頁/共53頁 30 1 1 11 max i ni aa nnnnn iinii n baaa baaa baaa baaa . . . . . . 21 21 2112221 111211 交換 第29頁/共53頁 31 順序消元 計(jì)算機(jī)中實(shí)現(xiàn) )3 ;:; 1)2 ;|;|maxmax| 2 1;i ; |max 1) 11 11 1 TaaaaT dontojfor kiathenaif dontokfor a ijijjj kk i 第30頁/共53頁 32 (k) kk a 1 )( A k (k) nk .a. (k) kk a k k ik k ki ilaa k 記

12、|max| )( nik )( kl 第31頁/共53頁 33 第32頁/共53頁 34 輸出奇異標(biāo)志，停機(jī)； ； 做對(duì) ； 即記選列主元： 做對(duì) 輸入： then0if)2 ,then|if ,., | ,|,|max|) ,.,)( ),.,(),.,() 1 ( max maxmax max a ilaaaa nkki aakl ilaa nk nibnjia ikik kk kik nik ki iij k 21 1 1212 2121 第33頁/共53頁 35 ；做對(duì) ； ； 做對(duì) ； ； 做對(duì) 行所有對(duì)應(yīng)元素，即行與第交換第 kjikijij kikii kkikikik iikk

13、 ljljkjkj alaankj blbb aala nki TbbbbT TaaaaT nkkj lkkl ,.,3 2 /1 ,.,)4 ;2 ; ,.,1 then if) 3 0 0 0 0 0 1 1 1 第34頁/共53頁 36 。輸出：方程組的解 ； 做對(duì) ； 并停機(jī)輸出奇異標(biāo)志 回代求解 ),.,()( / )( ,.,)2 /) 1 else,thenif )( nix axabxb ni abxb a i ii n ij jijiii nnnnn nn 214 121 0 3 1 第35頁/共53頁 37 T x x x x )3675. 0 ,05104. 0,4904

14、. 0( :4,4 000. 3 000. 2 000. 1 643. 5072. 1000. 2 623. 4712. 3000. 1 000. 3000. 2001. 0 * 3 2 1 位有效數(shù)字為精確解舍入到位浮點(diǎn)數(shù)進(jìn)行計(jì)算用 第36頁/共53頁 38 .)4000. 0 ,09980. 0,4000. 0( 00. 2 002. 1 000. 1 00. 500 005. 32.0040 000. 3000. 2001. 0 003. 2 002. 1 000. 1 006. 6001. 40 005. 32.0040 000. 3000. 2001. 0 000. 3 000. 2

15、 000. 1 643. 5072. 1000. 2 623. 4712. 3000. 1 000. 3000. 2001. 0 )|A( . 是一個(gè)很壞的解解得 用高斯順序消去法求解 T x b 第37頁/共53頁 39 T x b )3676.0,51080.0,88544.0( 6866.0 500.0 000.3 8676.100 8015.13.1760 5.6431.00722.000- 0015.1 500.0 000.3 0023.30005.20 8015.13.1760 5.6431.00722.000- 000.1 000.2 000.3 000.3000.2001.0

16、623.43.7121.000- 643.5072.1000.2 000.3 000.2 000.1 643.5072.1000.2 623.4712.3000.1 000.3000.2001.0 )|A( . 3i 得 用選列主元消去法求解 第38頁/共53頁 40 ； ，對(duì) ； 中選絕對(duì)值最大者從選主元 、第一步消元 jtilathen aifdo njni tla njia ij ij ij |max |max ,.,1,.,1 ; 11|max .),.,2 , 1,(,) 1 1 11 第39頁/共53頁 41 順序消元； ；做， 初值蹤數(shù)組序發(fā)生改變，因此設(shè)跟 解的次而交換列時(shí)解的

17、次序不變交換行時(shí) ；列交換第一列與第 ；行交換第一行與第 ) 3 )() 1 (,)Z(.2)Z(21)Z(1 ),( , ),.,2 , 1(: ),.,2 , 1(:)2 1 1 tZZnn iZ niaat njaal iti ljj 第40頁/共53頁 42 順序消元 列列交換 行行交換如果 ； 步選主元時(shí)得）假設(shè)第 步消元：、第 )2 )()(;, ;, ;|max 1 2 )( ; )( tzkztkkt lkkl jtilaa k k kk k ij njik k ji kk 第41頁/共53頁 43 ),.,2 , 1()(: )( )(),2(),1 ( 3 21 nibiz

18、xnx nzxbzxbzxb i n 則增加數(shù)組 理順解： 、求方程組的解 第42頁/共53頁 44 求最終的解。 。程序結(jié)束后，例如 332211 , 1) 3(, 2)2(, 3) 1 (: bxbxbx zzz ) 3() 1 (31ZZjj分析：做 。 ； ；其解 ，這時(shí) 3 2 1 ) 1 ()3( )2()2( ) 3()1 (: 2)2(, 1) 3(, 3) 1 ( bxzx bxzx bxzx zzz 第43頁/共53頁 45 ； 做對(duì) 做對(duì) ； 即記選全主元： 做對(duì) 輸入： jtilaaaa nkkj nkki aaktkl jtilaa nk niiiz nibnjia

19、ijij kk kkij njik ji iij kk ,|,|then|if ,., ,., |; ,|,|max|) ,.,)( );,.,()()( ),.,(),.,() 1 ( maxmax max , 21 21 1 1213 212 2121 第44頁/共53頁 46 ；做對(duì) ； ； 做對(duì) ；輸出奇異標(biāo)志，并停機(jī) kjikijij kikii kkikikik itik lkljkj alaankj blbb aala nki tzkzniaakt bbnkkjaakl a ,.,3 2 /1 ,.,)4 );()();,.,(then if ;);,.,(then if)3 t

20、hen0if)2 0 0 0 max 1 1 21 1 第45頁/共53頁 47 。輸出解 ； ； 做對(duì) ； 并停機(jī)輸出奇異標(biāo)志 ),.,()( ),.,()() 3 / )( ,.,)2 /) 1 else,thenif)( nix nibizx ababb ni abb a i i ii n ij jijii nnnn nn 215 21 121 04 1 第46頁/共53頁 48 )( )( 1 )( 1 )()( )( 1 )( 1 )( 1 )( 1 )()( 1 1 A k n k k k k nn k nk k kk k kk k n k k kk b b b aa aa aa b 第47頁/共53頁 49 Tn n nn k k k ik k i k i k kj k ik k ik k ij k ik k kk k k k