第五章 第一節(jié) Jacobi迭代法

1、整理ppt第一節(jié)第一節(jié) 迭代法迭代法 Jacobi三三 、 迭代法的收斂性迭代法的收斂性 Jacobi一、引言一、引言二、二、 迭代格式的構(gòu)造迭代格式的構(gòu)造 四、小結(jié)四、小結(jié)整理ppt( )kX 迭代法是解線性代數(shù)方程組的另一類重要方法，特別迭代法是解線性代數(shù)方程組的另一類重要方法，特別適于求解系數(shù)矩陣為稀疏陣的大型線性代數(shù)方程組。它適于求解系數(shù)矩陣為稀疏陣的大型線性代數(shù)方程組。它 的的基本思想是，從任一初始向量基本思想是，從任一初始向量 出發(fā)，按某一規(guī)則，逐出發(fā)，按某一規(guī)則，逐次構(gòu)造一個(gè)向量序列次構(gòu)造一個(gè)向量序列 ，當(dāng)，當(dāng) 收斂于收斂于 時(shí)，使時(shí)，使 是所給方程組的解。于是，就有下列問題需要

2、計(jì)論：是所給方程組的解。于是，就有下列問題需要計(jì)論：(0)X( )kX*X*X (1) 構(gòu)造迭代格式；構(gòu)造迭代格式；(2) 收斂性及誤差估計(jì)。收斂性及誤差估計(jì)。一、引言一、引言整理ppt 任取任取 代入（代入（1.1）的右端，算得的結(jié)果記為）的右端，算得的結(jié)果記為 ，再以，再以 代入（代入（1.1）的右端，算得的結(jié)果記為）的右端，算得的結(jié)果記為 ，如此進(jìn)行下去，便得到迭代格式如此進(jìn)行下去，便得到迭代格式 (0)nXR(1)X(1)X(2)X 其中，其中， 是是 階方陣，階方陣， 是已知身量是已知身量, 是未知向量。是未知向量。 BnFX二、二、 迭代格式的構(gòu)造迭代格式的構(gòu)造 XBXF設(shè)所給方程

3、組為（1.1）整理ppt(1)( ),0,1,kkXBXF k (1.2) 顯然，若顯然，若 存在，則有存在，則有 ( )*limkkXX*XBXF(1.3)此格式稱為此格式稱為 迭代格式迭代格式，稱，稱 為為迭代矩陣迭代矩陣。 JacobiB由此迭代格式可構(gòu)造出一個(gè)向量序列：012,kXXXX即即 為（為（1.1）的解。）的解。 *X整理ppt11,BMN FM b令令 ，即得（，即得（1.1）. 注注：若方程組由下面形式給出：若方程組由下面形式給出 1.4AXb 則需要把它改寫成便于迭代的形則需要把它改寫成便于迭代的形 式（式（1.1），），其其 方方 法是多種多樣的，最一般的方法是將法是

4、多種多樣的，最一般的方法是將 分分解為兩個(gè)矩陣之差解為兩個(gè)矩陣之差 A1.5AMN 其中矩陣其中矩陣M可逆，于是可逆，于是(1.4)成為成為 11XMNXM b(1.6)整理ppt 必須指出，必須指出，(1.5)中的中的 應(yīng)是便于求逆的，應(yīng)是便于求逆的， 的最簡(jiǎn)單選擇是把它選為對(duì)角陣，通常，當(dāng)?shù)淖詈?jiǎn)單選擇是把它選為對(duì)角陣，通常，當(dāng) 的的 對(duì)角線元素全不為對(duì)角線元素全不為 零時(shí)，就把零時(shí)，就把 選為選為 的對(duì)角的對(duì)角 線，于是線，于是MMAAMADE11XD EXD b 其中其中 是具有是具有 的對(duì)角線元素的對(duì)角陣的對(duì)角線元素的對(duì)角陣 ，而，而 在對(duì)角線上的元素為零。此時(shí)關(guān)系式在對(duì)角線上的元素為

