1、第三章 線性方程組迭代解法 Iterative techniques for solving linear system, 3.3 迭代法的收斂定理 The convergence theorem of iterative method,3.3 迭代法的收斂性,基本數(shù)學(xué)問題描述 The problem 一、基本收斂定理,The convergence theorem of iterative method,The Fundamental convergence theorem,二、Jacobi 迭代法和Gauss-Seidel迭代法的收斂條件 The condition for converg

2、ence of Jacobi and Guass-Seidel method,基本數(shù)學(xué)問題描述,迭代法的收斂性，是指方程組,從任意初始向量X(0)出發(fā)，由迭代算法,記各次誤差向量,The error vector,由于精確解X *自然滿足,因此有,或,再遞推出,The convergence of x(k) ,Bk 0 (k ),由 X(k+1)=BX(k)+f 及 X *=B X *+f,一、基本收斂定理 The Fundamental convergence theorem,Theorem :for any initial value , the fundamental iterative

3、 method defined by x(k+1)=Bx(k)+f (k=0,1,2,) converges to the unique solution of x=Bx+f if only if,Theorem 3.2: If |B|1 for any initial vector the sequence x(k) converges and the estimate (1) holds.,Theorem 3.2,進(jìn)一步，我們可以推知：,式(1)說明，當(dāng)|B|1 且不接近1并且相鄰兩次迭代向量X(k+1) 與 X (k)很接近時(shí)，則X(k)與精確解X *很接近。因此，在實(shí)際計(jì)算中，用| X

4、 (k+1) - X (k) |作為迭代終止條件是合理的。,So possible stopping criteria is to iterate until | x(k+1) - x(k)| is smaller than given tolerance .,反復(fù)利用 | X (k+1) - X*|=|BX (k)- BX*|=|B(X (k)- X*)| B.X (k)- X*, 可以得到 |X (k)- X*|Bk X(0)- X*， 可見X (0)越接近X*，序列 X (k)收斂越快，收斂速度 與初值X (0)的選取有關(guān)。 另一方面，由于(B) B1，B越小，說明(B) 越小，序列 X

5、 (k)收斂越快。,The relationship of the rate of convergence to the spectral radius of the iterative matrix B can be seen from theorem 3.2.,收斂速度的概念,下面我們給出收斂速度的概念： 定義3.1 R(B)= -ln(B)，稱為迭代法的漸進(jìn)收斂速度。,The rate of convergence,Definition 3.1 R(B)= -ln(B) is called by the rate of convergence.,因此,-（2）,The proof of

6、theorem 3.2,定理3.2的證明,顯然,根據(jù)范數(shù)性質(zhì)(4)(乘積不等式) 可知,也即,再將此不等式兩端同時(shí)減去 可得,由第2式可知,證明完畢。,將定理3.1和3.2用于Jacobi迭代法及Seidel迭代法，則有,Application to Jacobi and Guass-Seidel method:,Necessary and sufficient conditions,Sufficient conditions,在一般情況下，計(jì)算矩陣的范數(shù)比計(jì)算譜半徑省事，所以通常是利用定理3.2進(jìn)行判斷。 但定理3.2只是充分條件，所以即使判斷失效，迭代法仍可能收斂，這時(shí)就應(yīng)該使用定理3.1

7、判斷。,返回節(jié),二、Jacobi 迭代法和Gauss-Seidel迭代法的收斂條件,引子 對角占優(yōu)矩陣 實(shí)例 相關(guān)定理 定理3.3的證明,返回節(jié),Some convergence theorem of Jacobi and Guass-Seidel method for linear system With special matrix A,引子,雖然利用定理3.1和定理3.2可以判定Jacobi 迭代法和G-S迭代法的收斂性，但其中只有定理3.2對Jacobi 迭代法使用比較方便，此外，對于大型方程組，要求出G-S迭代矩陣BG和(BG)以及Jacobi 迭代矩陣BJ和(BJ)都不是容易的事。

