1、江西理工大學(xué)理學(xué)院江西理工大學(xué)理學(xué)院實(shí)際問(wèn)題中的線(xiàn)性方程組分類(lèi)：按系數(shù)矩陣中零元素的個(gè)數(shù)：稠密線(xiàn)性方程組稀疏線(xiàn)性方程組按未知量的個(gè)數(shù)：高階線(xiàn)性方程組(如1000)低階線(xiàn)性方程組按系數(shù)矩陣的形狀對(duì)稱(chēng)正定方程組三角形方程組三對(duì)角占優(yōu)方程組(80%)第四章第四章 解線(xiàn)性方程組的直接法解線(xiàn)性方程組的直接法.,)(,) 1 . 4() 1 . 4(22112222212111212111常數(shù)向量為方程組的未知向量和分別是方程組的系數(shù)矩陣其中其矩陣形式為階線(xiàn)性方程組本章研究的對(duì)象是bXaAbAXbxaxaxabxaxaxabxaxaxanijnnnnnnnnnnnxxx21nbbb21.,.,作簡(jiǎn)要介紹并

2、對(duì)誤差分析直接法本章討論幾種較實(shí)用的方程組精確解的方法經(jīng)過(guò)有限步運(yùn)算能求得就是在不計(jì)舍入誤差時(shí)所謂直接法4.1 Gauss消去法消去法4.1.1 Gauss順序消去法順序消去法 高斯高斯(Gauss)消去法實(shí)質(zhì)是消元法消去法實(shí)質(zhì)是消元法,它的基本做法是把方程它的基本做法是把方程組組(4.1)轉(zhuǎn)化成一個(gè)等價(jià)的三角方程組轉(zhuǎn)化成一個(gè)等價(jià)的三角方程組nnnnnnnngxbgxbxbgxbxbxb）（4.22222211212111.,.11為回代這個(gè)過(guò)程稱(chēng)逐個(gè)求出然后這個(gè)過(guò)程稱(chēng)為消元xxxnn4.1.1.1 高斯消去法的計(jì)算過(guò)程高斯消去法的計(jì)算過(guò)程 為了符號(hào)統(tǒng)一為了符號(hào)統(tǒng)一,把方程組把方程組(4.1)

3、改寫(xiě)成下面形式改寫(xiě)成下面形式其中用矩陣表示為)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其中用矩陣表示為方程組等價(jià)的即得與式等等倍方程減去第一個(gè)方程的第三個(gè)倍個(gè)方程的用第二個(gè)方程減去第一若)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的等價(jià)方程組得倍方程的個(gè)方程減去第二個(gè)中第若類(lèi)似地則令)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方程組即得等價(jià)的三角步經(jīng)過(guò)去上述步驟可繼續(xù)進(jìn)行下若則令,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式為消元過(guò)程元素的計(jì)算公程矩陣的過(guò)程稱(chēng)為消元過(guò)把系數(shù)矩陣化為上三角.)9 . 4(nikjabmbbaabbamaaaaaanjkibbaakijkkikkikkkkkkikkikikkjikkijkkjkkkkikkijkijkikikijkij10)/()/(,)1()()()()()()()1()()()()()()()1()()1()()1(njknik1,1)(1)()()()(211)()(/ )(/,), 2, 1(,/,)8 . 4(),8 . 4(iiijnijiijiiinnnnnninn

8、nnnnnnnnaxabxabxnixxxxxxbx其計(jì)算公式為叫回代過(guò)程這一過(guò)程依次求得全部變量式子可求出代入倒數(shù)第三個(gè)把可求出子把它代入倒數(shù)第二個(gè)式得最后一個(gè)式子從方程組有了等價(jià)的三角方程組1, 2, 1nni)10. 4(4.1.1.2 高斯消去法的運(yùn)算量高斯消去法的運(yùn)算量(只計(jì)算乘除法只計(jì)算乘除法)nknnkknnnnnn12) 1(3) 1(.,)2() 1(,2,) 1(,1共需次需做乘法個(gè)系數(shù)消去第二列的次需做乘法個(gè)系數(shù)消去第一列的nnnNNNnnkNnnnNnnknknk3131),1(26523),1(2,23211223111的運(yùn)算量為所以高斯消去法數(shù)為回代過(guò)程所需的乘除次

9、除次數(shù)為消元過(guò)程所需的乘要做的除法運(yùn)算次數(shù)為次乘法4.1.2 Gauss列主元消去法列主元消去法而中止溢出作除數(shù)計(jì)算機(jī)將因若它為稱(chēng)為主元數(shù)用到的除個(gè)倍數(shù)步求第高斯消去法消元過(guò)程中,”0“, 0,/,)()()(kkkkkkkikaaaknk10001. 02,0001. 0, 0, 1100001000010001. 0,.9999/9998,9999/10000210001. 01 . 4.,2121122211212121xxxxxxxxxxxxxxxx變?yōu)橄陆粨Q一先將方程組的兩個(gè)方程為了避免這種情況入誤差劇增造成的使舍作除數(shù)這是因?yàn)橛门c精確解相差甚遠(yuǎn)回代得得消去第二個(gè)方程的求解的計(jì)算機(jī)上

