（计算数学专业论文）ham和hpm方法求解非线性方程组.pdf

摘要 随着现代科学技术的迅速发展，科学与工程计算的许多领域中所出现的非线性问题 越来越多，如何求解非线性方程组，这在非线性科学中有着重要意义。本文主要研究将 各种方法应用于不同的方程中，并对各种方法进行修改或得到新的方法，或与其他方法 相结合得到更为理想的迭代公式，分析新方法的收敛性和收敛速度。在以上理论研究基 础上，通过数值试验与其他方法进行数值比较。主要用到大型数值软件m a t l a b 。取得的 主要成果如下： ( 1 ) 在求解非线性方程组的历史中，n e w t o n 迭代法和它的变体是解非线性方程组的 经典方法，至今都是基本而重要的。重点分析了由n e n a du j e v i c 根据求积规则推导出了 新的迭代公式，考虑迭代中导数值的计算和方法的收敛速度使其应用受到限制，针对此 情况，通过采用s t e f f e n s e n j n 速法对迭代公式进行修正，推导出一类新的无导数的非线性 迭代方法，并通过数值例子表明新方法的有效性。 ( 2 ) 通过上述的本质修改，我们得到的迭代公式有效的减小了计算量，提高了收敛 速度，但同时使得适用范围较小。考虑到二分法具有良好的区间序列渐近收敛性以及大 范围收敛性质，将二分法与新方法的结合，得到了一类求解非线性方程的新算法。数值 试验表明新算法与n e w t o n 法相比更为有效。 ( 3 ) h p m 是一种解决非线性方程组解的新方法。首先讨论了h p m 方法的重要理论知 识，其次在大量国内外文献调研的基础上对h p m 及其修正进行分析研究，讨论了将h p m 应用于求解非线性代数方程组，得到了新了迭代公式。通过数值试验，表明该方法的有 效性。 关键词：非线性方程组，h o m o t o p yp e r t u r b a t i o nm e t h o d ，h o m o t o p ya n a l y s i sm e t h o d ， 迭代法，收敛性 a p p l i c a t i o n so fh a m a n dh p mt on o n l i n e a re q u a t i o n s d u a nm i n ( c o m p u t a t i o n a lm a t h e m a t i c s ) d i r e c t e db yp r o f l iw e i g u o a b s t r a c t w i t ht h ed e v e l o p m e n to fm o d e ms c i e n c ea n dt e c h n o l o g y , t h e r ea r em o r ea n dm o r e n o n l i n e a rp r o b l e m si nt h ef i e l d so fs c i e n c ea n de n g i n e e r i n gc a l c u l a t i o n t h i sp a p e rm a i n l y s t u d i e st h ea p p l i c a t i o no fm e t h o d st od i f f e r e n te q u a t i o n s w ed e d u c en e wf o r m u l a s b y m o d i f y i n gt h ef o r m u l a so rg e tn e wm e t h o d ，o rd e d u c ep e r f e c ti t e r a t i v ef o r m u l a s c o n v e r g e n c e a n dr a t eo fc o n v e r g e n c eo fn e wm e t h o d sa r ea n a l y z e d o nb a s i so ft h e o r e t i c a ls t u d i e s ，w e c o m p a r ew i t ho t h e rm e t h o d sb yn u m e r i c a le x p e r i m e n t s m a t l a bi su s e dm a i n l y m a jo r a c h i e v e m e n t sa r ef o l l o w i n g ： ( 1 ) i n t h eh i s t o r yt os o l v en o n l i n e a r e q u a t i o n s ，n e w t o ni t e r a t i v em e t h o da n di t s a n a m o r p h o s i sa r ec l a s s i c a lm e t h o d st os o l v en o n l i n e a re q u a t i o n sw h i c ha r ee l e m e n t a r ya n d i m p o r t a n tu n t i ln o w i ti si m p o r t a n tt oa n a l y z et h en e wi t e r a t i v ef o r m u l a sw h i c ha r ed e d u c e d i na c c o r d i n gt ot h eq u a d r a t u r er u l e s b yn e n a du j e v i c i nc o n s i d e r a t i o no fd e r i v a t i v e c o m p u t a t i o na n dm e t h o d sr a t eo fc o n v e r g e n c e ，w h i c hl i m i ta p p l i c a t i o n ，w em o d i f yt h e f o r m u l a sb ys t e f f e n s e na c c e l e r a t i o nm e t h o da n dd e d u c ean e wc l a s so fn o n l i n e a ri t e r a t i v e m e t h o d sw i t h o u td e r i v a t i v e s t h en u m e r i c a le x p e r i m e n t ss h o wt h a tn e wm e t h o d sw i t h o u t d e r i v a t i v ea r ev e r ye f f e c t i v e ( 2 ) t h o u g h te s s e n t i a lm o d i f i c a t i o na b o v e m e n t i o n e d ，i t e r a t i v ef o r m u l aw eg o tl o w c o m p l e x i t ya n di m p r o v et h er a t eo fc o n v e r g e n c e ，b u tr a n g eo fa p p l i c a t i o ni sl i m i t e d b i s e c t i o n m e t h o dp r o v e sn i c e a s y m p t o t i cq u a d r a t i cc o n v e r g e n c ep r o p e r t ya n dg l o b a lc o n v e r g e n c e p r o p e r t yo fi n t e r v a l sd i a m e t e r ss e q u e n c e c o m b i n i n gb i s e c t i o nm e t h o d ，w ed e d u c en e w f o r m u l a sa n dt h ea d v a n t a g ei ss h o w e db yn u m e r i c a le x p e r i m e n t s ( 3 ) h p mi san e wm e t h o dt os o l v en o n l i n e a re q u a t i o n s f i r s t l y , w ed i s c u s st h et h e o r e t i c a l k n o w l e d g eo fh p m s e c o n d l y , o nt h eb a s i so fr e s e a r c h ，s t u d yo nh p ma n di t sm o d i f i c a t i o n s ， s t u d yt h ea p p l i c a t i o no fh p mt on o n l i n e a re q u a t i o n sa n dd e d u c et h en e wi t e r a t i v ef o r m u l a s t h en u m e r i c a le x p e r i m e n t ss h o wt h ea d v a n t a g e so ft h ei m p r o v e dm o d e l k e yw o r d s ：n o n l i n e a re q u a t i o n ，h o m o t o p yp e r t u r b a t i o nm e t h o d ，h o m o t o p ya n a l y s i sm e t h o d ， i t e r a t i v em e t h o d ，c o n v e r g e n c e 关于学位论文的独创性声明 本人郑重声明：所呈交的论义是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致i , j l j l - ， 本论文不包含其它人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对 研究所做的任何贡献均已在论文中做出了明确的说明。 若有不实之处，本人愿意承担j i ：目关法律责任。 学位论文作者签名：陷。址 日期： 年月日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借 阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩 印或其它复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名： 鞋 缸 指导教师签名： 一 月 日 多月厂日 年 年 1 期 期 日 同 中国石油大学( 华东) 硕士学位论文 第一章前言 1 1 课题提出背景及其研究意义 随着科学技术的发展和电子计算机的广泛应用，科学与工程计算的许多领域中所出 现的非线性问题越来越多，关于各种非线性问题的可解性分析以及有效解法的研究引起 了人们的重视，各门交叉学科中的非线性问题已经逐渐成为科学研究的热点之一。非线 性问题作为数学科学的主要研究课题之一，不仅是现代科学技术发展的需要，而且也是 现代计算技术高速发展的必然结果。利用计算机解决非线性问题时，最终总是将其化为 有限维非线性问题，或称为非线性代数问题。因此，非线性代数问题的解法就成为现代 计算数学的重要研究课题，而非线性方程组解法则是其最基本的问题。而非线性方程和 非线性方程组的数值求解，则是这些非线性代数问题数值近似的基础和关键所在。 有关这一课题早在七十年代以前，在理论上和数值解法上都对它做了大量研究，但 是由于非线性方程组求解问题无论在理论上或解法上都不如线性方程组成熟和有效，因 此对非线性方程组解的存在性及寻找有效的数值方法均存在很多问题，需要进一步研究 与解决。例如，对非线性方程组是否有解，有多少解，理论上就没很好解决。在解法上， 除对极特殊的非线性方程组外，直接法几乎是不能使用的，而迭代法由于受初值选取的 限制，往往不能有效地求出方程的解，因此主要用迭代法来求解。在方程非奇异的情况 下，众多迭代法中有经典的二阶收敛的n e w t o n 迭代，三阶收敛的c h e b y s h e v 迭代、h a l l e y 迭代、超h a l l e y 迭代及其变形等。但是这些三阶收敛的方法大多使用了目标函数的二阶 导数，在计算过程中会消耗大量额计算量，因此只使用目标函数的低阶导数来构造高阶 收敛的方法是值得深入讨论的问题。因此，非线性方程的数值方法的研究依然是十分重 要的课题。 1 2 国内外研究现状 我们假设非线性方程组的一般形式是 其中f ( i = 1 ，2 ，疗) 为给定在n 维实欧氏空间r ”中开区域d 上的实值函数为讨论方便， o 0 | i = ) ) 矗 ， ， ， 恐 吃 一 西石石 ，lfl ，l，(【 第一章前言 ，c z ，= r 主：二：- ，x = r 耋1 ，。= 厂习 f ( x ) = 0 若存在x + d ，使f ( x + ) = 0 ，则x + 称为方程组( 1 1 ) 的解。 在非线性方程组解法的研究中，n e w t o n 法及其变体- n e 州o n 型方法是解非线性 方程组的一类重要方法，他在非线性方程组迭代解法的理论研究中占用十分重要的地 位。n e w t o n 法的显著优点是收敛速度快，其不足是在迭代的每一步均需计算j a c o b i 矩阵 并求解n e w t o n 方程。当j a c o b i 矩阵难以形成，或者当问题的规模较大时，n e w t o n 法的计 算代价就很昂贵。此外，不具有全局收敛性质则是n e w t o n 法的另一缺点。近二十年来， 针对n e w t o n 法每步迭代都要计算导数的不足，人们对n e w t o n 法提出了各种不同的改进 方式，由此n e w t o n 法派生出了大量的新算法，这些算法已有大量的理论研究及计算实践 所证明，包括割线法，离散n e w t o n 法，拟n e w t o n 法等。在离散n e w t o n 法的基础上经过 发展又得到了b r o w n 方法矛l j b r e n t 方法。其中b r e n t 方法是计算效率较高的算法之一，该算 法在解非线性方程组的数学库中已被广泛采用。 拟n e w t o n 法是六十年代发展起来的有效方法之一，其最大优点是拟n e w t o n 矩阵 可由简单的递推关系而得到，因此，它大大降低了n e w t o n 法的计算量。拟n e w t o n 法 是局部收敛的，而且在一定的条件下，其收敛速度可以是超线性的。为减少n e w t o n 法 计算量大的不足，d e m b o ，e i s e n s t a t 和s t e i h a u g 于1 9 8 2 年提出了求解非线性方程组的 不精确n e w t o n 法。不精确n e w t o n 法实质上是一类内外迭代算法，其外迭代为经典 n e w t o n 法，而其内迭代则可采用任何能够准确而有效地对n e w t o n 方程加以求解的线性 迭代法，这种内外迭代技术由于能够充分利用j a c o b i 矩阵的结构和稀疏性，因此可以大 大降低n e w t o n 法的计算代价。理论分析和实际应用均表明，不精确n e w t o n 法是求解 大规模稀疏非线性方程组的十分有效的方法。 对于局部收敛的迭代方法，即要求初始近似x o 与解x + 充分靠近，才能使迭代序列 ) 收敛于x + ，实际计算中要找到满足要求的迭代初值x o 往往很困难。为了达到具有大 范围收敛性的特点，随后又给出了延拓法，区间迭代法与单纯形算法等。延拓法，又称 中国石油大学( 华东) 硕士学位论文 为同伦法，它作为研究算子方程的理论工具可追溯到上一世纪。用延拓法解非线性方程 组主要是求足够好的迭代初始近似，以及得到大范围收敛性的方法，但由于在实际计算 时收敛定理条件较难检验，并且初值x o 通常是任意给定的，这就给计算增加了不少困难。 近年来与同伦延拓法密切相关的转向点与分歧点问题的研究很多，不但有理论上的成 果，还有不少数值方法和实际应用。】9 9 8 年，上海大学的何吉欢教授在文提出了一类 新的由同伦法和摄动技术相耦合的方法，称为同伦摄动方法。这种方法用于解决非线性 问题，它不仅适合于小参数，而且当大参数时也一致有效，由于方法的有效性，同伦摄 动方法得到了很多人的认可，很快得到推广和应用。 近些年对于非线性方程又提出了很多新的解法。例如u i e v i c l 2 】利用求积公式推导出 了新的迭代公式，并且证明了新方法的二阶收敛性；陈金海提出了若干求解非线性方程 的二阶收敛的指数迭代公式等。 第二章关于非线性方程的尤导数的迭代解法 第二章关于非线性方程的无导数的迭代解法 求解非线性方程组一般都要用迭代法。在求解非线性方程组的历史中，二阶收敛的 n e w t o n 迭代，三阶收敛的c h e b y s h e v 迭代、h a l l e y 迭代、超h a l l e y 迭代及其变形等，至今 都是基本而重要的。n e n a du j e v i c 在文中首次根据求积规则推导出了新的迭代公式， 随后不断对其进行了修正及应用，使方法不断改进。然而，这些方法也存在着一些缺点， 每次迭代中需要调用导数值，计算量较大，这使其应用受到限制。考虑到迭代中导数值 的计算和方法的收敛速度，可以采用单点割线法和双点割线法，a i t k e n 加速法和s t e f f e n s e n 加速法等。本章针对此情况讨论n e n a du j e v i c 提出的迭代方法的一种推广，推导出一 类新的无导数的非线性迭代方法，并通过数值例子表明新方法的有效性。 2 1 线性方法的概述 考虑数值求解非线性方程 厂( x ) = 0( 2 1 ) 其中实值函数f ( x ) 在实零点x 的某邻域u ( x ) 内连续可微且( x ) 0 。 n e w t o n 法是科学与工程数学计算中数值求解( 2 1 ) 的常用数值方法。虽然它一般至 少是二阶收敛的，但每次迭代中需要调用一次导数值，这使其应用受到限制。为回避 n e w t o n 迭代中导数值的计算，我们修改n e w t o n 法，用割线代替切线可得不带导数的单 点割线法和双点割线法，但它们不再是二阶收敛的，分别是线性收敛和超线性收敛的。 为了提高收敛速度，我们往往只好借助于迭代过程的加速收敛方法，如a i t k e n 加速法和 s t e f f e n s e n 加速法。不用计算导数的s t e f f e n s e n 迭代的几何意义实际上仍然是“线性化 思想，就是通过两点( ，厂( 毛) ) ，( 吒+ ( 吒) ，厂( + 厂( ) ) ) 的弦线与x 轴交点的横坐标 + 。作为( 2 1 ) 式的根x + 的新近似值。 近些年来，对于非线性方程的研究我们已经有很多不错的方法，例如文1 3 - 1 0 1 。可以 看出在这些方法中，很多方法是通过使用泰勒多项式或插值多项式近似函数最终获得 的。如果我们积分这些多项式，就可以得到相应的求积公式。在某种程度上数值积分得 到的结果表明，通常对于用求积公式得到的误差界要比用相应的近似多项式得到的误差 界要好。因此，我们考虑用求积公式来近似求解非线性方程的解。文1 2 1 根据这种考虑给 4 中国石油大学( 华东) 硕士学位论文 出了新的迭代公式： 铲”口器 2 颤们( z k - x k ，揣 ( 2 2 ) ( 2 3 ) 共f 1 0 口 1 ，又卜1 给出j 此迭代公瓦的收敛性让明，井且说明1 r 冥结果费优于n e w t o n 迭代的结果。 我们可以看出，迭代公式( 2 2 ) 和( 2 3 ) 应用时每迭代一次需要计算一个导数值，因此 为回避导数值的计算，5 f i r es t e f f e n s 加速收敛方法，用垡冬掣 盟代替导数，( x ) 。 ，ix 因此本文给出了无导数的迭代公式，并证明其收敛，最后给出数值例子。 2 2 新方法的构造及其收敛性分析 根据迭代公式( 2 2 ) 和( 2 3 ) ，将笪羔上筝掣代替导数，( x ) 得到一类不用导数 ，i x ) 的迭代公式： 厶= x k 一瓦弓高 p 4 ， 矗+ ，2 + 3 ( 气一砟乏揣 ( 2 - 5 ) 其中o 口 1 。下面证明此迭代法( 2 4 ) ( 2 - 5 ) 仍然是收敛的，且结果也优于n e w t o n 迭代 的结果。 条件2 - 1 ：假苗矿c 2 ( c ，d ) ，( 6 ) = o , b ( c ，d ) ，f 。( x ) o ，f ”( x ) o ，x ( c ，d ) 。定义： 矽( 口) = 口+ 3 ( x 一日) 鼎 ( 2 6 ) 其中x = a 翼i ，o 口 1 。易证： f ( a + ( 口) ) 一f ( 口) 。 ( 2 - 7 ) 南， 焉 第二章关于非线性方程的无导数的迭代解法 所以 lirax=limb(瓦)却一口而ljmf(a)f(a = 易 、 + 厂( 口) ) 一( 口) 厂( 6 ) 下面我们考虑导数缈( 日) 在点b 的一个小邻域内的情况。 由x - a = - a 而有： 荆= 1 + 3 ( ) 鼎 一3 口 塑 丛竺监丝2 二丝! 】二丝坚垡竺2 二丛兰幽 f ( a + ( 口) ) - f ( a ) 2 f ( a ) 一厂( x ) 】2 吼3 晓叫鼎 一3 口 f ( 口) 厂( 臼) f ( a ) f ( a + ( 口) ) - f ( a ) 2 f ( a ) - f ( x ) 其中 工：1 一口丛型堑必! 堑型型塑乓盥些里掣型坐丛盟型! 。 f ( a + ( 口) ) 一( 口) 。 ：1 口 三鱼2 ：! 尘 + 口：! 尘【：! 竺( 竺塑! ! ：! 竺! 二：( 竺塑 f ( a + ( 日) ) 一( 口) f ( a + ( 口) ) 一厂( 口) 2 又容易证明： l 洲i m 斋f ( a f ( a = 脚而揣2 1 ( 2 - 8 ) a 一6 + 厂( 口) ) 一) a a ! 堡! 堡塑二! 竺2 、。 l i m ：! 型竖! 竺! 1 2 2 ( ! ：( 竺! 二竺塑 。一a 【f ( a + ( 口) ) 一( 口) 】2 6 厂( 口) + ( 口) ) ( 1 + ( 口) ) 一f 7 ( 口) 丝# 缈】： ( 口) 。丝。 嘞 = 中国石油大学( 华东) 硕士学位论文 ：丛塑笔攀一】( 2 - 9 ) ( 6 ) 2 故由( 2 - 8 ) 和( 2 9 ) 得：1 i 田毛= 卜一2 a + 口= 1 一口。 所以 1 i m 型：1 i m 熊：1 一口 a - - * b ( 口)。6 ( 口) 捌l i m2 ( 口f ) ( 一a ) 而= 黝丽1 = 而1 a 一62 ( 口) 一( z ) 。_ + 6 ， 一( x ) 1 + 口 一f ( a ) 所以由( 2 8 ) ( 2 一】1 ) 得：l i 田( 口) ：l 三生，且当0 口1 时， r - 。o 1 十口 l - 一惫f 1 0 ( 2 1 0 ) ( 2 - 11 ) 通过上面的假设，我们可以得出存在一个b 的邻域u ( b ) = ( b 一占，b + 占) ，使得： 矽7 ( 口) f 1 v a u ( 6 ) 不妨设j 缈( x ) 一缈( y ) i = 妒( f ) ( x y ) ，f ( x ，y ) 且x ，y u ( 6 ) ，我们可以得到： i 缈( x ) 一缈( y ) f p z - y f 其中0 1 ，x ，y u ( b ) 。因此，妒是一个压缩映像。 设蛾= 【6 一三，6 + 争。又有( 2 7 ) ( 2 11 ) 可得妒( 6 ) = 6 。所以帆或，有 l 妒( x ) 一6 l = l 妒( z ) 一缈( 6 ) l i x 一6 l 从而伊( d o ) cd o 。故存在唯一的不动点b ，有够( b ) = b 。即 缈( b ) = b 一3 a 盟 ：舍 厂( b + ( b ) ) 一( b ) 2 f ( b ) - f ( x ) 其中曼：舍一口_ 。k 。从而可得( 会) ：o 。既而容易得到舍：6 。 ( b + f ( b ) ) - f ( b ) 现在证明以下结论成立。 定理2 - 1 设f c 2 ( c ，d ) ，( 6 ) = 0 ，b ( c ，d ) ，7 ( z ) 0 ，f 4 ( x ) o x ( c ，d ) ，a u ( a ) ，其中 u ( b ) 同上面定义，若取= a ，缈定义为式( 2 6 ) ，则序列吒+ ，= 呼o ( x k + 。) 收敛到6 。 第二章关于非线性方程的无导数的迭代解法 或者 证明：我们考虑参数口的取值范围。假设f ( x ) o ，x o ，f ( x ) 0 ，x u ( 6 ) ( 1 ) 首先，考虑满足b b ，即 整理得： 一3 口 口+ 3 c x 露，鼎6 2 ( 口)f ( a ) f ( a + ( a ) ) 一厂( 口) 2 f ( a ) 一f ( x ) 6 一露 勘辔而高丽砸1b f ( af ( a 引 一口 + ( 口) ) 一 ) ，) 一( 苎2 ( 口) 根据l i r a f ：( a - - - - - 2 ) ：1 i m 掣：一f ，( 6 ) 及( 2 7 ) 和( 2 1o ) 式可得： o dd aa - + b 一1 l 。i r n 。- 3 af 二( a ) 而丽f ( a ) 砸1 b f ( a 2 嘲俐高击1 = 羔1 a + 6 一日+ ( 口) ) 一厂( 口) 一型。、7 ( 6 ) + 口+ 口 ( a ) 所以有三生1 ，即d 一1 。 l - - i - 口 2 ( 2 ) 其次，满足条件： 扣m 3 ( 卜口) 鼎m 七一需】 ( 2 - 1 2 ) 即说明对于精确解6 ，b 是比n e w t o n 迭代结果更好的近似解。由( 2 1 2 ) 整理得： 一3 ( x - a ) 丛竺2 盟 2 f ( a ) 一f ( x ) f 0 ) 营3 口 2 ( 口)f ( a ) f ( a + 厂( 口) ) 一( 口) 2 f ( a ) - f ( x ) 盟 f ( 口) 3 口 ! 型兰竺!z ! 堡2 1 f ( a - t - 厂( 口) ) 一f ( a ) 2 f ( a ) 一( x ) 两边取极限，利用( 2 8 ) 和( 2 1 1 ) 式得：生1 ，或口i 1 。由上面的结果，我们可以得 l + 口z 出，当口= 三时，有下式成立 中国石油大学( 华东) 硕上学位论文 日 o ，x 6 ，f ( x ) 0 ，聊 0 ，k = 0 ； ( b ) 计算z k = x k - - 瓦可f 丽2 ( x k ) ； 确= 叫z k - - x k ) 热； ( c ) 若k m ，停机，输出迭代失败信息； ( d ) 若i 厂( 坼+ 。) i ol ( ) | + ，停机，输出近似解x = + l ，否则 ( e ) 令k = k + l ，转( b ) 。 2 3 数值例子 问题1 。厂( z ) ：一1 1 问题2f ( x 1 = e 1 一”一1 问题3 厂( x ) ：一1 一s i n x + 1 问题4f ( x 1 = e 。一x 一1 问题5f ( x 1 = 1 2 s i nx 数值例子中我们给定f ，= 乇= 1 0 e - 1 0 ，口= 0 5 ，聊= 刀= 1 0 0 0 0 ，求解( x ) = 0 的根。 求解结果由表2 1 给出。 9 第- 二章关于非线性方程的无导数的迭代解法 表2 - 1 新方法与n e w t o n 法的对比 t a b l e2 - 1t h en u m e r i c a lc o m p a r i s o no fn e wm e t h o d a n dn e w t o nm e t h o d 新算法 n e w t o n 法 2 2 7 5 9 9 5 e 15 3 5 5 2 7 e 15 d i v e r g e n t 14 4 4 0 9 e 1 6 3 - 1 38- 0 6 2 9 4 54 4 4 0 9 e 一162 5 0 6 2 9 4 52 2 2 0 4 e 16 42 2 41 7 6 5 8 e 0 0 51 5 5 9 0 e 0 1 03 2 4 7 1 8 3 e 一0 0 90 51 54 5 2 3 5 9 e 一0 0 12 7 7 5 5 e 一0 1 4n oc o n v e r g e n t t o ，万、 1 n 【o i 其中d i v e r g e n t 表示相应算法在最大迭代步数之内迭代过程中断或者误差精度 f ( x n ) i oj ( ) i + 。 1 0 中国石油大学( 华东) 硕士学位论文 第三章大范围收敛的不带导数的迭代法 众所周知，二分法具有良好的区问序列渐进稳定收敛性1 1 1 , 1 2 以及大范围收敛性质 1 1 3 , 1 4 1 ，但二分法的收敛速度仅仅是线性的。在第二章中，我们得到的新方法具有不错的 收敛性，但由于近似代替的影响，使新方法适用范围较小。本章通过二分法与新方法的 结合，我们得到了一类求解非线性方程的新算法，新算法具有良好的点序列 ) 和区间 半径序列 ( 玩- a o z ，的渐进收敛性。数值试验表明新算法与n e w t o n 法相比更为有效。 3 1 导数在迭代中的应用与不足 对于非线性性方程( 2 - 1 ) ，此处我们考虑f ( x ) 满足李氏条件，且f ( a ) 0 ，f ( b ) 0 。 在第一章中，我们讨论了由求积公式推导出的新的迭代公式( 2 4 ) ( 2 5 ) ，并证得当口：当 时此迭代结果比n e w t o n 迭代结果要好，且无导数运算。 注意到只有当厂( x ) 非常小时，差商竖冬掣才是导数，( z ) 好的近似，这 ，x 必然使得迭代公式( 2 4 ) ( 2 5 ) 缺少数值稳定的保证，同时限制公式( 2 4 ) ( 2 - 5 ) 的收敛范围及 其适用范围。针对此情况，在本章中我们将讨论避免导数的具有高阶收敛性的求解非线 性方程的算法。我们将迭代公式( 2 4 ) ( 2 5 ) 与二分法有机的结合1 1 4 】，构造新的求解非线性 方程的算法。新算法即保持t - 阶收敛性，同时又具有良好的区间半径序列渐近稳定性 与大范围收敛性质。 3 2 新算法的构造及收敛性分析 上章中已经证明了公式( 2 4 ) ( 2 5 ) 的收敛性，但并不像二分法具有良好的区间半径序 列 ( 玩一) ) ：，的渐近稳定性质的收敛性，这使得我们考虑下列一类带步长的迭代格 式： 铲矿口瓦毒舞 p - ， 第三章人范围收敛的不带导数的迭代法 = 叫( z k - - x k ) 揣 ( 3 - 2 ) 其中o 口 0 。 下面证明此迭代法( 3 1 ) ( 3 2 ) 是收敛的，且结果也优于n e w t o n 迭代的结果。 条件3 - 1 ： 假谚扩c 2 ( c ，d ) ，f ( c ) f ( d ) o ，f ( b ) = o ，b ( c ，d ) ，f ( z ) o ，f ”( z ) o ，x ( c ，d ) 妒( 口) = 日+ 3 ( x 一日) 揣 其中x ：日一口嬖，o 口 o ( 3 - 3 ) f ( a + 应厂( 日) ) 一厂( 以) 易证得： 1 i m b煞：去 ( 3 4 ) f ( a + 悬厂( 口) ) 一( 口) f 7 ( 6 ) 、7 所以熙x = 姗( 口一口而考淼，劬一口号l i m f 矿( a ) = 6 下面我们考虑导数妒7 ( 口) 在点b 的一个小邻域内的情况。 p7(口)2，+3(毛一，)鼎+3(x一口)二竺2e!蔓竺上二乏号宅毛手兰；鼍萎虽!幽 x ：1 一口兰笙! 竺逆：! 型f 丛! 笙! ! 塑二丛! 塑二笙：l 竺丝! 氅笙f 竺丛! 笙堑! 二：! 竺塑 。 f ( a + 忍厂( 口) ) 一( 口) 】2 7 ( 口+ i ! 厂( 口) ) ( 1 + 忍，r ( 口) 一( 口) r f ( a + 矽( 口) ) - f ( a ) 1 2 o 面：两 1 l i m 八日+ f ( 加a ) f ) ) ( 一a ) 而= 脚而考= 1 a - a 。( 口+ ( 口) ) 一( 口)a a ( 口( 口) ) 一( 口) 脚等篙黼掣 h f ( a ) 。 厂( 口) 1 办 ( 3 5 ) 三：丝塑笺攀一1 ( 3 - 6 ) h h f ( b 、2 | 盟厂一”力一篇一八 中国石油大学( 华东) 硕士学位论文 由( 3 - 5 ) ( 3 - 6 ) 式得：l 。i 。m 6t 2 1 2 0 r + c r i 一口 所以 j i m 型：l i m 丛：卜口 。r + 6 ( 日) o 6 ( 日) l 枷i m2 厂( 口f ) ( 一a ) 而= 黝厕1 = 而1。- + 62 ( 口) 一( x ) 。_ + 6 ，) 一( x ) 1 + 口 一f ( a ) 邮5 ) - ( 3 - 8 ) 式豫l i mc o 十羔。且当o a l 时，有f 1 一刊 1 。 通过上面的假设，我们可以得出存在一个b 的邻域u ( b ) ，使得 j 缈( 口) j 1 ， v a ( 6 ) 设j 伊( x ) 一妒( y ) j = 缈7 ( 孝) ( x 一少) ，f ( x ，y ) 且x ，y u ( 6 ) 我们可以得到：j c o ( x ) 一( 少) j p l x y i ，其中0 1 ，x ，y u ( 6 ) o 因此，c o 是一个压缩映像。故存在唯一的不动点合，有汐( 舍) ：舍。即 c o ( b ) = b 一3 a 2 ( b )f ( b ) ( b + ( b ) ) 一( b ) 2 f ( b ) 一( x ) 其中i ：舍一口k ( b + 厂( b ) ) - f ( b ) = b ( 3 7 ) ( 3 - 8 ) 可得厂( b ) = 0 。既而得到b = b 。 证明以下结论成立。 定理3 - 1 设f c 2 ( c ，d ) ，f ( b ) = 0 ，b ( c ，d ) ，f ( x ) o ，f ”( x ) o x ( c ，d ) ，a u ( b ) ，其中 u ( b ) 同上面定义。若取= a ，缈定义为式( 3 3 ) ，则序列+ ，= c o ( x k 。) 收敛到b 。 证明：我们考虑参数口的取值范围，假i f l 芒f ( x ) 0 ，x o ，f ”( z ) o ，x u ( b ) 。 ( 1 ) 首先，考虑满足占6 ，即 口+ 3 。一口) 鼎6 或者一3 a h f 2 ( a )0 ) f ( a + 矽( 口) ) 一f ( a ) 2 f ( a ) 一厂( z ) s6 一口 第三章 大范围收敛的不带导数的迭代法 整理得： 一3 口而f ( a ) 而而h f 丽( a ) 而= 1 匝1 6 一口厂( a + j i ! ，r ( 口) ) 一( 口) ， ( x ) ( 口) 根扼j i 翼盟：l i m 掣：f ，( 6 ) 及( 3 4 ) ( 3 7 ) 式可得： 。- + 6d a a - - - b j l 洲i m - 3 c ef一(a)b a 。f ( a - i - 壶珈删志击1 = 篑1 a 一+ 6 一 矽( 口) ) 一( 口) ，( x )。、7 厂( 6 ) + c z + 口 厂( 口) 所以有旦1 ，即口一i i + 口 2 ( 2 ) 其次满足条件小( 针3 卜口) 鼎) l 或口虿1 由( 3 - 9 ) ( 3 1 1 ) 结果我们可以得出，当口= 去时，有下式成立。 1 口 口一= 鱼堕占6 厂( 口) ( 3 9 ) ( 3 一1 0 ) ( 3 1 1 ) 事实上，在更多情况下我们都可有a a - f 厂，( a - - - - 2 ) - ) 占6 成立。 ，f 口l 因此，迭代式( 3 3 ) 要优于n e w t o n 迭代，且不存在导数运算。 相同的方法，我们可以考虑其他可能得情况。 为了获得具有区间半径序硼允一僦- 的渐近收敛性，在( 3 - 3 ) 中置吃2 碉b - a ， 我们可得如公式： 籍， 一 中国石油大学( 华东) 硕士学位论文 。( 统一) j ( ) j 铲矿口才事词 _ = 吃或，7 = o ，1 ，2 ， = z n - - x n ) 揣 ( 3 1 2 ) 结合迭代公式( 3 1 2 ) 与二分法，可以构造以下新的算法： 算法n a ： 惰铲半。 2 计算：( 吼) ，若f ( q 。) = 0 ，则停。 3 若s ig n f ( q 。) ) = s ig 刀 ( ) ) ，则 瓦，瓦 = 【吼，玩】；否则 瓦，瓦 = ，吼】a 4 置 q 巩】+ 3 ( 乙训揣 ( 吃一) l ( ) l zn = x n 川可瓦芮 5 如果f 瓦，瓦 ， 则若厂( ) ( q ) 0 ，那么 a n 小钆+ l 】= 瓦，c o 】， 否则 h ，吮+ 。】= h ，瓦 ， 矗+ 1 2 q o 6 如果g 瓦，瓦 ，那么【小包+ ，】= 瓦，瓦 。 7 若f ( + 。) i q 或包+ l - a n + 。 岛，则停止并输出k ，否则，7 = ”十1 ，返回步骤1 。 在算法中，q ，s ，为预先给定的误差精度。 注1 算法n a 或者得到所要的解，或者得到一个渐近缩小的含根区间序列 【，吃】 ， 在算法中，若不采用步骤4 ，则不进行加速计算，此时对应二分法的结果；若加 速计算成功，则需要比二分法多调用函数计算过程，但获得比二分法更快的收敛 速度，因此算法n a 的最差结果就是二分法的结果。 注2 由于算法n a 采用了二分法的策略，因此算法n a 扩大了迭代公式( 3 - 1 ) ( 3 2 ) 的收 敛范围及适用范围。 第三章大范围收敛的不带导数的迭代法 有算法的执行过程知，我们可得到迭代序列 吒) 和区问半径序列 ( 既一) ) ：，。 定理3 2 设函数f ( x ) 满足条件3 1 的假设条件，则算法n a 或者在有限步内得到 方程( x ) = 0 的根，或者产生的区间半径序列 ( 瓯一) ) ：。收敛于0 。 因为二分法的收敛性是明显的，故定理的证明也是显然的。 下面我们给出算法n a 的收敛性证明。 定理3 3 设函数f ( x ) 满足条件3 1 的假设条件，若算法n a 不能在有限步内得到 方程( x ) = 0 的精确解而中止，则算法n a 所得的序列 矗) 渐进平方收敛于x ，且算法 产生的区间半径序列 ( 玩一) ) ：，q - 平方收敛1 0 1 于零，即存在一个常数c ，使得 玩+ 】一+ 】c