第七章解線性方程組的迭代法.

1、12 雅可比迭代法雅可比迭代法 高斯高斯-塞德爾迭代法塞德爾迭代法 SOR方法方法 迭代法的收斂性及誤差估計迭代法的收斂性及誤差估計3迭代法：從解的某個近似值出發(fā)，通過構(gòu)造一個無窮序列迭代法：從解的某個近似值出發(fā)，通過構(gòu)造一個無窮序列去逼近精確解的方法。（一般有限步內(nèi)得不到精確解）去逼近精確解的方法。（一般有限步內(nèi)得不到精確解） 直接法比較適用于中小型方程組。對高階方程組，直接法比較適用于中小型方程組。對高階方程組，既使系數(shù)矩陣是稀疏的，但在運(yùn)算中很難保持稀疏性，既使系數(shù)矩陣是稀疏的，但在運(yùn)算中很難保持稀疏性，因而有存儲量大，程序復(fù)雜等不足。因而有存儲量大，程序復(fù)雜等不足。 迭代法則能保持矩陣

2、的稀疏性，具有計算簡單，編制迭代法則能保持矩陣的稀疏性，具有計算簡單，編制程序容易的優(yōu)點(diǎn)，并在許多情況下收斂較快。故能有效程序容易的優(yōu)點(diǎn)，并在許多情況下收斂較快。故能有效地解一些高階方程組。地解一些高階方程組。4 迭代法的基本思想是構(gòu)造一串收斂到解的序列，即建立一種從已有近似解計算新的近似解的規(guī)則。由不同的計算規(guī)則得到不同的迭代法，本章介紹單步定常線性迭代法。1(0 )(1)()()() ()(,) , (k=0,1,2,)TijnnnnnkkkkAxbAabbbxM xgMngRxRxM xgxkxAxb對 線 性 方 程 組其 中非 奇 異 矩 陣 ， 構(gòu) 造 其 形 如的 同 解 方 程

3、 組 ， 其 中為階 方 陣 ，。任 取 初 始 向 量代 入 迭 代 公 式產(chǎn) 生 向 量 序 列， 當(dāng)充 分 大 時 ， 以作 為方 程 組的 近 似 解 ， 這 就 是 求 解 線 M性 方 程 組的 單 步 定 常 線 性 迭 代 法 。稱 為 迭 代 矩 陣 。5()()()()()( lim0 lim limknnkkkkknknikxRxRxxxxxxRxRxx 定義：設(shè)為中的向量序列，如果其中為向量范數(shù)，則稱序列收斂于 ，記為定理：中的向量序列收斂于中的向量 當(dāng)且僅當(dāng))()()()()1212()()()()()1() (1,2, )(,) ,(,) lim010max lim

4、=0 (1,2, ) kikkkkTTnnkkkkkkiijjjnkiikxinxxxxxxxxxxxxinxxxxxxxxin 其中。證：由定義，收斂于 即而對任意，有由極限存在準(zhǔn)則得即() lim (1,2, )kiikxxin 6()()()()()()() lim0 lim () (1, 2,),(kkkkkkkkijijkAnAnAAAAAAAakAanAA 定 義 ： 設(shè)為階 方 陣 序 列 ，為階 方 陣 ， 如 果其 中為 矩 陣 范 數(shù) ， 則 稱 序 列收 斂 于 矩 陣， 記 為定 理 ： 設(shè))均 為階 方 陣 ，則 矩 陣 序 列收 斂 于 矩 陣的 充()(1)()(

5、)(1)() lim ( ,1, 2,) , limlim kijijkkkkkkkkaaijnxM xgxxxxM xgM xgxA 要 條 件 為證 明 略 。定 理 表 明 ， 向 量 序 列 和 矩 陣 序 列 的 收 斂 可 以 歸 結(jié) 為 對 應(yīng)分 量 或 對 應(yīng) 元 素 序 列 的 收 斂 。若 按產(chǎn) 生 的 向 量 序 列收 斂 于 向 量則 有即是 方 程 組xb的 解 。71111221n12112222n2n11n12nn 0 (1, 2,),nnnniiina xa xa xba xaxaxba xa xaxba 若 系 數(shù) 矩 陣 非 奇 異 即則 有11221331

