第九講線性代數(shù)方程組的解法下ppt課件

1、 直接方法高斯簡單消去法直接方法高斯簡單消去法 、選主、選主 元消去元消去法法 、高斯、高斯約當(dāng)消去法約當(dāng)消去法 、三角分解法、三角分解法 范數(shù)與誤差分析范數(shù)與誤差分析 迭代法迭代法一、向量范數(shù): , 1, 0 , 00; () 2, , () 3, , nnxRxxxx x x x xy xy , x yR 向量范數(shù)定義設(shè)對任意向量按一定的規(guī)則有一實(shí)數(shù)與之對應(yīng) 記為若滿足且當(dāng)且僅當(dāng)正定為任意實(shí)數(shù)齊次對任意 () xx三角不等式則稱為 向量 的范數(shù))x(xxxnin12i212212 =+=1i11 nnixxxx,maxxmaxxxxnini11=1/1,pnpipixx 1111 -: 1

2、,2,(1, )maxmax maxmaxniiiiiii ni niii ni nx yRx y inxyxyxyxyxy 可驗(yàn)證上面范數(shù)均滿足范數(shù)定義的條件。以范數(shù)為例滿足條件顯然。 由于為向量，而其分量為實(shí)數(shù)，故有12 (1,2,3) 6,3,14. ,0, TnxxxxRm Mnxm xxMx例：計(jì)算向量的各種范數(shù)。解：如果中兩個范數(shù)和，存在實(shí)數(shù)，使得對任意 維向量都有 ， 則稱這兩個范數(shù)是等價(jià)的。對兩個等價(jià)范數(shù)而言，同一向量序列有相同的極限。2221221122212222 12 max.max. 2 ini njii nnjxxxxxxxxxxxxxxxnnxxxn 不難證明， 范

3、數(shù)，范數(shù)和范數(shù)是等價(jià)的。例： 設(shè)則范數(shù)和范數(shù)等價(jià)。如不作說明，今后是指任意一種向量范數(shù)。 1, 0 , 00; () 2, , () 3, , () 4 nAAAAA A A A AB AB , A Bn ABABAA定義：對任意 階方陣 ，按一定的規(guī)則由一實(shí)數(shù)與之對應(yīng)，記為。若滿足且當(dāng)且僅當(dāng)正定為任意實(shí)數(shù)齊次對任意兩個 階方陣三角，（相容性條件）則稱為矩陣 的范數(shù)。1 max () 1 maxmaxnxijxxAnRAxAxAanxnAxxAxxxxAxAAxx定理：設(shè) 為 階方陣，是中的向量范數(shù)，則 是一種矩陣范數(shù)，稱其為由向量范數(shù)誘導(dǎo)出的矩陣范數(shù)。證：設(shè)為任意 階方陣， 為任意 維非零向

4、量。因?yàn)闉榉稊?shù)是 的單位向量，故1111 10.0,max0. 00 0. 2 maxmax max. 3, xxxxAAAAxAAxAxAAAxAxAxAnABAB ，顯然若則反之，若，對任意兩個 階方陣 和 ，11111max ()max max()maxmax .xxxxxAB xAxBxAxBxAxBxAB1111 4 . max ()max() maxmax 5 xxxxnxAxAAxAxxABAB xA BxABxABxABnxAxAx，對任意 維非零向量 ,有 即 故有，對任意 維向量 ，都有。這一 性質(zhì)稱為矩陣范數(shù)與向量范數(shù)的相容性?？捎扇N常用的向量范數(shù)誘導(dǎo)出矩陣范數(shù)。211

5、221max , ()TxijAAxA AAan其中是的最大特征值。又稱為譜范數(shù)。 設(shè)為 階方陣。111111maxmax , 1nijxj niAAxa 為矩陣的列向量的 范數(shù)的最大值稱為矩陣的列范數(shù)。111m axm ax , 1nijxinjAA xa 為 矩 陣 的 行向 量 的 范 數(shù) 的 最 大 值 稱 為 矩 陣 的 行 范 數(shù) 。212* 12 ,34 6,7,5.46. /nRAAAAAAAAAAAAA如果將矩陣范數(shù)看作空間上的向量范數(shù)，則由向量范數(shù)的等價(jià)性可得矩陣范數(shù)的等價(jià)性。例：計(jì)算 的各種范數(shù)。解：矩陣的誤差可用矩陣范數(shù)表示：設(shè)是 的近似矩陣，、分別稱為的關(guān)于范數(shù)的絕對

