数值分析：6.3迭代法的收敛定理.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 线性方程组迭代解法,Numerical Value Analysis,6.3,迭代法的收敛定理,6.3,迭代法的收敛性,基本数学问题描述,一、基本收敛定理,定理,3.2,的证明,实例求解,二、,Jacobi,迭代法和,Gauss-Seidel,迭代法的收敛速度,基本数学问题描述,迭代法的收敛性,，是指方程组,从,任意初始向量,X,(0),出发，由迭代算法,算出,向量序列,随着,k,的增加而趋向于解向量,X,*,。,记各次,误差向量,显然，,迭代法的收敛性,与,误差向量序列,随着,k,的增加而趋向于零向量是等价的。,由于精确解,X,*,自然满足,因此有,或,再递推出,所以，,迭代法收敛性,与,迭代矩阵的幂,B,k,，,随着,k,的增加而趋向于零矩阵是,等价,的。,返回节,谱半径的相关定理,(,谱半径有界,),设,则对任一种算子范数,均有,定理,1,设,则 的充分条件是,B,的,谱半径,定理,2,前一章的内容：,一、基本收敛定理,由,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.,定理,6.1,为判断迭代法的收敛性提供 了强有力的手段：,注意是充分必要条件！,2.,定理,6.1,的条件往往不易验证：,矩阵的谱半径不易求出！,注：,利用谱半径的有界性可以给出另外一,个条件较弱的结果：,即定理,6.2,(1),进一步，我们可以推知,：,式,(1),说明，当,|B|1,且不接近,1,并且相邻两次迭代向量,X,(k+1),与,X,(k),很接近时，则,X,(k),与精确解,X,*,很接近。因此，在实际计算中，用,|,X,(k+1),-,X,(k),|,作为迭代终止条件是合理的。,反复利用,|,X,(k+1),-,XBX,(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,),B,1,，,B,越小，说明,(,B,),越小，序列,X,(k),收敛越快。,收敛速度的概念,下面我们给出收敛速度的概念：,定义,6.1,R,(,B,)=-,ln,(,B,),，,称为迭代法的渐进收敛速度。,定理,6.2,的证明,证明,:,显然,根据范数性质,(3)(,三角不等式,),可知,成立，也即,因此,显然,根据范数性质,(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,，故,定理,3.2,在此无法,判断；,但因为,1,=0.9,2,=0.8,即,(,B,)=0.91,由,定理,3.1,知本题迭代法收敛。,返回节,二、,Jacobi,迭代法和,Gauss-Seidel,迭代法的收敛速度,引子,对角占优矩阵,实例,相关定理,定理,3.3,的证明,返回节,引子,虽然利用,定理,6.1,和,定理,6.2,可以判定,Jacobi,迭代法和,G-S,迭代法的收敛性，但其中只有,定理,6.2,对,Jacobi,迭代法使用比较方便，此外，对于大型方程组，要求出,G-S,迭代矩阵,B,G,和,(,B,G,),以及,Jacobi,迭代矩阵,B,J,和B,J,),都不是容易的事。,这里介绍一些判定收敛的充分条件,，,它们是利用原方程组系数矩阵,A,和迭代矩阵,B,的特殊性质建立的，很实用，用起来也很方便。这些判定定理也都是以定理,3.1,和定理,3.2,为基础的。,对角占优矩阵,如果线性方程组,AX,=,b,的系数矩阵,A,具有某种特殊性质（如对称正定、对角占优等），则可从,A,本身直接得出某些迭代法收敛性结论。,定义,6.1,如果矩阵,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.1,），得,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,即,(,BG,)1,，,G-S,迭代法收敛。,定理得证,。,返回章,注意的问题,（,2,）,Jacobi,迭代法和,Gauss-Seidel,迭代法的收敛性没有必然的联系：,即当,Gauss-Seidel,法收敛时，,Jacobi,法可能不收敛；,而,Jacobi,法收敛时，,Gauss-Seidel,法也可能不收敛。,（,1,）,Jacobi,迭代法和,Gauss-Seidel,迭代法的,迭代矩阵不同：,B,J,=D,-1,(L+U),B,G-S,=(D-L),-1,U,举例,用,Jacobi,迭代法求解不收敛，但用,Gauss-Seidel,法收敛。,用,Jacobi,迭代法求解收敛，,但用,Gauss-Seidel,法不收敛。,B,J,的特征值为,0,，,0,，,0,，,而,B,G,S,的特征值为,0,，,2,，,2,迭代法程序简单，对于许多问题，收敛较快。因而，有时能够解决一些高阶问题。但应注意，对于某些问题，迭代法可能发散或收敛很慢，以致失去使用价值。这种情况下，仍以采用直接法为宜。,只要断定系数矩阵满足收敛条件,，,尽管多次迭代计算工作量大一些,，,却能达到预定精度,。,(,保障措施,高速计算机能胜任那些程序简单、重复量大的迭代计算，况且还有许多加速收敛的办法做保障。,),返回节,OK!Lets have a break!,