6、1221123322n112233 nnnnnnnngxb xb xb xgxbxbxbxxb xbxbx , (, ,1, 2,),(1, 2,).ijiijiiiiiabbij ijnginaag 其 中812131111212321221231(0)(1)10(1)(2)( )(1)( )00 0 , nnnnnnnnnnkkkbbbbgbbbbgBgbbbbgxBxgxxxBxgxxxxBx（ ）（ ）若記則方程組可簡記為選初值向量代入，代入，如此繼續(xù)下去，就產(chǎn)生一個向量序列滿足(0,1,2,)gkJacobi此過程所給出的迭代法稱為迭代法，又稱簡單迭代法。91211212122121

7、2120110001010 01001nnnnnnnnBbbbbbbbbbbbb AD I-aaaaaaaaaaaaInn1nnn2n12n22211n12111122111 1 12 111222(,)(, , , )TTnnnnggggbDbababa同 樣101* n0 1 2 B gnnkJacobiBgxxxxxx（）（ ）（ ）迭代，若收斂，則*1*1* () IB xgDAxDbAxb即故如果序列收斂, 則收斂到解。B稱迭代矩陣。11123123123110272 10283542 10010100101200.10.210100011020.100.2100011150.20.

8、201005 xxxJacobixxxxxxBIDA例：用迭代法求解解：1(0)(0)(2)(1)(9) (7.2,8.3,8.4)(0,0,0) ,(7.2,8.3,8.4)(9.71,10.70,11.5)(10.9994,11.9994,12.9992)(11,12,13) .TTTTTgDbxBxgxBxgxx(1)取代入迭代式，得x精確解為12(0)(0)(0)(0)112(0)1(0)(0)1.(),( ,),(,),.2.1.3.1,2, ()/4.,55.,1,(1,2, ),3 ijnnniiijjiijj iiiAabbbn xxxxNkinxba xaxxxkNkk xx

9、in 輸入維數(shù)最大容許迭代次數(shù)置對若輸出停機(jī)；否則轉(zhuǎn) 。若置轉(zhuǎn) ；否則，輸出失敗信息，停機(jī)。( )(1,kkMxx ）評價：公式簡單，每迭代一次只需計算一次矩陣和向量的乘法，不改變的稀疏性，需兩組工作單元，存。13(1)( )(1)( )( )( )112213311(1)( )( )( )221123322 (0,1,2,) kkkkkknnkkkknnxBxg kgxb xb xb xgxb xb xb x迭代公式用方程組表示為(1)( )( )( )1122,11( )(1) kkkknnnn nnnkkJacobixxgxb xb xbx因此，在迭代法的計算過程中，需同時保留兩個近似解

10、向量和。若把迭代公式改寫成14(1)( )( )( )112213311(1)(1)( )( )221123322(1)(1)112 kkkknnkkkknnkknnngxb xb xb xgxb xb xb xxb x(1)(1)2,11(0)( ) ,kkn nnnknxxGaussSeidelJacobigb xbx這樣，在整個計算過程中，只需用 個單元存儲近似解分量。而且通常認(rèn)為，近似解可能比老近似解更接近精確解，因此，可望這種迭代會更有效。選取初始向量用上式迭代產(chǎn)生近似解序列這種方法叫迭代法。評價：與相比，只需一組工作單元存放近似解。15(1)()1212,2112(1)()1(1)

11、1()1 0000 U00 ()1,() ()()kknnnnkkkkLxU xgLIL xU xgILILxILU xILgbbbbbb(k+1)用矩陣表示為x其中，移項可得因為故存在，上式可改寫為1612131212323132112111111(1)1( 000000000 , () ()nnnnnnnnkkAaaaaaaLaaUaaaaLD LUD UILD DD LDDLxILUx 如果用矩陣 來表示，記則由)1(1)1( )11()()() () kkILgxDLUxDLbMDLUGaussSeidel式中矩陣為迭代法的迭代矩陣0)1(0)(0)12311

12、(1)(0)21321310272 10283542(0,0,0) ,11 (2)727.2000101011 (2)(7.200083)9.02001010 TxxxGaussSeidelxxxxxxxxxxbxxxbx（ ）（ ）（ ）例：用迭代法求解解：仍取代入迭代式，得(1)(1)123(5)11()7.20009.020042)11.644055(10.9989,11.9993,12.9996)(11,12,13) .Txxbxx（如此繼續(xù)下去，精確解為18 GauseseidelJacobiGauseseidelJacobiGauseseidelJacobiJacobiGauses

