数值分析方法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.2 迭代法,2.2.1 迭代原理,2.2.2 迭代的收敛性,2.2.3 迭代的收敛速度,2.2.4 迭代的加速,2.2 迭代法,1,预备定理,预备定理,2,2.2.1 迭代原理,2.2.1 迭代原理,3,计算结果见下表,计算结果见下表,4,方程,f,(,x,)=0化为等价形式的方程,x=,(,x,)，,构造迭代公式,x,k+,1,=,(,x,k,),k,=0,1,2,取初始近似根,x,0,进行迭代计算,x,1,=,(,x,0,),x,2,=,(,x,1,),.,则有,x,1,x,2,.,x,k,.,得到迭代序列,x,k,.如果这个序列有极限，则迭代公式是收敛的。这时,则 ，,x,*,为不动点，等价地有,f,(,x,*,)=0,x,*,即为方程的根。连续函数,(x),称为迭代函数。,实际计算到|,x,k,x,k,-1,|,（,是预定的精度），取,x,*,x,k,。,方程f(x)=0化为等价形式的方程 x=,5,迭代公式收敛,指迭代序列,x,k,收敛，,迭代公式发散,指迭代序列,x,k,不收敛，即发散。迭代公式不一定总是收敛。,例如求方程,f,(,x,),=x,3,-x,-1=0的一个根,。,对应的迭代公式为,取初值,迭代序列,x,k,发散.,迭代公式收敛指迭代序列xk 收敛，迭代公式发散指迭代序列,6,数值分析方法课件,7,x,1,=,(x,0,),x,2,=,(x,1,),迭代法收敛与发散的图示,x1=(x0)x2=(x1)迭代法收敛与发散,8,迭代法的收敛与发散,收敛的情形 发散的情形,迭代法的收敛与发散 收敛的情形,9,2.2.2 迭代的收敛性,迭代法的收敛条件及误差估计式,定理（充分性条件）,设函数,(x),在,a,b,上连续，且,(1)对,x,a,b,有,(,x,),a,b,(2)存在,0 L 1,，使对任意,x,a,b,有,|,(,x,),|L 1,则方程,x=,(x),在,a,b,上的根,x,*,存在且唯一；对初值,x,0,a,b,迭代过程,x,k,+1,=,(,x,k,)均收敛于方程的根,x,*,。,2.2.2 迭代的收敛性,10,定理中的,(1)对 x,a,b,有,(x),a,b,，称为适定性（映内性）。,定理中的(1)对 xa,b,有 (x)a,11,证明,先证根的存在性。,作连续函数,(,x,),=x-,(,x,),由条件（1）,x,a,b,(,x,),a,b,，即,a,(,x,)、,xb,于是,(,a,),=a-,(,a,)0,(,b,),=b-,(,b,)0,由于,(,x,)是连续函数，故必存在,x,*,a,b,使,(,x,*,)=0.即,(,x,*,)=,x,*,-,(,x,*,)=0,.,于是,x,*,=,(,x,*,)即,x,*,为方程,x=,(,x,)的根。,其次，证根的唯一性。,设,y,*,也是方程的根，则,x,*,=,(x,*,),y,*,=,(y,*,),x,*,-y,*,=,(x,*,),(y,*,)=,()(x,*,-y,*,),x,*,-y,*,()(x,*,-y,*,)=0，,（,x,*,-y,*,）1-,(,)=0,由条件（2）,|,(x)|L 1，,故有,x,*,-y,*,=0，,即,x,*,=y,*,所以方程在,a,b,的根唯一,。,证明 先证根的存在性。,12,再证迭代的收敛性。,由,x,k,=,(x,k-1,),x,*,=,(x,*,),有,|,x,k,-x,*,|=|,()(x,k-1,-x,*,)|L|x,k-1,-x,*,|,L,2,|x,k-2,-x,*,|,L,3,|x,k-3,-x,*,|,L,k|,x,0,-x,*,|,0（k）,所以，对,a,b,上任取的,x,0,迭代公式,x,k+,1,=,(x,k,),都收敛于,x,*,。,L,越小收敛得越快。,定理是充分性条件,x,k,-x,*,=,(x,k-1,),(x,*,)=,()(x,k-1,-x,*,),再证迭代的收敛性。由xk=(xk-1),x*=,13,推论：在定理的条件下，有误差估计式,验后误差估计式,验前误差估计式,证明：,|,x,k,-x,*,|L|x,k-1,-x,*,|=L|x,k-1,-x,k,+x,k,-x,*,|,L（|x,k,-x,*,|+|x,k-1,-x,k,|）,（1-L)|x,k,-x,*,|L|x,k-1,-x,k,|,迭代法的终点判断：只要相邻两次迭代值的偏差充分小，就能保证迭代值足够准确，因而用,|x,k,-x,k,-1,|,控制迭代过程的结束。,推论：在定理的条件下，有误差估计式|xk -x*|L,14,定理,设在区间,a,b,上方程,x=,(,x,)有根,x,*,且对一切,x,a,b,都有|,(,x,)|1，则对于该区间上任意,x,0,(,x,*,),迭代公式,x,k,+1,=,(,x,k,)一定发散。,证明,不可能收敛于0。,定理 设在区间a,b上方程 x=,15,数值分析方法课件,16,数值分析方法课件,17,计算结果见下表,取方程的根 2.0946。,计算结果见下表取方程的根 2.0946。,18,数值分析方法课件,19,由于 ，故取,由于,20,迭代法的,局部收敛性,迭代法的局部收敛性,21,由于在实际应用中根,x,*,事先不知道，故条件,|,(x,*,)|1,无法验证。但已知根的初值,x,0,在根,x,*,邻域，又根据,(x),的连续性，则可采用,|,(x,0,)|1,来代替,|,(x,*,)|1,，判断迭代的收敛性。,由于在实际应用中根 x*事先不知道，故条件,22,例,求方程,x=,e,x,在,x=0.5,附近的一个根，按,5,位小数计算，结果的精度要求为,=10,3,.,解,迭代公式 x,k+,1,=e,x,k ，,取,(,x,)=e,x,迭代公式 x,k,+1,=e,x,k,收敛。,例求方程 x=e x在x=0.5附近的一个根，按5位小数计,23,迭代结果:,0,1,2,3,4,5,0.5,0.606 53,0.545 24,0.579 70,0.560 07,0.571 17,0.106 53,0.061 29,0.034 46,0.019 63,0.011 10,6,7,8,9 10,0.564 86,0.568 44,0.566 41,0.567 56,0.566 91,0.006 31,0.003 58,0.002 03,0.001 15,0.000 65,k,x,k,x,k,x,k-1,x,k,x,k-1,k,x,k,|x,10,-x,9,|=0.00065，,故 x,*,x,10,0.567,x,0,=0.5,x,2,=,e,x,1,=,0.54524,.,x,1,=e,x,0,=0.60653,x,k,+1,=e,x,k,迭代结果:0 0.5 6 0.,24,数值分析方法课件,25,迭代的计算步骤,迭代的计算步骤,26,迭代法计算框图的说明,迭代法计算框图的说明,27,数值分析方法课件,28,数值分析方法课件,29,2.2.3 迭代过程的收敛速度,2.2.3 迭代过程的收敛速度,30,数值分析方法课件,31,数值分析方法课件,32,数值分析方法课件,33,数值分析方法课件,34,数值分析方法课件,35,2.2.4 迭代的加速,2.2.4 迭代的加速,36,2 埃特金加速与斯蒂芬森迭代法,2 埃特金加速与斯蒂芬森迭代法,37,埃特金迭代,将不动点迭代法与埃特金加速结合即得斯蒂芬森迭代法,埃特金迭代将不动点迭代法与埃特金加速结合即得,38,数值分析方法课件,39,数值分析方法课件,40,数值分析方法课件,41,