計(jì)算方法2_線性方程組直接法

1、第第2 2章章 解線性代數(shù)方程組的直接法解線性代數(shù)方程組的直接法本章研究的對(duì)象是本章研究的對(duì)象是 n 階線性代數(shù)方程組階線性代數(shù)方程組 對(duì)象對(duì)象11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb(2.1)線性系統(tǒng)廣泛存在于工程、科學(xué)以及社會(huì)科學(xué)、線性系統(tǒng)廣泛存在于工程、科學(xué)以及社會(huì)科學(xué)、商業(yè)和經(jīng)濟(jì)問(wèn)題的定量分析等領(lǐng)域中商業(yè)和經(jīng)濟(jì)問(wèn)題的定量分析等領(lǐng)域中用矩陣和向量的記法來(lái)表示，用矩陣和向量的記法來(lái)表示，(2.1)式可寫成式可寫成BAX (2.2)其中其中A(aij)是方程組是方程組(2.1)的系數(shù)的系數(shù)aij構(gòu)成的構(gòu)成的

2、nn階矩陣，稱為階矩陣，稱為系數(shù)矩陣系數(shù)矩陣。Bbi,X xi是是n維向量，維向量，X是未知量，是未知量，B稱為稱為右端項(xiàng)右端項(xiàng)。nnnnnnijaaaaaaaaaaA212222111211)(nibbbbB21 nixxxxX21使方程組使方程組(2.1)中每一個(gè)方程都成立的一組數(shù)中每一個(gè)方程都成立的一組數(shù)x1*,x2*, ,xn* 稱為式，稱為式，(2.1)的解，把它記為向量的解，把它記為向量的形式，稱為的形式，稱為解向量解向量?？巳R姆克萊姆(cramer)(cramer)法則法則如果方程組如果方程組(2.1)(2.1)的系數(shù)矩陣的系數(shù)矩陣A A的行列式不等于零的行列式不等于零, ,那么

3、那么, ,這個(gè)方這個(gè)方程組有唯一解程組有唯一解, ,而且它們可以表示為而且它們可以表示為 按上面的等式求解按上面的等式求解, , 就要做就要做 N=(nN=(n2 2-1)n!+n-1)n!+n 次乘除法運(yùn)算次乘除法運(yùn)算, ,這這個(gè)計(jì)算量是大得驚人的個(gè)計(jì)算量是大得驚人的. .例如例如, ,當(dāng)當(dāng)n=10n=10時(shí)，乘除法的運(yùn)算次數(shù)共為時(shí)，乘除法的運(yùn)算次數(shù)共為3265921032659210次次 當(dāng)當(dāng)n=100n=100時(shí)，時(shí)， 1033次次/秒的計(jì)算機(jī)要算秒的計(jì)算機(jī)要算10120年年; ; nnninninniiiiiaabaaaabaaDADDDx11111111111det),det(,解線

4、性方程組的方法可以分為解線性方程組的方法可以分為2類：類：直接法直接法：在沒(méi)有舍入誤差的情況下，用有限：在沒(méi)有舍入誤差的情況下，用有限步的四則運(yùn)算得出精確解的方法。步的四則運(yùn)算得出精確解的方法。目前常用的是目前常用的是列主元消去法列主元消去法和和矩陣矩陣三角分解法三角分解法 迭代法迭代法：先給一個(gè)初始值，按一定法則逐步先給一個(gè)初始值，按一定法則逐步求解出各個(gè)更準(zhǔn)確的近似值的方法。求解出各個(gè)更準(zhǔn)確的近似值的方法。本章講解直接法本章講解直接法準(zhǔn)確，可靠，理論上得準(zhǔn)確，可靠，理論上得到的解是精確的到的解是精確的速度快，但有誤差速度快，但有誤差 2.1 消元法消元法我們知道，下面有我們知道，下面有3種

5、方程的解我們可以直接求出：種方程的解我們可以直接求出：niabxaaadiagAiiiinn, 1,),(2211n次運(yùn)算次運(yùn)算nilxlbxllllllAiiijjijiinnnn, 1,1121222111（n1）n/2次運(yùn)算次運(yùn)算1 ,122211211niuxubxuuuuuuAiinijjijiinnnn（n1）n/2次運(yùn)算次運(yùn)算對(duì)方程組（對(duì)方程組（2.1)2.1)，作如下的變換，解不變，作如下的變換，解不變交換兩個(gè)方程的次序交換兩個(gè)方程的次序一個(gè)方程的兩邊同時(shí)乘以一個(gè)非一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0 0的數(shù)的數(shù)一個(gè)方程的兩邊同時(shí)乘以一個(gè)非一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0 0數(shù)，加到另

