num_3.3迭代法的收斂定理

1、第三章第三章 線性方程組迭代解法線性方程組迭代解法 3.3 迭代法的收斂定理迭代法的收斂定理3.3 迭代法的收斂性迭代法的收斂性l基本數(shù)學(xué)問題描述基本數(shù)學(xué)問題描述l一、基本收斂定理一、基本收斂定理l定理定理3.2的證明的證明l實(shí)例求解實(shí)例求解l二、二、Jacobi 迭代法和迭代法和Gauss-Seidel迭代法的收斂速度迭代法的收斂速度基本數(shù)學(xué)問題描述基本數(shù)學(xué)問題描述迭代法的收斂性迭代法的收斂性，是指方程組bAX 從任意初始向量X(0)出發(fā)，由迭代算法fBXXkk )()1(算出向量序列,)1()()2()1( kkXXXX隨著k的增加而趨向于解向量X *。 記各次誤差向量)()1(1)0(0

2、kkXXXXXX 顯然，迭代法的收斂性迭代法的收斂性與誤差向量序列誤差向量序列,10k 隨著k的增加而趨向于零向量是等價(jià)的。 由于精確解X *自然滿足fBXX 因此有 )()1(kkXXBXX 或kkB 1 再遞推出0 kkB 所以，迭代法收斂性迭代法收斂性與迭代矩陣的冪迭代矩陣的冪B k，隨著k的增加而趨向于零矩陣是等價(jià)等價(jià)的。返回節(jié)返回節(jié)(譜半徑有界譜半徑有界) 設(shè)設(shè) ,則對(duì)任一種算子范數(shù)則對(duì)任一種算子范數(shù) ,均有均有n nAR|A( ) |AA定理定理1設(shè)設(shè) , 則則 的充分條件是的充分條件是B的的譜半徑譜半徑( )1B0()kBk n nBR定理定理2前一章的內(nèi)容：前一章的內(nèi)容：一、基

3、本收斂定理一、基本收斂定理由由 X(k+1)=BX(k)+f 及及 X *=B X *+f可見可見 X(k) X* B k 0 ( (k k ) ) k+1 = X (k+1) - X *= B（X (k) - X *） = = B k+1（X(0) -X *） = B k+1 0 可推知可推知 11 01,maxknii nJordanBBBBBB 利用矩陣的標(biāo)準(zhǔn)形，可以證明(前一章中的結(jié)論)其中叫做 的譜半徑。若 的特征值為 ，則(B) (0)(1) 1 3.1kkXBXfXXBXfB 迭迭代代法法收收斂斂的的充充要要條條件件設(shè)設(shè)有有線線性性方方程程組組，則則對(duì)對(duì)于于任任意意的的初初始始向

4、向量量，迭迭代代法法收收斂斂的的充充分分必必要要條條件件是是。定定理理性質(zhì)有關(guān)。性質(zhì)有關(guān)。的的代矩陣代矩陣的取值無關(guān)，而只與迭的取值無關(guān)，而只與迭和和與與法收斂與否法收斂與否表明，線性方程組迭代表明，線性方程組迭代定理定理 1 . 3 )0(BfX1. 定理定理3.1為判斷迭代法的收斂性提供為判斷迭代法的收斂性提供 了強(qiáng)有力的手段：了強(qiáng)有力的手段： 注意是充分必要條件！注意是充分必要條件！2. 定理定理3.1的條件往往不易驗(yàn)證：的條件往往不易驗(yàn)證： 矩陣的譜半徑不易求出！矩陣的譜半徑不易求出！注：注：3. 利用譜半徑的有界性可以給出另外一利用譜半徑的有界性可以給出另外一 個(gè)條件較弱的結(jié)果：個(gè)條

5、件較弱的結(jié)果： 即定理即定理3.2 0k 1B1 X 3 2X. kBXf 迭迭代代法法收收斂斂的的充充分分條條件件 如如果果，則則對(duì)對(duì)任任意意初初始始向向定定量量，迭迭代代法法必必理理收收斂斂，且且有有)1()()(*1 kkkXXBBXX(1)(1)A矩矩陣陣 的的譜譜半半徑徑不不超超過過矩矩陣陣的的任任何何一一種種算算子子范范數(shù)數(shù)! !( )(1)(0)*1kkBXXXXB進(jìn)一步，我們可以推知進(jìn)一步，我們可以推知： 式式(1)(1)說明，當(dāng)說明，當(dāng)|B|1 且不接近且不接近1并且相鄰兩次并且相鄰兩次迭代向量迭代向量X(k+1) 與與 X (k)很接近時(shí)，則很接近時(shí)，則X(k)與精確解與精

6、確解X *很接近。因此，在實(shí)際計(jì)算中，用很接近。因此，在實(shí)際計(jì)算中，用| X (k+1) - X (k) |作為迭代終止條件是合理的。作為迭代終止條件是合理的。 反復(fù)利用反復(fù)利用 | X (k+1) - X*|=|BX (k)- BX*|=|B( (X (k)- X*) )| B.XX (k)- X*,可以得到可以得到 |X (k)- X*|Bk XX(0)- X*，可見可見X X (0)越接近越接近X*，序列，序列 X (k)收斂越快，收斂速度收斂越快，收斂速度與初值與初值X (0)的選取有關(guān)。的選取有關(guān)。 另一方面，由于另一方面，由于(B) B1，B越小，越小，說明說明(B) 越小，序列越

7、小，序列 X (k)收斂越快。收斂越快。 收斂速度的概念收斂速度的概念下面我們給出收斂速度的概念：下面我們給出收斂速度的概念： 定義定義3.1 R(B)= -ln(B)，稱為迭代法的漸進(jìn)，稱為迭代法的漸進(jìn)收斂速度。收斂速度。證明: 顯然顯然)()()(*) 1(*) 1()(kkkkXXXXXX 根據(jù)范數(shù)性質(zhì)根據(jù)范數(shù)性質(zhì)(3)(三角不等式三角不等式) 可知可知YXYX YYXYYXX )(成立，也即成立，也即性質(zhì)成立。性質(zhì)成立。YXYX 因此因此成成立立)(*)1(*)(*)1(*)1()()()(kkkkkkXXXXXXXXXX )()()()1(*)1(*)1(*)(* kkkkXXBBX

8、BXfBXfBXXX顯然顯然根據(jù)范數(shù)性質(zhì)根據(jù)范數(shù)性質(zhì)(4)(乘積不等式乘積不等式) 可知可知BAAB成成立立) 1(*) 1(*)(*)( kkkXXBXXBXX)(*) 1(*1kkXXBXX 也即也即再將上兩式聯(lián)立，可以得出以下結(jié)果再將上兩式聯(lián)立，可以得出以下結(jié)果)1()()(*)1( kkkXXBBXX)(*kXX 再將此不等式兩端同時(shí)減去再將此不等式兩端同時(shí)減去 可得可得)(*)(*) 1(*)1 (kkkXXBBXXXX 由第由第2式可知式可知)(*)1(*)1()(kkkkXXXXXX 證明完畢。證明完畢。 將將定理定理3.1和和3.2用于用于Jacobi迭代法及迭代法及Seide

9、l迭代法，迭代法，則有則有 ; 1)( 1)( .1 GJBBSeidelJacobibAX 收收斂斂的的充充要要條條件件是是迭迭代代法法的的解解線線性性方方程程組組 。收收斂斂的的充充分分條條件件是是迭迭代代法法的的解解線線性性方方程程組組 1 1 .2 GJBBSeidelJacobibAX ULDBULDBGJ11, 其中其中在一般情況下，在一般情況下，計(jì)算矩陣的范數(shù)計(jì)算矩陣的范數(shù)比比計(jì)算譜半徑計(jì)算譜半徑省事，省事，所以通常是利用所以通常是利用定理定理3.2進(jìn)行判斷。進(jìn)行判斷。 但但定理定理3.2只是充分條件，所以即使判斷失效，只是充分條件，所以即使判斷失效，迭代法仍可能收斂，這時(shí)就應(yīng)該

10、使用迭代法仍可能收斂，這時(shí)就應(yīng)該使用定理定理3.1判斷。判斷。 設(shè)有線性方程組設(shè)有線性方程組 X=BX+f，其中，其中 218 . 03 . 00 . 09 . 0fB考察迭代法考察迭代法 X (k+1)=B X(k)+f 的收斂性。的收斂性。例如例如解解： 由于由于 均大于均大于1，故，故定理定理3.2在此無法在此無法判斷；判斷； 但因?yàn)榈驗(yàn)?1 =0.9, 2=0.8,即即(B) =0.91,由由定理定理3.1知知本題迭代法收斂。本題迭代法收斂。 54. 1, 1 . 1,02. 1, 2 . 121 FBBBB返回節(jié)返回節(jié)二、二、Jacobi 迭代法和迭代法和Gauss-Seidel迭

