計算方法第5章解線性方程組直接方法

1、2021-7-10計算方法第5章解線性方程組直接 方法 1 解線性方程組的直接方法解線性方程組的直接方法 2021-7-10計算方法第5章解線性方程組直接 方法 2 第五章第五章 解線性方程組的直接方法解線性方程組的直接方法 5.1 5.1 引言引言 解線性方程組的兩類方法： 直接法: 經(jīng)過有限次運算后可求得方程組精確解的 方法(不計舍入誤差) 迭代法：從解的某個近似值出發(fā)，通過構(gòu)造一個無窮 序列去逼近精確解的方法。（一般有限步內(nèi)得不到精 確解） 2021-7-10計算方法第5章解線性方程組直接 方法 3 , X , 11 T n n ij AXb T A nn , , ) , , )(x(b

2、 xbab 矩陣表示記為 這里 nnnnnn nn nn bxaxaxa bxaxaxa bxaxaxa 2211 22222121 11212111 n階線性方程組 2021-7-10計算方法第5章解線性方程組直接 方法 4 35 det( )0, det() (1,2, ) det( ) 1 (1)! 30,2.38 10 i i A A xin A nnn nnn n n 如果線性方程組的系數(shù)行列式不為零，即 則該方程組有唯一解。由克萊姆(cramer)法則，其解為 這種方法需要計算個 階行列式并作 次除法，而每個 階行列式計算需作次乘法，計算量十分驚人。 如需次乘法?？梢娖湓诶碚撋鲜墙^

3、對正確， 但在 較大時，在實際計算中確實不可行的。 35 det( )0, det() (1,2, ) det( ) 1 (1)! 30,2.38 10 i i A A xin A nnn nnn n n 如果線性方程組的系數(shù)行列式不為零，即 則該方程組有唯一解。由克萊姆(cramer)法則，其解為 這種方法需要計算個 階行列式并作 次除法，而每個 階行列式計算需作次乘法，計算量十分驚人。 如需次乘法?？梢娖湓诶碚撋鲜墙^對正確， 但在 較大時，在實際計算中確實不可行的。 2021-7-10計算方法第5章解線性方程組直接 方法 5 5.2 5.2 高斯消去法高斯消去法 11112211 2112

4、2222 1122 nn nn nnnnnn n a xa xa xb a xa xa xb a xa xa xb 對 階線性方程組： 11 , nn xxx 稱消元過程。 逐次計算出稱回代過程。 (1)(1)(1)(1)(1) 11112213311 (2)(2)(2)(2) 22223322 (3)(3)(3) 33333 nn nn nn a x a xa xa xb a xa xa xb a xa xb ( )( ) nn nnnna xb 轉(zhuǎn)化為同解的方程組 2021-7-10計算方法第5章解線性方程組直接 方法 6 11 bbaa )( ii )( ijij , 統(tǒng)一記號： 111

5、11 11 1 T ( )( )( )( )( ) ij ( )( ) X : , n (, , )babAA bb 原方程 )( )( :0 1 11 1 21 )1( 11 新第二行（第一行）第二行 若 aa a )()( )( )()( 1 11 1 31 新第三行第一行第三行 aa )()( )n(n aa )()( n 行新第（第一行）行第 )( 1 11 1 1 5.2.1 5.2.1 高斯消去法計算過程高斯消去法計算過程 2021-7-10計算方法第5章解線性方程組直接 方法 7 (1)(1)(1)(1)(1) 11112213311 (2)(2)(2)(2) 22223322

6、(2)(2)(2)(2) 32233333 (2)(2) 2233 nn nn nn nn a x a xa xa xb a xa xa xb a xa xa xb a xa x (2)(2) nnnna xb 2021-7-10計算方法第5章解線性方程組直接 方法 8 22 x bA （ ）（ ） 得到新同解方程組： b b b b aa aa aaa A nnnn n n )2( )2( 2 )1( 1 (2) )2()2( 2 )2( 2 )2( 22 )1( 1 )1( 12 )1( 11 )2( 0 0 ，其中 aamamaa )()( ii )( ji )( ij )( ij 1

7、11 1 11 1 11 12 211 11 2 3 , ()()() iii , , ,n i jbbbm 2021-7-10計算方法第5章解線性方程組直接 方法 9 子陣作如上計算： 對除第一行第一列外的，若第二步消元： 0 )2( 22a 00 00 0 3 3 3 2 2 1 1 (3) 33 3 3 3 3 33 2 2 2 23 2 22 1 1 1 13 1 12 1 11 3 b b b b b aa aa aaa aaaa A )( n )( )( )( )( nn )( n )( n )( )( n )()( )( n )()()( )( =， aamamaa ijijij

8、 )2( 22 )2( 2i2 )2( 2i2 )2()3( 322 22 3 4, ()()() iii , , ,n i j bbbm 2021-7-10計算方法第5章解線性方程組直接 方法 10 bxA )()(33 =得到同解方程組 行下去則此消去過程可依次進，若 0 )3( 33 a ( )( ) 1 nn n x bA 第步消去過程后， 得到等價三角方程組。 (1)(1)(1)(1)(1) 11112213311 (2)(2)(2)(2) 22223322 (3)(3)(3) 33333 nn nn nn a x a xa xa xb a xa xa xb a xa xb ( )(

9、 ) nn nnnna xb 2021-7-10計算方法第5章解線性方程組直接 方法 11 (1)(1)(1)(1)(1) 11121311 (2)(2)(2)(2) 222322 (n)( ) (3)(3)(3) 3333 ( )( ) 0 00 000 b n n n n nn nnn aaaab aaab A aab ab ， 系數(shù)矩陣與常數(shù)項： 2021-7-10計算方法第5章解線性方程組直接 方法 12 回代過程: (1)(1)(1)(1) 111111 ( )( )( ) (1)(1)(1) 11111 iinn iii iiiinni nnn nnnnnnn a xa xa xb

10、 a xa xb axaxb ( )( ) nn nnnna xb abx )n( nn )n( nn = ( )( )( ) 1 () in1 , n2 , , 1 n iii iiijjii j i xba xa 2021-7-10計算方法第5章解線性方程組直接 方法 13 123 23 123 133233 6; 45; 221. 11161116 |04150415 221104111 1116 0415 0026 ( 2), xxx xx xxx A b rrrrrr 例1：用消去法解方程組 解：用增廣矩陣表示求解過程 2021-7-10計算方法第5章解線性方程組直接 方法 14 消

11、去第一列的 n-1 個系數(shù)要計算n*(n-1） 個乘法。 1 2 2)n()*(n-n二 )(n n k) (k n k 1 3 2 1 2 乘法總計 2 1 1 1 )n(n k n k 除法 1 2 n(n) 回代總計算量 3 21 (30,9890) 33 nn n n 總乘除法共為 5.2.2 5.2.2 高斯消去法計算量高斯消去法計算量 2021-7-10計算方法第5章解線性方程組直接 方法 15 (2)(1)(2)(1) 11 1121 1111 311 1 , 1 1 01 2 3 001 L ( )( ) ii n i, ,n bbAL AL m m aa m m 記： 其中

12、每一步消去過程相當(dāng)于左乘初等變換矩陣Lk 5.2.3 5.2.3 矩陣的三角分解矩陣的三角分解 2021-7-10計算方法第5章解線性方程組直接 方法 16 (3)(2)(3)(2) 22 22 2222 322 2 , 1 01 01 3 4 001 L ()() ii n i, ,n bbAL AL m aa m m 記： (3)(1)(3)(1) 2121 , bbAL L AL L 2021-7-10計算方法第5章解線性方程組直接 方法 17 1 121 1 121 (n)() nn (n)() nn ALLL A bbLLL -1 i 1, 1, 1 1 01 01 1 1 01 0

13、1 01 01 i i ii ii ni ni LL m m m m 列 i列 i+1行 i+1行 -1 iiLL 與依次遞推 2021-7-10計算方法第5章解線性方程組直接 方法 18 LUULLLAA n 1 1 1 2 1 1 )1( 1 1 1 21 211 1 1 2 1 1 mm m nn n LLLL 定理定理7 7（矩陣的（矩陣的LULU分解）分解） 設(shè)A為n階矩陣，如果A的順序主子式順序主子式 D Di i0 0（i=1，2，n-1），則A可分解為一個單位下 三角矩陣L和一個上三角矩陣U的乘積，且這種分解是 唯一唯一的。 )(n AU 2021-7-10計算方法第5章解線性

14、方程組直接 方法 19 ( ) ( ) 213132 1 11161116 |04150415 221104111 1116 0415 0026 (1, ) 0,2,1, k ik kik kk A b a mikn a mmm 例2：對于例 ，由增廣矩陣表示消元過程有 由 故有 100111 010041. 211002 ALU 2021-7-10計算方法第5章解線性方程組直接 方法 20 5.3 5.3 高斯主元素消去法高斯主元素消去法 ( ) ( ) 0 0 k kk k kk a a 在高斯法消元過程中可能出現(xiàn)的情況，這時消去法 將無法進行；即使主元素但很小，用其作除數(shù)，也會 導(dǎo)致其他

15、元素數(shù)量級的嚴(yán)重增長和舍入誤差的擴散。 為避免此種情況的發(fā)生，可通過交換方程的次序，選取絕對值大絕對值大 的元素作主元。 5.3.1 列主元素消去法 2021-7-10計算方法第5章解線性方程組直接 方法 21 nkkjiaa k ij k kk , 1,max )()( 選取 或 nkkiaa k ik k kk , 1,max )()( 稱此方法為全主元素高斯消去法 稱此方法為列主元素高斯消去法 2021-7-10計算方法第5章解線性方程組直接 方法 22 1 2 3 * 0.0012.0003.0001.000 31.0003.7124.6232.000 2.0001.0725.6433

16、.000 ( 0.4904, 0.05104,0.3675) 1 0.0012.0003.0001.000 |1.000 T x x x x A b 例 ：階方程組 四位有效數(shù)字精確解為 解：（ ）高斯消去法 21 22 32 1000 2000 1.997 3.7124.6232.000 2.0001.0725.6433.000 0.001 2.0003.000 1.0000.001 2.0003.0001.000 02004300510020200430051002 0400160062003005.0002.000 ( 0. m m m x 400, 0.09989,0.4000)T 3

17、 2021-7-10計算方法第5章解線性方程組直接 方法 23 21 22 0.5000 0.0005 2 2.0001.0725.6433.000 |1.0003.7124.6232.000 0.0012.0003.0001.000 2.0001.0725.6433.000 03.7121.8010.500 02.001 3.003 1.002 m m A b （ ）交換行，避免絕對值小的主元作除數(shù)。（列主元素法） 32 0.6300 2.0001.0725.6433.000 03.7121.8010.500 001.8680.687 ( 0.4900, 0.05113,0.3678) m

18、T x 31 rr 2021-7-10計算方法第5章解線性方程組直接 方法 24 定理8（列主元素的三角分解定理） 如果A為非奇異 矩陣，則存在排列矩陣P使 PA=LU 其中L為單位下三角陣，U為上三角陣。 2021-7-10計算方法第5章解線性方程組直接 方法 25 3 2 GaussJordan A n 消去對角線下方和上方的元素，此方法稱 消去法。G-J方法將 約化為單位矩陣，計算解就在常數(shù)項 得到，無需回代求解。計算量大約需次乘除法，要比高 斯消去法大。G-J方法主要用途是求一個矩陣的逆矩陣。 1 123 5 G-J245. 356 123100356001 |245010245010

19、 356001123100 n AA A I 例 ： 用法求的逆矩陣 解： 5.3.2 5.3.2 高斯高斯若當(dāng)消去法若當(dāng)消去法 2021-7-10計算方法第5章解線性方程組直接 方法 26 1 15/32001/3 02/31012/3 01/31101/3 101/205/22 013/203/21 001/211/20 100132 010331|. 001210 n IA 2021-7-10計算方法第5章解線性方程組直接 方法 27 本章作業(yè) P176 7 2021-7-10計算方法第5章解線性方程組直接 方法 28 5.4 矩陣三角分解法矩陣三角分解法 5.4.1 直接三角分解法直接

20、三角分解法 將高斯消去法改寫為緊湊形式，可以直接從矩陣A的元素 得到計算L,U元素的遞推公式，而不需要任何中間步驟， 這就是直接三角分解法。 由于A=LU，求解Ax=b的問題就等價于求解兩個三角形方程組 Ly=b，求y； Ux=y，求x. 2021-7-10計算方法第5章解線性方程組直接 方法 29 1、不選主元的三角分解法 nn n n nn u uu uuu ll l A 222 11211 21 21 1 1 1 A=LU 其中L為單位下三角陣，U為上三角陣 （4.1） 2021-7-10計算方法第5章解線性方程組直接 方法 30 一、直接計算 A 的 LU 分解(例) 000 00 0

21、 1 01 001 0001 44 3433 442322 14131211 434241 3231 21 44434241 34333231 24232221 14131211 u uu uuu uuuu lll ll l aaaa aaaa aaaa aaaa uululululululululul uululuululululul uuluuluulul uuuu 44344324421441334323421341224212411141 34243214313323321331223212311131 2414212313212212211121 14131211 + + + 202

22、1-7-10計算方法第5章解線性方程組直接 方法 31 uululululululululul uululuululululul uuluuluulul uuuu 44344324421441334323421341224212411141 34243214313323321331223212311131 2414212313212212211121 14131211 + + + n. , 3,i - ; - , - 2 n , 2,j , - ; - , - , - u2 n ,2,i , ; , , 1 n , 1,j , ; , , , 1 2212i22i2 2212414242221

23、2313232 12122j 142124241321232312212222 111i1114141113131112121 11j1414131312121111 uulal uulaluulal ulau ulauulauulau ualualualual auauauauau )( )()(l l u i jj i j 列 行 列 行 2021-7-10計算方法第5章解線性方程組直接 方法 32 二、一般計算公式 n , 2,i , n, 1,j , 111i1 11 ual au i jj n)r , n; , r (i )/( , nr , ri n),(rrLrU uulal ulau rr r k krikirir r k kirkriri 且1 );1( 32 1 1 1 1 列元素的第行，的第計算 2021-7-10計算方法第5章解線性方程組直接 方法 33 三、LU 分解求解線性方程組 LY b , UXY AXb 11 2221 3132 12(1) 11 11121n 22 222n nn 1 1 1 1 UX nnnnn n nn y