13、eidelJacobi上例計算結(jié)果表明，迭代法比迭代法效果好。事實(shí)上，對有些問題迭代法確實(shí)比迭代法收斂得快，但也有迭代比迭代收斂得慢，甚至還有迭代收斂，迭代發(fā)散的情形。評價：與相比，只需一組工作單元存放近似解。19( 0 )( 0 )( 0 )( 0 )112( 0 )1111121( 0 )111.(),(,),(,),.2.1.3. () / () /(2,1) (ijnnnjjjiniiijjijjiijjinnAabbbn xxxxNkxbaxaxba xa xainxba 輸 入維 數(shù)最 大 容 許 迭 代 次 數(shù)置計 算11( 0 )( 0 ) /4.,55.,1,(1, 2,),

14、3nnjjnnjiixaxxxkNkkxxin若輸 出停 機(jī) ； 否 則 轉(zhuǎn)。若置轉(zhuǎn)；否 則 ， 輸 出 失 敗 信 息 ， 停 機(jī) 。20(1)( )(1)121(1)( )( )111(1)( )( )11 (,), 1 ()Tkkkninkkkiijjijjiijj iinkkkiijjijjijj iiiGaussSeidelxxxxxxxGaussSeidelxb xb xgxba xa xxa 為迭代法加速。記其中由迭代公式得到。于是有( )(1)( )(1,2, )kkkinxGaussSeidelkxxxx 可以把看作迭代的修正項，即第 次近似解以此項修正后得到新的近似解 21

15、(1)( )(1)1(1)( )11 (1)() (kkkkiiiinkkkiiijjijjjj iiixxxxxxxxba xa xai 松弛法是將乘上一個參數(shù)因子作為修正項而得到新的近似解，具體公式為即1,2, ) 111nAxbGaussSeidel按上式計算的近似解序列的方法稱為松弛法，稱為松弛因子。當(dāng)時稱為低松弛；是迭代；時稱為超松弛法。22(1)( )( )1(1)1( )1( )( )1(1)1( )11111(1)1 () (1)1,() () (1kkkkkkkkkkxxxxDLxD UxD bxxDLxD UxD bIDLIDLDLxDL松弛法迭代公式的矩陣表示：因為故（）

16、 與存在，有( )11)() () (1) ,kDU xDLbMDLDU松弛法的迭代矩陣為松弛因子的選取對收斂速度影響極大 但目前尚無可供實(shí)用的計算最佳松弛因子的方法。通常是根據(jù)系數(shù)矩陣的性質(zhì)及實(shí)際經(jīng)驗，通過試算來確定松弛因子。23(0)12123231(1)(1)( )11(1)( )( )112(1)( )22 1.4,(1,1,1) ,21 2021.8 (1)()0.40.7(1)0.4Tinkkkkiiiijjijjjj iiikkkkkxxxxxxxxxxba xa xaxxxxx 例：取用超松弛法解方程組解：由(1)( )13(1)( )(1)332(0)(9)0.7()(0,1

17、,2,)0.40.7(1.8)(1,1,1)(1.200,1.3996,1.6001) (1.2,1.4,1.6)kkkkkTTTxxkxxxxxx 將代入上式開始迭代，精確解24(0 )(0 )(0 )(0 )112(0 )(0 )11111121(0 )(0 )111.(),(,),(,),.2.1.3. (1)() / (1)() / ijnnnjjjiniiiijjijjiijjiAabbbn xxxxNkxxbaxaxxba xa xa 輸 入維 數(shù)最 大 容 許 迭 代 次 數(shù)， 參 數(shù)置計 算1(0 )1(0 )(0 ) (2,1) (1)() /4.,55.,1,(1, 2,)

18、,3nnnnnjjnnjiiinxxbaxaxxxkNkk xxin若輸 出停 機(jī) ； 否 則 轉(zhuǎn)。若置轉(zhuǎn)；否 則 ， 輸 出 失 敗 信 息 ， 停 機(jī) 。2511212 (1,2, ) ( )max(,) (,)(1,2,), () (iii nnkkkkknAninAAAAAAAAkA 迭代法的收斂與迭代矩陣的特征值有關(guān)。定義：設(shè) 為 階方陣，為 的特征值，稱特征值的最大值為矩陣 的譜半徑，記為稱為矩陣 的譜。由特征值的定義知，矩陣的譜是因而)kA26 :, ():, , () . :,iiiiiiiiiiiAnAAAuuuAuAuuAAAAn定理 設(shè) 為任意 階方陣為任意由向量范數(shù)誘導(dǎo)

19、出的矩陣范數(shù) 則證 對 的任一特征值及相應(yīng)的特征向量都有因為為非零向量 于是有由的任意性即得證畢定理 設(shè) 為任意 階方陣 則對任意正數(shù)存在一種矩陣2, () , ()()AAnAAAAA范數(shù)使得證明略。對任意 階方陣 一般不存在矩陣范數(shù)使得。但若 為對成矩陣，則有。27 lim0()1 lim0 lim0 () 0()() lim()0 ()11 ()1kkkkkkkkkkkAnAAAAAAAAAAAA定理：設(shè) 為階方陣，則的充要條件為。證：必要性：若由矩陣收斂的定義知又因由極限存在的準(zhǔn)則，有所以。充分性。若，取()0,21() ()12,limlim0lim0.kkkkkkkkAAAAAAA

20、AA由上一定理知，存在一種矩陣范數(shù)，使得而28(0)(1)( )( )*( )*( ) (0,1,2,)()1. : , lim kkkkkkxgxMxgkxMnxxxxxMxgx定理：對任意初始向量和右端項 ，由迭代格式產(chǎn)生的向量序列收斂的充要條件是證 必要性 設(shè)存在 維向量使得則滿足由迭代公式有*(1)*(1)*2(2)*(0)*(0)*( )*(0) ()()() lim()lim()0, lim0 ()1.kkkkkkkkkkxMxgMxgM xxMxxMxxMxxxxxnMM于是有因為為任意 維向量 因此上式成立必須由上一定理29*()*(1)*(0 )*(0 )()* :()1,1

21、,0, lim0 ()(), lim ()limkkkkkkkkMMIMngIMxgxxM xgMxxMxxMxxxxxM 充 分 性 若則不 是的 特 征 值 因 而 有于 是 對 任 意維 向 量方 程 組有 唯 一 解 記 為即并 且又 因 為所 以 對 任 意 初 始 向 量都 有(0 )*(1)()()(0 )(1)()()()=0.1 1, (0,1, 2,).kkkkkkkxxxM xgxxgMxM xgkx即 由 迭 代 公 式產(chǎn) 生 的 向 量 序 列收 斂推 論對 任 意 初 始 向 量和 右 端 項， 若由 迭 代格 式產(chǎn) 生 的 向 量 序 列收 斂3012121111

22、22 2 02 , det()() det()1 det()()(1)1 () (1nnnnnMMMMMDLDUDLa aa 推論松弛法收斂的必要條件是。證：設(shè)松弛法的迭代矩陣由特征值。因為由定理，松弛法收斂必有又因為1122)(1)det()(1)102 nnnnDUa aaM。迭代法收斂與否只決定于迭代矩陣的譜半徑，與初始向量及右端項無關(guān)。對同一方程組，由于不同的迭代法迭代矩陣不同，可能出現(xiàn)有的方法收斂，有的方法發(fā)散的情形。31123123123221 2223 1122100 111 010221001000 100220 xxxxxxxxxADL例：對方程組討論Jacobi迭代法與Ga

23、uss-Seidel迭代法的收斂性。解：求迭代矩陣判別其譜半徑是否小于 。022 001000U3213123 Jacobi022 10122022 110220,()01,JacobiBIDAIBB迭代法的迭代矩陣為其特征方程為因此有于是所以迭代法收斂。331121 Gauss-Seidel100100 110 ()110221021100022022()11000102302100000222 023(2)00020,DLDLMDLUIM 迭代，由特征方程特征值為232,()21,M故所以迭代發(fā)散。34 021 121,1,1 BM上例說明了確實(shí)只是松弛法收斂的必要條件，而非充要條件，因為

24、Gauss-Seidel迭代記為的情形。判斷定理雖然給出了判別迭代收斂的充要條件，但要求逆矩陣和特征值。推論 與 僅分別給出了收斂的充分與必要條件，許多情形下不能起作用。如上例，兩個方法均有由推論 無法判別收斂性。對一些特殊的系數(shù)矩陣可給出幾個常用的判別收斂條件3511112112222 ()(1,2, ) ,0110 11nijiiijjj inAaaainiAiAAAAAAAAAA定義：若 階方陣滿足且至少有一個 值，使上式中不等號嚴(yán)格成立，則稱 為弱對角占優(yōu)陣。若對所有 ，上式不等號均嚴(yán)格成立，則稱為嚴(yán)格對角占優(yōu)陣。定義：如果矩陣 不能通過行的互換和相應(yīng)的列互換成為形式其中，為方陣，則稱

25、 為不可約。 例：132100011012011PITP AP 36 ,1.JacobiG auss-S eidel2.01,3.021012210 1102121115012A xbAAAABA設(shè) 有 線 性 方 程 組下 列 結(jié) 論 成 立 ：若為 嚴(yán) 格 對 角 占 優(yōu) 陣 或 不 可 約 弱 對 角 占 優(yōu) 陣 ， 則迭 代 法 和迭 代 法 均 收 斂 。若為 嚴(yán) 格 對 角 占 優(yōu) 陣 ，則 松 弛 法 收 斂 。若為 對 稱 正 定 陣 ， 則 松 弛 法 收 斂 的 充 要 條 件 為。上 兩 例 中 ：為 嚴(yán) 格 對 角 占 優(yōu)B陣 ， 故 Jacobi與 Gauss-Sei

26、del迭代 均 收 斂 。為 非 嚴(yán) 格 對 角 占 優(yōu) 陣 ， 但 為 對 稱 正 定陣 ，=1.4故 松 弛 法 收 斂 。37-11112211,122111223(02)11102211 -02211022Axb AAAABIDA例 ：討 論 用 三 種 迭 代 法 求 解 的 收 斂 性 。解 ： 因為 對 稱 且 其 各 階 主 子 式 皆 大 于 零 ， 故為 對 稱 正 定 矩陣 。 由 判 別 條 件， Gauss-Seidel迭 代 法 與 松 弛 法均 收 斂 。不 是 弱 對 角 占 優(yōu) 陣 ， 故 不 能 用 條 件 判 斷 。Jacobi迭 代 法 的 迭 代 矩

27、陣 為383212311221131 224411221 ()(1 )021,1 , ()12 IBBJ a c o b i其特征方程得因而迭代法不收斂。39 310 , 9410100033 , 91500423015(),()22AxbAJacobiGaussSeidelBMBM改 變 方 程 組 中 方 程 的 次 序 ， 即 將 系 數(shù) 矩 陣 作 行交 換 ， 會 改 變 迭 代 法 的 收 斂 性 。例 ：與迭 代 的 迭 代 矩 陣 分 別 為譜 半 徑 分 別 是。 均 不 收 斂 。40 ,31094 94310AxbAxbAAAAxbJacobiGaussSeidel若交換

28、方程的次序，得的同解方程組為嚴(yán)格對角占優(yōu)陣，因而對方程組用與迭代求解均收斂。41(1 )()()*()*(1 )( 0 )1*1()*(1 )*( 0 )* ,1, 1 ()1,0 ,) ()() kkkkkkkkxM xgMxxMxxxxMMMIMIMxM xgxxIMgxxMxxMxx定 理 ： 設(shè) 有 迭 代 格 式若收 斂 于則 有 誤 差 估 計 式證 ： 因故于 是(存 在 ， 方 程 組有 唯 一 解，且(。 從 而 有( 0 )11( 0 )1( 0 )1 ) ) )kkkMxIMgMIMIMxgMIMxx（）(42()*1( 0 )11111111()* ) ) ) ) )1

