《迭代法的收敛定理.ppt》由会员分享，可在线阅读，更多相关《迭代法的收敛定理.ppt（28页珍藏版）》请在三一办公上搜索。
1、第三章 线性方程组迭代解法 Iterative techniques for solving linear system,3.3 迭代法的收敛定理 The convergence theorem of iterative method,3.3 迭代法的收敛性,基本数学问题描述 The problem 一、基本收敛定理,The convergence theorem of iterative method,The Fundamental convergence theorem,二、Jacobi 迭代法和Gauss-Seidel迭代法的收敛条件 The condition for converge
2、nce of Jacobi and Guass-Seidel method,基本数学问题描述,迭代法的收敛性，是指方程组,从任意初始向量X(0)出发，由迭代算法,记各次误差向量,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 method de
3、finedby 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,进一步，我们可以推知：,式(1)说明，当|B|1 且不接近1并且相邻两次迭代向量X(k+1)与 X(k)很接近时，则X(k)与精确解X*很接近。因此，在实际计算中，用|X(k+1)-X(k)|作为迭代终止条件是合理
4、的。,So possible stopping criteria is to iterate until|x(k+1)-x(k)|is smaller than given tolerance.,反复利用|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)B1，B越小，说明(B)越小，序列 X(k)收敛越快。,The relationship of the rate of convergence tothe
5、 spectral radius of the iterative matrix B can be seen from theorem 3.2.,收敛速度的概念,下面我们给出收敛速度的概念：定义3.1 R(B)=-ln(B)，称为迭代法的渐进收敛速度。,The rate of convergence,Definition 3.1 R(B)=-ln(B)is called by the rate of convergence.,因此,-（2）,The proof of theorem 3.2,定理3.2的证明,显然,根据范数性质(4)(乘积不等式)可知,也即,再将此不等式两端同时减去 可得,由第
6、2式可知,证明完毕。,将定理3.1和3.2用于Jacobi迭代法及Seidel迭代法，则有,Application to Jacobi and Guass-Seidel method:,Necessary and sufficient conditions,Sufficient conditions,在一般情况下，计算矩阵的范数比计算谱半径省事，所以通常是利用定理3.2进行判断。但定理3.2只是充分条件，所以即使判断失效，迭代法仍可能收敛，这时就应该使用定理3.1判断。,返回节,二、Jacobi 迭代法和Gauss-Seidel迭代法的收敛条件,引子对角占优矩阵实例相关定理定理3.3的证明,返
7、回节,Some convergence theorem of Jacobi and Guass-Seidel method for linear systemWith special matrix A,引子,虽然利用定理3.1和定理3.2可以判定Jacobi 迭代法和G-S迭代法的收敛性，但其中只有定理3.2对Jacobi 迭代法使用比较方便，此外，对于大型方程组，要求出G-S迭代矩阵BG和(BG)以及Jacobi 迭代矩阵BJ和(BJ)都不是容易的事。这里介绍一些判定收敛的充分条件，它们是利用原方程组系数矩阵A和迭代矩阵B的特殊性质建立的，很实用，用起来也很方便。这些判定定理也都是以定理3.
8、1和定理3.2为基础的。,对角占优矩阵diagonally dominant matrix,如果线性方程组AX=b的系数矩阵A具有某种特殊性质（如对称正定、对角占优等），则可从A本身直接得出某些迭代法收敛性结论。,实例(Example),例如,其中,A 是严格对角占优阵；B 是弱对角占优阵。,定理3.3 若A为严格对角占优阵，则Jacobi 迭代法和G-S迭代法收敛。,定理3.4 若A为对称正定阵，则G-S迭代法收敛。,相关定理,Theorem 3.3 If A is strictly diagonally dominant matrix,thenFor any choices of x0,b
9、oth 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 Ax=b,在偏微分方程数值解中，有限差分往往导出对角占优的线性代数方程组，有限元法中的刚性矩阵往往是对称正定阵，因此这两个判断定理是很实用的。对于给定的线
10、性方程组，借助于定理3.3和定理3.4可以直接判断Jacobi 迭代法和G-S迭代法的收敛性。但同时应当注意，迭代法收敛与否与方程组中方程排列顺序有关，如线性方程组,无法直接判断Jacobi 迭代法和G-S迭代法的收敛性，但如果将方程组的次序修改为,由于系数矩阵A是严格对角占优阵，因此用Jacobi 迭代法和G-S迭代法求解该方程组均收敛。,定理3.3的证明,证 首先证明Jacobi 迭代的收敛性。由,易求,由严格对角占优定义（定义3.1），得 BJ 1,所以,Jacobi 迭代法收敛。,The proof of theorem 3.3,下面证明G-S迭代法的收敛性。对于严格对角占优阵A，其对
11、角元素 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,In order to prove the eignevalues of BG satisfying that|1We can use a method by Contradictions.
12、Suppose|1,then,返回章,我们通过A的严格对角占优性质去证明det(D-L)-U)=0的根有性质|1。用反证法：假设|1，且由于A的严格对角占优性质，有,therefore,is strictly diagonally dominant and(D-L)-U is nonsingular.Then|1 holds.,是严格对角占优阵，所以它是非奇异的，即det(D-L)-U)0与特征值满足det(D-L)-U)=0 矛盾。故|1即(BG)1，G-S迭代法收敛。定理得证。,对于对称正定矩阵A，Jacobi迭代法不一定收敛。一般来说，可能Jacobi迭代法和Guass-Seidel迭代法都收敛，也可能都是都不收敛，或一个收敛，一个不收敛，在两者都收敛的情况下，收敛速度也不一定。p76例3.2,For a symmetry and positive definite A,Jacobi method mayNot be convergent necessarily.,迭代法程序简单，对于许多问题，收敛较快。因而，有时能够解决一些高阶问题。但应注意，对于某些问题，迭代法可能发散或收敛很慢，以致失去使用价值。这种情况下，仍以采用直接法为宜。只要断定系数矩阵满足收敛条件，尽管多次迭代计算工作量大一些，却能达到预定精度。,返回节,