10、用高斯消元字若在尾數(shù)為三位十進(jìn)數(shù)的精確解為方程組例或產(chǎn)生較大的誤差計(jì)算.|max|) 11, 2, 1)2(.,) 1 (.1 . 4.,.,),(,.1, 112,)()()(, 1)(122211paanknbAnknkkkpaaaakkxxxxxxiknikpkkpkknkkkkkkk保存主元所在的行標(biāo)按列選主元做對(duì)階數(shù)常數(shù)列向量輸入系數(shù)矩陣列主元高斯消去法算法全主元高斯消去法則稱(chēng)為列中選主元行在步若在消去過(guò)程的第主元高斯消去法元的高斯消去法稱(chēng)為列這種選主兩行則交換設(shè)絕對(duì)值最大的數(shù)為中選主元列在第步可在消去過(guò)程的第為避免出現(xiàn)小主元結(jié)果和精確解非常接近回代得得消去第二個(gè)方程的6557710

11、46232 . 4.1, 1,/ )3(, 1, 1,) 13 , 2 , 1()5., 1/)4.,)3.;, 0|)2321213211xxxxxxxxbXnniababxnkibmbbnkjiamaanknkiaamkpkpanijiijijiikikiikjikijijkkikikpk解方程組用列主元高斯消去法求例中存于常數(shù)項(xiàng)解回代消元計(jì)算兩行交換若否則順序進(jìn)行計(jì)算停止則系數(shù)矩陣奇異若2/5|52/5010/61|610/107|07100,6|5154|6237|07102, 1105,10, 3max,6|5157|07104|623|:312121為化消元行交換第選主元表示計(jì)算過(guò)

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分解法分解法 求解線(xiàn)性方程組的三角分解法求解線(xiàn)性方程組的三角分解法,源于高斯消去法的矩陣形式源于高斯消去法的矩陣形式. 從矩陣的角度看從矩陣的角度看,把式把式(4.3)化為式化為式(4.4),相當(dāng)于系數(shù)

13、矩陣和相當(dāng)于系數(shù)矩陣和常數(shù)列向量左乘初等矩陣常數(shù)列向量左乘初等矩陣列向量左乘初等矩陣相當(dāng)于系數(shù)矩陣和常數(shù)化為式把式即),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由式三角陣其逆的乘積也是單位下也是單位下三角矩陣其逆的下三角矩陣對(duì)角元為為單位下三角矩陣其中得步經(jīng)過(guò)即innnnnnnMbMMMMbAMMMMAnbMbAMAmmM)11. 4(設(shè)可惟一分解為矩陣時(shí)為的所有順序主子式都不當(dāng)分解的乘積叫做和上三角矩陣下三角矩陣

14、分解為單位即將系數(shù)矩陣是上三角矩陣是單位下三角矩陣其中則令.,0.,)1()(111211)(111211)1(LUAAALUULAULLUAAUMMMLAMMMAnnnn)12. 4(nnnnnnuuuuuuUlllllL2221121121323121,1111LUAULniuxuyxuyxYUXniylbybybLYbLYYUXbLUXnikiikikiinnnnikkikii由于矩陣與系數(shù)矩陣如何分解成問(wèn)題得再解得解則令這時(shí)方程組可寫(xiě)為:1, 1/ )(/, 3, 2.,11111)13. 4()14. 4(nkkjikijnjiula1),2 , 1,(:根據(jù)矩陣的乘法有.), 3