6、誤差與相對誤差。1 (1,2, ) ( ) maxn niii nARinAA 定義：設(shè)的特征值為稱為 的譜半徑。 ( ) , A AAA定理：為的任意矩陣范數(shù) ( , A ( )AxxxAxxxAxAAA1211221211225 22 .1.000012021.1.000012.000011 10 ,xxxxxxxxxxxx一個實(shí)際問題化為數(shù)學(xué)問題，初始數(shù)據(jù)往往會有誤差，即有擾動，從而使計(jì)算結(jié)果產(chǎn)生誤差。例：方程組而方程組比較這兩個方程組可以看出，他們只是右端項(xiàng)有微小的差1別，最大相對誤差為但它們的解卻大不相同，解分2量1的相對誤差至少為 。2 AbAxbAAAxb定義： 如果矩陣 或常數(shù)

7、項(xiàng) 的微小變化，引起方程組解的巨大變化，則稱此方程組為“病態(tài)”方程組，矩陣 稱為“病態(tài)”矩陣（相對于方程組而言）。否則稱方程組為“良態(tài)”方程組， 稱為“良態(tài)”矩陣。矩陣的“病態(tài)”性質(zhì)是矩陣本身的特性。為了定量刻劃方程組的“病態(tài)”程度，下面對方程組就系數(shù)矩陣或右端項(xiàng)分別有擾動的兩種情形進(jìn)行討論。111111 , () ,bbxxA xxbbAxbAxbxAbxAbAbAxbxAAAbAAbxbxbAAA設(shè)有 擾 動， 相 應(yīng) 解 的 擾 動 記 為即由，兩 邊 取 范 數(shù)又 因 為此 式 表 明 當(dāng) 右 端 項(xiàng) 有 擾 動 時 解 的 相 對 誤 差 不 超 過右 端 項(xiàng) 的 相 對 誤 差 的

8、倍 。11111111 , ()()()0()()1, 11AAxxAAxxbAxA xxxAA xxAAxxAAAAAAAAxAAxAAAAAAAAA如果右端項(xiàng)無擾動，系數(shù)矩陣有擾動，相應(yīng)的解的擾動仍記為則如果充分小，使得則由上式得上式表明，當(dāng)系數(shù)矩陣有擾動時，解的擾動仍與有關(guān)。一般地，1越大，解的擾動也越大。-11-11max222min , ()(1,2 (1) ()(2) A() ().()vvvTTAAAcond AAAvAcond AAAA Acond AAAA AA綜上分析可知 量實(shí)際上刻劃了解對原始數(shù)據(jù)變化的靈敏程度 即刻劃了方程組的“病態(tài)”程度。定義：設(shè) 為非奇異陣，稱數(shù)或）

9、為矩陣 的條件數(shù)。常用的條件數(shù)，有的譜條件數(shù)當(dāng) 為對稱矩陣時121 (),nncond AA，其中，為 的絕對值最大和絕對值最小的特征值。1122 1( )1. ( )1. 20 ()( ) 3( )1 ()vvvvvvvAcond Acond AAAA AIAccond cAcond AAcond AARcond RAcon、對任何非奇異矩陣 ，都有由定義、設(shè) 為非奇異矩陣且（常數(shù)），則、如果 為正交矩陣，則 ；如果 為非奇異矩陣， 為正交矩陣,則22()( ) .d ARcond A3 1112111 231111121nHilbertnHnnnnH例：矩陣計(jì)算的條件數(shù)。133331333

10、661112393630111 ,3619218023430180180111345(1)() .11()408748.6()2.910 .nHHHcond Hcond HHHcond HHn解：計(jì)算條件數(shù) 同樣可計(jì)算一般矩陣當(dāng) 越大時，病態(tài)越嚴(yán)重。1122331122311111236111113 2 1234121471116034531.000.5000.333 0.5000.3330.2500.3330.2500.200 xxxxxxHbxxxxx（ ）考慮設(shè)及 有微小誤差（取 位有效數(shù)字）有3331.831.080.783()(). (1.0895,0.4880,1.491)TxHH

11、xxbbxx簡記為其解為3333 (1.0895,0.4880,1.491) , (1,1,1)(0.0895, 0.5120,0.4910)0.18 100.02%0.51200.182%51.2%1 50TTTxxxxHHbxbxHb由于 這表明 與 相對誤差不超過0.2%，而引起解的相對誤差超過. 123 ,det()0,()(nAAAIAcond Acond計(jì)算條件數(shù)需要求矩陣的逆，因而比較困難。根據(jù)數(shù)值經(jīng)驗(yàn)，在下列情況下，方程組常是“病態(tài)”的。（ ）在用主元素法時出現(xiàn)小主元；（ ）如果 的最大特征值和最小特征值之比（按絕對值）是大的，則是“病態(tài)”的。（ ）系數(shù)矩陣中有行（或列）近似線

12、性相關(guān)，或系數(shù)行列式的值近似于零。但這不是絕對的，如當(dāng)為很小的數(shù)時，有但)1,4IAA方程組狀態(tài)良好。（ ）系數(shù)矩陣元素間數(shù)量級相差很大，并且無一定規(guī)則可能“病態(tài)”。1 ; ., ()( ).,AxbPAQyPbyQ xP Qcond PAQcond AP Q用選主元素的消去法不能解決病態(tài)問題，對病態(tài)方程組可采用高精度的算術(shù)運(yùn)算或采用預(yù)處理方法。即將求解轉(zhuǎn)化為一等價(jià)方程組選擇非奇異矩陣使一般選擇為對角陣或者三角矩陣。*12112112 22 1.00001201,1 AxbxxrbAxrxrxxxxxxxx在求得方程組的一個近似解后，檢驗(yàn)精度的一個簡單方法是將代入方程組求得殘量（余量）。如果很

13、小，就認(rèn)為解比較準(zhǔn)確。但在“病態(tài)”嚴(yán)重的方程組，也有即使殘差量很小，近似解與準(zhǔn)確解的差仍很大的情形。上例中，方程組若以作為它的近似解，其殘量5*(2,2)(2,2.00001)(0, 10) (2,0)(1,1)(1, 1) TTTTTTrxx很小，但解的誤差卻不小。*1*11*11 - ( ). () ( ). xxAxbx xrrxcond AxbbAxA xxxAbAxA rArxxArrrAAcond AbxbbA定理：設(shè) 和分別是方程組的準(zhǔn)確解和近似解，為 的殘量，則證：因?yàn)樗杂缮鲜娇煽闯?，?dāng)方程組“病態(tài)”嚴(yán)重時，條件數(shù)很大，即使殘量很小，解的相對誤差仍可能很大。直接法直接法: :

