計(jì)算方法第3章線性方程組數(shù)值解法

1、計(jì)算方法北京工業(yè)大學(xué)應(yīng)用數(shù)理學(xué)院北京工業(yè)大學(xué)應(yīng)用數(shù)理學(xué)院楊中華楊中華第三章線性方程組的數(shù)值解法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111bAx nnnnnnnnbbbbxxxxaaaaaaaaaA2121212222111211,(3.1)(3.2)3.1 消去法消去法224056242321321321xxxxxxxxx102736362423232321xxxxxxx消消去去法法3123636242332321xxxxxx 這一過程就是消元過程消元過程，即把方程化為等價(jià)的上三角方程(對角線下變?yōu)?)。 第一個(gè)階段完成后，進(jìn)入第二個(gè)

2、階段，稱為回代過程回代過程，其方法是：先由第3個(gè)方程解出，將代入第2個(gè)方程解出 ，再將和 代入第1個(gè)方程解出 也就解出所有的未知量。如下就是所求的解：3x3x1x2x2x3x41,23,41321xxx消消去去法法nnnnknknkkkkkknnkkkknnkkkkbxabxaxaxabxaxaxaxabxaxaxaxaxa.11,2211,222221111, 11212111(3.3)消消去去法法nnnnabx假如已經(jīng)求出 ，代入第k個(gè)方程得：1, 1, 11nnnnnnnaxabx1nxnxnx第2步：根據(jù)已求出的 和第n-1個(gè)方程求 ，得到11,knnxxxkknkjjkjkkaxab

3、x/)(1回代過程就是對實(shí)施這一公式，注意必須從后向前計(jì)算方可，所以此過程叫做回代過程回代過程。1 , 2 , 1,nnk(3.4)消消去去法法kkkkaxx/kkbxjijkkxaxxnkj, 1 1 , 2 , 1,nnknjibakikij, 2 , 1,)()(nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111)()(kkbA、)1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaa)1(1)1(21,naa(3.5)消消去去法法)2()2(2)2(2

4、)2(3)2(3)2(32)2(2)2(2)2(22)1(1)1(1)1(12)1(11000nnnnnnbaabaabaabaaani, 3 , 2nnnnnnnbaabaabaabaaa233322222111211000)1(11)1(11/ aamii1 imni, 4 , 32222/ aamii2im(3.6*)(3.6)消消去去法法 個(gè)列元素變?yōu)?0. 1,.,2 , 1,.,1,.,1,/nknkjikijijkikiikkikiknknkinkjamaabmbbaamnnnnnnbabaabaaabaaaa000000333322232211131211nnnnnnnbaab

