计算方法迭代法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章迭代法,3.1,二分法,3.2,迭代法原理,3.3 Newton,迭代法和迭代加速,3.4,解线性方程组的迭代法,3.1,二分法,根的估计,二分法,根的估计,引理,3.1,（,连续函数的介值定理,）,设,f(x),在,a,b,上连续，且,f(a)f(b)0,，则存在,x*,(a,b),使,f(x*)=0,。,例,3.1,证明,x,3,3,x,1=0,有且仅有,3,个实根，并确定根的大致位置使误差不超过,=0.5,。,解,:,单调性分析和解的位置,选步长,h=2,扫描节点函数值,异号区间内有根,f(x)=,x,3,3,x,1,二分法,条件,:,设,f,(,x,),在,a,b,上连续，,f,(,x,)=0,在,a,b,上存在唯一解，且,f,(,a,),f,(,b,)0,。记,Step 1,:If f(a,0,)f(x,0,)0,then x*,(a,0,x,0,)let a,1,=a,0,b,1,=x,0,;Else,x*,(x,0,b,0,)let a,1,=x,0,b,1,=b,0,;,L,et x,1,=(a,1,+b,1,)/2.,Step k,:If f(a,k-1,)f(x,k-1,)0,then x*,(a,k-1,x,k-1,)let a,k,=a,k-1,b,k,=x,k-1,;Else,x*,(x,k-1,b,k-1,)let a,k,=x,k-1,b,k,=b,k-1,;,L,et x,k,=(a,k,+b,k,)/2.,收敛性及截断误差分析,:,例,3.2,x,3,3,x,1=0,1,2,精度,0.5e-1,二分法,优点,算法简单,收敛有保证,只要,f(x),连续,缺点,对区间两端点选取条件苛刻,收敛速度慢,3.2,迭代法原理,迭代法的思想,不动点原理,局部收敛性,收敛性的阶,迭代法的思想,条件,:f(x)=0,在,x,0,附近有且仅有一个根,设计同解变形,x=g(x),迭代式,x,k,=g(x,k-1,),k=1,2,如果收敛,x,k,x*,则,x*,是,f(x)=0,的,根,不动点原理,(,迭代过程收敛,),定理,3.1(,不动点原理,),设映射,g(x),在,a,b,上有连续的一阶导数且满足,1,o,封闭性,：,x a,b,g(x)a,b,2,o,压缩性,：,L(0,1),使对,x a,b,|g(x)|L,则在,a,b,上存在唯一的不动点,x*,，且对,x,0,a,b,x,k,=g(x,k-1,),收敛于,x*,。进一步，有误差估计式,后验估计,先验估计,算法设计中迭代结束条件,:,近似使用,|x,k,-x,k-1,|,不动点原理,证明步骤,解的存在性,;,解的唯一性,;,解的收敛性,;,误差估计式。,例,3.3,局部收敛性,(,格式收敛,),定理,3.2,（,局部收敛性,）设,g(,x,),连续,则存在充分靠近,x,*,的初值，使迭代收敛于,x,*,。,证明：利用定理,3.1,取,L,=,具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；,而不具有局部收敛性的迭代对任何初值都不可能收敛。,应用中,:,近似使用,|g(x,0,)|1,判断,收敛性的阶,(,局部收敛速度,),定义,3.1,当,x,k,x*,，记,e,k,=,x*,-x,k,，若存在实数,p,，使,e,k+1,/e,p,k,c,0,，,则称,x,k,有,p,阶收敛速度,。,线性收敛,p=1,平方收敛,p=2,定理,3.3,设,x,k,=g(x,k-1,),x*,，则,(1),当,g(x*),0,时，,x,k,线性收敛；,(2),当,g(x*)=0,而,g(x*),0,时，,x,k,平方收敛。,3.3 Newton,迭代法和迭代加速,牛顿,(Newton),迭代法,“迭代加速”技术,牛顿,(Newton),迭代法,原理,(1,次近似,直线代替曲线,),牛顿格式,Newton,法几何意义：切线法,切线代替曲线,Newton,法局部收敛性,单根：平方收敛,m,重,根：线性收敛,例,3.5,（,P56),Newton,迭代法，计算,3,次达到,4,位有效数字,计算,4,次达到,4,位有效数字,越是精度要求高,Newton,迭代法优势越明显,“,迭代加速”技术,加快迭代过程的收敛速度,将发散的迭代格式加工成收敛的,若,g(x),在,x*,附近大约为,D,改进,x,k,=,g,(,x,k,-1,),为,例,3.6,（,P57),4,解线性方程组的迭代法,1,迭代思想,2,Jacobi,迭代和,Gauss-Seidel,迭代,3,迭代的收敛性,4,迭代加速,逐次超松弛（,SOR,）法,1,迭代思想,解大型稀疏型方程组比直接法存储量小,条件,:Ax=b,解存在唯一,设计同解变形,x=Gx+f,迭代式,x,(k),=Gx,(k-1),+f,k=1,2,取初值,x,(0),，如果收敛,x,(k),x*,则,x*,是,Ax=b,的解,x,(k),x*,2 Jacobi,迭代和,Gauss-Seidel,迭代,例,3.7,解：变形,Jacobi,迭代,Jacobi,迭代,初值取 ，精度要求,=10,-3,。,计算得,|,x,(,6,),x,(5),|,10,-3,.,Gauss-Seidel,迭代,Gauss-Seidel,迭代,初值取 ，精度要求,=10,-3,。,计算得,|,x,(,5,),x,(4),|,10,-3,.,编程计算公式,Jacobi,迭代,Gauss-Seidel,迭代,迭代结束条件一般用,|,x,(,k,),x,(,k-,1),|,问题,(1),收敛性条件,?(2),|,x,(,k,),x,(,k-,1),|,作为结束条件是否可靠,?,计算公式矩阵形式,和分解：,A=L(,下三角,)+D(,对角,)+U(,上三角,),迭代,x,(k),=Gx,(k-1),+f,k=1,2,Jacobi,迭代,G=-D,-1,(L+U)=I-D,-1,A,f=D,-1,b,Gauss-Seidel,迭代,G=-(L+D),-1,U,f=(L+D),-1,b,3,迭代的收敛性,定理,3.4,设,G,的某种范数,|G|1,，则,x=Gx+f,存在唯一解，且对任意初值，迭代序列,x,(k),=Gx,(k-1),+f,收敛于,x*,，进一步有误差估计式,证明思路,：,(1),解的存在唯一性,;(2),解的收敛性,;(3),误差估计式,(,习题,),。,直接从,Ax=b,判断,推论,若,A,按行严格对角占优（），则解,Ax=b,的,Jacobi,迭代和,Gauss-Seidel,迭代均收敛。,证明思路：用定理,3.4.A,严格对角占优，则无穷大范数,|G|1,Jacobi,迭代,(,直接证,|G|,1),Gauss-Seidel,迭代,令,y=Gx,，则,y,=-,D,-1,(,Ly+Ux,),先证存在某,x,|,x,|,=1,使,|G|,=|,y,|,再证当,|,x,|,=1,有,|,y,|,1,Gauss-Seidel,迭代收敛性证明,记迭代矩阵,存在,m,令,那么 且,Gauss-Seidel,迭代收敛性证明,记 ，其中迭代矩阵,那么,存在,k,使得,所以,充分必要条件,谱半径,(,G,),：,G,的特征值模的最大值,定理,3.5,迭代,x,(k),=Gx,(k-1),+f,对任意初值收敛,(,G,)1.,（证明较深，略）,三种方法比较,方法一,(,推论,):,从,A,判断,A,严格对角占优，则,Jacobi,迭代和,Gauss-Seidel,迭代收敛,充分条件,最方便,方法二,(,定理,3.4):,从,G,判断,有一种范数,|G|1,充分条件,方法三,(,定理,3.5):,从,G,判断,谱半径,(,G,)1,充要条件,最宽,P63,例,3.8,（特征值的性质：特征值之和等于对角线元素的和）,4,逐次超松弛（,SOR,）法,Gauss-Seidel,迭代格式的加速,收敛的必要条件,0,2,低松弛法,0,1,=1,Gauss-Seidel,迭代,超,松弛法,1,2,P66,例,3.9,P70,习题,ex1,ex2,ex3,ex5,ex6,ex9,ex10,ex11(2),ex13,