非线性方程的求根方法3

《非线性方程的求根方法3》由会员分享，可在线阅读，更多相关《非线性方程的求根方法3（34页珍藏版）》请在装配图网上搜索。

1、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,*,附近成立，则,收敛,。,,若取,

2、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,,例,用简化,Newt

3、on,法和弦截法计算方程,,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,,x1

4、0 = 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,迭代法,是否收敛均与,初值的

5、位置,有关。,例,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

6、,,下山因子选取法,的选取：从,=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

7、,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,)

8、=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

9、 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,法计算，此时,为线

10、性收敛。,方法二：,若取,则,`(,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

11、,法，可得,,,,它是,平方阶收敛,的。,这是求方程,,(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

12、, 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,),的二次插值多项式,抛物线法

13、（,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,迭代法

14、算法,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,,