5、零。此時(shí)關(guān)系式(1.6)成為成為DAE 式中，式中， 是簡(jiǎn)單的對(duì)角陣，是簡(jiǎn)單的對(duì)角陣， 它的對(duì)角線元它的對(duì)角線元素是素是 的元素的倒數(shù)。的元素的倒數(shù)。 1DD整理ppt例1、將方程組：123123123202324,812,231530 xxxxxxxxx:AXb化成便于迭代的形式.XBXF最直觀的方法是，將方程組改寫為：11232123312323240,20202011120,88823300151515xxxxxxxxxxxx 11223313501020411308822210155xxxxxx整理ppt三三 、 迭代法的收斂性迭代法的收斂性 Jacobi 若由迭代格式若由迭代格式所構(gòu)

6、成的向量序列所構(gòu)成的向量序列 收斂，則稱收斂，則稱 迭代格式迭代格式(1.2)收斂，或稱收斂，或稱 迭代法收斂。迭代法收斂。( )kXJacobi(1)( ),0,1,kkXBXF k (1.2)由關(guān)系式：(1)( )*,kkXBXFXBXF可得(1)*( )2(1)*(1)(0)*()()()kkkkXXB XXBXXBXX 整理ppt(0)X 定理定理 對(duì)任意右端向量對(duì)任意右端向量F和初始向量和初始向量 ， 迭代格式迭代格式(1.2)收斂于（收斂于（1.1）的解）的解 的充要條的充要條件是件是 *X( ) 1B 所以，為使所以，為使 Jacobi迭代法收斂，即要使迭代法收斂，即要使( )*

7、kXXk 0()kBk必要且只要0kB 。而 的( )1B充要條件是矩陣B的譜半徑，故有. 由定理由定理1可以看出，迭代是否收斂只與迭代矩陣可以看出，迭代是否收斂只與迭代矩陣的譜半徑有關(guān)，而迭代矩陣的譜半徑有關(guān)，而迭代矩陣 是由系數(shù)矩陣是由系數(shù)矩陣 演變過演變過來的，所以迭代是否收斂是與系數(shù)矩陣來的，所以迭代是否收斂是與系數(shù)矩陣 以及演變的以及演變的方式有關(guān)，方式有關(guān)， 與與 右右 端向量和初始迭代向量的選擇無關(guān)。端向量和初始迭代向量的選擇無關(guān)。BAA整理ppt 在具在具 體問體問 題題 中中 ， 譜譜 半半 徑徑 是是 很很 難計(jì)算的，難計(jì)算的，但由于有但由于有 ，所，所 以可以以可以 用用

8、 來來 作作 為為 的的 一種估計(jì)。一種估計(jì)。 當(dāng)當(dāng) 時(shí)迭代格式一定收時(shí)迭代格式一定收斂，不斂，不 過這過這 只是只是 收斂收斂 的充分條件。的充分條件。( )BBB( )B1B 定理定理 2 若若 則迭代格式（則迭代格式（1.2）收斂于）收斂于（1.1）的解）的解 , 且有誤差估計(jì)且有誤差估計(jì) 1B *X( )*( )(1),1kkkBXXXXB（1.7）或或( )*(1)(0),1kkBXXXXB(1.8)整理ppt( )*(1)*()kkXXB XX證明證明 因?yàn)橐驗(yàn)?，所以迭代格式，所以迭代格式 （1.2）收斂。其次，由關(guān)系式）收斂。其次，由關(guān)系式( )1BB從而有從而有( )*( )

9、(1)(1).,kkkXXBBXX有有( )*(1)*.kkXXBXX(1)( )( )*.()kkkBXXXX( )(1)( )*.,kkkBXXBXX因此有因此有 ( )*( )(1),1kkkBXXXXB（1.7）整理ppt( )(1)(1)(2)1(1)(0)()(),kkkkkXXB XXBXX所以所以1( )(1)(1)(0).kkkXXBXX又從迭代格式又從迭代格式 (1)( ),0,1,kkXBXF k有 將此式代入（將此式代入（1.7）式，便有）式，便有 ( )*( )(1)11010111kkkkkBXXXXBBBXXBBXXB這就證明了定理2。整理ppt1max1niji

