资源描述
School of Mathematics and Information Sciences of Henan University,*,Other Kinds of Newton Method,Newton,迭代法几个变形,1,简化,Newton,法（平行弦法）,弦截法，又称,割线法，弦位法，线性插值法,Newton,下山法,Newton,法对,重根,的求解,抛物线法（,muller,法），,又称,二次插值法,代数多项式求根,2,若,|, (,x,)|=|1-c,f,(,x,)|1,，,即取,0,c,f,(,x,)2,在,x,*,附近成立，则,收敛,。,若取,c=1/,f,(,x,0,) or 1/,f,(,x,k,),，,则称,简化,Newton,法,。,简化,Newton,法（平行弦法）,迭代公式：,（,c,0,k=0,1,）,迭代函数：,3,在,Newton,迭代格式中，用差商近似导数，,弦截法（割线法），弦位法,称,弦截法,.,得,4,弦截法的几何意义：,x,y,x*,x,k+1,x,k-1,P,k-1,y=f(x),x,k,P,k,弦线,P,k,P,k-1,的方程：,当,y,0,时，,5,证明略，因弦截法非单步法，不能用前述定理判别,证明参考（关治，陆金甫,数值分析基础,）,。,6,例,用简化,Newton,法和弦截法计算方程,x,3,-3,x,+1=0,的根。,解,设,f(x,)=,x,3,-3,x,+1,，则,f (,x,)=3,x,2,-3,由简化的,Newton,法，得,由弦截法，得,7,x0=0.5,x1= 0.3333333333,x2 = 0.3497942387,x3 = 0.3468683325,x4 = 0.3473702799,x5 = 0.3472836048,x6 = 0.3472985550,x7 = 0.3472959759,x8 = 0.3472964208,x9 = 0.3472963440,x10 = 0.3472963572,x11 = 0.3472963553,x0=0.5;,x1=0.4;,x2 = 0.3430962343,x3 = 0.3473897274,x4 = 0.3472965093,x5 = 0.3472963553,x6 = 0.3472963553,简化,Newton,法,弦截法,要达到精度,10,-8,，简化,Newton,法迭代,11,次，弦截法迭代,5,次（,Newton,迭代法迭代,4,次,）。,8,无论前面哪种迭代法：,（,Newton,迭代法、,简化,Newton,法、,弦截法）,Newton,迭代法,是否收敛均与,初值的位置,有关。,例,x0 = 2,x1 = -3.54,x2 = 13.95,x3 = -279.34,x4 = 122017,x0 =1,x1 = -0.5708,x2 = 0.1169,x3 = -0.0011,x4 = 7.9631e-010,x5 = 0,收敛,发散,9,为防止,Newton,法发散，可增加一个条件,：,|,f,(,x,k+1,)|,f,(,x,k,)|,，,满足该条件的算法称,下山法,。,可用下山法保证收敛，,Newton,法加速收敛。,Newton,下山法,（,0,1,下山因子）,记,称,Newton,下山法,。,即,10,下山因子选取法,的选取：从,=1,开始，逐次减半计算，即按,的顺序，直到使下降条件,|,f,(,x,k+1,)|,f,(,x,k,)|,成立为止。,11,例,求解方程,要求达到精度,|,x,n,-,x,n-1,|,10,-5,，取,x,0,=-0.99.,解：先用,Newton,迭代法,：,f (,x,)=,x,2,-1,x,2=21.69118,x,3=15.15689,x,4 = 9.70724,x,5 = 6.54091,x,6 = 4.46497,x,7 = 3.13384,x,8 = 2.32607,x,9 = 1.90230,x,10= 1.75248,x,11= 1.73240,x,12= 1.73205,x,13= 1.73205,需迭代,13,次才达到精度要求,12,用,Newton,下山法，结果如下：,k=0,x,0,=-0.99 f(,x,0,) =0.666567,k = 1,x,1,=32.505829 f(,x,) = 11416.4,=0.5,x,1,=15.757915 f(,x,) = 1288.5,=0.25,x,1,=7.383958 f(,x,) =126.8,=0.125,x,1,=3.196979 f(,x,) =7.69,= 0.0625,x,1,=1.103489 f(,x,)=-0.655,k = 2,x,2,= 4.115071 f(,x,) =19.1,= 0.5,x,2,= 2.60928 f(,x,)=3.31,=0.25,x,2,=1.85638 f(,x,)=0.27,k = 3,x,3,=1.74352 f(,x,)=0.023,k = 4,x,4,= 1.73216 f(,x,)=0.00024,k = 5,x,5,= 1.73205 f(,x,)=0.00000,k = 6,x,6,= 1.73205 f(,x,)=0.000000,k,下山因子,x,k,f(,x,k,),13,设,f,(,x,)=(,x,-,x,*),m,g,(,x,) ,m,2,，,m,为整数，,g,(,x,*)0,则,x,*,为方程,f,(,x,)=0,的,m,重根。此时有,f,(,x,*)=,f,(,x,*)=,f,(m-1),(,x,*)=0,f,(m),(,x,*),0,Newton,法对重根的求解,方法一：,只要,f,(,x,k,) 0,，,仍可用,Newton,法计算，此时,为线性收敛。,方法二：,若取,则,(,x,*)=0,，,用迭代法,求,m,重根，则具,2,阶,收敛，,但要知道,m,。,14,令,称之为,带参数,m,的,Newton,迭代法,它是求方程,(x)=0m,重根的具有,平方收敛,的迭代法,.,方法二简证：,设是方程,(x)=0,的,m,重根，则：,(x)=(,x-),m,h(x,),其中,h(x),在,x=,处连续且,h()0,。,则恰是方程,F(x,)=0,的单根,应用,Newton,迭代法,:,15,方法三：,还可令,则,故,x,*,是,(,x,)=0,的单根,，对,(,x,),用,Newton,法，可得,它是,平方阶收敛,的。,这是求方程,(x)=0,重根的具有平方收敛的迭代法,而且,不需知道根的重数,.,16,例,利用,Newton,迭代法求方程,(x)=x,4,-8.6x,3,-35.51x,2,+464.4x-998.46=0,的正实根,.,o,x,y,2,4,6,8,10,y=f(x),解,y=,(x),的,图形为,由图可知,方程在,x=4,附近有一个,重根,在,x=7,附近有一单根,.,17,利用,Newton,迭代法,求,方程的单根,取初值,x,0,=7,精度,=10,-6,计算可得,:,x,4,=7.34846923, x,5,=7.348469229, |x,5,-x,4,|=0.000000001,迭代,5,次就得到满足精度的解,x,5,=7.348469229,利用求重根的,Newton,迭代法求重根,取,x,0,=4,可得,x,3,=4.300000, x,4,=4.300000, |x,4,-x,3,|=0.000000006,若用,一般的,Newton,迭代法求重根,取,x,0,=4,虽然也收敛,却需要迭代,19,次才能得到满足精度要求的解,.,迭代,4,次就得到满足精度的解,x,4,=4.300000.,18,类似割线法，过三点做,f(x,),的二次插值多项式,抛物线法（,muller,法）,19,20,(1),要有三个初始值,(2),收敛速度是,1.84,阶。（单根） 二重根的收敛阶是,1.23,。,各种插值方法的比较,21,代数多项式求解,Splitting Method,劈因子法,秦九韶算法,22,设,n,次代数方程,用,Newton,迭代法求有限区间的实根，则要计算,，一般采用秦九韶算法。,23,由,Taylor,展式,24,25,26,同理,27,比较,x,的同次幂系数得：,故代数方程的,Newton,迭代公式,28,代数方程的,Newton,迭代法算法,29,Splitting Method,劈因子法,求多项式的根,从,f,(,x,),中分离出一个,2,次因子。即：,通过 可解出一对共轭复根。,思路,从一对初值,(,u,v,),出发，则有,其中,(,r,s,),取决于,u,和,v,，,可以看作是,(,u,v,),的函数，即,r,=,r,(,u,v,),，,s,=,s,(,u,v,),。,目标：,r,=,r,(,u,*,v,* ) = 0,，,s,=,s,(,u,*,v,* ) = 0,。,30,将,r,和,s,在初值点,(,u,v,),做一阶,Taylor,展开,，并代入,(,u,*,v,*),：,每步迭代须计算,从中解出,，以 更新,u,和,v,再迭代，直到,r,和,s,充分接近,0,。,v,v,v,u,u,u,-,=,D,-,=,D,*,*,31,计算,r,和,s,：,可记,为,b,n,1,若,令 ，则,32,计算,：,n,2,阶多项式,n,4,阶多项式,与前一步同理，可导出和 的公式。,33,计算,：,而前一步得到,可见,34,
展开阅读全文