6、一個(gè)方程上數(shù)，加到另一個(gè)方程上因此，對(duì)應(yīng)的對(duì)增廣矩陣因此，對(duì)應(yīng)的對(duì)增廣矩陣(A(A，B)B)，作如下的變換，解不變，作如下的變換，解不變交換矩陣的兩行交換矩陣的兩行某一行乘以一個(gè)非某一行乘以一個(gè)非0 0的數(shù)的數(shù)某一個(gè)乘以一個(gè)非某一個(gè)乘以一個(gè)非0 0數(shù)，加到另一行數(shù)，加到另一行消元法消元法就是對(duì)增廣矩陣作上述行的變換，變?yōu)槲覀円阎木褪菍?duì)增廣矩陣作上述行的變換，變?yōu)槲覀円阎? 3種種類型之一，而后求根類型之一，而后求根 2.2 高斯消去法高斯消去法(Gaussian elimination)首先將首先將A化為上三角陣，再回代求解化為上三角陣，再回代求解 =nnnnnnnbaaabaaabaaa

7、21222221111211(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333( )( )000000nnnnnnnnaaaabaaabaabab高斯消去法的求解過(guò)程分為兩個(gè)階段高斯消去法的求解過(guò)程分為兩個(gè)階段:首先，把原方程組化為上三角形方程組，首先，把原方程組化為上三角形方程組，稱之為稱之為“消元消元”過(guò)程；過(guò)程；然后，用逆次序逐一求出三角方程組然后，用逆次序逐一求出三角方程組(原方原方程組的等價(jià)方程組程組的等價(jià)方程組)的解，并稱之為的解，并稱之為“回代回代”過(guò)程。過(guò)程。消元消元 ：將：將(2.1)式寫成式寫成(1)(1)(1)BX

8、A 矩陣形式矩陣形式 )()()()()()()()()()()()(11212111121221221121111121121111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa(2.3)(2.4)第第1步步:若若a11 (1) 0，用第二個(gè)方程減去第一個(gè)方程乘以，用第二個(gè)方程減去第一個(gè)方程乘以a21(1)/ a11(1),用第三個(gè)方程減去第一個(gè)方程乘以用第三個(gè)方程減去第一個(gè)方程乘以a31(1)/ a11(1)則有則有(2)(2)(2)BXA 矩陣形式矩陣形式 )()()()()()()()()()(2222222222222111121121111nnnnnnnnnbxax

9、abxaxabxaxaxa(2.5)(2.6)第第2步步:若若a22 (2) 0，用第三個(gè)方程減去第二個(gè)方程乘以，用第三個(gè)方程減去第二個(gè)方程乘以a32(2)/ a22(2),用第四個(gè)方程減去第二個(gè)方程乘以用第四個(gè)方程減去第二個(gè)方程乘以a42(2)/ a22(2)則有則有(3)(3)(3)BXA 矩陣形式矩陣形式 )()()()()()()()()()()()()()()(33333333333332222322322221111311321121111nnnnnnnnnnnbxaxabxaxabxaxaxabxaxaxaxa(2.7) (2.8)第第k步步:若若akk (k) 0，用第，用第k

10、+1個(gè)方程減去第個(gè)方程減去第k個(gè)方程乘以個(gè)方程乘以ak+1k(k)/ akk(k) 則有則有(k)(k)(k)BXA矩陣形式矩陣形式)()(1)(11)()()()2(2)2(23)2(232)2(22)1(1)1(13)1(132)1(121)1(11knnknnkkkkkknkknkkkknnnnbxaxabxaxabxaxaxabxaxaxaxa(2.9)(2.10)重復(fù)重復(fù)n1次，得到次，得到等價(jià)的等價(jià)的上三角形方程組上三角形方程組)()()(nnnBXA 矩陣形式矩陣形式 )()()3(3)3(33)3(33)2(2)2(23)2(232)2(22)1(1)1(13)1(132)1(

11、121)1(11nnnnnnnnnnnnbxabxaxabxaxaxabxaxaxaxa(2.11)(2.12)以上過(guò)程把系數(shù)矩陣以上過(guò)程把系數(shù)矩陣A(1)變成上三角矩陣變成上三角矩陣A(n)，稱之為，稱之為消元，計(jì)算公式可歸納為消元，計(jì)算公式可歸納為 nikjanjknikbaabbaaaaanjkibbaakijkkkkkkikkikikkjkkkkikkijkijkikikijkij101,1)/()/(,)1()()()()()1()()()()()1()()1()()1(2.13)回代回代為為，回代過(guò)程可歸納，回代過(guò)程可歸納各方程即可得出未知量各方程即可得出未知量依次代入依次代入則有