11、代法的收斂速度迭代法的收斂速度l引子引子l對(duì)角占優(yōu)矩陣對(duì)角占優(yōu)矩陣l實(shí)例實(shí)例l相關(guān)定理相關(guān)定理l定理定理3.3的證明的證明返回節(jié)返回節(jié)引子引子 雖然利用雖然利用定理定理3.1和和定理定理3.2可以判定可以判定Jacobi 迭代迭代法和法和G-S迭代法的收斂性，但其中只有迭代法的收斂性，但其中只有定理定理3.2對(duì)對(duì)Jacobi 迭代法使用比較方便，此外，對(duì)于大型方程迭代法使用比較方便，此外，對(duì)于大型方程組，要求出組，要求出G-S迭代矩陣迭代矩陣BG和和(BG)以及以及Jacobi 迭代迭代矩陣矩陣BJ和和(BJ)都不是容易的事。都不是容易的事。 這里介紹一些判定收斂的充分條件這里介紹一些判定收斂

12、的充分條件，它們是利它們是利用原方程組系數(shù)矩陣用原方程組系數(shù)矩陣A和迭代矩陣和迭代矩陣B的特殊性質(zhì)建立的特殊性質(zhì)建立的，很實(shí)用，用起來也很方便。這些判定定理也都的，很實(shí)用，用起來也很方便。這些判定定理也都是以定理是以定理3.1和定理和定理3.2為基礎(chǔ)的。為基礎(chǔ)的。 如果線性方程組如果線性方程組AX=b的系數(shù)矩陣的系數(shù)矩陣A具有某種特殊性質(zhì)具有某種特殊性質(zhì)（如對(duì)稱正定、對(duì)角占優(yōu)等），則可從（如對(duì)稱正定、對(duì)角占優(yōu)等），則可從A本身直接得出某本身直接得出某些迭代法收斂性結(jié)論。些迭代法收斂性結(jié)論。 定義定義3.1 如果矩陣如果矩陣A滿足條件滿足條件(1,2, )(2)iiijj iaain則稱則稱A是