15、, 2(/;), 2 , 1(:)(0)(01:111111的第一列元素得的第一行元素得從而可得注意到LniualUnjaujiujilliijjijijii的要確定列元素的前行元素的前現(xiàn)設(shè)已求出UrLrU,1,1nrnriuulalnriulululanrriulaunrriuululalkrlrLrrkrrkrikirirnkrkrrirkrikkrikirrkkirkririnkrkrikirkkirkrirrrk, 2:)16. 4(), 1(/ )(), 1()15. 4(), 1,(), 1,(,1,)(0.1111111111其中于是同理有于是則有由于列元素的第行元素及第可以引進(jìn)

16、步分解時(shí)在進(jìn)行第步的分解已完成若分解元可采用列主為避免這種情況產(chǎn)生較大的誤差入誤差的積累計(jì)算會(huì)引起舍的絕對(duì)值很小時(shí)當(dāng)分解時(shí)直接進(jìn)行與用高斯消去法相同為分解解方程組的計(jì)算量用所需乘除次數(shù)為解次數(shù)為所需乘除解所需乘除次數(shù)為分解討論,1.,.,2.3131).(21),(21),(311:23321232231kkLUuLU、nnnNNNNLUnnNYUXnnNbLYnnNLUA、kk列元素的第行元素和的第計(jì)算兩行的交換并記錄選主元計(jì)算做對(duì)和階輸入矩陣分解算法如下列主元分解這種分解稱(chēng)為列主元步分解再進(jìn)行第兩行的交換令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分解先把系數(shù)矩

18、陣進(jìn)行解分解求解方程組用例中存放在和分解后)(,.,2 . 2 . 42, 2, 16, 5, 3613322,121121321321計(jì)算按列不難得出計(jì)算公式的元素算用直接分解的辦法來(lái)計(jì)這種分解是惟一的當(dāng)限定對(duì)角元為正時(shí)使矩陣存在一個(gè)非奇異下三角是正定矩陣時(shí)當(dāng)平方根法一改進(jìn)的平方根法平方根法得再解得解LLLALA、xxxYUXyyybLYULT設(shè)設(shè)nnnnnaaaaaa11222111AnnnnllllllL21222111將 直接利用矩陣乘法,得:TLLA 2332322313322322131321131312222212211212121111,lllallllallallallala

19、則可由上式逐行求出矩陣則可由上式逐行求出矩陣L的元素的元素:31222111llll計(jì)算公式為計(jì)算公式為:2111211211111)() 1, 3 , 2 , 1(/ )(iiikiiiijkjjjkikijijlalijlllalal這時(shí)將原方程的解化為求解兩個(gè)三角方程組的解這時(shí)將原方程的解化為求解兩個(gè)三角方程組的解: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稱(chēng)為改進(jìn)的平方根法用開(kāi)方的分解法可得一種不是對(duì)角矩陣是單位下三角矩陣其中分解為把為避免開(kāi)方運(yùn)算次開(kāi)方但需要計(jì)算量減少一半分解比高斯消去法分解矩陣的計(jì)算量為得再由得DLLDLAAn、LUnOnxxxyyyxxxl

21、lllllyyyT 二、改進(jìn)的平方根法。二、改進(jìn)的平方根法。 定理：若線(xiàn)性方程組定理：若線(xiàn)性方程組AX=b的系數(shù)矩陣的系數(shù)矩陣A為為n階對(duì)稱(chēng)陣階對(duì)稱(chēng)陣,且且A的的各階順序主子式都不等于零各階順序主子式都不等于零,則可將則可將A惟一分解為惟一分解為A=LDLT,其中其中L為單位下三角陣，為單位下三角陣，D為對(duì)角陣，寫(xiě)成矩陣形式為為對(duì)角陣，寫(xiě)成矩陣形式為:1111112121212121212222111211nnnnnnnnnnnllldddlllaaaaaaaaa根據(jù)矩陣乘法根據(jù)矩陣乘法,對(duì)對(duì)i=1,2, n有有:.,6,:, 2, 1:,) 1, 2, 1(,3111111112而且無(wú)需開(kāi)方

22、運(yùn)算上式所需的計(jì)算量約為容易看出有對(duì)于則上式可整理如下引進(jìn)輔助量為了避免重復(fù)計(jì)算nltaddtlltatnidltijddllaldladikikikiiijijijjkjkikijijjijijjkjkjkikijijkjkikiii1,2, 1ij.:)2(:,) 1 (:,11111的解此即方程組中的求未知數(shù)計(jì)算中的求未知數(shù)求解下三角方程組令的解的步驟如下再求解方程分解以后的求得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因此分解故有等于零的各階順序方子式都不且階對(duì)稱(chēng)陣為陣滿(mǎn)足可知此方程組的系數(shù)矩解方程組用改進(jìn)的平方根法求解例ltltaddtldtlltatatiltaddtlatiadiLDLAnAxxxxxxxxxT112:2, 1, 1:1, 1, 6:175. 0125. 025. 01144175. 025. 0125. 013312211113322223332321313312122

24、11xxlxldyxxldyxdyxYXDLylylbyylbybybLYLDLATT即原方程組的解為得代入式的解為代入式nnnnnnndbadcbadcbadcbadcb111133332222111.陣為三對(duì)角方程組的增廣矩程組最適用的追趕法nnnnlalalalal1133221nnnyyuyuyuyu1111111332211可得對(duì)三對(duì)角方解法用于三對(duì)角方程組將高斯消去法或三角分追趕法,3 . 2 . 4若A滿(mǎn)足:1.|b1|c1|02.|bi|=|ai|+|ci|,(aici不等于0)3.|bn|an|0則可以證明A是非奇異的，且A的各順序主子式不為01, 1), 2(/ )(/,1

25、1111111111nixuyxyxnilyadyuabllculdybliiiinniiiiiiiiiiii回代得得比較兩邊相應(yīng)的元素)19. 4()20. 4( 上述方法稱(chēng)為追趕法上述方法稱(chēng)為追趕法,其中分解的過(guò)程叫追其中分解的過(guò)程叫追,回代的過(guò)程叫趕回代的過(guò)程叫趕.追趕法所需乘除次數(shù)為追趕法所需乘除次數(shù)為5n-4,比高斯消去法和三角分解法少的多比高斯消去法和三角分解法少的多. 實(shí)際遇到的方程組實(shí)際遇到的方程組,系數(shù)矩陣往往對(duì)角占優(yōu)系數(shù)矩陣往往對(duì)角占優(yōu),不選主元就可順不選主元就可順利穩(wěn)定地進(jìn)行利穩(wěn)定地進(jìn)行.5/3)2/5/()2/112(/ )(, 2/52/113, 2/1/2/1/,

26、2)19. 4(111121101221112131112122112111131125 . 421222122211111111433221143214321lyadyuabllculdyblyyuyuyullllxxxx得由解設(shè)用追趕法求解方程組例0, 1, 1, 2)20. 4 (213735153521212113725312512012211121311121234xxxx得由式于是4.3 線(xiàn)性方程組數(shù)值求解的誤差分析線(xiàn)性方程組數(shù)值求解的誤差分析 前面介紹了求解線(xiàn)性方程組的各種方法，但從數(shù)值計(jì)算的前面介紹了求解線(xiàn)性方程組的各種方法，但從數(shù)值計(jì)算的角度看，除介紹算法外，還要進(jìn)行誤差分析

27、。而向量范數(shù)角度看，除介紹算法外，還要進(jìn)行誤差分析。而向量范數(shù)、矩、矩陣范數(shù)及矩陣的條件數(shù)在誤差分析中是十分重要的，本節(jié)先介陣范數(shù)及矩陣的條件數(shù)在誤差分析中是十分重要的，本節(jié)先介紹向量范數(shù)、矩陣范數(shù)及矩陣的條件數(shù)。紹向量范數(shù)、矩陣范數(shù)及矩陣的條件數(shù)。 4.3.1 向量范數(shù)向量范數(shù)向量范數(shù)是向量范數(shù)是n維實(shí)空間維實(shí)空間Rn中長(zhǎng)度概念的推廣中長(zhǎng)度概念的推廣。.|. |,:) 3(. |:)2(. 00, 0|:) 1 (:|,|,1 . 4的范數(shù)為向量則稱(chēng)有對(duì)所有三角不等式有和對(duì)所有齊次性時(shí)當(dāng)且僅當(dāng)有對(duì)所有正定性若具有性質(zhì)對(duì)應(yīng)一非負(fù)實(shí)數(shù)任一向量定義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向量范數(shù)的基本性質(zhì)解范數(shù)范數(shù)和范數(shù)的求例分量個(gè)的是其中范數(shù)范數(shù)和范數(shù)分別稱(chēng)為幾種常用的范數(shù)有中在XXXXnXxxxxXxxxXxxxXRTnininnn)21. 4(. 00, 0|:) 1 (:|,|,2 . 4.,2 . 3 . 4. 0|lim.)3(.|,|.)2(.,|.) 1 ()()(21A，AARAARAXXXXXMXXmMmRXXnxxxXnnnnkkkrsr

29、nsrn時(shí)當(dāng)且僅當(dāng)有對(duì)所有正定性質(zhì)若具有性對(duì)應(yīng)一非負(fù)實(shí)數(shù)任一矩陣定義可定義矩陣的范數(shù)類(lèi)似于向量范數(shù)的定義矩陣范數(shù)等價(jià)于收斂于向量向量序列范數(shù)收斂性使得數(shù)則存在常上任意兩種范數(shù)為和設(shè)等價(jià)性函數(shù)元連續(xù)的是其分量向量的范數(shù)連續(xù)性. 1)2(.|,|:|) 1 (:.| ,)4(|,:) 3(. |:)2(EXXAAXAABAABRBABABARBAAaaARaRAnnnnnn單位矩陣范數(shù)為向量范數(shù)其中相容性質(zhì)矩陣范數(shù)常用的幾個(gè)性的范數(shù)為矩陣則稱(chēng)對(duì)所有有對(duì)所有三角不等式有和對(duì)所有齊次性|)|1 (1|)(|,1|)3(1BBEBEB且可逆時(shí)|)(|)|1 (|)(|)(|)()(|)()(|1.0|)

