《专题十 非线性方程的区间算法》由会员分享,可在线阅读,更多相关《专题十 非线性方程的区间算法(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具超线性收敛速度。