14、 經(jīng)過有限次運(yùn)算后可求得方程組準(zhǔn)確解的經(jīng)過有限次運(yùn)算后可求得方程組準(zhǔn)確解的方法方法( (不計(jì)舍入誤差不計(jì)舍入誤差!)!)迭代法：從解的某個近似值出發(fā)，經(jīng)過構(gòu)造一個無窮序列迭代法：從解的某個近似值出發(fā)，經(jīng)過構(gòu)造一個無窮序列去逼近準(zhǔn)確解的方法。普通有限步內(nèi)得不到準(zhǔn)確解去逼近準(zhǔn)確解的方法。普通有限步內(nèi)得不到準(zhǔn)確解 直接法比較適用于中小型方程組。對高階方程組，直接法比較適用于中小型方程組。對高階方程組，既使系數(shù)矩陣是稀疏的，但在運(yùn)算中很難堅(jiān)持稀疏性，既使系數(shù)矩陣是稀疏的，但在運(yùn)算中很難堅(jiān)持稀疏性，因此有存儲量大，程序復(fù)雜等缺乏。因此有存儲量大，程序復(fù)雜等缺乏。 迭代法那么能堅(jiān)持矩陣的稀疏性，具有計(jì)算簡

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

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

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

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

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

20、 01001nnnnnnnnBbbbbbbbbbbbb AD I-aaaaaaaaaaaaInn1nnn2n12n22211n12111122111 1 12 111222(,)(, , , )TTnnnnggggbDbababa同 樣1* n0 1 2 B gnnkJacobiBgxxxxxx（）（ ）（ ）迭代，若收斂，則*1*1* () IB xgDAxD bAxb即故假設(shè)序列收斂, 那么收斂到解。B稱迭代矩陣。123123123110272 10283542 10010100101200.10.210100011020.100.2100011150.20.201005 xxxJacob

