《专题十 非线性方程的区间算法》由会员分享，可在线阅读，更多相关《专题十 非线性方程的区间算法（8页珍藏版）》请在金锄头文库上搜索。
1、 专题十 非线性方程的区间算法 对于非线性方程组 11211(, , ) 0(, , ) 0(, , ) 0nnnnfx xfx xfx x=LLLLL(10.1) 其中 (1,2,)if in= L 为定义在区域nDR 上的非线性函数。若令12(, , , )Tnx xx x= L ，12() ( (), (), , ()Tnf xfxfx fx= L ，则 (10.22)变为 () 0fx= (10.2) 称为方程组 (10.1)的向量形式。 求解 (10.1)的一类基本而重要的方法是 Newton 迭代法，然而 Newton 法对初始点的要求非常苛刻，要求初始点(0)x 比较接近精确解*
2、x ，否则可能不收敛，而事实上我们不知道*x ，而且在迭代过程中，我们始终不知道迭代实列()kx 与*x 相差多远。 区间迭代法，首先是由 Moore 在区间算数的基础上提出的一类新型的求解非线性方程组的迭代法，它是以区间为变量，通过迭代映射变换到新区间的一种迭代法。 Moore 在 1966 年对 1n= 的情形建立了区间 Newton 法，并且对 f 为有理函数情形证明了算法的收敛性以及具用平方阶的收敛速度， 同时还将算法应用于 1n 的情形。其后， ,Hansen Nickel Krawczyk ，以 及 Moore 等，对区间 Newton法又作了许多推广与改进，使区间迭代法从理论与实
3、践上更趋完善。特别，,Nickel Hansen对 1n= 的情形分别讨论了区间 Newton 法的全局收敛问题，这样对于单变量非线性函数方程的点 Newton 法所存在的弱点，对于区间 Newton 法而言已不成问题了。对于 1n 的情形， Hansen 全局算法的推广， Nickel 球形Newton 程序的建立，给非线性方程组 (10.23)的求解提供了全局收敛程序。 10.1 区间及其运算 对于给定的数 ,x xR ,若满足条件 x x ，则有界闭集合 , X xx x Rx x x= = 称为有界闭区间， () ( )/2mX midX x x=+称为区间的中点， ()WX x x=
4、称为区间的宽度， R 上所有有界闭区间的集合记为 ()I R 。 对于给定的区间 , , , ()X xx Y yy IR=，其四则运算定义为 , ,min( , , , ), max( , , , ), 1/ ,1/ ,0X YxyxyXY xyxyX Y xyxyxyxy xyxyxyxyXY xx y y Y+=+ += =nullnull对于 n维情形，定义 111222,nnnX xxX xxXX xx = MM其中 , (), 1,2, ,iiiX xx IRi n=L ，为 n维区间向量， n维区间向量的全体记为()nI R ，其代数运算与一维情形相似，只是通过它们的分量来定义。
5、 对于函数 :nf RR ，若存在区间值映射 :( ) ()nFIR IR 对任意 ,1,2,iix Xi n=L ，成立 11 1( , , , , ) ( , , )nn nFxx xx fx x=LL 则称 F 为函数 f 的区间扩展。它是一个以区间向量为变量，取值为区间的函数。当变量每个分量的区间长度为 0 时，即为原来的函数 f 。 设 :( ) (), , ( )nnFIR IRXY IR满足 X Y ,如果成立 () ()FX FY 则称区间值映射 F 具包含单调性。 10.2 Moore 的基本区间算法 设函数 ()f x 为给定在区间 ,Aab= 上的连续可微函数， X 为表
6、示包含 f 零点*x 的某区间， X A 。利用微分中值公式，对任意 y X ,成立 *() () ( ( )( ),0 1fx fy fy xyxy=+ 的情形，由 (10.10)得 (), 0(), 0, ,kkkkkkqNX p dqp= = Uk- 当c 时当时 其他情况（ 10.11） 2）对于()( ) 0kfmX 的情形，由 (10.10)得 (), 0(), 0, , ,kkkkkkqNX p dpq= =Uk 当c时-当- 其他情况（ 10.12） 其中 () ()() ()()( /()( /kkkkp mX fmX cqmX fmX d =（ 10.13） 容易看出()
7、()()kkXNXI 仍然是一个有限集合。但是，这个有限集合可以是一个有界闭区间，亦可以是两个不相交区间的联合，亦可能是一个空集，为以后讨论方便，我们记 (),kkkX ab= 公式 (10.30)(10.34)就是对于()0()kFX 情况下的 Hansen 算法的基本描述。由于问题解决得比较广泛， Hansen 算法比 Moore 的区间 Newton 法更复杂了。因为，如果(0)0(FX ，那么，从(0)X 到(1)X 就可能出现两个不相交区间(1) (1)12,X X 。往后，将区间 Newton 法分别应用于(1) (1)12,X X ，又可能变成 4 个互不相交的区间。如此继续下去
8、，可能会产生许多子区间。不过，实际上这些区间的个数是不会超过 f 在(0)X 中的实零点的个数的，因而子区间数总是有限的。当然，对于(0)0()FX 的情形，则与 Moore 的区间 Newton 法一样，而且对于这种情形的区间， Newton 算法的全局收敛性已由 Nickel 解决。 10.4 实非线性方程组的区间算法 将 10.2 的区间扩展到区间向量， 则可以得到非线性方程组的区间 Newton 算法，但 Newton 算法需要求一个区间矩阵的逆，计算量相当大。 1969 年 Krawczyk针对 Moore 的区间 Newton 程序在计算量方面的缺陷，提出了一种区间 Newton
9、算子的改进， 建立了不需要计算区间矩阵逆的 Krawczyk算子。 设 :nnDR R 在 D上连续可微，则对于任意 ,()x yXXID ， 的每一个分量 (1,2,)iin = L 成立 () () ( ( )( ) 1,2, ,Tiiiix yyxyxyi n=+ =L (10.14) 其中 (0,1)( 1,2, , )iin =L 。今设i 为i的具包含单调性的区间扩展。同时注意到 ()(1,2,)iy xy Xi n+=L ，于是有 () () ( )( ) ( 1,2, ,)Tii ix yXXyi n + =L 其向量形式为 () () ( )( )xy XXy + 其中 1(
10、)()()TTnXXX = M 它是 ()x 的具包含单调性的区间扩展，于是 () () ()( )X yXXy = + (10.15) 就是 ()x 的区间扩展。式 (10.14)常称为中值型区间扩展。 假定方程组 (10.1)中的映射 :nnf DR R在 D上连续可微，且 F为 f的具包含单调性的区间扩展，则对任意 x D ，定义迭代映射 () ()x xYfx = (10.16) 其中 Y 为任意 nn 阶非奇异矩阵。显然， 亦是 D上的连续可微映射，且其导数为 () ()x IYfx = (10.17) 同时，对于给定的区间向量 (), ()X ID x 的具包含单调性的区间扩展是
11、() ()X IYFX = (10.18) 现将 (10.15)、 (10.17)代入 (10.14)，则对任意 yX ，得到 ( , ) ( ) (1 ( )( )KyX y Yfy YFX X y= + (10.19) 这就是我们所要建立的 Krawczyk 算子。 若取 ()ymX= ，则 (10.19)成为 () () () ( ()( ()KX mX YfmX I YF X X mX= + (10.20) 或 1() () () ( () ()1,12KX mX YfmX I YF X WX= + 它表示了点迭代 ()y 与一个对称区间之和。 Krawczyk Moore 区间迭代法
12、是 Moore于 1977 年设计的。他将 Krawczyk 算子(, )KyX中的 ()mX 和 Y 取为 1 ( ( )YmFX= 这里将 Krawczyk 算子称为 Krawczyk 算子的 Moore形式，他构造的区间迭代法为： 首先，给定初始区间向量(0)X . 其次，构造区间迭代法 (1) () ()() () () () () () () ()()( ) ( ) ( ( ) ( ( )( ( )0,1,2,kk kkkkk kkkkXXKXKX mK Y fmX I Y F X X mXk+ = + =IL(10.21) 其中()kY 按以下规则选择 () 1() () ( 1)
13、 ( 1)(1)() ()() )() (,()kkkkkkkkYmFXYIYIYFXYIYFX = =k是 的一近似矩其他情形r(10.22) 定理 10.2 设 :nnf DR R连续可微， F为 f的具包含单调性的区间扩展，给定初始区间向量(0)()X ID ，且满足条件 (0) (0)()KX X (10.23) 和 (0) (0)()1IYFX= 0r (10.24) 则有以下结论成立： 1) 在(0)X 中方程组 (10.23)有解*X 2) 由算法 (10.2)确定的区间向量序列 ()kkNX是一个区间套序列，即对一切k 成立 (1) (),0,1,2,kkXXk+=L 且有 *()0kkx X=I3) 若方程组 (10.2)在(0)X 中有惟一解，算法 (10.21)所确定的序列 ()kkNX至少线性地收敛于这个惟一解。 进而可以证明，若数列 kkNr收敛于 0，则算法 (10.43)所产生的区间向量序列 ()kkNX具超线性收敛速度。
