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

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

1、第六章线性方程组迭代解法NumericalAnalysis§6.3迭代法的收敛性基本数学问题描述一、基本收敛定理收敛充分条件及其证明二、Jacobi迭代法和Gauss-Seidel迭代法的收敛条件基本数学问题描述迭代法的收敛性，是指方程组从任意初始向量X(0)出发，由迭代算法算出向量序列随着k的增加而趋向于解向量X*。记各次误差向量显然，迭代法的收敛性与误差向量序列随着k的增加而趋向于零向量是等价的。由于精确解X*自然满足因此有或再递推出所以，迭代法收敛性与迭代矩阵的幂Bk，随着k的增加而趋向于零矩阵是等价的。返回节一、基本收敛定理由X(k+

2、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ε0可推知(B)(1)进一步，我们可以推知：式(1)说明，当

3、

4、B

5、

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

7、

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

9、

10、≤ε作为迭代终止条件是合理的。反复利用

11、

12、X(k+1)-X*

13、

14、=

15、

16、BX(k)-BX*

17、

18、=

19、

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

21、

22、≤‖B‖.‖X

23、(k)-X*‖,可以得到

24、

25、X(k)-X*

26、

27、≤‖B‖k·‖X(0)-X*‖，可见X(0)越接近X*，序列{X(k)}收敛越快，收敛速度与初值X(0)的选取有关。另一方面，‖B‖越小，序列{X(k)}收敛越快。更精确的说法是：ρ(B)越小，序列{X(k)}收敛越快。收敛速度的概念下面我们给出收敛速度的概念：定义6.1R(B)=-lnρ(B)，称为迭代法的渐进收敛速度。定理6.2的证明证明:显然根据范数性质(3)(三角不等式)可知成立，也即因此-------（2）显然根据范数性质(4)(乘积不等式)可知也即再将上两式联立，可以得出以下结果再将此

28、不等式两端同时减去可得由第（2）式可知证明完毕。将定理6.1和6.2用于Jacobi迭代法及Seidel迭代法，则有在一般情况下，计算矩阵的范数比计算谱半径省事，所以通常是先利用定理6.2进行判断。但定理6.2只是充分条件，所以即使判断失效，迭代法仍可能收敛，这时就应该使用定理6.1判断。设有线性方程组X=BX+f，其中考察迭代法X(k+1)=BX(k)+f的收敛性。例如解：由于均大于1，故定理6.2在此无法判断；但因为λ1=0.9,λ2=0.8,即ρ(B)=0.9<1,由定理6.1知本题迭代法收敛。返回节二、Jacobi迭代法和Gauss-

29、Seidel迭代法的收敛条件引子对角占优矩阵实例相关定理定理6.3的证明返回节引子虽然利用定理6.1和定理6.2可以判定Jacobi迭代法和G-S迭代法的收敛性，但其中只有定理6.2对Jacobi迭代法使用比较方便，此外，对于大型方程组，要求出G-S迭代矩阵BG和ρ(BG)以及Jacobi迭代矩阵BJ和ρ(BJ)都不是容易的事。这里介绍一些判定收敛的充分条件，它们是利用原方程组系数矩阵A和迭代矩阵B的特殊性质建立的，很实用，用起来也很方便。这些判定定理的建立也都是以定理6.1和定理6.2为理论基础的。对角占优矩阵如果线性方程组AX=b的系数矩

30、阵A具有某种特殊性质（如对称正定、对角占优等），则可从A本身直接得出某些迭代法收敛性结论。定义6.2如果矩阵A满足条件则称A是严格对角占优阵；如果矩阵A满足条件且其中至少有一个不等式严格成立，则称A是弱对角占优阵。实例例如其中A是严格对角占优阵；B是弱对角占优阵。定理6.3若A为严格对角占优阵，则Jacobi迭代法和G-S迭代法收敛。定理6.4若A为对称正定阵，则G-S迭代法收敛。相关定理在偏微分方程数值解中，有限差分往往导出对角占优的线性代数方程组，有限元法中的刚性矩阵往往是对称正定阵，因此这两个判断定理是很实用的。对于给定的线性方程组，借

31、助于定理6.3和定理6.4可以直接判断Jacobi迭代法和G-S迭代法的收敛性。但同时应当注意，迭代法收敛与否与方程组中方程排列顺序有关，如线性方程组无法直接判断Jacobi迭代法和G-S迭代法的收敛性，但如果将方程组的次序修改为由于系数矩阵A是严格对角占优阵，因此用Jacobi迭代法和G-S迭代法求解该方程组均收敛。定理6.3的证明证首先证明Jacobi迭代的收敛性。由易求由严格对角占优定义（定义6.2），得BJ∞<1,所以,Jacobi迭代法收敛。下面证明G-S迭代法的收敛性。对于严格对角占优阵A，其对角元素aii≠0，i=1,2

32、,,n（定义6.2），故所以矩阵（D-L）为可逆下三角矩阵，其逆也是下三角矩阵，G-S迭代法的迭代矩阵是BG=(D-L)-1U。考虑BG的特征值λ，其特