ch06 数值分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,第,六,章,线性方程组的数值解法,-迭代法,1,直接法得到的解是理论上准确的，但是计算量都是,n3数量级，存储量为n2量级，这在n比较小的时候,还比较合适（n400）,实际问题,中,，往往,方程组的阶数很高,，而且这些矩,阵(系数矩阵)往往是含有大量的0元素,（,稀疏矩阵,方程组,）。直接法运算量将会很大并且大量占用计,算机资源。,因此有必要引入一类新的方法：,迭代法,。,引言,2,迭代法的基本思想,迭代法是解线性方程组的一种重要的实用方,法，特别适用于求解在实际中大量出现的，系,数矩阵为稀疏阵的大型线性方程组。,迭代法的基本思想是去构成一个向量序,列,x,(,k,),，,使其收敛至某个极限向量,x,*,，并且,x,*,就是要求解,的方程组：,Ax=b,的准确解。,3,迭代法的主要步骤,The process of iterative method,解线性方程组迭代法的主要步骤是:,把线性方程组,Ax=b,化成如下形式的同解方程组,x,=,Bx,+,f,给出初始向量 ,按迭,代公式,x,(,k,+1),=Bx,(,k,),+f,(,k,=0,1,2,),进行计算,其中k 表迭代次数,。,4,如果按上述迭代公式所得到的向量序列,x,(,k,),收敛于某个向量,x,*,则,x,*,就是方程组,Ax=b,的解，并称此迭代法,收敛,否则，就叫不收敛或发散。,迭代公式中,的矩阵,B,，,称为,迭代矩阵,。,问题,迭代公式的建立,迭代公式的收敛性,收敛速度,误差估计,5,基本迭代公式,把矩阵,A,分裂为,则,记,B,=,M,-,1,N，f,=,M,-,1,b,，,则,注,：,选取M阵，就得到解 Ax=b 的各种迭代法.,6,本章重点介绍三个迭代法，即：,Jacobi,迭代法,Gauss-Seidel,迭代法,超松弛迭代法（,SOR,法）,7,Jacobi,迭代法,由方程组,AX,=,b,的第,i,个方程解出,得到一个同解方程组,8,获得相应的迭代公式,Jacobi,迭代法,取初始向量,称上式为雅可比迭,Jacobi,迭代公式。,9,Jacobi,迭代法,的矩阵形式,若记,则有,A=D-L-U,成立，矩阵形式为,D,x,=（L+U,)x,+b,等式两边乘以,D,-,1,，得,x,=D,-,1,（L+U）,x,+D,-,1,b,由此得到迭代公式(,The iterative scheme is:,),x,（,k,+1）,=,D,-1,（,L+U,）,x,（,k,）,+,D,-1,b,10,迭代矩阵,Jacobi,迭代法,的特点,每迭代一次主要是计算一次矩阵乘向量,所以计算量为n平方数量级。,计算过程中涉及到的中间变量 及 ,需要,两组工作单元x(n),y(n)来存储.,计算过程中,初始数据A始终不变;,11,问题：如何判断迭代,终止,？,定理,若迭代矩阵B满足|B|1 则,此定理,给出了一个停止迭代的判别准则。,12,输入最大迭代次数,N,，,控制误差,以及迭代初值,x,=,（,x,1,，,x,2，,x,n）,输出近似值,y,=（,y,1，,y,2，,y,n）,Jacobi,迭代法,的计算步骤,k,=1,；,如果,|,y-x,|,N,，算法失败。,如果,k,=1.0e6,x0=y;,y=B*x0+f;n=,n+1;,end,16,高斯,塞德尔,(,Gauss-Seidel,),迭代法,J,acobi,迭代法,的优点是公式简单，迭代矩阵容易得到，,称为,同时替换法,：在每一步迭代计算过程中，计算,x,(,k,+1),时是用,x,(,k,),的全部分量代入求,x,(k+1),的全部分量。,研究雅可比迭代法，我们发现在逐个求,的分量时，,当计算到 的分量时，当计算到,都已,经求得.设想一旦新分量代替旧分量，可能会加速收敛,。,例如,17,Gauss-Seidel,迭代法,分量形式,18,Gauss-Seidel,迭代的矩阵形式,作,A,的另一个分裂：,迭代矩阵,19,例子,解：,相应的高斯,-,赛德尔迭代公式为,20,取迭代初值,按此迭代公式进行迭代，计算结果为,0,1,2,3,4,5,0,0.3,0.8804,0.9843,0.9978,0.9997,0,1.56,1.9445,1.9923,19989,1.9999,0,2.684,2.9539,2.9938,2.9991,2.9999,21,迭代法的收敛,性,迭代法的收敛性,，,是指方程组,从,任意初始向量,X,(0),出发，由迭代算法,算出,向量序列,随着,k,的增加而趋向于解向量,X,*,。,记各次,误差向量,22,迭代法的收敛,性,迭代法的收敛性,等价于,误差向量序列,随着,k,的增加而,趋向于零,。,由,x,(,k,+1),=,B,x,(,k,),+,f,及,x,*=,B,x,*+,f,k,+1,=,X,(,k,+1),-,X,*=,B,（,X,(,k,),-,X,*）,=,=,B,k,+1,（,X,(0),-,X,),B,k,+1,0,可推知,x,(,k,),的收敛性,B,k,0,(,k,),23,迭代法的收敛,性定理,定理,(,充要条件判别法,),给定方程组,X,=,BX,+,f,则迭代公式,对任意初始向量,，都收敛的充要条件为,24,迭代法的收敛,性定理,定理,(,充分条件判别法,),给定方程组,X,=,BX,+,f,如果 ，则,迭代公式,1,.,对任意初始向量 收敛。,2,.,有如下估计,25,证明,26,注,由于此估计式，,在实际计算中，用,|,X,(k+1),-,X,(k),|,作为迭代终止条件是合理的。,进一步可以推知,：,由于,(,B,),B,1,，,B,越小，说明,(,B,),越小，序列X,(k),收敛越快。,27,收敛速度,下面我们给出收敛速度的概念,：,定义,R,(,B,)=-,ln,(,B,),，,称为迭代法的渐进,收敛速度。,由于,Gauss-Seidel,迭代法逐次用计算出来的新值代替旧值，所以在收敛的条件下，它要比,Jacobi,迭代法收敛速度快。,28,Jacobi 和,Gauss-Seidel,的收敛性,29,注,30,对于前面的例子,由迭代矩阵的特征方程,因而雅可比迭代公式是收敛的。,31,注,32,直接用矩阵,A,判定敛散性,收敛性,定理虽然给出了判别迭代法收敛的充要条件，,但实际使用时很不方便，因为求逆矩阵和特征值的,难度并不亚于用直接法求解线性方程组下面对一些特殊的方程组，从方程组本身出发给出几个常用,的判别条件，而不必求迭代阵的特征值或范数。,定义,如果矩阵,A,满足条件,则称,A,是,严格对角占优阵(,strictly diagonally dominant matrix),；,33,A,为按行按列,严格,对角占优阵；,B,为按行对角占优阵。,实例(,Example,),34,定理,1,若,A,为,严格对角占优阵,，则,J,acobi,迭代法,和,G-S,迭代法,收敛。,定理,2,若,A,为,对称正定阵,，则,G-S,迭代法收敛,。,相关定理,可以总结，讨论迭代法的收敛性，应首先从,A,出发讨,论其是否具有主对角占优或对称正定性；其次对迭代,法的迭代阵讨论其是否有范数小于,1,；最后利用迭代,阵的谱半径讨论（这是充分必要条件）。,35,定理,1,的证明,证,首先证明,Jacobi,迭代的收敛性。由,易求,由严格对角占优定义，得,B,J,det,(,(,D-L,)-,U,)=0,37,我们通过,A,的严格对角占优性质去证明,det,(,(,D-L,)-,U,)=0,的根,有性质,|,|1。,用,反证法,：假设,|,|1，,且由于,A,的严格对角占优性质，有,38,是严格对角占优阵，所以它是非奇异的，即,det,(,(D-L)-U),0,与特征值,满足,det,(,(D-L)-U),=0,矛盾。,故,|,|1即,(,B,G,)1，,G-S,迭代法收敛。,定理得证,。,39,注,值,得注意的是，改变方程组中方程的次序，即将,系数矩阵进行行交换，会改变迭代法的收敛性,。,无法直接判断,Jacobi,迭代法和,G-S,迭代法的收敛性，但如果将方程组的次序修改为,40,注,对于对称正定矩阵,A，,Jacobi,迭代法不一定收敛。,迭代法程序简单，对于许多问题，收敛较快。因而，有时能够解决一些高阶问题。但应注意，对于某些问题，迭代法可能发散或收敛很慢，以致失去使用价值。这种情况下，仍以采用直接法为宜。,41,