《6.3迭代法的收敛定理.ppt》由会员分享，可在线阅读，更多相关《6.3迭代法的收敛定理.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章 线性方程组迭代解法6.3 迭代法的收敛性l 基本数学问题描述l 一、基本收敛定理l 收敛充分条件及其证明l 二、Jacobi 迭代法和Gauss-Seidel迭代法的收敛条件基本数学问题描述迭代法的收敛性，是指方程组从任意初始向量X(0)出发，由迭代算法算出向量序列随着k的增加而趋向于解向量X*。记各次误差向量显然，迭代法的收敛性与误差向量序列随着k的增加而趋向于零向量是等价的。由于精确解X*自然满足因此有或 再递推出 所以，迭代法收敛性与迭代矩阵的幂B k，随着k的增加而趋向于零矩阵是等价的。返回节一、基本收敛定理由 X(k+1)=BX(k)+f 及 X*=B X*+f可见 X(k)
2、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)进一步，我们可以推知：式(1)说明，当|B|1 且不接近1并且相邻两次迭代向量X(k+1)与 X(k)很接近时，则X(k)与精确解X*很接近。因此，在实际计算中，用|X(k+1)-X(k)|作为迭代终止条件是合理的。反复利用|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)的选取有关。另一方面，B越小，序
3、列 X(k)收敛越快。更精确的说法是：(B)越小，序列 X(k)收敛越快。收敛速度的概念下面我们给出收敛速度的概念：定义6.1 R(B)=-ln(B)，称为迭代法的渐进收敛速度。定理6.2的证明证明:显然根据范数性质(3)(三角不等式)可知成立，也即因此-（2）显然根据范数性质(4)(乘积不等式)可知也即再将上两式联立，可以得出以下结果再将此不等式两端同时减去 可得由第（2）式可知证明完毕。将定理6.1和6.2用于Jacobi迭代法及Seidel迭代法，则有在一般情况下，计算矩阵的范数比计算谱半径省事，所以通常是先利用定理6.2进行判断。但定理6.2只是充分条件，所以即使判断失效，迭代法仍可能
4、收敛，这时就应该使用定理6.1判断。设有线性方程组 X=BX+f，其中 考察迭代法 X(k+1)=B X(k)+f 的收敛性。例如解：由于 均大于1，故定理6.2在此无法判断；但因为 1=0.9,2=0.8,即(B)=0.91,由定理6.1知本题迭代法收敛。返回节二、Jacobi 迭代法和Gauss-Seidel迭代法的收敛条件l 引子l 对角占优矩阵l 实例l 相关定理l 定理6.3的证明返回节引子 虽然利用定理6.1和定理6.2可以判定Jacobi 迭代法和G-S迭代法的收敛性，但其中只有定理6.2对Jacobi 迭代法使用比较方便，此外，对于大型方程组，要求出G-S迭代矩阵BG和(BG)
5、以及Jacobi 迭代矩阵BJ和(BJ)都不是容易的事。这里介绍一些判定收敛的充分条件，它们是利用原方程组系数矩阵A和迭代矩阵B的特殊性质建立的，很实用，用起来也很方便。这些判定定理的建立也都是以定理6.1和定理6.2为理论基础的。对角占优矩阵 如果线性方程组AX=b的系数矩阵A具有某种特殊性质（如对称正定、对角占优等），则可从A本身直接得出某些迭代法收敛性结论。定义6.2 如果矩阵A满足条件则称A是严格对角占优阵；如果矩阵A满足条件且其中至少有一个不等式严格成立，则称A是弱对角占优阵。实例例如其中A 是严格对角占优阵；B 是弱对角占优阵。定理6.3 若A为严格对角占优阵，则Jacobi 迭代
6、法和G-S迭代法收敛。定理6.4 若A为对称正定阵，则G-S迭代法收敛。相关定理 在偏微分方程数值解中，有限差分往往导出对角占优的线性代数方程组，有限元法中的刚性矩阵往往是对称正定阵，因此这两个判断定理是很实用的。对于给定的线性方程组，借助于定理6.3和定理6.4可以直接判断Jacobi 迭代法和G-S迭代法的收敛性。但同时应当注意，迭代法收敛与否与方程组中方程排列顺序有关，如线性方程组 无法直接判断Jacobi 迭代法和G-S迭代法的收敛性，但如果将方程组的次序修改为 由于系数矩阵A是严格对角占优阵，因此用Jacobi 迭代法和G-S迭代法求解该方程组均收敛。定理6.3的证明证 首先证明Ja
7、cobi 迭代的收敛性。由易求 由严格对角占优定义（定义6.2），得 BJ 1,所以,Jacobi 迭代法收敛。下面证明G-S迭代法的收敛性。对于严格对角占优阵A，其对角元素 aii 0，i=1,2,n（定义6.2），故 所以矩阵（D-L）为可逆下三角矩阵，其逆也是下三角矩阵，G-S迭代法的迭代矩阵是 BG=(D-L)-1U。考虑BG的特征值，其特征方程为 det(I-BG)=det(I-(D-L)-1U)=det(D-L)-1det(D-L)-U)=det(D-L)-U)=0 我们通过A的严格对角占优性质去证明det(D-L)-U)=0的根有性质|1。用反证法：假设|1，且由于A的严格对角占优性质，有 这说明矩阵 是严格对角占优阵，所以它是非奇异的，即det(D-L)-U)0，这与特征值满足det(D-L)-U)=0 矛盾。故|1 即(BG)1，G-S迭代法收敛。定理得证。返回章l 迭代法程序简单，对于许多问题，收敛较快。因而，有时能够解决一些高阶问题。但应注意，对于某些问题，迭代法可能发散或收敛很慢，以致失去使用价值。这种情况下，仍以采用直接法为宜。l 只要断定系数矩阵满足收敛条件，尽管多次迭代计算工作量大一些，却能达到预定精度。(保障措施 高速计算机能胜任那些程序简单、重复量大的迭代计算，况且还有许多加速收敛的办法做保障。)返回节OK!Lets have a break!