8、 這里介紹一些判定收斂的充分條件，它們是利用原方程組系數(shù)矩陣A和迭代矩陣B的特殊性質(zhì)建立的，很實(shí)用，用起來也很方便。這些判定定理也都是以定理3.1和定理3.2為基礎(chǔ)的。,對角占優(yōu)矩陣diagonally dominant matrix,如果線性方程組AX=b的系數(shù)矩陣A具有某種特殊性質(zhì)（如對稱正定、對角占優(yōu)等），則可從A本身直接得出某些迭代法收斂性結(jié)論。,實(shí)例(Example),例如,其中,A 是嚴(yán)格對角占優(yōu)陣； B 是弱對角占優(yōu)陣。,定理3.3 若A為嚴(yán)格對角占優(yōu)陣，則Jacobi 迭代法和G-S迭代法收斂。,定理3.4 若A為對稱正定陣，則G-S迭代法收斂。,相關(guān)定理,Theorem 3.

9、3 If A is strictly diagonally dominant matrix, then For any choices of x0, both the Jacobi and Guass-Seidel methods converge to the unique solution 0f Ax=b,Theorem 3.4 If A is symmetry and positive definitive matrix, then for any choices of x0, Guass-Seidel methods converge to the unique solution 0f

10、 Ax=b,在偏微分方程數(shù)值解中，有限差分往往導(dǎo)出對角占優(yōu)的線性代數(shù)方程組，有限元法中的剛性矩陣往往是對稱正定陣，因此這兩個(gè)判斷定理是很實(shí)用的。 對于給定的線性方程組，借助于定理3.3和定理3.4可以直接判斷Jacobi 迭代法和G-S迭代法的收斂性。 但同時(shí)應(yīng)當(dāng)注意，迭代法收斂與否與方程組中方程排列順序有關(guān)，如線性方程組,無法直接判斷Jacobi 迭代法和G-S迭代法的收斂性，但如果將方程組的次序修改為,由于系數(shù)矩陣A是嚴(yán)格對角占優(yōu)陣，因此用Jacobi 迭代法和G-S迭代法求解該方程組均收斂。,定理3.3的證明,證 首先證明Jacobi 迭代的收斂性。由,易求,由嚴(yán)格對角占優(yōu)定義（定義3.

11、1 ），得 BJ 1,所以, Jacobi 迭代法收斂。,The proof of theorem 3.3,下面證明G-S迭代法的收斂性。對于嚴(yán)格對角占優(yōu)陣A，其對角元素 aii 0 ， i=1,2,n（定義3.1 ），故,考慮BG的特征值，其特征方程為 det(I-BG) = det(I-(D-L)-1U) = det(D-L)-1det(D-L)-U)= = det(D-L)-U)=0,The proof of convergence for G-S method,Considering the eigenvalues of iterative matrix BG = (D-L)-1U,I

12、n order to prove the eignevalues of BG satisfying that | |1 We can use a method by Contradictions. Suppose | |1,then,返回章,我們通過A的嚴(yán)格對角占優(yōu)性質(zhì)去證明det(D-L)-U)=0的根有性質(zhì) | |1。用反證法：假設(shè)| |1，且由于A的嚴(yán)格對角占優(yōu)性質(zhì)，有,therefore,is strictly diagonally dominant and (D-L)-U is nonsingular. Then | |1 holds.,是嚴(yán)格對角占優(yōu)陣，所以它是非奇異的，即 det(D-L)-U) 0與特征值滿足det(D-L)-U) =0 矛盾。 故 | |1即(BG) 1， G-S迭代法收斂。 定理得證。,對于對稱正定矩陣A， Jacobi迭代法不一定收斂。 一般來說，可能Jacobi迭代法和Guass-Seidel迭代法都收斂，也可能都是都不收斂，或一個(gè)收斂，一個(gè)不收斂，在兩者都收斂的情況下，收斂速度也不一定。 p76例3.2,For a symmetry and pos