30、|1 (|)(|0|0,0)(,:111111BEBBBEBEBBEBEBEBEEBEXBXBXBXXBXXXBEXXBEBE因?yàn)榭赡嫠悦苡蟹橇憬鈩t方程組不可逆若證明|)|1 (1|)(|1BBE所以.,2,2 ,1 ,.,)(|max|)()(|2|max|)(1112111在理論證明時(shí)常用到它范數(shù)有一些很好的性質(zhì)但范數(shù)比較復(fù)雜范數(shù)計(jì)算簡(jiǎn)單范數(shù)和這三種范數(shù)中的譜半徑稱(chēng)為矩陣的絕對(duì)值最大的特征值表示矩陣其中行范數(shù)范數(shù)范數(shù)列范數(shù)范數(shù)三種常用的矩陣范數(shù)為AAAAAAaAAAAaATTTnjijniTniijnj)22. 4(特征方程為解求設(shè)例范數(shù)矩陣范數(shù)為一個(gè)常用且易于計(jì)算的此外2010101

31、03043)2(1|7)43(|),2|1max(|6)4|2(|),31max(|:| ,| ,| ,|,43217 .4)|(|.,22221211,2/12AAAAAAAAAAaAFTFFnjiijF01003020101010|2AAIT1167.512515|,125152A于是特征值為4.3.3 線(xiàn)性方程組固有性態(tài)與條件數(shù)線(xiàn)性方程組固有性態(tài)與條件數(shù) 一個(gè)線(xiàn)性方程組一個(gè)線(xiàn)性方程組AX=b是由它的系數(shù)矩陣是由它的系數(shù)矩陣A和常數(shù)向量和常數(shù)向量b確確定的。在實(shí)際問(wèn)題中，定的。在實(shí)際問(wèn)題中，A和和b中的數(shù)據(jù)是帶有誤差的，現(xiàn)在研究中的數(shù)據(jù)是帶有誤差的，現(xiàn)在研究A和和b受到微小擾動(dòng)后對(duì)解有何影

32、響？受到微小擾動(dòng)后對(duì)解有何影響？0001. 20001. 12,)0001. 2, 2(,. 0, 220001. 128 . 42121212121xxxxbbxxxxxxT方程組變?yōu)樽優(yōu)橐晃⑿∽兓舴匠探M右端常數(shù)項(xiàng)有的精確解為線(xiàn)性方程組例1, 121xx其解為 常數(shù)項(xiàng)的第二個(gè)分量的微小變化，引起了方程組解的巨大常數(shù)項(xiàng)的第二個(gè)分量的微小變化，引起了方程組解的巨大變化，這樣的方程組稱(chēng)為病態(tài)方程組，矩陣變化，這樣的方程組稱(chēng)為病態(tài)方程組，矩陣A稱(chēng)為病態(tài)矩陣。稱(chēng)為病態(tài)矩陣。 應(yīng)該注意，矩陣的應(yīng)該注意，矩陣的“病態(tài)病態(tài)”性質(zhì)是矩陣本身固有的性態(tài)，性質(zhì)是矩陣本身固有的性態(tài)，下面我們希望找出刻畫(huà)矩陣下面我