13、嚴(yán)格對(duì)角占優(yōu)陣是嚴(yán)格對(duì)角占優(yōu)陣； 如果矩陣如果矩陣A滿足條件滿足條件(1,2, )(3)iiijj iaain且其中至少有一個(gè)不等式嚴(yán)格成立，則稱且其中至少有一個(gè)不等式嚴(yán)格成立，則稱A是弱對(duì)角占優(yōu)陣是弱對(duì)角占優(yōu)陣。例如例如 4121114238A 210011011B其中其中A 是嚴(yán)格對(duì)角占優(yōu)陣；是嚴(yán)格對(duì)角占優(yōu)陣；B 是弱對(duì)角占優(yōu)陣。是弱對(duì)角占優(yōu)陣。定理定理3.3 若若A為嚴(yán)格對(duì)角占優(yōu)陣，則為嚴(yán)格對(duì)角占優(yōu)陣，則Jacobi 迭代法迭代法和和G-S迭代法收斂。迭代法收斂。 定理定理3.43.4 若若A為對(duì)稱正定陣，則為對(duì)稱正定陣，則G-S迭代法收斂迭代法收斂。 在偏微分方程數(shù)值解中，有限差分往往

14、導(dǎo)出對(duì)角占優(yōu)的在偏微分方程數(shù)值解中，有限差分往往導(dǎo)出對(duì)角占優(yōu)的線性代數(shù)方程組，有限元法中的剛性矩陣往往是對(duì)稱正定陣，線性代數(shù)方程組，有限元法中的剛性矩陣往往是對(duì)稱正定陣，因此這兩個(gè)判斷定理是很實(shí)用的。因此這兩個(gè)判斷定理是很實(shí)用的。 對(duì)于給定的線性方程組，借助于對(duì)于給定的線性方程組，借助于定理定理3.3和定理和定理3.4可以可以直接判斷直接判斷Jacobi 迭代法和迭代法和G-S迭代法的收斂性。迭代法的收斂性。 但同時(shí)應(yīng)當(dāng)注意，迭代法收斂與否與方程組中方程排列但同時(shí)應(yīng)當(dāng)注意，迭代法收斂與否與方程組中方程排列順序有關(guān)，如線性方程組順序有關(guān)，如線性方程組 22. 367. 233. 422. 143