12、則有若若,/, 0)()()(nnnnnnnnnabxa (2.12) 1 , 2, 1/ )(/1)()()()()(nniaxabxabxnijiiijiijiiinnnnnnnjkkkjkjknnnikikiijkjikijikkkikkkxaxabnnkForxabbbabnkkjaaaaaaankkiForstopthenaIfnkFornBA1/)(1 ,2, 1/.3),2, 1(/,2, 101,2, 1.2.1Gauss1.2輸出“不能消元”，階，右端項(xiàng)輸入系數(shù)矩陣消去法算法43422033228222432132143214321xxxxxxxxxxxxxxx解方程組解方程

13、組例例.4341120111203322812111)(AA1242006112041100812112)(A1242004110061120812113)(A420004110061120812114)(A22374321xxxx 2.3 主元素消去法主元素消去法因此，因此，x10 x21 2100010322121xxxx.方程組方程組例例散，計(jì)算結(jié)果不可靠。散，計(jì)算結(jié)果不可靠。也會(huì)帶來(lái)舍入誤差的擴(kuò)也會(huì)帶來(lái)舍入誤差的擴(kuò)情況，即使情況，即使消去法無(wú)法處理消去法無(wú)法處理00GAUSS)()( nnnnnnaa 100001000010001. 03221xxx位有效數(shù)字條件下）位有效數(shù)字條件下

14、）消元得到（在消元得到（在因此，因此，x11 x21 10001. 022121xxxx更換一下方程次序更換一下方程次序 123221xxx位有效數(shù)字條件下）位有效數(shù)字條件下）消元得到（在消元得到（在精確解，精確解，x110000/9999 x29998/9999在做除法運(yùn)算時(shí)，選取絕對(duì)值大的作分母。在做除法運(yùn)算時(shí)，選取絕對(duì)值大的作分母。主元素消去法的基本思路。主元素消去法的基本思路。61531815331242321321321xxxxxxxxx方程組方程組例例.615331215318321321321xxxxxxxxx交換方程次序作為主元素，選取絕對(duì)值最大的系數(shù) 167. 5944. 0

15、167. 1000. 5333. 21531832323211xxxxxxxx，得到，得到消去后兩個(gè)方程中的消去后兩個(gè)方程中的 428. 9142. 3167. 5944. 0167. 1153183323212xxxxxxx ，得到，得到個(gè)方程中的個(gè)方程中的并消去第三并消去第三交換后兩個(gè)方程次序，交換后兩個(gè)方程次序，001. 3000. 2000. 1321 xxx經(jīng)過(guò)回代，得到經(jīng)過(guò)回代，得到1 1.用高斯消去法求解線性方程組時(shí),應(yīng)避免小的主元.在實(shí)際計(jì)算中,進(jìn)行第k步消去前,應(yīng)該在第k列元素 中找出絕對(duì)值最大者,例如 列主元素消去法基本思想列主元素消去法基本思想n,.,ki ,a1-kik

16、n,.,kiaa1-kiknik1-kpkmax2.再把第p 個(gè)方程與第k 個(gè)方程組進(jìn)行交換,使 成為主元.我們稱這個(gè)過(guò)程為選主元素選主元素.由于只在第k 列元素中選主元素,通常也稱為按列選主元素按列選主元素(或稱部分選主元).1-kpka3.如果在第k步消去前,在第k 個(gè)方程到第n 個(gè)方程所有的xk到xn的系數(shù) 中,找出絕對(duì)值最大者,例如 再交換第k,p 兩個(gè)方程和第k,q 兩個(gè)未知量的次序,使 成為主元素. 稱這個(gè)過(guò)程為完全選主元素完全選主元素。4.不論是哪種方式選出主元素,而后再按上面介紹的計(jì)算步驟進(jìn)行消去的計(jì)算,一般都稱為主元素高斯消去法主元素高斯消去法。在實(shí)際計(jì)算中,常用按列選主元素

17、的高斯消去法。列主元素消去法基本思想列主元素消去法基本思想n,.,kj, n,.,ki ,a1-kijn,.,kj , n,.,kiaa1-kijnj , ik1-kpqmax1-kpqa1 , 1./)(.3, 1, 1,. e, 1,/.d, 1，. c,0.b|max. a121.2.1Gauss2.21，nniababbnkibmbbnkjiamaankiaambbnkjaadkiia,n,knBAiinijjijiikikiikjikijijkkikikkikjjikkiknikkk，回代，消元：計(jì)算乘子，否則換行轉(zhuǎn)向若停止，則系數(shù)矩陣奇異若保存主元所在行的指標(biāo)按列選主元循環(huán)對(duì)，階，

18、右端項(xiàng)輸入系數(shù)矩陣消去法列主元素算法例2.5 列主元消去法解方程組解 第一次消元對(duì)因列主元素為a31(1)，故先作行變換r2r3，然后進(jìn)行消元計(jì)算可得4178. 745625. 5996. 33816. 1078125. 014 . 022002. 0|)1()1(BA40371. 00020. 20029. 2047471. 000010. 161077. 004178. 745625. 5996. 3|)2()2(BA4178. 745625. 5996. 33816. 178125. 04 . 022002. 032121321xxxxxxxx續(xù)解 第二次消元對(duì) ，因列主元素為a32(2

19、) ，故先作行變換r2r3，然后進(jìn)行消元計(jì)算可得由此回代,得 x =(1.9272,-0.69841,0.90038)T與精確解 x =(1.9273,-0.69850,0.90042)T相比較是比較準(zhǔn)確的. )2()2(| BA35160. 039050. 00040371. 00020. 20029. 204178. 745625. 5996. 3|)3()3(BA高斯消去法的乘除總運(yùn)算分析如下：消元次數(shù)k 消元乘法次數(shù) 消元除法次數(shù) 回代乘除法總次數(shù) 1 n(n-1) n-1 2 (n-1)(n-2) n-2 . . . k (n-k+1)(n-k) n-k . . n-1 2*1 1

20、n(n+1)/2 故高斯消去法的計(jì)算量為 N=n(n2-1)/3+n(n-1)/2+n(n+1)/2=n3/3+n2-n/3 當(dāng) N 充分大時(shí)為 n3/3 2.4 高斯消去法的計(jì)算量高斯消去法的計(jì)算量 方法的特點(diǎn)方法的特點(diǎn)1. 全主元素法的精度優(yōu)于主元素法,這是由于全主元素是在全體系數(shù)中選主元,故它對(duì)控制舍入誤差十分有效.但全主元素法在計(jì)算過(guò)程中,需同時(shí)作行與列的互換,因而程序比較復(fù)雜,計(jì)算時(shí)間較長(zhǎng)。列主元素法的精度雖稍低于全主元素法,但其計(jì)算簡(jiǎn)單工作量大為減少,且計(jì)算經(jīng)驗(yàn)與理論分析均表明,它與全主元素法同樣具有良好的數(shù)值穩(wěn)定性,列主元素法是求解中小型稠密性方程組的最好方法之一。2. 選主元消

21、去法(包括解線性方程組的所有直接的方法)比較適用于中小型方程組.對(duì)高階方程組,即使系數(shù)矩陣是稀疏的,但在計(jì)算中很難保持稀疏性,因而有存儲(chǔ)量大，程序復(fù)雜等不足,所幸的是這一缺點(diǎn)可用迭代法解決。3. 另外,高斯選主元消去法還可技巧性的解決一些特殊線性方程組。 在計(jì)算過(guò)程中，由于計(jì)算機(jī)字長(zhǎng)的有限性，不可避免地產(chǎn)生舍入誤差。同時(shí)，由于所求問(wèn)題的初始數(shù)據(jù)（例如線形方程組的系數(shù)矩陣和右端項(xiàng)系數(shù)）往往是帶有一定誤差的。因此計(jì)算結(jié)果總是不可避免地帶有誤差，或者說(shuō)，如果初始數(shù)據(jù)有擾動(dòng)，勢(shì)必將帶來(lái)具有一定誤差的計(jì)算結(jié)果。就拿Ax = b來(lái)說(shuō)，由于觀測(cè)或計(jì)算等原因，線性方程組兩端的系數(shù)A和b都帶有誤差A(yù)和b，這樣實(shí)

22、際建立的方程組是近似方程組(A+A)(x+x)=b+b。對(duì)近似方程組求出的解是原問(wèn)題的真解x加上誤差x,即x+x。而x是由A及b引起的，它的大小將直接影響所求解的可靠性。這種解依賴于方程組系數(shù)的誤差這種解依賴于方程組系數(shù)的誤差 A A及及 b b的問(wèn)的問(wèn)題，稱為線性方程組解對(duì)系數(shù)的敏感性。題，稱為線性方程組解對(duì)系數(shù)的敏感性。 2.5 線性方程組解對(duì)系數(shù)的敏感性線性方程組解對(duì)系數(shù)的敏感性方程組 此方程組的準(zhǔn)確解為x1=0, x2=-1?，F(xiàn)將其右端加以微小的擾動(dòng)使之變?yōu)椋?經(jīng)計(jì)算可得準(zhǔn)確解為x1=2, x2=-3. 這兩個(gè)方程組的解相差很大，說(shuō)明方程組的解對(duì)常數(shù)項(xiàng)b的擾動(dòng)很敏感。 121001.