33、們希望找出刻畫(huà)矩陣“病態(tài)病態(tài)”性質(zhì)的量。性質(zhì)的量。 (1).設(shè)有非奇異方程組設(shè)有非奇異方程組AX=b，其精確解為，其精確解為X，b受到擾動(dòng)受到擾動(dòng)b b，從而相應(yīng)的解，從而相應(yīng)的解X有擾動(dòng)有擾動(dòng)X，即，即|:|:)(111XAbbAXbAbAXbAXbXAbAXbbXXA得由兩邊取范數(shù)得由.|,|, 0|, 0|111倍誤差的端項(xiàng)相對(duì)解的相對(duì)誤差不超過(guò)右有擾動(dòng)時(shí)右端項(xiàng)此式表明從而則若以上兩式相乘得AAkbbbAAXXAbXbAAbX)23.4(XAAAXAAEAAAAAAXAXAAbXXAAXXAAb)()(,.)(,1|,)()()(,).2(111此時(shí)也可逆時(shí)所以當(dāng)可逆因?yàn)榧从袛_動(dòng)從而相應(yīng)

34、的解有微小擾動(dòng)是精確的現(xiàn)假定.)(|)(3 . 4.|.,.|)(,|1|1|,|1|)(|)(|,1111111111111的條件數(shù)或方程組稱(chēng)為矩陣數(shù)定義的條件數(shù)稱(chēng)為方程組我們把會(huì)很大則擾動(dòng)對(duì)解的影響可能很大而會(huì)很大則對(duì)解的影響不不大若倍系數(shù)矩陣相對(duì)誤差的不超過(guò)近似解的相對(duì)誤差有擾動(dòng)時(shí)系數(shù)矩陣此式表明得并利用兩邊取范數(shù)bAXAAAAcondbAXAAkkkAAkAAAAAAAAAAAAAXXAAAAAEAAAvvv)24. 4(minmax2minmax221211111)(:2)()()()3(1)()2()() 1 (:AcondAAAAAAAAAcondAAAAcondAAAAcond

35、TT為對(duì)稱(chēng)陣時(shí)有特別當(dāng)條件數(shù)的條件數(shù)的條件數(shù)的常用的條件數(shù)有)()()(1)(),(,)2()()(, )()(,1)() 1 (:22221AUcondUAcondAcondUcondEUUUAcondAcondAcondAcondAcondT則單位陣即為正交陣若條件數(shù)的性質(zhì)AAAcondAAAcondXXbbAcondXX)(1)(:)24. 4()(:)23. 4(,可表示成而式可表示成式引入條件數(shù)后)()(1)(,AAbbAAAcondAcondXXbAb則有擾動(dòng)和若同時(shí)考慮 由以上討論可知，條件數(shù)很大（由以上討論可知，條件數(shù)很大（cond（A）1）的方程）的方程組為病態(tài)方程組，條件數(shù)

36、很小的方程組為良態(tài)方程組。組為病態(tài)方程組，條件數(shù)很小的方程組為良態(tài)方程組。21010,9 . 4.140004|)(20001|0001. 2|1110001. 110000,0001. 1111,8 . 4,21525111111111xxxxAAAcondAAAA考察方程組的性態(tài)求方程組的條件數(shù)例程組所以該方程組為病態(tài)方中例例如.,)2(.) 1 (.,.,1100003|)(1101101102,110101max|10111,101max|111011011|,1110115得出的解變化很大將系數(shù)稍加變化相差懸殊系數(shù)矩陣的元素?cái)?shù)量級(jí)表示方程組病態(tài)下列條件可能計(jì)

