1. 引言
非线性方程的求根问题是数值分析的一个基本问题。1966年,Moore [1] 提出的二次收敛的古典区间牛顿法是一种重要的方法,但是该方法要求
,对于求重根的情况,此时,
,该方法不再适用。
对于
的情况,Hansen [2] 对古典的区间Newton法做了有效的改进,给出了在相应初始区间始终收敛的区间Newton法。改进的区间Newton法,仅需在初始迭代区间存在有限个实根,无论这些实根的重数是多少,均可以有效计算初始区间的所有根,而且可以推广到高维的情形。但是应用改进的区间Newton法来求解非线性方程的重根问题时,其收敛速度将变得很慢。
在实际应用中,遇到的问题可能是求方程的单根,也可能是求方程的重根。现有的许多高阶收敛的区间迭代法 [6] - [15] 在求解方程单根时表现出非常好的数值结果,但当求解的是非线性方程的重根时,其计算效率就会大大下降。
在本文中,我们引入以下符号说明:
表示R上所有区间的集合,关于区间
(如果
,则
退化为一个点),称
为区间X的中点,
为区间X的宽度,
为区间X的绝对值。与本文相关的其它区间分析的内容可参阅文献 [1] - [6] 等。
定义1:设
,若存在区间值映射
,对任意
,有
成立,则称区间值映射
为函数
的区间扩展。相对应,
为导函数
的区间扩展,
为二阶导数
的区间扩展。
定义2:设区间值映射
为函数f的区间扩展,而
且满足
,如果成立
,则称区间值映射F具有包含单调性。
2. Hansen改进的区间Newton法
古典区间Newton法是求解非线性方程的经典方法。设f是单变量实值的连续可微函数,
是
在区间X上具有包含单调性的区间扩展,记
为函数
在给定区间
上的区间扩展,如果
,则可建立如下迭代公式
这里
这就是著名的古典区间Newton法 [1] [2] [3] [4] 。
当
时,Hansen通过引进无界区间的概念来定义区间除法。
设
,因为
,定义
若成立
,则
就是f的零点,否则
就有两种可能的定义,
1) 对于
的情形,有
2) 对于
的情形,有其它情况
其中
当
时,有
此时
即为Hansen [2] 改进的区间Newton法。
3. 新的区间迭代算法
对于非线性方程
,设
为该方程的单根或重根,
是比较靠近
的初始值。使用泰勒公式将
展开到二阶,有
(1)
这是一个关于x的二次方程且一定存在实根,解得
(2)
或
(3)
设
为
的具有包含单调性的区间扩展,新的区间迭代法如下
(4)
这里
(5)
或
(6)
4. 新方法的收敛性与误差分析
说明:以上区间算子S有两种,所用方法完全相同,所以以下定理只就第一种情况进行证明,第二种情况的证明步骤也完全相同,就不作详叙。
定理1:设f为给定区间
上的一个二阶连续可微函数,且
如果
包含有f的一个零点
,则所有的
都包含
,且有
。
证明:由式(2)可知
故
。
同理,如果
,则
,由数学归纳法可得
所以
,由式(4)可得
。
该区间算子的好处在于:1) 能检测到一个区间是否有根存在,这样可以避免无用的迭代运算;2) 能保证在一个区间有且只有一个实根。
定理2:设f为给定区间
上的一个二阶连续可微函数,且
,则
1) 如果
,则X中有且仅有方程
的一实根。
2) 如果
,则X中不含方程
的任何实根。
证明:1)首先证明方程
根的存在性,
对任意实数
,构造算子
其中
由于
在X上的连续,以及
,所以
为定义在X的连续算子,当
时,由
的包含单调性可知
当
时,化简可得
,又因为
,则区间算子
是将X变换到其自身的连续算子,且区间X为有界闭凸集,根据Browner不动点定理,可知
存在不动点
,使得
,从而有
因为
,所以
,故有
。
下面证方程
根的唯一性,如果
是函数f的零点,成立
则有
,这表明程序终止在有限步。
如果
不是f的零点,此时,由
的定义可知总有
或
成立,这表明
不包含
的中点,因此必有
,从而,故由根的存在性可知点收敛于。
综上可得X中有且仅有的一个零点。
2) 若X包含的零点,由定理1的证明可知,故与条件矛盾,所以X中不含的零点。
定理3:设f为给定区间上的一个二阶连续可微函数,且方程存在唯一的重根 (至少二重)。如果且为Lipschitz区间函数,则由迭代公式(4)所得区间列二次收敛,即存在常数,使得
.
证明:因为为Lipschitz区间函数,则存在,使得
且
,
所以
.
又因为,则存在,使得,且
故
这里,存在常数使得
.
综上可得,令,则有
Table 1. Numerical comparison of both HM method and SM method
表1. HM和SM两种方法的数值对比
.
同理有。
5. 数值算例及结果分析
为了验证本文方法的正确性,在联想G400笔记本电脑(处理器:英特尔第三代酷睿i5-3230M @ 2.60 GHz双核)上借助MATLAB R2012b与工具箱INTLAB_V5.5进行编程求解。下面将给出一些数值算例,分别应用本文的方法与Hansen改进的区间Newton法来求解,并对结果进行了对比分析,其中,“HM”表示Hansen改进的区间Newton法,“SM”表示本文的方法,ε表示精度,N表示迭代次数time表示迭代所用时间(单位为秒),X表示计算结果(表1)。
具体算例和数值计算结果如下:
例1:求方程在区间上的根,方程的准确重根为。
例2:求方程在区间上的根,方程的准确重根为。
例3:求方程在区间上的根,方程的准确重根为。
例4:求方程在区间上的根,方程的准确重根为。
例5:求方程在区间上的根,方程的准确重根为。
例6:求方程在区间上的根,方程的准确重根为。
例7:求方程在区间上的根,方程的准确重根为。
上述数值算例的结果以及更多的数值计算结果都验证了,在求解非线性方程的重根问题中,本文所建立的区间迭代法与Hansen改进的区间Newton法相比,在迭代次数和时间花费上具有更好的优势,这充分证明了本文方法是有效可靠的。
基金项目
本文工作由江苏省自然科学基金(No. BK20151139)支持。