10、jBb或或時(shí)，時(shí)， 迭代法收斂。迭代法收斂。 Jacobi11max1nijjiBb依依 定定 理理 2 可知，當(dāng)可知，當(dāng)例2、用Jacobi迭代法解方程組123123123202324,812,231530 xxxxxxxxx:AXb整理ppt取 00,0,0TX,問Jacobi迭代法是否收斂？若收斂，需要迭代多少次，才能保證各分量的誤差絕對(duì)值小于610？11223313501020411308822210155xxxxxx解：解：由例1知，此方程組可改寫為 1112312123131231360,102051130,8822102155kkkkkkkkkkkkxxxxxxxxxxxx 其迭

11、代格式為整理ppt由于迭代矩陣：130102011088210155B的范數(shù)113B，所以用Jacobi迭代法解此方程組一定收斂。經(jīng)一次迭代得： 1111123,63,252TTXxxx于是有， 102XX整理ppt由誤差估計(jì)式( )*(1)(0),1kkBXXXXB可知，若使610kXX只須(1)(0)6101kBXXB 610101lnlnBkBXX亦只須 610101lnlnBXXkB整理ppt由于113B 102XX故611013ln2131ln3k所以，要保證各分量誤差絕對(duì)值小于610，需要迭代14次。整理ppt 除了用定理除了用定理1、定理、定理2來判別迭代法的來判別迭代法的收斂性

12、外，還可根據(jù)方程組的系數(shù)矩陣的特收斂性外，還可根據(jù)方程組的系數(shù)矩陣的特點(diǎn)給出一些點(diǎn)給出一些收斂性的判別條件收斂性的判別條件。JacobiA 1) 若若 是嚴(yán)格對(duì)角占優(yōu)陣（各行非對(duì)角元是嚴(yán)格對(duì)角占優(yōu)陣（各行非對(duì)角元 絕對(duì)值之和小于對(duì)角元絕對(duì)值的矩陣），則絕對(duì)值之和小于對(duì)角元絕對(duì)值的矩陣），則 迭代法收斂。迭代法收斂。 設(shè)線性代數(shù)方程組的形式為設(shè)線性代數(shù)方程組的形式為 ,則則AX b2）若A為對(duì)稱正定矩陣，1112121222122nnnnnnaaaaaaDAaaa也為對(duì)稱正定矩陣，則 迭代法收斂；Jacobi整理ppt例例3 用用Jacobi迭代法解下列方程組（精確到迭代法解下列方程組（精確到

13、） 310 ( 其中其中 為為 A 的對(duì)角元組成的對(duì)角陣，所以的對(duì)角元組成的對(duì)角陣，所以 與與 只是非對(duì)角元的符號(hào)不同只是非對(duì)角元的符號(hào)不同 ）。）。 AJacobi2DA2DAADA若若 為對(duì)稱正定陣而為對(duì)稱正定陣而 為非正定陣，則為非正定陣，則迭代法不收斂。迭代法不收斂。12340.240.0880.0930.1590.040.08420 xxx解、顯然，系數(shù)矩陣A是一個(gè)嚴(yán)格對(duì)角占優(yōu)矩陣， 所以Jacobi迭代法收斂。整理ppt 先將方程組化成（先將方程組化成（1.1）的形式。）的形式。以以4，3，4分別除三個(gè)方程兩邊得分別除三個(gè)方程兩邊得 12310.060.0220.0310.0530.010.0215xxx 其迭代矩陣為00.060.020.0300.050.010.020B 11112213300.060.0220.0300.0530.010.0205kkkkkkxxxxxx 從而有從而有Jacobi迭代格式：迭代格式：（1.9）整理ppt(0)(2,3,5) ,TX 因?yàn)樵谒蟮木葍?nèi)因?yàn)樵谒蟮木葍?nèi) ，故停止計(jì)，故停止計(jì) 算算, 即為所求近似解即為所求近似解 。(3)(2)XX(3)X 從條件從條件 中，也可以看出，對(duì)任意中，也可以看出，對(duì)任意初始向量初始向量 ， 迭代法收斂。取迭代法收斂。取 0.081,B(0)XJa