15、. 112. 005. 901.1058. 037.1269. 325. 1321321321xxxxxxxxx無法直接判斷無法直接判斷Jacobi 迭代法和迭代法和G-S迭代法的收斂性，但如果將迭代法的收斂性，但如果將方程組的次序修改為方程組的次序修改為 58. 037.1269. 325. 122. 367. 233. 422. 143. 112. 005. 901.10321321321xxxxxxxxx 由于系數(shù)矩陣由于系數(shù)矩陣A是嚴(yán)格對(duì)角占優(yōu)陣，因此用是嚴(yán)格對(duì)角占優(yōu)陣，因此用Jacobi 迭代迭代法和法和G-S迭代法求解該方程組均收斂迭代法求解該方程組均收斂。 定理定理3.3的證明的

16、證明證證 首先證明首先證明Jacobi 迭代的收斂性。由迭代的收斂性。由nnnJnnnnnnnnJabababfaaaaaaaaaaaaULDB22211121222222111111121,000)(易求易求ijnjiiijniJaaB,11max 由嚴(yán)格對(duì)角占優(yōu)定義（由嚴(yán)格對(duì)角占優(yōu)定義（定義定義3.1 ），得），得 BJ =det( ( ( (D-L)-)-U)=0)=0 我們通過我們通過A A的嚴(yán)格對(duì)角占優(yōu)性質(zhì)去證明的嚴(yán)格對(duì)角占優(yōu)性質(zhì)去證明det( ( ( (D-L)-)-U)=0)=0的根的根 有性質(zhì)有性質(zhì) | |1。用反證法：假設(shè)。用反證法：假設(shè)| |1，且由于，且由于A的的嚴(yán)格對(duì)角

17、占優(yōu)性質(zhì)，有嚴(yán)格對(duì)角占優(yōu)性質(zhì)，有 11111 2, ,niniiijijijjj ijj iaaaain 這說明矩陣這說明矩陣 11111121221112()nnnnaaaaaaDLUaaa 是嚴(yán)格對(duì)角占優(yōu)陣，所以它是非奇異的，即是嚴(yán)格對(duì)角占優(yōu)陣，所以它是非奇異的，即det( (D-L)-U) 0與特征值與特征值 滿足滿足det( (D-L)-U) =0 矛盾。矛盾。故故 1 即即(BG) 1，G-S迭代法收斂。迭代法收斂。定理得證定理得證。 返回章返回章（2）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的迭代法的收斂性沒有必然的聯(lián)系：收斂性沒有必然的聯(lián)系：即當(dāng)即當(dāng)Gauss-

18、Seidel法收斂時(shí)，法收斂時(shí)，Jacobi法可能不收斂；法可能不收斂；而而Jacobi法收斂時(shí)，法收斂時(shí)， Gauss-Seidel法也可能不收斂。法也可能不收斂。（1）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的迭代法的迭代矩陣不同：迭代矩陣不同：BJ =D-1(L+U), B G-S = (D-L) -1U12312312321121xxxxxxxxx例如用用Jacobi迭代法求解不收斂，但用迭代法求解不收斂，但用 Gauss-Seidel法收斂。法收斂。1231231232212223xxxxxxxxx用用Jacobi迭代法求解收斂，迭代法求解收斂，但用但用 Gauss-Seidel法不收斂。法不收斂。022022101 ,023220002JG SBB BJ的特征值為0，0，0， 而BGS的特征值為 0，2，2l 迭代法程序簡單，對(duì)于許多問題，收斂較快。迭代法程序簡單，對(duì)于許多問題，收斂較快。因而，有時(shí)能夠解決一些高階問題。因而，