5、aabaaabaaaa333332223221113121100000(3.7)消消去去法法ikm1, 2 , 1nknki, 1 kkikikaaa/kikiibabb., 1,nkjaaaakjikijij1 , 2 , 1,/ )(1nnkaxabxkknkjjkjkk，消消去去法法0)(kkka)()2(22)1(11kkkkaaaDnkDk, 2 , 1, 0)()2(22)1(11nnnnaaaDA消消去去法法)31(3333323nOnnnn222) 1() 1(211nnnnkknnknk65236) 12)(1() 1()2()(2()2(231111111nnnnnnnnk

6、kknknknnknknknki 消消去去法法消消去去法法22275 .2226002. 0453. 421m27.3726. 7453. 415.8713.87002. 0bA27.3726. 7453. 415.8713.87002. 02121xxxx21m194100194000015.8713.87002. 035,001. 112xx1,1021xx消消去去法法0004491. 0453. 4002. 021m15.8713.87002. 072 .372674534.-.21m13.8713.87072 .372674534.-.00.10453. 4000. 126. 727.

7、37,000. 113.8713.8712xx消消去去法法nnnnkkknkkknkkkkknkknkkbaabaabaaabaaaabaaaaa0000000001, 1, 11, 12221,2221111, 1121111a11a消消去去法法kr kka0rkaiknikrkaa maxkka(3.8)消消去去法法0rka0rka1, 2 , 1nkrkrjkjbbnkjaa，.,rkaiknikrkaa maxnki, 1kkikikaaa/kikiibabbnkjaaaakjikijij, 1,1 , 2 , 1,/ )(1nnkaxabxkknkjjkjkk，消消去去法法0,|ma

8、x|njikaaijrqkqxx 、消消去去法法011annnnnnnbaaabaaabaaabA2122222111121111a1 iannnnnnbaabaabaabA222221112001) 1( ii消消去去法法022a22a2iannnnnnbaabaabaa222221112001) 2( iinnnnnnnbaabaabaabaa333332223111300001001消消去去法法nnnnkkknkkknkkknkbaabaabaabaa1, 1, 11111 1nnnnkknkkkknkkknkbaabaabaabaa1, 11, 1,1,111, 11 10kkakka

9、)(kiiika消消去去法法nbbb100010001210kka0kka消消去去法法nk, 2 , 1rkrjkjbbnkjaa，.,iknikrkaa maxki 1., 1,/kkkkkjkjankjaaakikiibabbnkjaaaakjikijij, 1,消消去去法法rka0641321110A100641010321001110IA322132110320001110010321100641001110010321100641010321001110rrrr消元1121001130101200011-0001012000100111011032001032121212121212

10、3消元消元消消去去法法1121131201A消消去去法法1121131202113110120121103213213211103216411103216413211102132322121212123212132ccccrrrr消元消元消元21cc ,32cc 消消去去法法nk, 2 , 1., 1,njaarjkjiknikrkaa maxki kkkjkjakjaa.,ikikaakjaaaakjikijij,rpkrka11 , 2 , 1nkkpkkpk,niaakipik, 2 , 1,消消去去法法rka0jinAij1nji, 2 , 1，消消去去法法22221221211121

11、2112122121222nnnnnnA(3.9)(3.10)3.2 LU分解分解LU分分解解nnnknknkkkkknkkkkknkkkkkkknkknbaabaabaaabaaaabaaaaa1,1, 11, 11,1, 11, 1, 11, 1111, 111110000000000nnnknnkknkkkkkkknkkkkknkkkkkkknkknnkkkbaaabaaabaaabaaaabaaaaamm1,1, 11, 1, 11,1, 11, 1, 11, 1111, 11111, 1000000011111LU分分解解nnnknknkkkkknkkknkkknkbaabaabaa

12、baabaa1,1, 11, 11,1, 11, 1111, 1000000100010001nnnknnkknkkkkkkknkkkkknkkkkknkknkkkkkkkkbaaabaaabaaabaaabaaammamm1,1, 11, 1, 11,1, 11, 1, 1111, 11, 1, 1, 100000010111/ 111JordanLU分分解解式中的 就是我們消去法的消元因子消元因子，如果記：則Gauss消去法的整個(gè)過程可以表示為：注意到形如(3.11)式的單位下三角矩陣單位下三角矩陣具有以下兩個(gè)性質(zhì)：(1) 逆陣仍然是單位下三角陣；(2) 任意兩個(gè)單位下三角陣的乘積仍然是單

13、位下三角陣。所以上式也可以表示為：kkikikaam/1, 2 , 1,1111, 1nkllLnkkkkbLLLAxLLLUxnn121121bLAxLUx11(3.11)LU分分解解因此Gauss消去法的本質(zhì)上是將系數(shù)矩陣A進(jìn)行如下的矩陣分解：其中L是單位下三角矩陣，是單位下三角矩陣，U是上三角矩陣是上三角矩陣，此種分解也稱為杜里特爾杜里特爾(Doolittle)分解分解，如果L是下三角矩陣，U是單位上三角矩陣，則稱為克洛特克洛特(Crout)分解分解，以下內(nèi)容討論的是杜里特爾分解方法。LUA(3.12)LU分分解解2. LU分解分解 上述A=LU也可以寫成： 實(shí)現(xiàn)矩陣的LU分解算法既可以

14、仿照消去法設(shè)計(jì)算法也可以直接從該式推導(dǎo)出計(jì)算公式，以下我們討論直接LU分解方法。 首先用L的第1行乘以U的各列，則有 由此可以得到U的第1行：再讓L的各行乘以U的第1列得到 ，由此又可以得到L的第1列：njuajj, 1,111nnnnnnnnnnnnuuuuuulllaaaaaaaaa222112112121212222111211111njaujj, 2 , 1,11niulaii., 2,1111niualii, 3 , 2,/1111假如我們已經(jīng)得到了L的前k-1列和U的前k-1行：按如下方法確定U的第k行和L的第k列，將L的第k行與U的第 各列相乘，有得到U的第k行將L的第i(ik)

15、各行與U的第k列相乘，有得到L的第k列nkjululaujkkkjkkjkj,),(, 11,11?1?111, 1, 11, 1111, 1111,11,11 , 1nkkkkknkkknnkkkkuuuuuuulllllAnkjuululakjjkkkjkkj, 11,11nkiulululakkikkkkikiik, 1, 11,11nkiuululalkkkkkikiikik, 1,/)(, 11,11)(kjjLU分分解解LU分分解解則有如下結(jié)果：按如此方法，從k=1執(zhí)行到n-1則完成了矩陣的LU分解。 綜上所述，我們得到直接LU分解的計(jì)算公式分解的計(jì)算公式：?1?111, 1, 1

16、1, 1111, 1111,11,11 , 1knkknkkkkknkknkknnkkkkuuuuuuuuullllllAnknkiuulalnkjulaukqkkqkiqikikkqqjkqkjkj,.,2 , 1,.,1/ )(,.,1111(3.13)LU分分解解定理定理3.2 設(shè)n階矩陣A的順序主子式均不為0，則A存在LU分解，且分解是唯一的。 事實(shí)上，如果分解成功，A的第k個(gè)順序主子式的值就是 ，因此結(jié)論是顯然的。本定理表明LU分解可以正常進(jìn)行的前提是順序主子式不為0，表現(xiàn)在分解過程中就是所有 。 通?？梢詫⑾氯蔷仃嘗和上三角矩陣U放在一個(gè)矩陣內(nèi)，即：nkukk, 2 , 1, 0

17、kkuuu2211nnnnnnulluuluuuLU212222111211：(3.14)332322131211323121111516234212uuuuuulll516234212ALU分分解解2, 1, 2131211uuu22/4/112121ual3323223221213121516234212uuul，112121ula，113131ula32/6/113131ual3121,aaLU分分解解2232123132ulula112312212222ulau3321212123121516234212u，22122122uula，23132123uula222213213223ul

18、au2322,aa32a21/131/2212313232uulal33u33a332332133133uulula5)2()2(235233213313333ululauLU分分解解521212123121516234212523212212LU分分解解Uxy bAx bUxL)(bLy yUx LU分分解解nkylbykjjkjkk,.,2 , 1,11nnnnnnbyylylbyylby11,112212111.11,xxxnnnyyy,21LU分分解解nk, 2 , 1nkjulaukqqjkqkjkj,11nkiuulalkqkkqkiqikik, 1,/ )(11nkylbykjj

19、kjkk,.,2 , 1,111 , 1,/ )(1nnkaxayxkknkjjkjkk533,1033123121321321yyyyyy1033516234212321xxxLU分分解解521212,123121UL111,533521212321321xxxxxxLUPA LU分分解解(3.15)LU分分解解nk, 2 , 1nki, 1 ,maxnkiaaikrkrkrjkjppnjaa，, 2 , 1,kkikikaaa/., 1,nkjaaaakjikijijrka0LU分分解解iklkju3.3 三對角線性方程的追趕法三對角線性方程的追趕法nnnnnnnnndddddxxxxxb

20、acbacbacbacb1321132111133322211nnnRdxRAdAx,(3.16)(3.17)nniiininnnnnucucuculllbacbacbacb111112111222111111nibuclaulbuiiiiiii, 3 , 2,1111追追趕趕法法niclbuualbuiiiiiii,.,3 , 2,/1111(3.18)nnnnnddddyyyylll121121321111追追趕趕法法niyldydyiiii,.,3 , 2111nnnnnnnyyyyxxxxucucucu1211211122111,.,1/ )(/1niuxcyxuyxiiiiinnn追

21、追趕趕法法11bu 1 , 1/1niuxcyxuyxiiiiinnnniyldydyiiii, 3 , 2111niclbuualiiiiiii, 3 , 2,/11追追趕趕法法417. 323.42923.5002000. 410.29210.28610.25014124124124341241242244343232121xxxxxxxxxx追追趕趕法法417. 3429. 150. 1000. 2,311210.2921286. 010.250132214321yyyyyyyy1111417. 3429. 1500. 1000. 1417. 32429.32500. 32000. 44

22、3214321xxxxxxxx，追追趕趕法法nnnnnnnnnndddddxxxxxbaccbacbacbaacb13211321111333222111(3.19)nca 、2nca 、2) 2 ,(), 2(nn 、追追趕趕法法nnnnnnnnnndddddxxxxxbaccbacbaacbacb13211321111333222111(3.19)11111222222222211111nnnnnnnnnnnnnnnbcaxdbcaxdbcaxdabcxdcabxdnkca、1) 1,(), 1(knnk、3 nk3, 2 , 1nk、), 1(kk nkca、1(3.20),(kn追追趕

23、趕法法1111122222222221111nnnnnnnnnnnnbcaxdbcaxdbcaxdbcxdbxd(3.21)nnnaca、13, 2 , 1nkkkkkkcbabb111kkkkkdbadd111kkkkabaa11kknnnabcbbkknnndbcddkknncbcc追追趕趕法法nnnbdx 2nk22111nnnnncbabb22111nnnnndbadd22111nnnnnabacc11nnnnncbabb11nnnnndbadd1111nnnnnbxcdx1nk22nnnnncbcaakknnndbcddkknncbcc1 , 2 , 1, 21nnkbxaxcdxk

24、nkkkkk，3.4 平方根法平方根法nnRATAA nRx0AxxT0AxxTAARATnn,TLDLA LUDLVLDVAATTTTLUA DVuuuuuuuuuuuuuuuUnnnnnnnn1112221111112221122211211平平方方根根法法LDVLUATLV (3.22)niuii, 2 , 1, 0TLLA TTTTLLLDLDLDLDLDLA1121212121)(),(221121nnuuudiagD平平方方根根法法(3.23)nknkilllallalkkkjkjijikikkjkjkkkk, 2 , 1, 1,/11112nnnnnnnnnnnnnnllllll

25、llllllaaaaaaaaa2221211121222111212222111211nkkillllllakkikkjkjijnjkjijik, 1,111平平方方根根法法1k(3.25)333,333,31131311121211111lallalal653553333A22335,23522213132322212222lllallal123233L 6123222A1236222322313333llal平平方方根根法法TTLA LDT 1111112121212121nnnnnllldddlllAjijijdlt平平方方根根法法TLDLA yDxLT11 , 1,/, 2 , 111

26、1nnkxldyxnkylbynkiiikkkkkjjkjkknkltadkidtlltatadkjkjkjkkkiikikijijkjikik, 3 , 2,1, 2 , 1,/1111111bLy 平平方方根根法法(3.26)(3.27)平平方方根根法法1111albA，nk, 3 , 211kjjkkjkkkkllaliiikkiijjkijikiklllllal/111, 2 , 1ki平平方方根根法法ijl1 , 1,/1nnkxllyxnkjjjkkkkknkylbykjjkjkk, 2 , 1,11ija平平方方根根法法12341111011100110001DL，1111221

27、133314444)(TL10974997477744444A3.5 迭代法迭代法3/3n3/3nfBxx)0(x, 2 , 1 , 0,)()1(kfBxxkk迭迭代代法法)(kx(3.28)(3.29)njijijnibxa1, 2 , 1,nixabaxijjijiiii, 2 , 1),(1nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111迭迭代代法法niaii, 2 , 1, 0, 2 , 1 , 0, 2 , 1),(1)()1(knixabaxijkjijiiiki(3.31)(3.30)bDxULDx11)(bxULDx)(

28、000,000,211221212211nnnnnnaaaUaaaLaaaD迭迭代代法法ULDA, 2 , 1 , 0,)(1)(1)1(kbDxULDxkk)(1ULDBJbDfJ1, 2 , 1 , 0,)()1(kfxBxJkJk(3.32)77221582469321321321xxxxxxxxx迭迭代代法法21331232172721858281919694xxxxxxxxx)()1(kkxx0迭迭代代法法)(2)(1)1(3)(3)(1)1(2)(3)(2)1(172721858281919694kkkkkkkkkxxxxxxxxx0)0(x310迭代迭代序號序號 0 0.000

29、0.000 0.000 1 0.444 -0.125 1.000 2 0.417 -0.861 0.909 3 0.918 -0.797 1.127 4 0.851 -1.059 0.966 5 1.043 -0.941 1.059 6 0.954 -1.048 0.971 7 1.035 -0.970 1.027 8 0.977 -1.026 0.9811x2x3x迭迭代代法法迭代迭代序號序號 9 1.019 -0.983 1.014 10 0.987 -1.013 0.990 11 1.010 -0.990 1.008 12 0.993 -1.007 0.994 13 1.005 -0.9

30、95 1.004 14 0.996 -1.004 0.997 15 1.003 -0.997 1.002 16 0.998 -1.002 0.998 17 1.002 -0.998 1.001 18 0.999 -1.001 0.999 19 1.001 -0.999 1.001 20 0.999 -1.001 0.999 21 1.000 -1.000 1.0001x2x3xTx) 1 , 1, 1 ( jikjijiiikixabax)() 1(1迭迭代代法法ni, 2 , 1)()1(kkxx0)0(x)1( kx00k，, 2 , 1 , 0, 2 , 1),(11)(11) 1()

31、1(knixaxabaxnijkjijijkjijiiiki)1(2kx)(1kx)1(1kx)1(1kx)(1kx(3.33)迭迭代代法法bLDUxLDxbUxLxDxkkkkk1)(1) 1()() 1() 1()()(ULDBG1)(GkGkfxBx)()1(bLDfG1)(迭迭代代法法(3.34)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(172721858281919694kkkkkkkkkxxxxxxxxx0)0(x310迭代次數(shù)迭代次數(shù) 1 0.444 -0.236 0.940 2 0.497 -0.837 1.097 3 0.881 -1.031 1.043

32、4 1.016 -1.031 1.004 5 1.020 -1.008 0.996 6 1.006 -0.999 0.998 7 1.000 -0.999 1.000 8 0.999 -1.000 1.0001x2x3x迭迭代代法法nijkjijijkjijiiikixaxabax1)(11) 1() 1(1迭迭代代法法ni, 2 , 1)()1(kkxx0)0(x)1( kx00k，nixxxxxaxabaxkikikikiijnijkjijkjijiiiki,.,2 , 1),()(1)()1()()1(111)()1()1(1110迭迭代代法法迭迭代代法法2430244101430343

33、21xxxTx) 1 , 1 , 1 ()0(410迭代次數(shù)迭代次數(shù) 0 1.000 1.000 1.000 1 5.250 3.813 -5.047 8 3.008 3.993 -5.002 9 3.005 3.996 -5.001 10 3.003 3.997 -5.001 11 3.002 3.998 -5.000 12 3.001 3.999 -5.0001x2x3x1迭迭代代法法迭代次數(shù)迭代次數(shù) 0 1.000 1.000 1.000 1 6.313 3.520 -6.650 2 2.622 3.959 -4.600 3 3.133 4.010 -5.097 4 2.957 4.00

34、7 -4.973 5 3.004 4.003 -5.006 6 2.996 4.001 -4.998 7 3.000 4.000 -5.0001x2x3x25. 1)(-1)() 1()() 1(1)(11) 1() 1(kikikikinijkjijijkjijiiikixxxxxaxabax迭迭代代法法ni, 2 , 1)()1(kkxx00k，0)0(x)1( kx20 nxnRnRx0lim*)(xxkk nx迭迭代代法法1B|1|1|)0()1(*)()1()(*)(xxBBxxxxBBxxkkkkkfBxxfBxxkk)()1()0(x(3.36)(3.37)迭迭代代法法1310311310311A00031000310,100010001,03100031000UDL迭迭代代法法JB912710319100310000310003101311311)(11ULDBG0310310310310)(1ULDBJ13231,3131,31max1JB19491271,3191,31maxGB迭迭代代法法*)(limxxkk)()(*)0(*)1(*)