《迭代法的收敛定理》PPT课件

《《迭代法的收敛定理》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性方程组迭代解法Iterativetechniquesforsolvinglinearsystem§3.3迭代法的收敛定理Theconvergencetheoremofiterativemethod§3.3迭代法的收敛性基本数学问题描述Theproblem一、基本收敛定理TheconvergencetheoremofiterativemethodTheFundamentalconvergencetheorem二、Jacobi迭代法和Gauss-Seidel迭代法的收敛条件TheconditionforconvergenceofJacobiandGuas

2、s-Seidelmethod基本数学问题描述迭代法的收敛性，是指方程组从任意初始向量X(0)出发，由迭代算法算出向量序列随着k的增加而趋向于解向量X*。记各次误差向量Theerrorvector显然，迭代法的收敛性与误差向量序列随着k的增加而趋向于零向量是等价的。由于精确解X*自然满足因此有或再递推出Theconvergenceof{x(k)}Bk0(k∞)由X(k+1)=BX(k)+f及X*=BX*+f可见X(k)X*Bk0(k∞)εk+1=X(k+1)-X*=B（X(k)-X*）=·············=Bk+1（X(0)-X*）=Bk+1ε

3、0可推知(B)一、基本收敛定理TheFundamentalconvergencetheoremTheorem:foranyinitialvalue,thefundamentaliterativemethoddefinedbyx(k+1)=Bx(k)+f(k=0,1,2,…)convergestotheuniquesolutionofx=Bx+fifonlyif(1)Theorem3.2:If

4、B

5、<1foranyinitialvectorthesequence{x(k)}convergesandtheestimate(1)holds.Theorem3.2进一

6、步，我们可以推知：式(1)说明，当

7、

8、B

9、

10、<1且不接近1并且相邻两次迭代向量X(k+1)与X(k)很接近时，则X(k)与精确解X*很接近。因此，在实际计算中，用

11、

12、X(k+1)-X(k)

13、

14、≤ε作为迭代终止条件是合理的。Sopossiblestoppingcriteriaistoiterateuntil

15、x(k+1)-x(k)

16、issmallerthangiventoleranceε.反复利用

17、

18、X(k+1)-X*

19、

20、=

21、

22、BX(k)-BX*

23、

24、=

25、

26、B(X(k)-X*)

27、

28、≤‖B‖.‖X(k)-X*‖,可以得到

29、

30、X(k)-X*

31、

32、≤‖B‖k·‖X(0)-

33、X*‖，可见X(0)越接近X*，序列{X(k)}收敛越快，收敛速度与初值X(0)的选取有关。另一方面，由于ρ(B)≤‖B‖<1，‖B‖越小，说明ρ(B)越小，序列{X(k)}收敛越快。TherelationshipoftherateofconvergencetothespectralradiusoftheiterativematrixBcanbeseenfromtheorem3.2.收敛速度的概念下面我们给出收敛速度的概念：定义3.1R(B)=-lnρ(B)，称为迭代法的渐进收敛速度。TherateofconvergenceDefinition3.1R(B)=

34、-lnρ(B)iscalledbytherateofconvergence.证明:显然根据范数性质(3)(三角不等式)可知成立，也即因此-------（2）Theproofoftheorem3.2定理3.2的证明显然根据范数性质(4)(乘积不等式)可知也即再将上两式联立，可以得出以下结果再将此不等式两端同时减去可得由第2式可知证明完毕。将定理3.1和3.2用于Jacobi迭代法及Seidel迭代法，则有ApplicationtoJacobiandGuass-Seidelmethod:NecessaryandsufficientconditionsSuffici

35、entconditions在一般情况下，计算矩阵的范数比计算谱半径省事，所以通常是利用定理3.2进行判断。但定理3.2只是充分条件，所以即使判断失效，迭代法仍可能收敛，这时就应该使用定理3.1判断。设有线性方程组X=BX+f，其中考察迭代法X(k+1)=BX(k)+f的收敛性。Example:解：由于均大于1，故定理3.2在此无法判断；但因为λ1=0.9,λ2=0.8,即ρ(B)=0.9<1,由定理3.1知本题迭代法收敛。返回节二、Jacobi迭代法和Gauss-Seidel迭代法的收敛条件引子对角占优矩阵实例相关定理定理3.3的证明返回节Someconver

36、gencetheoremofJacob