基于Gauss求积公式的Newton迭代法

摘要:利用Gauss数值积分公式构造牛顿迭代法的变形格式,得到牛顿迭代方法的三个新格式,并证明了它们的收敛阶都为3。通过matlab编程进行数值试验,结果表明三个新格式具有较好的收敛速度。它们丰富了非线性方程求根的方法,在理论上和应用上都有一定的价值。

Abstract: This paper mainly employs Gauss numerical integral formulas to construct the deformation of Newton iterative method, therefore, we get the three new formats of the Newton iterative method and prove its convergence order is 3. With the numerical tests of matlab, it is shown that the three new formats, compared with the Newton iterative method, have better convergence speed, which to some extent enrich the method of location of root for nonlinear equations and prove the value of it both in theory and application.

关键词: Gauss数值积分公式;Newton迭代法;三个新格式;数值试验。

Key words: gauss numerical integral formulas;Newton iterative method;three new formats;numerical experiments

中图分类号:O1 文献标识码:A文章编号:1006-4311(2010)10-0118-02

0引言

牛顿迭代法是非线性方程求根的一个基本方法,它二次收敛到单根,线性收敛到重根。其迭代格式为:xk+1=xk-(1)

牛顿法因收敛速度快而得到广泛应用。近年来很多文献中提出各种改进的牛顿迭代法,它们的一个基本的出发点是下面的恒等式:

f(α)=f(x)+f′(x)dx(2)

其中α是所要求的方程的单根。用左矩形公式计算式(2)中的积分,并注意到得到f(α)=0,有:α=xk-(3)

把(3)式左边作为对根的一个近似,则得到式(1)[1]。

因此,人们有理由相信,如果采用精度更高的积分公式计算(2)式中的积分,可能会得到收敛阶更高的牛顿迭代公式。文献[1]利用梯形公式计算积分从而得到所谓的梯形牛顿法,并证明了收敛阶为3,文献[2]利用中点公式计算积分得到中点牛顿迭代法,收敛阶为3[3],文献[3]用典型的四等分5个节点的Newton-Cotes公式得到Cotes牛顿迭代法,收敛阶为3,文献[4]利用Simpson公式,也得到一个收敛阶也为3 的Simpson牛顿迭代法。

1基本定义

定义[5] 设序列{x}收敛于α,若存在p?叟1及常数c?叟0,使

成立,则称序列{x}是p阶收敛的,c称为收敛因子。p=1时称收xk敛于α是线性收敛,p>1是超线性收敛,p=2是平方收敛,p=3是三次收敛。在定义中,令en=xn-α,则称关系式e=ce+o(e)为误差方程,p称为收敛的阶。

2主要结果

2.1 一点G-N迭代格式设α是f(x)=0的根,f(x)是可导函数。通过对(2)式右端的积分作变换,则有:

0=f(x)+f′(t+)dt(4)

对式(4)右端的积分采用一点Gauss求积公式近似代替,用xn+1近似代替α,整理得到迭代格式:xn+1=xn-(5)

式(5)中的xn+1是隐式的,这给计算带来了很大的障碍,从而提出对式(5)进行预估-校正,有如下格式:

z=x-x=x-(k=1,2,…)(6)

从式(6)则得到:x=x-(k=1,2,…)(7)

式(7)是Newton迭代法与一点Gauss求积公式结合得到的,在此简称为一点G-N迭代格式。

2.2 两点G-N迭代格式对(4)式右端的积分采用两点Gauss求积公式近似代替,用xn+1近似代替α,并进行预估-校正,得到:

x=x-

(k=1,2,…)(8)

简称式(8)为两点G-N迭代格式。

2.3 三点G-N迭代格式采用三点Gauss求积公式近似代替(4)式右端的积分,用xn+1近似代替α,并进行预估-校正,得:

x=x-

