APP下载

一族带有参数的三阶收敛迭代方法

2015-03-07裕静静

关键词:求根迭代法三阶

江 平, 裕静静

(合肥工业大学 数学学院,安徽 合肥 230009)

在科学与工程计算中经常遇到非线性方程,但是只有不高于4次的代数方程有求根公式可以计算出精确解,而无高于4次的求根公式,为了解决实际问题需要求出满足一定精度要求的近似解,目前数值求解非线性方程f(x)=0的根方法有很多,经典牛顿迭代法(CN法)[1]是非线性方程求根的一个基本方法,它至少二阶收敛到单根,线性收敛到重根,牛顿法因收敛速度快而得到广泛应用,也倍受学者的重视。对该方法进行改进,使之具有更高的收敛速度是当今国内外研究的热点问题之一。近年来很多文献中提出各种改进的牛顿方法,例如Simpson牛顿方法(SN 法)[2]、几何平均牛顿法 (GN 法)[2]、调和 平均牛顿方法(HN 法)[3]、中点牛顿法(MN 法)[3]、算术平均牛顿法[4]、文献[5]中利用f(x)的二阶泰勒展开式导出改进的牛顿法、文献[6]中利用经典牛顿和Runge-Kutta方法改进的2-Runge-Kutta牛顿法以及文献[7]中改进的Simpson牛顿方法(SN法),它们都是至少三阶收敛的。文献[8]提出求解非线性方程的加权迭代方法,收敛阶为三阶,但使用起来不方便,每次计算量大。这些文献提出的算法收敛速度都比经典牛顿迭代法速度快,效率指数较高。

本文基于文献[3,6]提出一族带有参数的三阶收敛的牛顿方法,通过选取不同的参数值,可以得到不同的收敛方法,它们包含了多种已知的、改进的牛顿迭代法,而且在满足参数条件时都是至少三阶收敛到单根,线性收敛到重根。

1 带参数三阶牛顿方法格式

经典牛顿算法(CN法)[1]迭代格式为:

其迭代函数为:

通过对(1)式进行带参数变换,可以得到新的迭代格式,本文根据此想法得到新的算法。

已有改进的三阶收敛牛顿迭代法,例如2-Runge-Kutta牛顿法[3],其迭代格式为:

中点牛顿法[7]迭代格式为:

根据上述的迭代格式以及Runge-Kutta方法的思想,在每步迭代中多计算几次函数的导数值,使得整体的收敛阶提高,如果每次迭代计算2次不同的函数导数值,可以构造一个带参数格式如下:

其中,λ1,λ2,p1,p2,q1,q2∈R。

2 收敛性分析

下面先给出迭代序列的收敛阶和效率指数的定义。

