第四章 迭代法4.1 2迭代过程的收敛性 迭代加速.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章,方程求根的迭代法,迭代法的思想,压缩映像原理,局部收敛性,收敛性的阶,第,一节,迭代过程的收敛性,非线性方程的根,求,f,(,x,)=0,的根,代数方程：,f,(,x,)=,a,0,+,a,1,x,+.+,a,n,x,n,超越方程：,f,(,x,),含超越函数，如,sin(,x,),e,x,ln,x,等,实根与复根,根的重数,f,(,x,)=(,x,x,*),m,g,(,x,),且,g,(,x,*,),0,则,x,*,为,f,(,x,),的,m,重根,有根区间：,a,b,上存在,f,(,x,)=0,的一个实根,在,有根,的前提下求出方程的,近似根,。,研究 内容,:,(,x,),的不动点,x,*,迭代法的思想,f,(,x,)=0,x,=,(,x,),称为迭代函数,等价变换,基本思想,从一个给定的初值,x,0,出发，计算,x,1,=,(,x,0,),x,2,=,(,x,1,),若 收敛，即存在,x,*,使得 ，则由,的连续性和 可得,x,*=,(,x,*),，即,x,*,是,的不动点，也就是,f,(,x,),的零点。,具体做法：,不动点迭代,f,(,x,),的零点,x,*,几何含义：,求曲线,y,=,(,x,),与直线,y,=,x,的交点,x,k,+1,=,(,x,k,),x,y,y=x,x,y,y=x,x,y,y=x,x,y,y=x,x*,x*,x*,x*,y=,(,x,),y=,(,x,),y=,(,x,),y=,(,x,),x,0,p,0,x,1,p,1,x,0,p,0,x,1,p,1,x,0,p,0,x,1,p,1,x,0,p,0,x,1,p,1,x,2,例,x,3,x,1,=,0,1,2,取,x,0,=1.5,迭代公式,1,：,迭代公式,2,：,计算结果：,公式,1,：,公式,2,：,怎么判断迭代公式收敛或发散呢？,精确解,x,*,=,1.3247179.,压缩映像原理,定理,4.1,设,(,x,),C,a,b,且一阶导数连续，若,(2),0,L,1,，使得,|,(,x,)|,L,对,x,a,b,成立,则函数,f,(,x,)=,x,-,(,x,),在,a,b,中有,唯一,的零点,x,*,。,(,压缩映像原理，不动点原理,),x,*,称为,(,x,),的,不动 点,(,x*,),=,x,*,(1),a,(,x,),b,对一切,x,a,b,都成立,简证：,f,(,a,)=,a,-,(,a,)0,f,(,b,)=,b,-,(,b,)0,f,(,x,),在,a,b,上有零点。,唯一性：反证法，假设存在,x,*,y,*,a,b,使得,x,*,=,(,x,*),y,*,=,(,y,*),矛盾！,封闭性,压缩性,收敛性分析,定理,4.1,设,(,x,),C,a,b,且一阶导数连续，若,(2),0,L,1,，使得,|,(,x,)|,L,对,x,a,b,成立,(1),a,(,x,),b,对一切,x,a,b,都成立,则有,(a),对任意,x,0,a,b,，由,x,k,+1,=,(,x,k,),产生的迭代序列,均收敛到,(,x,),在,a,b,中的唯一不动点,x,*,。,(b),有如下的误差估计,可用,|,x,k,+1,-,x,k,|,来,控制收敛精 度,L,越小收敛越快,.,后验估计,:,先验估计,:,证,:,(a),由压缩映像定理可知，不动点,x,*,存在且唯一。,(b),又,书上,P129(7),(8),式,全局收敛与局部收敛,定理的条件保证了不动点迭代的,全局收敛性,。,即迭代的收敛性与初始点的选取无关。,这种在,x,*,的邻域内具有的收敛性称为,局部收敛性,。,定理中的条件,|,(,x,)|,L,1,可以适当放宽,(2,),(,x,),在,x,*,的某个邻域内连续，且,|,(,x*,)|1,由,(,x,),的连续性及,|,(,x*,)|1,即可推出：,若,(x),的一阶导数连续,且满足条件,(2),则一定存在,x*,的,某个,邻域,N,(,x,*,),=,x,*,-,x*,+,使得对,x,N,(,x,*,),都有,|,(,x,)|,L,1,则由,x,0,N,(,x,*,),开始的迭代都收敛。,具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；,而不具有局部收敛性的迭代对任何初值都不可能收敛。,定理,4.2,例,用不同方法求,x,2,3,=,0,的根,取,x,0,=2.,迭代公式,1,：,迭代公式,2,：,迭代公式,3,：,迭代公式,4,：,计算结果：,怎么判断收敛的迭代公式的速度快慢呢？,精确值：,收敛性的阶,设迭代,x,k,+1,=,(,x,k,),收敛到,(,x,),的,不动点,x,*,。,记 绝对误差,e,k,=,x,k,x,*,，,若,定义,则称该迭代为,r,阶收敛,。,(1),当,r,=1,时称为,线性收敛,，此时,|,C|,1,时称为,超线性收敛,。,不动点迭代中，若,(,x,*)0,，,且迭代收敛，则,取极限得,(,C,为常数,),线性收敛,.,p,阶收敛,设迭代,x,k,+1,=,(,x,k,),，若,(,p,),(,x,),在,x,*,的某邻域内连续，则该迭代法具有,p,阶收敛的充要条件是,定理,4.3,并且有,证明：,充分性,.,根据泰勒展开有,必要性,(,不证,).,设迭代,x,k,+1,=,(,x,k,),是,p,阶收敛。,迭代两边取极限,，由,(,x,),的连续性可知,x,*=,(,x,*),。,设,p,0,是满足,的最小正整数。,由充分性的证明过程可知迭代,p,0,阶收敛。,又,若,p,0,p,，,与迭代,p,0,阶收敛矛盾,.,p,0,=,p,第四章 方程求根的迭代法,第二节,迭代加速,迭代加速,设有不动点迭代：,（,在,x,k,和,x,*,之间）,设：,缺点,：,每次迭代需计算,如何避免计算导数？,简化：,迭代加速,设：,“迭代,-,加速”格式,迭代函数由 变为,所以此格式定义合理。,故选择适当的,D,可能使,从而此迭代格式应该比原迭代格式的收敛速度,更快,！,埃特金,(,Aitken,),加速,设：,Aitken,加速,为了避免计算导数,还可以进行如下改进,:,Aitken,加速的收敛阶,定理,设,(,x,),在不动点,x,*,的某个邻域内具有二阶连续导数，,(,x,*)=L,1,且,L,0,，则,Aitken,加速,二阶收敛,到,x,*,。,证明：略,迭代加速法的优点：,加快迭代过程的收敛速度,将发散的迭代格式加工成收敛的,