((k=1,2,3…)(9)

简称式(9)为三点G-N迭代格式。

2.4 一点、两点和三点G-N迭代格式的收敛性分析定理 设α是充分光滑函数f(x):I?哿RR的单根,I是一开区间。若x0充分接近α,迭代格式(7)、(8)、(9)收敛阶为3。

证明:首先证明一点G-N迭代格式(7)3阶收敛。设α是f(x)的单根,由于f(x)充分光滑,将f(x)和f′(x)在α处展开得:

f(x)=f′(α)[en+c2e2n+c3e3n+c4e4n+o(en5)](10)

f′(x)=f′(α)[1+2c2en+3c3e2n+4c4e3n+o(en4)](11)

其中en=xn-α,ck=,(k=1,2,3,…)则:

=en-c2e2n+2(c22-c3)e3n+o(en4)

所以有:xn-=α+[en+c2e2n-2(c22-c3)e3n+o(en4)](12)

从而利用(12)将f′(x-)在α处展开,有:

f′(x-)=f′(α)[1+c22e2n+2(c2c3-c32)e3n+o(en4)](13)

将式(10)和(13)代入迭代格式(7),得到:

xn+1=xn-[en+c2e2n+(c3-c22)e3n+o(en4)]

所以xn+1-α=xn-α-[en+c2e2n+(c3-c22)e3n+o(en4)]

即:en+1=en-en-c2e2n-(c3-c22)e3n+o(en4)=-c2e2n-(c3-c22)e3n+o(en4)(14)

由式(14)可知一点G-N迭代格式(7)3阶收敛。

两点和三点G-N迭代格式3阶收敛的证明和上述证明过程完全类似,为节省篇幅在这里就不再给出。

3数值试验

例求解非线性方程f(x)=xex-1[5]。

方法一:利用一点G-N迭代格式(7),取初值x0=0.5,精确到0.00001,利用matlab求解如下:先建立GN1.m文件如下:

再建立两个函数文件:fn.m和dfn.m如下,

最后在Matlab窗口中输入GN1(0.5,0.00001),运行结果如下:

x1 =0.56714329040978n=3

方法二:利用两点G-N迭代格式(8),取初值,精确到0.00001,利用matlab求解如下:建立GN2.m文件如文件3:

利用上面的fn.m和dfn.m函数文件,在matlab窗口中输入GN2(0.5,0.00001),运行结果如下:

x1 =0.56714329040978n =3

方法三:利用三点G-N迭代格式(9),取初值,精确到0.00001,利用matlab求解如下:

先建立GN3.m文件如文件4:

利用相同的fn.m和dfn.m函数文件,在matlab窗口中输入GN3(0.5,0.00001),运行结果如下:

x1 =0.56714329040978n =3

方法四:利用Newton迭代法,取初值X0=0.5,精确到0.00001,利用matlab求解如下:

建立diedai.m如下:

再利用上文中的fn.m和dfn.m函数文件,在matlab窗口中输入Newton(0.5,0.00001),运行结果如下:

x1 =0.56714329040978n =4

从结果可以看出,同样的初值,同样的精度要求,用Newton迭代法要迭代4次才可以,而用上述三种迭代格式均只需3次迭代就可以完成。

综上,三种新的迭代公式均收敛,且收敛的速度远比Newton迭代法快,这一点从它们的收敛阶不难得出。

参考文献:

[1] Weerakoon S,Fernando T G I.A variant of Newton's method with accelerated third-order convergence [J].Appl Math Lett,2000,13(8):87-93.

[2] Dozen A Y.Some new variants of Newton's method[J].Appl Math Lett,2004,17: 677-682.

[3] 薛雅萍,吴开谡,刘晓晶.基于等距节点积分公式的牛顿迭代法及其收敛阶[J].数学的实践与认识,2007,37(24).

[4] 王霞,赵玲玲,李飞敏.牛顿迭代法的两个新格式[J].数学的实践与认识,2007,37(1).

[5]李庆扬, 易达义, 王能超. 现代数值分析[M]. 高等教育出版社,1995.