29、 )1 1kkkkxxMIMxxIMIMIIMIMIMIMIMIMIMIMIMMMxx（）取 范 數(shù)(又 因 為(取 范 數(shù)(移 項 得(代 入 得(1)( 0 )xxM。43()*(1)(0 )(1)(0 )(0 )(1)4( 1:(1)ln ln00.10.207.20.100.2,0,8.30.20.2008.410, 0.4, kkMxxxxMkMxxkMMxxMx由 誤 差 估 計 式根 據(jù) 事 先 給 定 的 精 度， 可 估 計 出 迭 代 的 次 數(shù)例 ： 若則 有1)(0 )8.4 12.932,13xk即 需 要 迭 代次 才 能 滿 足 精 度 。44(1)()()*()

30、*()(1)()*(1)*(1)11(1)(1)1(1)()()*1(1) ,1, 1() )()kkkkkkkkkkkkkkkxMxgMxxMxxxxMxxM xxM xIMgM IMxMxgM IMxxxxMIMx定理：設(shè)有迭代格式若收斂于則有誤差估計式證：因 ()()(1)()(1) .11kkkkkxMxxMMxx當(dāng)不太接近 時，可用作為停機(jī)準(zhǔn)則。4511112211211222221122 nnnnnnnnnnna x a xa xba x a xa xba x a xa xb階線性方程組： , X ,11Tn nijAXbTA nn , , ) , , )(x(bxbab矩陣表示記

31、為這里46 工程實(shí)際計算中，線性方程組的系數(shù)矩陣常常具有對稱正定性，即其各階順序主子式及全部特征值均大于零。矩陣的這一特性使它的三角分解也有更簡單的形式，從而導(dǎo)出一些特出的解法，如平方根法與改進(jìn)的平方根法。 , TALALLL定理：設(shè) 是對稱正定矩陣，則存在唯一的非奇異下三角陣使得且 的對角元素皆為正。47111112121222221211221000 0000 (1,2,).0 (),()(1,2,), () /(1,)nnTnnnnnniijkjjjjjjkkijijikjkjjllllllllALLlllllinljklaljnlal llijn 由其中由矩陣乘法及當(dāng)時得1101111

32、222;0(2,3,)(3,)jkkiillinllin 這里規(guī)定。計算順序是按列進(jìn)行，即。4821114 2 ,; 2.()/(1,2, ).()/(,1,1).Tiiiikkiikniikikiik ibbacAAxbaLybyL xyxybl ylinxyl xlin n 當(dāng)矩陣 完成平方根分解后，求解，即求解兩個三角形方程組(1)求（ ），求3 /6, AnGaussAbLAy xbLn由于 的對稱性，平方根法的乘除運(yùn)算量為數(shù)量級，約是消去法的一半。上機(jī)計算時，所需存儲單元也少，只要存儲 的下三角部分和右端項 ，計算中 存放在 的存儲單元，存儲在 的存儲單元。但這種方法在求 時需作 次

33、開方運(yùn)算，這樣又增加了計算量.為了避免開方，可使用改進(jìn)的平方根方法。49123412413412342312552141635158xxxxxxxxxxxxxx例例 用用平方根法平方根法求解方程組求解方程組解解1213112131250522121010141161232535115831211A11210,11 3531221TALLLy ,1, 1, 1, 1 .TTL xy x 解畢故知故知解得解得50121212211211 111 11,0 (),TnnnnnjjjkdldALDLlldllllljk 其中由比較法得5112111111 1,2, ,;()/(1, ). 1,2, ,

34、;()/(1, ).iiiiikkkijijijkk ikikikikkiiiiik ikkijijiik jkikindal dlal d ldjintl dindat llat ldjin 對于上式雖避免了開方運(yùn)算，但增加了相乘因子，引進(jìn)變量對于有15211111 ,;(2, )./;/(1,2,1).TTTTiiiikkknnnniiikikk iALDLLLLDLLyb DL xyybybl yinxydxydl xin 對稱正定矩陣 按分解和按分解計算量差不多，但分解不需要開方計算。求解計算公式5311112222211111 .iiiiinnnnnnnnnxdbcxdabcxdab

35、cAxdabcxdabxd 在數(shù)值計算中，如三次樣條插值或用差分方法解常微分方程邊值問題，常常會遇到求解以下形式的方程組簡記 此系數(shù)矩陣的非零元素集中分布在主對角線及其相鄰兩次對角線上，稱為三對角矩陣。方程組稱為三對角方程組。54111122231 0 0(2,3,1)01111(1,2,1)iiiiinnnnnibcbaca cinbauclucALUlcluc in 定理：設(shè)三對角方程組系數(shù)矩陣滿足下列條件：則它可分解為其中為已給出的，且分解是唯一的5511111111 , (2,3,) 0(1 2,) /(2,3,)iiiiiiiiiiiiiiiAbualuimbc luuimublau

36、imubc l將上式右端按乘法規(guī)則展開 并與 進(jìn)行比較 得如果，則由上式可得5611( )111111111/(2,3, )kkkkkknnnnnkkkkkGausekucucAabcabcabubcaukn按消去法步驟易得，經(jīng)次消元后，三對角方程的系數(shù)矩陣變?yōu)槠渲小?711112221 2121 2121 21 2121 2121 2122221111(2)2 0., 00(1,2, )iAubbcbacbbbabcc abcbbc abbc abcc aubcubbbuAuinLU由于 滿足定理所給條件，顯然有又因為于是從而有故且矩陣仍滿足定理條件。依此類推可得出。因此由上面公式唯一確定了

37、 和 。5811111111 /(2,3, ) (2,3, )/: ()/(1,2,1) ,iiiiiiikkkknnnkkkkkubALUla uimubc lydLydydl yknxyuUxyxyc xuknnGause分解公式：解得：再解得追趕法的基本思想與消去法及三角分解法相同只是由于系數(shù)中出現(xiàn)了,大量的零可使計算公式簡化減少了計算量。可證當(dāng)系數(shù)矩陣為嚴(yán)格對角占優(yōu)時此方法具有良好的數(shù)值穩(wěn)定性。59A事實(shí)上，追趕法的求解過程就是將系數(shù)矩陣事實(shí)上，追趕法的求解過程就是將系數(shù)矩陣分解兩個簡單的二對角矩陣，從而歸結(jié)為求解兩分解兩個簡單的二對角矩陣，從而歸結(jié)為求解兩個簡單方程組的過程。個簡單方

38、程組的過程。上述定理也表明，追趕法的原理和高斯消去上述定理也表明，追趕法的原理和高斯消去法相同，但考慮到方程組的特點(diǎn)，計算時會把大法相同，但考慮到方程組的特點(diǎn)，計算時會把大量零元素撇開，從而大大節(jié)省計算量。量零元素撇開，從而大大節(jié)省計算量。60例例 用追趕法解下面三對角方程組用追趕法解下面三對角方程組12343 1 0 0101 4 1 0110 1 6 1300 0 2 848xxxx61解解：先把系數(shù)矩陣分解成如下形式：先把系數(shù)矩陣分解成如下形式11223341 3 1 0 0 1 1 1 4 1 0 1 0 1 6 1 1 0 0 2 8 1 1pqpqpqp由遞推公式可知由遞推公式可知

39、1111113, 3pbqcp2221222113, 113pba qqcp33323336311, 1163pba qqcp62444348263pba q又由遞推公式（又由遞推公式（4.274.27）可得：）可得：111103ydp2221223()11yda yp33323307()63yda yp44434()5yda yp63再由遞推公式（再由遞推公式（4.284.28）可得：）可得：445xy33344xyq x22231xyq x11123xyq x故所求的解向量為故所求的解向量為3,1,4,5Tx 6460年代出現(xiàn)的QR算法是目前計算中小型矩陣的全部特征值與特征向量的最有效方法

40、。實(shí)矩陣、非奇異。理論依據(jù)：任一非奇異實(shí)矩陣都可分解成一個正交矩陣Q和一個上三角矩陣R的乘積，而且當(dāng)R的對角元符號取定時，分解是唯一的。()(1)(1)(1)1(2)1(2)1111111 QRQR (1,2,). , kkkkkkAQ RkAR QAAAAAQ RQARAR QQAQAA基本方法的基本思想是利用矩陣的分解通過迭代格式將化成相似的上三角陣（或分塊上三角陣），從而求出矩陣 的全部特征值與特征向量。由即。于是即與相似。同理可()(2,3,)kAAk 得，。故它們有相同的特征值。65可證，在一定條件下，基本可證，在一定條件下，基本QR方法產(chǎn)生的矩陣序列方法產(chǎn)生的矩陣序列A(k) “基本基本”收斂于一個上三角陣（或分塊上三角陣）。收斂于一個上三角陣（或分塊上三角陣）。即主對