37、算若方程組的條件數(shù)不易實(shí)際應(yīng)用中該方程組是病態(tài)方程組所以解AAAcondAAAAAA采用平衡措施后例如值最大的元素除以該行絕對(duì)就是將系數(shù)矩陣的各行所謂平衡措施迭代改善等如平衡措施或采用其他處理方法計(jì)算可采用雙精度字長(zhǎng)進(jìn)行程組對(duì)于病態(tài)不太嚴(yán)重的方很差所得的解也可能即使算法是穩(wěn)定的對(duì)于病態(tài)方程組主元數(shù)量級(jí)相差懸殊采用選主元技術(shù)時(shí)線(xiàn)性相關(guān)系數(shù)矩陣的行或列近似差較遠(yuǎn)算出的解與期望的解相1100003)(,11101,1).,(,.,.,)5(.)4(.)3(5.AcondA111105A通過(guò)事前誤差估計(jì)實(shí)際上是一種前面介紹的誤差估計(jì)稱(chēng)為迭代改善逐漸接近真正解的方法使得新解這樣反復(fù)解再修改再求修改量仍是

38、近似解所得解滿(mǎn)足使求修改量為求更好的近似解即先求近似解所謂迭代改善方程組變成良態(tài)的了, ,.,.,)(,. 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得有擾動(dòng)的解再解方程組有擾動(dòng)現(xiàn)在的精確解為方程組例事后誤差估計(jì)這就是所謂的然

39、后再作誤差分析也可先上機(jī)求解當(dāng)條件數(shù)難以計(jì)算時(shí)計(jì)算條件數(shù)來(lái)估計(jì)誤差6 .1316 .13|XX. 6 .136 .13331 . 04488|)(|4488)(33|1 . 0|估計(jì)相對(duì)誤差也是實(shí)際相對(duì)誤差為bbAcondXXAcondbb 第五章第五章 線(xiàn)性方程組的迭代法線(xiàn)性方程組的迭代法 第四章介紹的直接法是通過(guò)有限步運(yùn)算后得到方程組的解第四章介紹的直接法是通過(guò)有限步運(yùn)算后得到方程組的解,當(dāng)系數(shù)矩陣當(dāng)系數(shù)矩陣A為非奇異的低階稠密矩陣時(shí)，直接法是有效的為非奇異的低階稠密矩陣時(shí)，直接法是有效的.但但在實(shí)際計(jì)算中在實(shí)際計(jì)算中,常會(huì)遇到大型稀疏矩陣（常會(huì)遇到大型稀疏矩陣（A的階數(shù)很大，但零元的階數(shù)

40、很大，但零元數(shù)很多）數(shù)很多）.迭代法是求解大型稀疏矩陣方程組的有效方法。迭代法是求解大型稀疏矩陣方程組的有效方法。 迭代法的基本思想是構(gòu)造一個(gè)向量序列迭代法的基本思想是構(gòu)造一個(gè)向量序列X(k),使其收使其收斂于方程組斂于方程組AX=b的精確解的精確解.因此因此,對(duì)迭代法來(lái)說(shuō)對(duì)迭代法來(lái)說(shuō),一般一般有以下幾個(gè)問(wèn)題有以下幾個(gè)問(wèn)題: (1) 如何構(gòu)造迭代序列如何構(gòu)造迭代序列? (2) 構(gòu)造的序列在什么情況下收斂構(gòu)造的序列在什么情況下收斂? (3) 如果收斂如果收斂,收斂速度如何收斂速度如何? (4) 近似解的誤差估計(jì)近似解的誤差估計(jì).5.1 Jacobi迭代法迭代法nnnnnnnnnnnnniinnn

41、nnnnnnnaxaxaxabxaxaxaxabxaxaxaxabxabAXbxaxaxabxaxaxabxaxaxa/)(/)(/)(, 0112211222323121221113132121122112222212111212111方程組可改寫(xiě)成假設(shè)其矩陣形式為設(shè)有方程組) 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、這種迭代法稱(chēng)為簡(jiǎn)單迭就是方程組的解則收斂于若序列時(shí)當(dāng)可得一向量序列這樣迭代格式為一般地如此繼續(xù)下去量右端得向把它代入式記為新向量右端可得一代入式選取初始向量JacobiXXXkXaxaxaxabxaxaxaxabxaxaxaxabxXxxxXxxxXkknnknnnknknnknknnkkkknnkkkTnTn)4 . 5(.; 2,1,)4(. 4,|)3(./ )(, 2, 1)2(. 1.,) 1 (1 . 5)0()0(1)0()0(否則輸出失敗信息轉(zhuǎn)若否則轉(zhuǎn)停止計(jì)算輸出若計(jì)算對(duì)令代次數(shù)容許最大迭容許誤差初始向量維數(shù)常數(shù)向量輸入矩陣迭代法算法XXkkNkXXaxabxnikNXnbAJ

43、acobinijjiijijii5.2 Seidel迭代法迭代法即得迭代格式使用時(shí)再計(jì)算后若計(jì)算出不使用時(shí)計(jì)算用簡(jiǎn)單迭代法,)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方程組變形為解迭代法求解線(xiàn)性方程組迭代法和用例迭代法這種方法稱(chēng)為)5 . 5(容許最大容許誤差初始向量維數(shù)常數(shù)向量輸入矩陣迭代法算法迭代得取迭代格式為），迭代得取迭代格式為,) 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否則輸出失敗信息轉(zhuǎn)若否則轉(zhuǎn)停止計(jì)算輸出若計(jì)算令迭代次數(shù)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、它的精確解為法解方程組用例迭代法是松弛法的特例迭代法時(shí)為法這種迭代稱(chēng)為松弛法或叫做松弛因子其中)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令容許最大迭代次數(shù)容許誤差松弛因子初始向維數(shù)常數(shù)向量輸入矩陣松弛法算法果則可能達(dá)不到加速的效好但若選擇得不加速會(huì)使迭代法的收斂大大松弛因子選擇得好得取迭代格式為解.; 2,1,)4(. 4,|)3()1 (/ )() 1, 3, 2()1 (/ )()1 (/ )()2()0()0()0(11)0()0(111)0(111)0(2111否則輸出失敗信息轉(zhuǎn)若否則轉(zhuǎn)停止計(jì)算輸出若計(jì)算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()(迭代法對(duì)迭代法對(duì)簡(jiǎn)單迭代法可以統(tǒng)一寫(xiě)成下面形式以上幾種迭代格式即可表示為式即或)8 . 5()9 . 5()10. 5