21、ixxxxxxBIDA例：用迭代法求解解：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精確解為(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 xxin 輸入維數(shù)最大容許迭代次數(shù)置對

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

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

24、()kknnnnkkkkLxU xgLIL xU xgILILxILU xILgbbbbbb(k+1)用矩陣表示為x其中，移項(xiàng)可得因?yàn)楣蚀嬖?，上式可改寫?2131212323132112111111(1)1( 000000000 , () ()nnnnnnnnkkAaaaaaaLaaUaaaaLD LUD UILD DD LDDLxILUx 如果用矩陣 來表示，記則由)1(1)1( )11()()() () kkILgxDLUxDLbMDLUGaussSeidel式中矩陣為迭代法的迭代矩陣。123123123(0)1(0)(0)12311(1)(0)21321310272 10283542(

25、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ù)下去，精確解為 GauseseidelJacobiGauseseidelJacobiGauseseidelJacobiJacobiGauseseidelJacobi上例計(jì)算結(jié)果表明，迭代法比迭代法效果

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

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

28、kkkiiijjijjjj iiixxxxxxxxba xa xai 松弛法是將乘上一個參數(shù)因子作為修正項(xiàng)而得到新的近似解，具體公式為即1,2, ) 111nAxbGaussSeidel按上式計(jì)算的近似解序列的方法稱為松弛法，稱為松弛因子。當(dāng)時稱為低松弛；是迭代；時稱為超松弛法。(1)( )( )1(1)1( )1( )( )1(1)1( )11111(1)1 () (1)1,() () (1kkkkkkkkkkxxxxDLxD UxD bxxDLxD UxD bIDLIDLDLxDL松弛法迭代公式的矩陣表示：因?yàn)楣剩ǎ?與存在，有( )11)() () (1) ,kDU xDLbMDLDU松

29、弛法的迭代矩陣為松弛因子的選取對收斂速度影響極大 但目前尚無可供實(shí)用的計(jì)算最佳松弛因子的方法。通常是根據(jù)系數(shù)矩陣的性質(zhì)及實(shí)際經(jīng)驗(yàn)，通過試算來確定松弛因子。(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,2,)0.40.7(1.8)(1,1,1)(1.200,1.3996,1.6

30、001) (1.2,1.4,1.6)kkkkkTTTxxkxxxxxx 將代入上式開始迭代，精確解(0 )(0 )(0 )(0 )112(0 )(0 )11111121(0 )(0 )111.(),(,),(,),.2.1.3. (1)() / (1)() / ijnnnjjjiniiiijjijjiijjiAabbbn xxxxNkxxbaxaxxba xa xa 輸 入維 數(shù)最 大 容 許 迭 代 次 數(shù)， 參 數(shù)置計(jì) 算1(0 )1(0 )(0 ) (2,1) (1)() /4.,55.,1,(1, 2,),3nnnnnjjnnjiiinxxbaxaxxxkNkk xxin若輸 出停 機(jī)

31、 ； 否 則 轉(zhuǎn)。若置轉(zhuǎn)；否 則 ， 輸 出 失 敗 信 息 ， 停 機(jī) 。11212 (1,2, ) ( )max(,) (,)(1,2,), () (iii nnkkkkknAninAAAAAAAAkA 迭代法的收斂與迭代矩陣的特征值有關(guān)。定義：設(shè) 為 階方陣，為 的特征值，稱特征值的最大值為矩陣 的譜半徑，記為稱為矩陣 的譜。由特征值的定義知，矩陣的譜是因而)kA :, ():, , () . :,iiiiiiiiiiiAnAAAuuuAuAuuAAAAn定理 設(shè) 為任意 階方陣為任意由向量范數(shù)誘導(dǎo)出的矩陣范數(shù) 則證 對 的任一特征值及相應(yīng)的特征向量都有因?yàn)闉榉橇阆蛄?于是有由的任意性即

