第五章 第一節(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òu)造一個向量序列 ，當(dāng)，當(dāng) 收斂于收斂于 時，使時，使 是所給方程組的解。于是，就有下列問題需要

2、計論：是所給方程組的解。于是，就有下列問題需要計論：(0)X( )kX*X*X (1) 構(gòu)造迭代格式；構(gòu)造迭代格式；(2) 收斂性及誤差估計。收斂性及誤差估計。一、引言一、引言整理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)造出一個向量序列：012,kXXXX即即 為（為（1.1）的解。）的解。 *X整理ppt11,BMN FM b令令 ，即得（，即得（1.1）. 注注：若方程組由下面形式給出：若方程組由下面形式給出 1.4AXb 則需要把它改寫成便于迭代的形則需要把它改寫成便于迭代的形 式（式（1.1），），其其 方方 法是多種多樣的，最一般的方法是將法是

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

5、零。此時關(guān)系式(1.6)成為成為DAE 式中，式中， 是簡單的對角陣，是簡單的對角陣， 它的對角線元它的對角線元素是素是 的元素的倒數(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 定理定理 對任意右端向量對任意右端向量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 在具在具 體問體問 題題 中中 ， 譜譜 半半 徑徑 是是 很很 難計算的，難計算的，但由于有但由于有 ，所，所 以可以以可以 用用

8、 來來 作作 為為 的的 一種估計。一種估計。 當(dāng)當(dāng) 時迭代格式一定收時迭代格式一定收斂，不斂，不 過這過這 只是只是 收斂收斂 的充分條件。的充分條件。( )BBB( )B1B 定理定理 2 若若 則迭代格式（則迭代格式（1.2）收斂于）收斂于（1.1）的解）的解 , 且有誤差估計且有誤差估計 1B *X( )*( )(1),1kkkBXXXXB（1.7）或或( )*(1)(0),1kkBXXXXB(1.8)整理ppt( )*(1)*()kkXXB XX證明證明 因為因為 ，所以迭代格式，所以迭代格式 （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或或時，時， 迭代法收斂。迭代法收斂。 Jacobi11max1nijjiBb依依 定定 理理 2 可知，當(dāng)可知，當(dāng)例2、用Jacobi迭代法解方程組123123123202324,812,231530 xxxxxxxxx:AXb整理ppt取 00,0,0TX,問Jacobi迭代法是否收斂？若收斂，需要迭代多少次，才能保證各分量的誤差絕對值小于610？11223313501020411308822210155xxxxxx解：解：由例1知，此方程組可改寫為 1112312123131231360,102051130,8822102155kkkkkkkkkkkkxxxxxxxxxxxx 其迭

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

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

13、） 310 ( 其中其中 為為 A 的對角元組成的對角陣，所以的對角元組成的對角陣，所以 與與 只是非對角元的符號不同只是非對角元的符號不同 ）。）。 AJacobi2DA2DAADA若若 為對稱正定陣而為對稱正定陣而 為非正定陣，則為非正定陣，則迭代法不收斂。迭代法不收斂。12340.240.0880.0930.1590.040.08420 xxx解、顯然，系數(shù)矩陣A是一個嚴(yán)格對角占優(yōu)矩陣， 所以Jacobi迭代法收斂。整理ppt 先將方程組化成（先將方程組化成（1.1）的形式。）的形式。以以4，3，4分別除三個方程兩邊得分別除三個方程兩邊得 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 因為在所要求的精度內(nèi)因為在所要求的精度內(nèi) ，故停止計，故停止計 算算, 即為所求近似解即為所求近似解 。(3)(2)XX(3)X 從條件從條件 中，也可以看出，對任意中，也可以看出，對任意初始向量初始向量 ， 迭代法收斂。取迭代法收斂。取 0.081,B(0)XJa