數(shù)值分析3.3迭代法的收斂定理

1、第三章 線性方程組迭代解法Numerical Analysis3.3 迭代法的收斂性基本數(shù)學(xué)問(wèn)題描述一、基本收斂定理定理3.2的證明二、Jacobi 迭代法和Gauss-Seidel迭代法的收斂條件基本數(shù)學(xué)問(wèn)題描述迭代法的收斂性，是指方程組從任意初始向量X(0)出發(fā)，由迭代算法算出向量序列隨著k的增加而趨向于解向量X *。 記各次誤差向量顯然，迭代法的收斂性與誤差向量序列隨著k的增加而趨向于零向量是等價(jià)的。 由于精確解X *自然滿足因此有或 再遞推出 所以，迭代法收斂性與迭代矩陣的冪B k，隨著k的增加而趨向于零矩陣是等價(jià)的。返回節(jié)一、基本收斂定理由 X(k+1)=BX(k)+f 及 X *=

2、B X *+f可見 X(k) X* B k 0 (k ) k+1 = X (k+1) - X *= B（X (k) - X *） = = B k+1（X(0) -X *） = B k+1 0 可推知(B)(1)進(jìn)一步，我們可以推知： 式(1)說(shuō)明，當(dāng)|B|1 且不接近1并且相鄰兩次迭代向量X(k+1) 與 X (k)很接近時(shí)，則X(k)與精確解X *很接近。因此，在實(shí)際計(jì)算中，用| X (k+1) - X (k) |作為迭代終止條件是合理的。 反復(fù)利用 | X (k+1) - X*|=|BX (k)- BX*|=|B(X (k)- X*)| B.X (k)- X*,可以得到 |X (k)- X

3、*|Bk X(0)- X*，可見X (0)越接近X*，序列 X (k)收斂越快，收斂速度與初值X (0)的選取有關(guān)。 另一方面，由于(B) B1，B越小，說(shuō)明(B) 越小，序列 X (k)收斂越快。 收斂速度的概念下面我們給出收斂速度的概念： 定義3.1 R(B)= -ln(B)，稱為迭代法的漸進(jìn)收斂速度。定理3.2的證明證明:顯然根據(jù)范數(shù)性質(zhì)(3)(三角不等式) 可知成立，也即因此-（2）顯然 根據(jù)范數(shù)性質(zhì) 可知也即再將上兩式聯(lián)立，可以得出以下結(jié)果再將此不等式兩端同時(shí)減去 可得由第2式可知證明完畢。 將定理3.1和3.2用于Jacobi迭代法及Seidel迭代法，則有在一般情況下，計(jì)算矩陣的

4、范數(shù)比計(jì)算譜半徑省事，所以通常是利用定理3.2進(jìn)行判斷。 但定理3.2只是充分條件，所以即使判斷失效，迭代法仍可能收斂，這時(shí)就應(yīng)該使用定理3.1判斷。 設(shè)有線性方程組 X=BX+f，其中 考察迭代法 X (k+1)=B X(k)+f 的收斂性。例如解： 由于 均大于1，故定理3.2在此無(wú)法判斷； 但因?yàn)?1 =0.9, 2=0.8,即(B) =0.91,由定理3.1知本題迭代法收斂。 返回節(jié)二、Jacobi 迭代法和Gauss-Seidel迭代法的收斂條件引子對(duì)角占優(yōu)矩陣實(shí)例相關(guān)定理定理3.3的證明返回節(jié)引子 雖然利用定理3.1和定理3.2可以判定Jacobi 迭代法和G-S迭代法的收斂性，但

5、其中只有定理3.2對(duì)Jacobi 迭代法使用比較方便，此外，對(duì)于大型方程組，要求出G-S迭代矩陣BG和(BG)以及Jacobi 迭代矩陣BJ和(BJ)都不是容易的事。 這里介紹一些判定收斂的充分條件，它們是利用原方程組系數(shù)矩陣A和迭代矩陣B的特殊性質(zhì)建立的，很實(shí)用，用起來(lái)也很方便。這些判定定理也都是以定理3.1和定理3.2為基礎(chǔ)的。對(duì)角占優(yōu)矩陣 如果線性方程組AX=b的系數(shù)矩陣A具有某種特殊性質(zhì)（如對(duì)稱正定、對(duì)角占優(yōu)等），則可從A本身直接得出某些迭代法收斂性結(jié)論。 定義3.1 如果矩陣A滿足條件則稱A是嚴(yán)格對(duì)角占優(yōu)陣； 如果矩陣A滿足條件且其中至少有一個(gè)不等式嚴(yán)格成立，則稱A是弱對(duì)角占優(yōu)陣。實(shí)

6、例例如其中A 是嚴(yán)格對(duì)角占優(yōu)陣；B 是弱對(duì)角占優(yōu)陣。定理3.3 若A為嚴(yán)格對(duì)角占優(yōu)陣，則Jacobi 迭代法和G-S迭代法收斂。 定理3.4 若A為對(duì)稱正定陣，則G-S迭代法收斂。 相關(guān)定理 在偏微分方程數(shù)值解中，有限差分往往導(dǎo)出對(duì)角占優(yōu)的線性代數(shù)方程組，有限元法中的剛性矩陣往往是對(duì)稱正定陣，因此這兩個(gè)判斷定理是很實(shí)用的。 對(duì)于給定的線性方程組，借助于定理3.3和定理3.4可以直接判斷Jacobi 迭代法和G-S迭代法的收斂性。 但同時(shí)應(yīng)當(dāng)注意，迭代法收斂與否與方程組中方程排列順序有關(guān)，如線性方程組 無(wú)法直接判斷Jacobi 迭代法和G-S迭代法的收斂性，但如果將方程組的次序修改為 由于系數(shù)矩

7、陣A是嚴(yán)格對(duì)角占優(yōu)陣，因此用Jacobi 迭代法和G-S迭代法求解該方程組均收斂。 定理3.3的證明證 首先證明Jacobi 迭代的收斂性。由易求 由嚴(yán)格對(duì)角占優(yōu)定義（定義3.1 ），得 BJ det(D-L)-U)=0 我們通過(guò)A的嚴(yán)格對(duì)角占優(yōu)性質(zhì)去證明det(D-L)-U)=0的根有性質(zhì) | |1。用反證法：假設(shè)| |1，且由于A的嚴(yán)格對(duì)角占優(yōu)性質(zhì)，有 這說(shuō)明矩陣 是嚴(yán)格對(duì)角占優(yōu)陣，所以它是非奇異的，即det(D-L)-U) 0，這與特征值滿足det(D-L)-U) =0 矛盾。故 | 1 即(BG) 1，G-S迭代法收斂。定理得證。 返回章 迭代法程序簡(jiǎn)單，對(duì)于許多問(wèn)題，收斂較快。因而，有時(shí)能夠解決一些高階問(wèn)題。 但應(yīng)注意，對(duì)于某些問(wèn)題，迭代法可能發(fā)散或收斂很慢，以致失去使用價(jià)值。這種情況下，仍以采用直接法為宜。只要斷定系數(shù)矩陣滿足收斂條件，盡管多次迭代計(jì)算工作量