32、得證畢定理 設(shè) 為任意 階方陣 則對任意正數(shù)存在一種矩陣2, () , ()()AAnAAAAA范數(shù)使得證明略。對任意 階方陣 一般不存在矩陣范數(shù)使得。但若 為對成矩陣，則有。 lim0()1 lim0 lim0 () 0()() lim()0 ()11 ()1kkkkkkkkkkkAnAAAAAAAAAAAA定理：設(shè) 為階方陣，則的充要條件為。證：必要性：若由矩陣收斂的定義知又因由極限存在的準(zhǔn)則，有所以。充分性。若，取()0,21() ()12,limlim0lim0.kkkkkkkkAAAAAAAAA由上一定理知，存在一種矩陣范數(shù)，使得而(0)(1)( )( )*( )*( ) (0,1,

33、2,)()1. : , lim kkkkkkxgxMxgkxMnxxxxxMxgx定理：對任意初始向量和右端項(xiàng) ，由迭代格式產(chǎn)生的向量序列收斂的充要條件是證 必要性 設(shè)存在 維向量使得則滿足由迭代公式有*(1)*(1)*2(2)*(0)*(0)*( )*(0) ()()() lim()lim()0, lim0 ()1.kkkkkkkkkkxMxgMxgM xxMxxMxxMxxxxxnMM于是有因?yàn)闉槿我?維向量 因此上式成立必須由上一定理*()*(1)*(0 )*(0 )()* :()1,1,0, lim0 ()(), lim ()limkkkkkkkkMMIMngIMxgxxM xgMxx

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

35、LDUDLa aa 推論松弛法收斂的必要條件是。證：設(shè)松弛法的迭代矩陣由特征值。因?yàn)橛啥ɡ?，松弛法收斂必有又因?yàn)?122)(1)det()(1)102 nnnnDUa aaM。迭代法收斂與否只決定于迭代矩陣的譜半徑，與初始向量及右端項(xiàng)無關(guān)。對同一方程組，由于不同的迭代法迭代矩陣不同，可能出現(xiàn)有的方法收斂，有的方法發(fā)散的情形。123123123221 2223 1122100 111 010221001000 100220 xxxxxxxxxADL例：對方程組討論Jacobi迭代法與Gauss-Seidel迭代法的收斂性。解：求迭代矩陣判別其譜半徑是否小于 。022 001000U13123 J

36、acobi022 10122022 110220,()01,JacobiBIDAIBB迭代法的迭代矩陣為其特征方程為因此有于是所以迭代法收斂。1121 Gauss-Seidel100100 110 ()110221021100022022()11000102302100000222 023(2)00020,DLDLMDLUIM 迭代，由特征方程特征值為232,()21,M故所以迭代發(fā)散。 021 121,1,1 BM上例說明了確實(shí)只是松弛法收斂的必要條件，而非充要條件，因?yàn)镚auss-Seidel迭代記為的情形。判斷定理雖然給出了判別迭代收斂的充要條件，但要求逆矩陣和特征值。推論 與 僅分別給

37、出了收斂的充分與必要條件，許多情形下不能起作用。如上例，兩個方法均有由推論 無法判別收斂性。對一些特殊的系數(shù)矩陣可給出幾個常用的判別收斂條件11112112222 ()(1,2, ) ,0110 11nijiiijjj inAaaainiAiAAAAAAAAAA定義：若 階方陣滿足且至少有一個 值，使上式中不等號嚴(yán)格成立，則稱 為弱對角占優(yōu)陣。若對所有 ，上式不等號均嚴(yán)格成立，則稱為嚴(yán)格對角占優(yōu)陣。定義：如果矩陣 不能通過行的互換和相應(yīng)的列互換成為形式其中，為方陣，則稱 為不可約。 例：132100011012011PITP AP ,1.JacobiG auss-S eidel2.01,3.0

38、21012210 1102121115012A xbAAAABA設(shè) 有 線 性 方 程 組下 列 結(jié) 論 成 立 ：若為 嚴(yán) 格 對 角 占 優(yōu) 陣 或 不 可 約 弱 對 角 占 優(yōu) 陣 ， 則迭 代 法 和迭 代 法 均 收 斂 。若為 嚴(yán) 格 對 角 占 優(yōu) 陣 ，則 松 弛 法 收 斂 。若為 對 稱 正 定 陣 ， 則 松 弛 法 收 斂 的 充 要 條 件 為。上 兩 例 中 ：為 嚴(yán) 格 對 角 占 優(yōu)B陣 ， 故 Jacobi與 Gauss-Seidel迭代 均 收 斂 。為 非 嚴(yán) 格 對 角 占 優(yōu) 陣 ， 但 為 對 稱 正 定陣 ，=1.4故 松 弛 法 收 斂 。-11112211,122111223(02)111022