不动点迭代法和其加速技术教育课件.ppt

不动点迭代法和其加速技术PPT讲座,若,|,g,(,x,)|,1，,则将,x,=,g,(,x,),等价地改造为,求,K,，使得,一、待定参数法,例：,求 在(1,2)的实根。,如果用 进行迭代，则在,(1,2),中有,现令,希望,，即,在,(1,2),上可取任意 ，例如,K,=,0.5,，,则对应,即产生收敛序列。,设,x,k,是根,x,*,的某个预测值，用迭代公式校正一次得：,假设 在所考虑范围内改变不大，其估计值为L，则有,二、Aitken加速法,相除,将 再校正一次，,所以,Aitken,加速：,x,y,y=x,y,=,g,(,x,),x,*,x,0,P,(,x,0,x,1,),x,1,x,2,P,(,x,1,x,2,),一般地，有：,比 收敛得略快。,Newton 迭代法,将f(x)在点,x,n,作Taylor展开:,Taylor展开线性化,f(x)=0,近似于,f(x,n,)+f,(x,n,)(x-x,n,)=0,(1),从,(1),解出,x,记为,x,n+1,则,1.Newton迭代公式建立,它对应的迭代方程为 显然是f(x)=0的同解方程，故其迭代函数为,在 f(x)=0的根,x*,的某个邻域 内,在,x*,的邻域R 内，对任意初值 ，,应用,公式（2）,来解方程的方法就称为,牛顿迭代法,。它是解代数方程和超越方程的有效方法之一,.,2.Newton迭代法的几何意义,与,x轴(y=0),的交点x,作为下一个迭代点,x,n+1,即,用,f(x),在,x,n,处,的切线,Newton迭代法又称切线法.,例,用Newton迭代法求下面方程的一个正根,计算结果精确到7位小数.,解:,由Newton迭代法,由Newton迭代法,x,1,=,1.4666667,x,4,=,1.3688081,x,5,=,1.3688081,迭代5次,精度达,10,-7,x,*,1.368808,4.Newton迭代法收敛定理,（1）Newton迭代公式在单根情况下至少2阶收敛;,（2）,定理,设,f(x*)=0,且在,x*,的邻域,上 存在,连续,则可得,证：,将,f(x),在,x,n,处作,2,阶,Taylor,展开,并将解,x*,代入,注意到,n,在,x,n,及,x*,之间,及 ,故,所以，Newton法至少二阶收敛.,注意到,n,在,x,n,及,x*,之间,及 ,故,例3.,为线性收敛,证明:,所以,例4.,至少是平方收敛的,由定义1,注意例4与例3的迭代法是相同的,两例有何区别?,证明:,令,则,所以,由,定理2,该迭代法至少是平方收敛的,Newton,迭代公式是一种特殊的不动点迭代,其迭代矩阵为,:,Newton,迭代是局部线性化方法,它在单根附近具有较高的收敛速度,.,方法有效前提,:,Newton迭代法的特征,5.Newton迭代法的应用,-,开方公式,对于给定正数 应用牛顿迭代法解二次方程,可导出求开方值 的计算公式,设 是 的某个近似值，则 自然也是一个近似值，上式表明，它们两者的算术平均值将是更好的近似值。,定理,开方公式对于任意给定的初值 均为平方收敛。,牛顿迭代法的优缺点,优点：在单根附近,牛顿迭代法具有平方收敛的速,度，所以在迭代过程中只要迭代几次就会得到很精,确解,。,缺点,:,1.重根情形下为局部线性收敛;,2.牛顿迭代法计算量比较大:因每次迭代除,计算函数值外还要计算微商值;,3.,选定的初值要接近方程的解，否则有可能得,不到收敛的结果;,牛顿迭代法的改进,缺点克服:,1.局部线性收敛,-改进公式或加速,2.每步都要,计算微商值简化Newton迭代法,或弦截法,3.,初值近似问题,-二分法求初值或”下山算法”,方法一,.若已知重数m(m1),则利用m构造新的迭代公式:,此时,至少2阶收敛.,不实用:m往往不确定.,方法二,.取 ,再对函数F(x)用Newton迭代:,此时,X*为F(x)的单根,所以是2阶收敛.但要用到二阶导数.,6.Newton法的改进(I)-重根情形,Newton,迭代法,需要求每个迭代点处的导数,f,(,x,k,),复杂！,这种格式称为,简化Newton迭代法,精度稍低,6.Newton法的改进(II),则Newton迭代法变为,这种格式称为,弦截法,收敛阶约为1.618,例4,用简化Newton法和弦截法解下面方程的根，并和Newton 迭代法比较,解:,由简化Newton法,由弦截法,由Newton迭代法,x,0,=0.5,x,1,=0.3333333333,x,2,=0.3497942387,x,3,=0.3468683325,x,4,=0.3473702799,x,5,=0.3472836048,x,6,=0.3472985550,x,7,=0.3472959759,x,8,=0.3472964208,x,9,=0.3472963440,x,10,=0.3472963572,x,11,=0.3472963553,x,0,=0.5;,x,1,=0.4;,x,2,=0.3430962343,x,3,=0.3473897274,x,4,=0.3472965093,x,5,=0.3472963553,x,6,=0.3472963553,简化Newton法,由弦截法,要达到精度10,-8,简化Newton法迭代11次,弦截法迭代5次,Newton迭代法迭代4次,x,0,=0.5;,x,1,=0.3333333333,x,2,=0.3472222222,x,3,=0.3472963532,x,4,=0.3472963553,由Newton迭代法,无论哪种迭代法：,Newton迭代法,简化Newton法,弦截法,用Newton迭代法求解:,x,0,=2,x,1,=-3.54,x,2,=13.95,x,3,=-279.34,x,4,=122017,是否收敛均与初值的位置有关.,例:,x,0,=1,x,1,=-0.5708,x,2,=0.1169,x,3,=-0.0011,x,4,=7.9631,10,-,10,x,5,=0,收敛,发散,迭代法的,局部收敛性,6.Newton法的改进(III):,牛顿下山法,一般地说，牛顿法的收敛性依赖于初值 的选取，如果 偏离 较远，则牛顿法可能发散。,为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降：,满足这项要求的算法称为,下山法,。,牛顿下山法,采用以下迭代公式：,其中 称为下山因子。,牛顿下山法只有线性收敛,.,例7.,解:,1.先用Newton迭代法,x4=9.70724,x5=6.54091,x6=4.46497,x7=3.13384,x8=2.32607,x9=1.90230,x10=1.75248,x11=1.73240,x12=1.73205,x13=1.73205,迭代13,次才达,到精度,要求,2.用Newton下山法,结果如下,k=0 x0=-0.99 fx0=0.666567,k=1 x1=32.505829 f(x)=11416.4,w=0.5 x1=15.757915 f(x)=1288.5,w=0.25 x1=7.383958 f(x)=126.8,w=0.125 x13.196979 f(x)=7.69,w=0.0625 x1=1.103489 f(x)=-0.655,k=2 x2=4.115071 f(x)=19.1,w=0.5 x2=2.60928 f(x)=3.31,w=0.25 x2=1.85638 f(x)=0.27,k=3 x3=1.74352 f(x)=0.023,k=4 x4=1.73216 f(x)=0.00024,k=5 x5=1.73205 f(x)=0.00000,k=6 x6=1.73205 f(x)=0.000000,故有,且,由例3.,对于Newton迭代法,趋于零,Newton迭代法也只是线性收敛,此时Newton迭代法可能不收敛,由,定理2,，迭代法,至少是二阶收敛,