一类新的求解非线性方程的算法

白晓燕,李 炜

(杭州电子科技大学理学院,浙江杭州310018)

0 引 言

非线性方程的解法和理论是当今数值分析研究的重要课题之一,也是科学和工程计算中最重要的问题之一,许多优化问题也往往可以归结为非线性方程的求解。求解此问题最常用的方法是二阶收敛的经典的牛顿法CN。近年来,许多工作者通过增加函数、导数的个数或改变迭代点来提高牛顿法收敛的阶,提出了许多解非线性方程的迭代法[1-3,5,9]。本文在三阶收敛牛顿法的基础上提出了一个新的加速算法,收敛性分析证明了新算法是三阶收敛的,通过一些测试函数验证了该算法的有效性。

1 算法描述及其收敛性分析

1.1 新算法导入

为了避免计算高阶导数,许多新算法都是利用导函数的插值导出的,不同的插值方法有不同的优点与不足。综合利用这些插值方法的特性,有望导出同阶收敛且具备自己特性的新算法。以求解非线性方程的三阶算法为例导出一般的构造方法。

关于求非线性方程的单根,众所周知的三阶收敛法有,算术平均牛顿法AN[3]和New ton-Steffensen法NS[2]。最近,文献5中,提出了如下的三阶收敛算法:

为了综合利用算术平均牛顿法AN[3]和Newton-Steffensen法NS[2]的不同插值性质,令:

由式2解得:

将式3的值代入式1中,导出新的求解非线性方程的迭代法

将从理论上证明迭代算法式4的收敛性。

1.2 收敛性分析

定理1 设f:D→R的连续可微函数 ,其中D是开区间 ,α为f(x)在D内的单根 ,即f(α)=0且′(α)≠0,如果初值x0充分接近于α时,式4是三阶收敛的,且误差方程为en+1=(2c22+c2)e3n+O(e4n):其中,en=xn-α,cj=

证明 设 α为f(x)在D内的单根,en=xn-α是迭代xn的误差,将 f(xn)和 f′(xn)在零点 α处泰勒展开,可得:

式中,en=xn-α,cj=

将式5、6代入yn=xn中,有

将f(yn)在零点α处泰勒展开,由式5可得:

有式5-7,得:

从而,误差方程为:

证明可知,新算法对于单根来说是三阶收敛的。

1.3 Ostrowski算法的新推导

显然,利用前述思想的方法可以导出不同的迭代法,具有综合插值性质的式3适用范围很广。利用式3来重新得到文献7中著名的四阶收敛的Ostrowski算法。

事实上,用式3代替文献6中的调和平均牛顿法HN中的 f′(yn),得:

即著名的Ostrowski四阶收敛迭代法。

同样得到了Ostrowski四阶收敛迭代法。

此即在文献8中提到的有名的两步牛顿迭代法TN。

类似地,利用式3还可以导出其他的一些已知方法或一些新算法,这些新算法往往是效率较高的。验证迭代式4的数值实验结果如下。

2 数值计算

为检验所得到的三阶迭代法式4的有效性,分别用CN、AN、HN、NS和TN来解下列常用测试函数的根,用迭代的次数i来说明所得到的三阶迭代法的收敛有效性,所有的结果都是在Matlab7.0的环境下操作,从初始值x0开始迭代,停止准则是|xn+1-α|+|f(xn+1)|＜10-14。

(1)f1(x)=x3+4x2-10,α=1.365 230 013 414 097。

(2)f2(x)=sin2x-x2+1,α=1.404 491 648 215 341。

(3)f3(x)=(x-1)3-1,α=2。

(4)f4(x)=ex2+7x-30,α=3。

(5)f5(x)=x2+-ex-3x+2,α=0.257 530 285 439 860 8。

新算法与其它同阶著名算法解非线性方程的迭代次数比较表,如表1所示:

表1 迭代次数比较表

从表1中,可以看出迭代法式4的迭代的次数比经典的牛顿法CN少,除f1(x)中x0=-0.5和f2(x)中x0=3之外比算术平均牛顿法AN的迭代次数少,除f1(x)中x0=-0.5中比两步牛顿法TN的迭代次数少,需要指出的是迭代次数与所选的初始值x0紧密相关。

3 结 论

本文提出了一种构造求解非线性方程的迭代算法的一种框架,以三阶为例进行了探讨,但这种思想显然可以方便的推广的更一般的迭代式中。而且,猜测这种方法不仅仅局限于对f′(yn)表达式的考虑,还可以考虑诸如)等的综合插值性质,从而有望构造好的算法,这是今后的研究方向。

[1] Frontini M,Sormani E.Some variant of New ton's method with third-order convergence[J].Appl Math Comput,2003,(2-3):419-426.

[2] Chun C,Ham Y.Some fourth-order modifications of New ton's method[J].Appl.Math.Comput.2008,(2):654-658.

[3] Weerakoon S,Fernando G I.A variant of New ton's method with accelerated third-order convergence[J].App lMath Lett,2000,13(8):87-93.

[4] Sharma JR.A composite third order New ton-Steffensen method for solving nonlinear equations[J].Appl Math Comput,2005,(1):242-246.

[5] Chun C.Some third-order families of iterative methods for solving nonlinear equations[J].Appl Math Comput2007,(1):924-933.

[6] Homeier H H H.On Newton-type methods with cubic convergence[J].Comput Appl Math,2005,(2):425-432.

[7] Traub JF.Iterative Methods for the Solution of Equations[M].New York:Chelsea Publishing Company,1997:211.

[8] Potra F A,Ptak V.Nondiscrete induction and iterative processes[M].Boston:Research Notes in Mathematics,1984:8-9.

[9] Chun C.A simply constructed third-order modifications of Newton's method[J].Comput Appl Math,2008,(1):81-89.