6.3迭代法的收敛定理

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 线性方程组迭代解法,Numerical Analysis,6.3,迭代法的收敛性,基本数学问题描述,一、基本收敛定理,收敛充分条件及其,证明,二、,Jacobi,迭代法和,Gauss-Seidel,迭代法的收敛条件,基本数学问题描述,迭代法的收敛性,，是指方程组,从,任意初始向量,X,(0),出发，由迭代算法,算出,向量序列,随着,k,的增加而趋向于解向量,X,*,。,记各次,误差向量,显然，,迭代法的收敛性,与,误差向量序列,随着,k,的增加而趋向于零向量是等价的。,由于精确解,X,*,自然满足,因此有,或,再递推出,所以，,迭代法收敛性,与,迭代矩阵的幂,B,k,，,随着,k,的增加而趋向于零矩阵是,等价,的。,返回节,一、基本收敛定理,由,X,(,k,+1),=,BX,(,k,),+,f,及,X,*=,B X,*+,f,可见,X,(,k,),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*|,B,k,X,(0),-X*,，,可见,X,(0),越接近,X,*,，,序列,X,(k),收敛越快，收敛速度,与初值,X,(0),的选取有关。,另一方面，,B,越小，序列,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,只是充分条件，所以即使判断失效，迭代法仍可能收敛，这时就应该使用,定理,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,迭代法的收敛条件,引子,对角占优矩阵,实例,相关定理,定理,6.3,的证明,返回节,引子,虽然,利用,定理,6.1,和,定理,6.2,可以判定,Jacobi,迭代法和,G-S,迭代法的,收敛性,，,但,其中只有,定理,6.2,对,Jacobi,迭代法使用比较方便，此外，对于大型方程组，要求出,G-S,迭代矩阵,B,G,和,(,B,G,),以及,Jacobi,迭代矩阵,B,J,和,(,B,J,),都不是容易的事,。,这里介绍,一些,判定收敛,的,充分条件,，它们是利,用,原方程组,系数矩阵,A,和,迭代矩阵,B,的,特殊性质,建立的，,很实用,，用起来也,很方便,。这些判定定理的建立也都是以定理,6.1,和定理,6.2,为理论基础的。,对角占优矩阵,如果线性方程组,AX,=,b,的系数矩阵,A,具有某种特殊性质（如对称正定、对角占优等），则可从,A,本身直接得出某些迭代法收敛性结论。,定义,6.2,如果矩阵,A,满足条件,则称,A,是,严格对角占优阵,；,如果矩阵,A,满足条件,且其中至少有一个不等式严格成立，则称,A,是,弱对角占优阵,。,实例,例如,其中,A,是严格对角占优阵；,B,是弱对角占优阵。,定理,6.3,若,A,为严格对角占优阵，则,Jacobi,迭代法和,G-S,迭代法收敛。,定理,6.4,若,A,为对称正定阵，则,G-S,迭代法收敛,。,相关定理,在偏微分方程数值解中，有限差分往往导出对角占优的线性代数方程组，有限元法中的刚性矩阵往往是对称正定阵，因此这两个判断定理是很实用的。,对于给定的线性方程组，借助于,定理,6.3,和定理,6.4,可以直接判断,Jacobi,迭代法和,G-S,迭代法的收敛性。,但同时应当注意，迭代法收敛与否与方程组中方程排列顺序有关，如线性方程组,无法直接判断,Jacobi,迭代法和,G-S,迭代法的收敛性，但如果将方程组的次序修改为,由于系数矩阵,A,是严格对角占优阵，因此用,Jacobi,迭代法和,G-S,迭代法求解该方程组均收敛。,定理,6.3,的证明,证,首先证明,Jacobi,迭代的收敛性。由,易求,由严格对角占优定义（,定义,6.2,），得,B,J,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,即,(,B,G,)1,，,G-S,迭代法收敛。,定理得证,。,返回章,迭代法程序简单，对于许多问题，收敛较快。因而，有时能够解决一些高阶问题。但应注意，对于某些问题，迭代法可能发散或收敛很慢，以致失去使用价值。这种情况下，仍以采用直接法为宜。,只要断定系数矩阵满足收敛条件，尽管多次迭代计算工作量大一些，却能达到预定精度。,(,保障措施,高速计算机能胜任那些程序简单、重复量大的迭代计算，况且还有许多加速收敛的办法做保障。,),返回节,OK!Lets have a break!,