23、22121xxxx120002. 1001. 22121xxxxTb)0 ,0002. 0(病態(tài)方程組：病態(tài)方程組：n如果方程組AX=b由于A或b的小擾動(dòng)而導(dǎo)致解嚴(yán)重失真，則此方程組稱為病態(tài)方程組，否則稱為良態(tài)方程組。n判定一個(gè)病態(tài)方程組的簡(jiǎn)單方法；病態(tài)方程組一般不能用解方程組的常用方法求解，而采用“迭代求解法”來(lái)計(jì)算 2.6 LU分解分解當(dāng)當(dāng)A的所有順序主子式均不為零時(shí)，矩陣的所有順序主子式均不為零時(shí)，矩陣A可唯可唯一地分解為兩個(gè)三角矩陣的乘積一地分解為兩個(gè)三角矩陣的乘積ALU其中，其中，L是單位下三角矩陣，是單位下三角矩陣，U是上三角矩陣是上三角矩陣 1112121nnlllL(2.13)

24、 nnnnuuuuuuU22211211定義定義 LUA 叫叫A的三角（因子）分解，其中的三角（因子）分解，其中 是是L是上三角。是上三角。U下三角下三角, , L為單位下三角陣（對(duì)角元全為為單位下三角陣（對(duì)角元全為1 1），），U為上三角陣，則稱為上三角陣，則稱LUA 為為DoolittleDoolittle分解分解; ;L若若 是下三角，是下三角，U 是單位上三角，則稱是單位上三角，則稱LUA 定理定理 n n階陣階陣)2( nA 有唯一有唯一DoolittleDoolittle分解分解(Crout(Crout）A 的前的前n-1n-1個(gè)順序主子式不為個(gè)順序主子式不為0.0.（證略）（證略

25、）三角分解不唯一三角分解不唯一, ,為此引入為此引入定義定義 若若 為為CroutCrout分解。分解。為什么要討論三角分解？為什么要討論三角分解？若在消元法進(jìn)行前能實(shí)現(xiàn)三角分解若在消元法進(jìn)行前能實(shí)現(xiàn)三角分解ALU，則則 BXLUBAX)(下三角方程組）下三角方程組）則有則有上三角方程組）上三角方程組）令令( ( BLYYUX 容易回代求解容易回代求解(2.14)L是單位下三角矩陣，因此是單位下三角矩陣，因此(2.15) 111132ijjijiiniylbyby,其中其中，yi是向量是向量Y的分量，的分量，Y(y1,y2,yn)T,再?gòu)脑購(gòu)腢XY中解出中解出X(2.16) 1211,/ )(

26、/nniuxuyxuyxnijiijijiinnnnnnnnnnaaaaaaaaa212222111211 1. 1.直接三角分解法（以直接三角分解法（以DoolittleDoolittle分解為例）分解為例） 設(shè)設(shè)1112121nnlllnnnnuuuuuu22211211 由矩陣乘法由矩陣乘法2212122222212112122221111111111121321111uulalaululiuLLulauauuljuLuniualauliuiLaujjULuiiiiiijjjjjjiiiijj/ )( n),3,4, 2i4) n),2, j223) ),( n),2,3,L2) n),