定义1 设序列{xn收敛于x*,若存在p≥1及常数C≠0,使成立,则称序列{xn是p阶收敛的,其中C为收敛因子,也称为渐进误差常数。p=1时称xn收敛于x*是线性收敛;p>1,是超线性收敛;p=2,是平方收敛;p=3,是三阶收敛。

在定义1中,令en+1=xn-x*,则称关系式)为误差方程,p称为收敛的阶,这与定义1是吻合的。

定义2 设迭代序列{xn的收敛阶为p≥1,每步迭代计算量为ω,则称量e=为迭代序列的效率指数。

定理1 (1)设x*是函数f(x)的单零点,f(x)在x*的某一邻域内有连续三阶导数,当参数λ1、λ2、p满足下列条件:

则(2)式所得到的序列{xn}至少是三阶收敛到x*的;如果f″(x*)=0且=1,(2)式是四阶收敛的。

(2)若x*是函数f(x)的多重根,那么(2)式所得到的序列{xn}是线性收敛到x*的。

证明 (1)因为x*是函数f(x)的单零点,设xn在x*的去心邻域内,令en=xn-x*,由带Peano余项的Taylor公式得到:

用辗转相除法可得:

则可得yn为:

由(3)式可知:

同理可得:

由已知条件中参数满足的关系式λ1+λ2=1,λ1p1+λ2p2=1/2和(4)式可知:

不妨设:

将(5)式代入(2)式,利用辗转相除法,可得:

由误差方程的定义可知:

所以迭代格式(2)式至少是三阶收敛到单根的。

如果f″(x*)=0且1,将其代入(2)式,由误差方程定义可知,(2)式是四阶收敛的。

(2)因为x*是函数f(x)的多重根,不妨设x*是f(x)的二重根,多重根的证明与二重根的证明是类似的。由x*是二重根可知f(x)=0,f′(x*)=0,但f″(x*)≠0,

令en=xn-x*,则f(xn)在x*处的泰勒展开式为:

由(7)式、(8)式可知:

所以

同理可得:

将λ1+λ2=1,λ1p1+λ2p2=1/2以及(9)式代入(2)式,可得:

由误差方程的定义可知:

所以迭代格式(2)式是线性收敛到重根的。

3 举例分析

下面给出一些非线性方程的例子。

x0表示初始值,而且分别给出2个不同的初始值,CN表示经典牛顿法,FCN表示λ1p1+λ2p2=2/5≠1/2的算法(其收敛性已证明),PCN表示符合λ1=3/5,p1=1/3,p2=3/4的本文迭代算法,AM表示算术平均牛顿法,MN表示中点牛顿法,2-R-K 表示2-Runge-Kutta牛顿法,2-G-S表示2点高斯求积牛顿法,计算如下数值例子进行比较,所得测试结果见表1所列。

表1 数值计算所需迭代次数的比较

程序运行环境为 Matlab7.0,运行终止条件为|xn+1-xn|<10-14,测试函数选取如下:

(1)f1(x)=ex-3x2,

(2)f2(x)=cosx-x,

(3)f3(x)=x3+4x2-15,

(4)f4(x)=x2sinx-1,

(5)f5(x)=cosx+e-x,

(6)f6(x)=sin2x-x2+1,

(7)f7(x)=(x-1)6-1,

(8)f8(x)=x5-1,

4 结束语

本文所构造的迭代方法比经典牛顿法迭代次数明显减少,且对于任意选取的满足参数条件的本文算法与那些已知改进的三阶收敛法的迭代效果比较,收敛效果相差不大,且对于不满足本文参数关系式λ1p1+λ2p2=1/2的FCN法,其迭代效果比本文算法差一点,但是比牛顿法的迭代效果好,更加证明了本文算法的有效性。对于(2)式,其效率指数为1.316,其中FCN和PCN的效率指数也为1.316,可以通过选取特殊参数值使得其效率指数增大,例如AM法、MN法、2-R-K法,效率指数均为1.442 2,比牛顿迭代的效率指数1.414 2高。

综上所述,本文所得到的方法不仅迭代次数较少,且可以通过选参提高效率指数,具有一定的优越性,丰富了求非线性方程根的求解方法。

[1] 朱晓临.数值分析[M].合肥:中国科学技术大学出版社,2010:84-102.

[2] 王 霞,赵玲玲,李飞敏.牛顿方法的两个新格式[J].数学的实践与认识,2007,37(1):72-76.

[3] Ozban A Y.Some new variants of Newton’s method[J].Appl Math Lett,2004,17:677-682.

[4] Weerakoon S,Fernando T G L.A variant of Newton’s method with accelerated third-order convergence[J].Appl Math Lett,2000,13:87-93.

[5] 吴鲁光.牛顿法的推广:一种方程求根的迭代法[J].兰州石化职业技术学院学报,2000(1):8-10.

[6] 王 霞,赵玲玲.Runge-Kutta方法用于非线性方程求根[J].数学的实践与认识,2008,38(16):134-139.

[7] 李洋洋,郭清伟.Simpson牛顿公式的一种改进[J].合肥工业大学学报:自然科学版,2012,35(6):853-856.

[8] 冯新龙,张知难.求解非线性方程的加权迭代方法[J].大学数学,2006,22(4):85-88.

猜你喜欢

求根迭代法三阶
迭代法求解一类函数方程的再研究
三阶非线性微分方程周期解的非退化和存在唯一性
用换元法推导一元二次方程的求根公式
不可轻视求根公式
对某些特殊一元四次方程求根公式的推导
切比雪夫多项式零点插值与非线性方程求根
迭代法求解约束矩阵方程AXB+CYD=E
预条件SOR迭代法的收敛性及其应用
三类可降阶的三阶非线性微分方程
三阶微分方程理论