1. 引言
虽然非线性问题自古有之,但人类一开始对客观世界的认识不够细致,主要停留在宏观层面,用线性模型就足以解决。进入20世纪,随着科学技术的飞速发展,人类对客观事物的认识逐渐由宏观层面向微观层面迈进,人们在物理、化学等很多学科中逐渐发现了非线性关系问题。到20世纪六七十年代,随着非线性理论的不断涌现,非线性科学彻底诞生了,它贯穿了自然科学、社会科学、工程学等领域中几乎每一门学科,被誉为20世纪继量子力学的又一次革命。在工程、经济等领域中出现的很多问题都可以转化为非线性方程来求解。如机器人学习中的几何设计问题 [1],三自由度并联机构正解问题 [2],化学工程中的分子模型问题 [3],动力学中的平衡问题 [4],经济管理学中的非线性规划问题 [5],材料力学中的弹塑性问题 [6],计算机制图中求解几个平面交点的问题 [7],等式约束优化中寻求可行初始点的问题 [8] 等。
对于非线性方程
(1)
其中
。1966年美国计算数学家Moore首次提出求解非线性方程的区间牛顿法 [9] [10] [11]。区间牛顿法在古典的点牛顿迭代法的基础之上,引进区间变量,构造了点牛顿迭代法的区间变形,得到了区间牛顿法,对于任取
:
(2)
(3)
其中
表示区间
的中点。利用区间牛顿法,每次迭代都产生了解的界限,从而不仅取得了解的近似,亦得到了解的误差,且该迭代法还是二阶收敛的。Ostrowski [12] 等人在Moore的区间牛顿法的基础上提出了一种切合实际的改进,后来人们称之为区间Ostrowski迭代法 [12]。由于区间迭代法的计算效率还是远远低于点迭代法,因此寻求计算效率高的区间迭代法一直是区间数学的重要研究课题之一。
引理1 [10]:对于单变量实有理函数
,区间牛顿算子(2)具有如下性质:
(1) 若
是f的零点且
,则
;
(2) 若
,则函数f在区间
上必无零点存在;
(3) 若
成立,则函数f在区间
上必有零点存在。
引理2 [11]:对于单变量实有理函数
,
分别为
的有理扩展,函数f在区间
内存在
一单根
且
,则由区间牛顿法所产生的区间序列
二阶收敛于
,即存在实数
使得
引理3 [11]:对于区间序列
,存在实数
。现定义区间序列
为:
则区间序列
是极限为
的嵌套区间序列且对任意
有
。
引理4 [9]:设
为Lipschitz区间函数,
为非线性方程的实根,则存在常数
使得
因此,存在常数
使得
2. 求解非线性方程的多步区间迭代
本节我们将基于点迭代的两步牛顿法 [13] 和King迭代法 [14] 建立基于区间迭代的多步迭代法。首先我们建立求解非线性方程(1)的两步区间牛顿法,对于点迭代的两步牛顿法
为了获取包含解,根据区间牛顿法的思想构造如下两步区间牛顿法
(4)
这里
进一步,基于文 [14] 提出的King迭代法
这里取
。
对King迭代法进行区间扩展,可得如下区间King迭代法
(5)
这里
3. 收敛性分析
定理1. 设函数
在区间
内连续可微,
是由两步区间牛顿法(4)得到的,且
。如果
中包含有非线性方程(1)的一个实根
,则所有区间
均包含实根
,
是一个极限为
的嵌套区间序列且
。
证明. 因为
,由引理1可知
。应用泰勒中值定理,存在
(
介于
与
之间),使得
则
故
同理,当
时,有
。综上,由数学归纳法可知
由引理3可知,两步区间牛顿法(4)所得的区间序列是极限为
的嵌套区间序列且
。
两步区间牛顿法的最大优点是:在计算的过程中能判断某区间是否含有方程的解,如果该区间内不含有方程的解,可以换一个区间再进行迭代,而无需重复无用的迭代。另一个优点是:该算法给出了某一区间内解存在唯一性的充分条件。
定理2. 设函数
在区间
内连续可微,
是由两步区间牛顿法(4)得到的,且
(1) 如果
,则区间
内有且仅有非线性方程(1)的一个解。
(2) 如果
,则区间
内不含有非线性方程(1)的任何解。
证明. (1)由于
,则对任意
有
,故函数
在区间
内单调,所以区间
最多含有方程的一个解。下面证明解的存在性。
设函数
其中
即
由泰勒中值定理可知,存在
使得
则
故
即
是将
映射到自身的连续映射,又区间
为有界闭凸集,依据Browuer不动点定理,存在
使得
,从而有
,因为
,所以有
,因此非线性方程(1)在区间
中有且仅有唯一解。
(2) 设
是非线性方程(1)的一个解且
,则
,故
与条件相矛盾,所以定理得证。
定理3. 假设函数
在区间
内连续可微,
且非线性方程(1)在
中有唯一单根
。由两步区间牛顿法得到序列
,如果
,则
至少是三阶收敛的,即存在常数
使得
证明. 由中值定理可知,存在
(
介于
与
之间),使得
则
又因为
,由引理2可知,存在
使得
由引理4可知,存在
使得
因为
在区间
上连续,则存在
,使得
。
综上
这里
,定理得证。
注1. 区间King迭代法的收敛情况与定理(1)、定理(2)类似,这里不再重复,下面只给出区间King迭代法的收敛速度。
定理4. 假设函数
在区间
内连续可微,
且非线性方程(1)在区间
中有唯一单根。由区间King迭代法(5)得到序列
,如果
,则
至少三阶收敛,即存在常数
使得
证明. 由中值定理可知,存在
(
介于
与
之间),使得
则
因为
则存在
使得
由引理2可知,存在
使得
由引理4可知,存在
使得
因为
在区间
上连续,则存在
,使得
。
由上式可以得出
这里
,故定理得证。
4. 数值算例
本节通过数值算例对两步区间牛顿法,区间King迭代法,区间牛顿法 [10],区间Ostrowski迭代法 [12] 的数值效果进行对比。虽然文献 [12] 证明区间Ostrowski迭代法为四阶收敛的,但其证明过程存在错误,实质上是三阶收敛。为了区分这些迭代法,下面用不同方法的简称来表示:
TWOSN:两步区间牛顿法
KING:区间King迭代法
NEWT:区间牛顿法
OSTRO:区间Ostriwski迭代法
为了方便起见,“Method”表示上面所示的区间迭代法,“Iter”表示各区间迭代法的迭代次数,“
”表示迭代计算结束时的区间,“Error”表示迭代误差(即通过
进行计算),“Time”表示计算时间(单位为秒)。现对上面所示的几种区间迭代法的数值效果进行比较,使用区间工具箱INTLAB-V6 [15] 在计算机(Intel i5, 1.8GHz/8GB, MATLAB 2008a)上进行计算。
例1 设
,非线性方程
在区间
内的解为
。数值结果见表1:
Table 1. Numerical results for example 1
表1. 例1的数值结果
例2 设
,非线性方程
在区间
内的解为
。数值结果见表2:
Table 2. Numerical results for example 2
表2. 例2的数值结果
例3 设
,非线性方程
在区间
内的解为
。数值结果见表3:
Table 3. Numerical results for example 3
表3. 例3的数值结果
例4 设
,非线性方程
在区间
内的解为
。数值结果见表4:
Table 4. Numerical results for example 4
表4. 例4的数值结果
例5设
,非线性方程
在区间
内的解为
。数值结果见表5:
Table 5. Numerical results for example 5
表5. 例5的数值结果
从表1~5,可以看出,新提出的两种区间迭代法在计算效率上比区间牛顿法有所提高,计算效果最好的是区间King迭代法。
5. 总结
本论文提出了两种求解非线性方程的区间迭代法,分别对这两种方法进行收敛性分析,最后选取五个数值算例对这些方法进行比较。数值结果表明新提出的区间迭代法可能比现有的区间迭代法更有效,这为科学与工程应用提供了一种新的选择。
基金项目
本文工作由江苏省自然科学基金(BK20151139)支持。