27、1,2,(j n),1,2, ) 21 （列列的的第第行行的的第第列列：用用的的第第求求（列列的的第第行行的的第第行行：用用的的第第求求列列（的的第第行行的的第第列列：用用的的第第求求（列列的的第第的的第第一一行行乘乘行行：用用的的第第求求 11112121100001kmmjkmkjkjkjkjkmmjkmkjjjkjjjkkkkulauauulauuuulll,n,k,kjjukLku),()(,，列列的的第第行行的的第第行行：用用的的第第求求kkkmmkimikikikkkikkmmkimikkkkkkkikiuulalaululauuulll,n),k(ikuiLkL 11112110

28、0001)(,，即，即列列的第的第行行的第的第列：用列：用的第的第求求 ),( ),( ),(),( ),( nkiuulalnkkjulaunkniualnjauDoolittlekkkmmkimikikkmmjkmkjkjiijj113232211111111111對(duì)于對(duì)于分解公式分解公式(2.18)(2.17) 718754277432271354277432262321321xxxxxx和和分解求解方程組分解求解方程組用用例例LU.12322113131112121131211 ualualuuu/,/,解解先先LU分解系數(shù)矩陣，由分解系數(shù)矩陣，由2.17式得式得再由再由2.18式得式

29、得621323321331333322123132321321232312212222 ululauuulalulauulau/ )( 613322121121542774322653321 yyy,對(duì)第一個(gè)方程組，由對(duì)第一個(gè)方程組，由2.15式得式得再由再由2.16式得式得221123 xxx,647321 yyy,對(duì)第二個(gè)方程組，由對(duì)第二個(gè)方程組，由2.15式得式得再由再由2.16式得式得111123 xxx,2 2平方根法平方根法定理定理 設(shè)設(shè)A A對(duì)稱正定，則有非奇異下三角陣對(duì)稱正定，則有非奇異下三角陣L L，使，使TLLA - - 理論基礎(chǔ)理論基礎(chǔ) ( (證略）證略）分解方法：設(shè)分解

30、方法：設(shè)jiijnnnnnnnnnnnnnnaallllllllllllaaaaaaaaa 其其中中 2221211121222111212222111211( choleskey( choleskey分解分解) )2222221222211111111121lllalaallllLlalallLlalaallLalaljjjjjjjTTjjjjjT121222212122222111111111 n),3,4,(j j2L )2 22L 1) )( n),2,(j j1L )2 )( )1 )(2222 列列第第行行第第列列第第行行第第列列第第行行第第取取正正由由矩矩陣陣乘乘法法及及其其改改

31、進(jìn)進(jìn)分分解解。缺缺點(diǎn)點(diǎn)：開開方方運(yùn)運(yùn)算算。主主元元。平平方方根根法法穩(wěn)穩(wěn)定定，不不必必先先受受到到控控制制舍舍入入誤誤差差的的放放大大所所以以說(shuō)說(shuō)的的最最大大元元的的值值不不會(huì)會(huì)超超過(guò)過(guò)程程中中這這說(shuō)說(shuō)明明在在分分解解過(guò)過(guò)故故列列：第第行行、第第、計(jì)計(jì)算算量量小小優(yōu)優(yōu)點(diǎn)點(diǎn)：）（，可可得得：TkmkknkkmkknkkkkmkmkmkkkmjmkmjkkkjmkmkmkkkklalaallakknkjllalllalLDL,A maxmax21,2 1121211112113 3 追趕法追趕法n追趕法仍然保持LU分解特性，它是一種特殊的LU分解。充分利用了系數(shù)矩陣的特點(diǎn)，而且使之分解更簡(jiǎn)單，得到

32、對(duì)三對(duì)角線性方程組的快速解法。n因三對(duì)角矩陣的非零元素呈“帶狀”，我們也因此將它叫做帶狀矩陣。 nnnnnnnnnnnnnnnnnbacbacbacbAdxbxadxcxbxadxcxbxadxcxb111222111111111232221212111對(duì)應(yīng)的系數(shù)矩陣三對(duì)角線性方程組：三對(duì)角線性方程組：設(shè)有方程組Ax=d，其中A為三對(duì)角矩陣。假設(shè)系數(shù)矩陣A滿足條件：對(duì)A作Crout分解形式為：11112222221111111111nnnnnnnnnnbcabcabcab ijjiijiaUL01000,0,0,011 的計(jì)算公式推得計(jì)算由比較系數(shù)所得關(guān)系式定義，有：即根據(jù)矩陣乘法及相等時(shí)待定常數(shù)。比較其中iiiiiiiiiiiiiiianiacniabaacabBa,) 1, 2(), 2(,;,)(,111111第i個(gè)分量第j個(gè)分量), 2()(), 3 , 2(,)1, 2 , 1(1111111nibcniabaacbaniaiiiiiiiiiii追趕法計(jì)算公式追趕法計(jì)算公式分解進(jìn)行也可對(duì)三對(duì)角矩陣的過(guò)程可稱為趕的解將計(jì)算的過(guò)程可稱為追及將計(jì)算計(jì)算公式從而得之對(duì)角方程組的解出及時(shí)，可由當(dāng)求解分解后的實(shí)現(xiàn)DoolittleAxxxd