（计算数学专业论文）求解非线性方程组的若干迭代算法之研究.pdf

摘要 本文主要研究b a n a c h 空间内求解非线性方程组f ( x ) = o 的理论分析问题， 特别是对n e w t o n 法，不精确n e w t o n 法( i n e x a c tn e w t o nm e t h o d ) ，n e w t o n l i k e 方 法的局部收敛性和半局部收敛性进行了详细的讨论，并给出新的结果。 n e w t o n 法 z 惫+ 1 = x k 一厂7 ( z 詹) 一1 f ( x k ) 是用来求解非线性方程组常用的办法。因为在初始近似足够好的情形 下，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 法的半局部收 敛定理，特别是m y s o v s k i i 型定理和k a n t o r o v i c h 型定理的发展；以及n e w t o n 法 的全局收敛性定理等。其中，k a n t o r o v i c h 定理以其典型的条件，确切的结果 成为研究n e w t o n 法半局部收敛性的典范。在对其条件结论的种种改进发展 中，w a n g ( 1 3 ) 中给出的n e w t o n 法的半局部收敛性定理有很强的概括性，它 将k a n t o r o v i c h 型条件和s m a l e 型条件统一起来。这里我们给出这个结果新的 应用，可以推出a r g y r o s ( 1 4 ) 中给出的含t 厂的m 阶导数信息的半局部收敛性定 理( 即定理2 1 3 ) ，并对其结果进行改进。 定理0 1 若，满足_ a r g y r o s ( 1 4 ) 定理的条件： ( 1 ) i | ，( z o ) - 1 f ( x o ) i i p ， ( 2 ) l i f 7 ( z o ) _ 1 厂( ) ( z o ) | | 啦，i = 2 ，m ， ( 3 ) l f 7 ( z o ) 一1i f ( m ( z ) 一，( m ( z o ) 川o ! m + li i z x o ( 4 ) p 2 ( s ) 0 ，这勤z ( r ) 定义如下： v z d o ， p 2 。意南t m + l m r n ：r m + + 矿o 。2 _ 2 叫 这里s 是硝( r ) 的一个根。 j j j z , , f 满足w a n g ( 1 3 ) 定理的条件： 浙江大学博士学位论文 ( i ) 对任意的x s ( x o ，6 ) 和z 7 s ( x ，6 一p ( z ) ) 有 ，p ( 互歹) i i f 7 ( z o ) 一1 ( 厂7x 7 ) 一厂7 ( z ) ) | l l ( 乱) d u j p ( o ) ( i i ) 令如满足片。l ( u ) d u = li m b = o l ( u ) u d u 。假设 p = i i f 7 ( z o ) _ 1 f ( x o ) l i b ( i i i ) 1 + 6 ，这里亡+ 是 ( 亡) 较小的正根， h ( t ) ：= p t + l ( 札) ( 亡一u ) d u ，0 亡r t ，0 由于n e w t o n 法每步都需要解一个线性方程组厂7 ( x k ) a k = 一f ( x k ) ( 通常称 为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 ( 5 9 ) 提 出求n e w t o n 方程组的近似解( 例如用迭代法求解该方程组) ，即 f 7 ( x k ) a k + f ( x k ) = r k ， 称之为不精确n e w t o n 法( i n e x a c tn e w t o nm e t h o d ) 。我们在介绍了该方法已有的 局部收敛性以及半局部收敛性结果后，给出。厂7 在满足弱条件下不精确n e w t o n 法 的k a n t o r o v i c h 型收敛性定理，并在余项弦三0 的情况下得到关于n e w t o n 法的著 名的半局部收敛性定理。 定理o 2 假设。厂：dcx 叫y 在s ( x o ，6 ) cd 上f r 6 c h e t 可微，x 0 d 为 给定的初始近似且厂7 ( z o ) - 1 存在。令l ( u ) 是 o ，卅上正的非降函数，p ( x ) = i i x x o i l ，p ( k - 7 ) = p ( x ) + i i z 7 一x l i 6 。假定f 7 ( 黝) _ 1 厂7 满足关于l 平均的内切球中 一凸, l i p s c h i t z 条件，即 厂7x o ) _ 1 ( 厂7 ( z ) 一厂7 ( z ，) ) | i f p ( x x 7 ) d p ( x ) l ( u ) d u ，v x s ( x o ，6 ) ，v x 7 s ( x ，6 一p ( z ) ) 对0 伽 1 2 以及饥 2 伽，余项满足 i i ，7 ( z o ) - 1 r k i 辄| | 知i i ， k = 0 ，1 ， 假定s o b 且 ( 1 - a 明k ) 一半吼厂l ( p k + u ) 砒 i v 摘要 这里盯庇：= a k ( 1 一r k a k ) ，魄：= o k + 1 仃七。 以及 瓦面万c 可丢两，( 5 0 6 ) ， o l ( u ) d u = 1 2 7 0 ，b = 。u l ( u ) d u ( 1 一伽) ，亡；是咖( 亡) 的最小正 根， 似小= 击。( 亡一u ) 狮) d u 一。1 1 - i 2 r i o + s o 那么，不精确n e w t o n 序列 z 七) ( 后0 ) 保留在颐碉内且收敛于厂( z ) = o 的一 个根x 4 。 在求解n e w t o n 方程组时，有时，7x 七) 的计算较为困难，为了降低计算代价， 我们通常用可逆算子a ( x k ) 来逼近它，这就是n e w t o n l i k e 方法 z 七+ 1 = z 知一a ( x 角) 一1 f ( x k ) 我们对n e w t o n l i k e 方法的局部收敛行为和半局部收敛性行为进行讨论，给出弱 条件下n e w t o n l i k e 的半局部收敛性定理，并给出相应的推论。 定理o 3令厂：dcx y 在s ( z o ，r ) cd 上n 6 c h e t 可微，a ( z ) 是厂7 ( z ) 的 一个近似。假定存在初始近似z o s ( x o ，r o ) ( 其中伯 0 ，r 】) 使得a ( 黝) 非奇异， 对任恿x s ( x o ，r ) 及任意z 7 s ( x ，r p ( z ) ) 满足 i i a ( x o ) _ 1 ( 厂7 ( z ) 一厂7x ，) ) i i l ( u ) d u f p ( x x 7 ) j p ( x ) 假设下列条件成立：( i ) 存在非负常数s o ，q ，p 以及o t t 0 1 ，使得下面关系式 成立： i i a ( x o ) f ( z o ) i i 8 0 ， i i a ( x o ) 一1 ( 厂7x ) 一a ( z ) ) i i u o + p l ( u ) d u ， 厂p ( z ) ，0 以及 ， p ( z ) i i a ( x o ) 一1 a ( z ) 一i i i 及l ( u ) d u ，v z s ( x o ，r o ) ，0 ( i i ) 对某个a m a x 1 ，q + p ) ，下面式子均成立： z 加洲u = ( 1 - u o 伽 浙江大学博士学位论文 s 。r 。( 1 - u o ) 一n f o r 。l ( u ( r - u ) d u ( i i i ) s ( x o ，t + ) cs ( x o ，r 0 ) ，这里亡+ 是( 亡) 的最小正根，砂( 亡) 定义如下： ( 亡) ：= n 0 ( 亡一乱) l ( 钆) d u 一( 1 一乱。) 亡+ s 。 那么，n e w t o n l i k e ) 事歹l j x k ( k o ) 保留在两丽内，并收敛t f ( x ) = o 的一个 解z + 。 关键词：b a n a c h 空间，非线性方程组，n e w t o n 法，不精确n e w t o n 法，n e w t o n - l i k e 方法，弱l i p s c h i t z 条件，半局部收敛性 a b s t r a c t t h i sd i s s e r t a t i o nm a i n l ys t u d yt h et h e o r e t i ca n a l y s i so fs o l v i n gn o n l i n e a r e q u a t i o n sf ( x ) = 0i nb a n a c hs p a c e ，e s p e c i a l l yo nt h el o c a la n ds e m i - l o c a lc o n v e r g e n c eo fn e w t o n sm e t h o d ，i n e x a c tn e w t o nm e t h o da n dn e w t o n - l i k em e t h o d n e w t o n sm e t h o d x k + 1 = z 七一厂7 ( z 惫) 一1 ，( z 尼) i st h eu s u a lm e t h o df o rs o l v i n gn o n l i n e a re q u a t i o n s g i v e nas u f f i c i e n t l yg o o d i n i t i a lg u e s sx 0 ，n e w t o n sm e t h o di s c o n v e r g e n tt ot h er o o to ft h ee q u a t i o n s q u i c k l y m o r e o v e r ，t h ec o m p u t a t i o no fe v e r ys t e po n l yh a sr e l a t i o nt ot h ep r e v i o u s s t e p ，s ot h ee r r o ri s n tp r o g e n i t i v ea n ds e l g c o r r e c t i v e h e n c en e w t o n sm e t h o d i sa ni m p o r t a n tm e t h o di nb o t ht h e o r e ma n da p p l i c a t i o n ，a n di sp o p u l a rw i t h t h en u m e r i c a lr e s e a r c h e r s s i n c en e w t o n sm e t h o dw a sp r o p o s e d ，t h e r eh a sb e e n ag r e a tm a n yt h e o r e t i cp r o d u c t i o n ，m a i n l yc o n c e r n i n gt h el o c a lc o n v e r g e n c e ， e s p e c i a l l yt h es i z eo ft h ec o n v e r g e n tb a l la n dt h eu n i q u eb a l l ；t h es e m i - l o c a l c o n v e r g e n c e ，e s p e c i a l l yt h em y s o v s k i it y p et h e o r e ma n dt h ek a n t o r o v i c ht y p e t h e o r e m ；a sw e l la st h eg l o b a lc o n v e r g e n c e k a n t o r o v i c ht h e o r e mi sab e a u t i f u l a n dp o w e r f u ls e m i l o c a lc o n v e r g e n c et h e o r e ma n da t t r a c t ss t u d i e r st oi m p r o v e a n dd e v e l o pi t sc o n d i t i o na n dc o n c l u s i o n w a n g ( 1 3 ) a l s oi n t r o d u c e sas e m i l o c a lc o n v e r g e n c eo fn e w t o n sm e t h o d ，w h i c hi ss or e c a p i t u l a t i v ea n de l e g a n t t h a tc o m b i n e sk a n t o r o v i c ht y p ec o n d i t i o nw i t hs m a l et y p ec o n d i t i o n h e r ew e g i v ean e wa p p l i c a t i o na n ds h o wt h a ti tc a nc o n c l u d ea n di m p r o v et h er e s u l ti n a r g y r o s ( 1 4 ) i ti ss t a t e da st h ef o l l o w i n gt h e o r e m t h e o r e m0 1i ffs a t i s f i e st h ef o l l o w i n gc o n d i t i o n s ，w h i c ha r ep r o p o s e d b ya r g y r o si n ( 1 4 ) ： ( 1 ) l l f 7 ( z o ) f ( x o ) | j ， ( 2 ) l l f 7x o ) - 1 厂( ( 加) | | 叱，i = 2 ，m ， ( 3 ) l l f 7 ( z o ) 一1 i f ( m ) ( z ) 一，( m ) ( z o ) 川o z r n + l i l z x o | i 比d o ， 浙江大学博士学位论文 ( 4 ) p 2 ( s ) 0 ， w h e r e p 2 ( r ) i sd e f i n e db y ： p 2 ( r ) =高南r m + 1 + 丽o l m ，+ + r o l 2 _ 2 叫m a n dsi sar o o to f 癌( r ) t h e nfs a t i s f i e st h ec o n d i t i o n si nw a n g ( 1 3 ) ： ( i ) f o rv z s ( x o ，5 ) a n dv x 7 s ( x ，5 一p ( z ) ) ，t h e r ei s ，x o ) 一1 ( 厂7x 7 ) 一，7 ( z ) ) | | l(乱)dufp(zx 7 ) j p ( x ) ( i i ) l e t5 0b es u c ht h a t 舻三( u ) d u = 1a n db =o l ( u ) u d u a s s u m e p = 伊( z o ) f ( x o ) | | b ( i i i ) t + 5 ，w h e r et + i st h el e a s tp o s i t i v er o o to f 允( 亡) ，a n d ( 亡) ：= p 一亡+ 9 t l ( u ) ( 亡一u ) 砒，。亡兄 s i n c ew eh a v et os o l v eal i n e a re q u a t i o n sf 7 ( x k ) a k = - ( z k ) ( o f t e nc a l l e d n e w t o ne q u a t i o n s ) e v e r ys t e p ，o n c et h en u m b e ro ft h eu n k n o w n si sg r e a t ，i tw i l l t a k eu sh i g hc o s ti ns o l v i n gi tb yad i r e c tm e t h o ds u c ha se l i m i n a t i o nm e t h o d f o r t h i sr e a s o n ，d e m b o - e i s e n s t a t s t e i h a u g ( 5 9 】) i n t r o d u c ei n e x a c tn e w t o nm e t h o d ， i e | ( x k ) a k + ( x k 、= r k ， w h i c hc o m p u t e sa na p p r o x i m a t es o l u t i o nt ot h en e w t o ne q u a t i o n s w en o to n l y i n t r o d u c es o m er e l a t e dl o c a la n ds e m i l o c a lc o n v e r g e n c er e s u l t sp r o p o s e db ym a n y r e s e a r c h e r s lb u ta l s og i v ean e ws e m i - l o c a lc o n v e r g e n c et h e o r e mw h e n | s a t i s f i e s s o m ew e a kl i p s c h i t zc o n d i t i o n a ss p e c i a lc a s e so fo u rm a i nr e s u l tw er e - o b t a i n s o m ew e l l - k n o w nc o n v e r g e n c et h e o r e m sf o rn e w t o nm e t h o d s 定理0 2l e tf ：dcx yb ef r 6 c h e td i f f e r e n t i a b l eo ns ( x o ，5 ) cd s u p p o s ex 0 di sag i v e ni n i t i a lg u e s ss u c ht h a t ，7x o ) e x i s t s l e tl ( u ) b ea p o s i t i v en o n d e c r e a s i n gf u n c t i o ni n 0 ，司，p ( x ) = i i x x o i i ，p ( i - 2 ) = p ( x ) + i i z 7 一 a b s t r a c t xi 5 a s s u m e 厂7 ( z o ) 1 ，7s a t i s f yt h ec e n t e rl i p s c h i t zc o n d i t i o ni nt h ei n s c r i b e d s p h e r ew i t ht h ea v e r a g eo fl ，i e ，7 ( z o ) 一1 ( 厂7 ( z ) 一厂7 ( z 7 ) ) l i l(乱)du，vzs(xfp(xx o ， 7 ) j p ( x ) 6 ) ，比7 s ( x ，6 一p ( z ) ) f o r0 伽 1 2a n d 啦 2 伽，t h er e s i d u a l s u c ht h a t s u p p o s e8 0 ba n d 厂7 ( z o ) 一1 r 七i i 叼i | 七| | ，k = 0 ，1 ， ( 1 一盯南吼) 1 1 k a k ? 7 k + l l k盯凫f o s 。l ( p k + u ) d 钆， w h e r eo k ：= a k ( 1 一? _ 7 k o l k ) a n d 地：= o k + i a k a sw e l la s s ( x o ，亡6 ) cs ( x o ，晶) ， w h e r e5 氇i sd e f i n e db y 意l ( u ) d u = 1 2 r o 1 e a s tp o s i t i v er o o to f 如( 亡) ，a n d o ( z ) ：= 1 一伽 ( 如 6 ) ， b=o u l ( u ) d u ( 1 一伽) ， 。( 亡一) m ) d u 一亡r 1 - i 2 叩0 + s 。 亡；i st h e t h e n ，i n e x a c tn e w t o ns e q u e n c e z 七) ( 庇0 ) r e m a i n si ns ( x o ，) a n dc o n v e r g e n t t oas o l u t i o nx + o ff ( x 1 = 0 w h e nw es o l v et h en e w t o ne q u a t i o n s ，t h ec a l c u l a t i o no ff 7 ( x k ) i ss o m e t i m e s d i f f i c u l ta n dw i t hh i g hc o s t f o ri m p r o v i n gt h ec o m p u t i n ge f f i c i e n c y , w eo f t e nu s e n o n s i n g u l a ro p e r a t o ra ( x k ) t oa p p r o x i m a t ef 7 ( z 七) t h a ti sn e w t o n - l i k em e t h o d ， i e x k + l = x k a ( x k ) - 1 厂( z ) w ed i s c u s si t sl o c a la n ds e m i - l o c a lc o n v e r g e n c ea n dg i v ean e ws e m i - l o c a lc o n v e r g e n c et h e o r e md e r i v e df r o mi n e x a c tn e w t o nm e t h o d 定理0 3l e t 厂：dcx 叫yb ef r 6 c h e td i f f e r e n t i a b l eo ns ( x o ，6 ) cd a n da ( x ) i sa na p p r o x i m a t i o nt of 7 ( z ) s u p p o s ea ( x o ) i sn o n s i n g u l a rf o rs o m e i n i t i a lg u e s sx 0 s ( x o ，t o ) ，w h e r e 伯 0 ，r 】a s s u m e a ( x o ) 一1 ( 厂7 ( z ) 一厂7 ( z 7 ) ) i | l i i x z 川， 浙江大学博士学位论文 w h e r ez s ( x o ，r ) a n di i x z o i | + i i z z ，r ，a n dt h ef o l l o w i n g ： ( i ) t h e r ee x i s t sn o n n e g a t i v ec o n s t a n t s8 0 ，a ，pa n d0 u o 1 s u c ht h a t a ( x o ) f ( x o ) i | s8 0 ， i i a ( x o ) 一1 ( 厂7 ( z ) 一a ( z ) ) i | o - t - p l ( u ) d u ， j 0 a n d r p ( x ) i i a ( x o ) 一1 a ( z ) 一i i i q l ( u ) d u ，v z s ( x o ，r o ) j 0 ( i i ) t h e r eh o l df o rs o m ea m a x l ，o e + p ) f o r 。l ( u ) d u = ( 1 - u 0 ) 。 s 由。( 1 - u o h 卜( u ( r - - u 肌 ( i i i ) s ( x o ，t + ) cs ( x o ，r o ) ，f o rt h el e a s tp o s i t i v er o o tt + o f ( 亡) ： ) ：= n ( 亡一u ) 讹) d 钆一( 1 一乱出+ s o t h e nt h en e w t o n l i k es e q u e n c e _ z 血) ( k 0 ) r e m a i n si ns ( x o ，t + ) a n dc o n v e r g e n t t oas o l u t i o nx + o ff ( x 1 = 0 k e y w o r d s ：b a n a c hs p a c e ，n o n l i n e a re q u a t i o n s ，n e w t o n sm e t h o d ，i n e x a c tn e w - t o nm e t h o d ，n e w t o n - l i k em e t h o d ，w e a kl i p s c h i t zc o n d i t i o n s ，s e m i - l o c a lc o n v e r - g e n c e x 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝鎏盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：武眼 签字日期：z 阴g 年多月5 日 学位论文版权使用授权书 本学位论文作者完全了解逝姿态堂有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权澎江盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：试镯久 签字日期：俐年 莎月j 日 导师签名： 签字日期： 致谢 本文是在导师王兴华教授的悉心指导下完成的。首先，非常感谢王老师给 予我自由选择研究课题的余地，使我能够有机会在一个非常有意思的领域内做 一些研究工作。其次，王老师渊博的知识、严谨的治学态度和活跃的学术思维使 我受益匪浅。最后，王老师在生活上的关心，并创造了良好的学习和研究氛围使 我能够顺利完成学业。值此毕业之际，谨向他致以崇高的敬意与诚挚的谢意。 借此机会我还要感谢李冲、韩丹夫、程晓良、吴庆标、黄正达和梁克维等老 师在我的求学过程中给我的悉心指导和热情帮助。感谢杨士俊、宓湘江、崔峰、 谢聪聪、王承竞作为师兄师姐给予的许多有益的讨论、启发和帮助。感谢徐爱 民、崔德灶、唐培培、白洪欢、黄振坤、兰莉莉、祝汉灿、强华、马国春、刘飞和 胡志成等同学，多年来在讨论班上与他们的交流使我受益匪浅。感谢读研究生 时的室友给予我的生活上和学习上的帮助。同时感谢浙江大学数学系资料室的 各位老师为我提供了良好的学习环境。 特别地，我要感谢我的家人和各位亲朋好友，他们是我求学道路上巨大的 精神靠山，没有他们的理解与支持，也许我就不会跨越一道道难关。 谨以此文献给所有关心我、支持我、帮助我的亲人和朋友们1 2 0 0 8 年3 月于浙大 第一章绪论 近年来，随着数学和其它学科的相互渗透以及大型计算机的出现和完善， 用计算机求解非线性方程组的有效算法，对求解各种非线性力学问题、电路问 题、经济平衡问题、非线性规划以及各种非线性偏微分方程离散化得到的方程 组，都有重要的实际意义。 1 1研究背景及其现状 设x ，y 同为实或复的b a n a c h 空间，f ：dc x _ y 为非线性算子，求解非 线性方程 y ( x ) = 0( 1 1 ) 的算法问题，无论是从理论上还是从实际上考虑，都是相当重要的数学内容。和 线性方程组不同，解非线性方程组的直接方法，通常只用于形式很特殊的小型 方程组。因此我们这里主要研究用迭代法解非线性方程组，而最基本的、最核 心的迭代法便是n e w t o n 迭代法。 假定t 厂在开凸集d ocd 内n 6 c h e t 可微，z + 是方程( 1 1 ) 的根，而x k 是它的k 次 近似，n e w t o n 法由下式定义： x k + 1 = x k 一厂7 ( z 七) 一1 f ( z k ) ，k = 0 ，1 ， ( 1 2 ) 事实上，公式( 1 2 ) 只是一种形式记号，实际计算时求逆就是解方程 f 7 ( x k ) a k = 一厂( z 彪) ，( 1 3 ) 而x k + 1 = x k + 七是对z + 新的近似。 这一方法是1 6 6 9 年n e w t o n 求解三次方程3 2 3 2 z 一5 = 0 时第一次引 入( 见 1 ) ，虽然具体形式与( 1 2 ) 不同，但是可以证明它们是等价的。随 后，1 6 9 0 年，r a p h s o n 在求解更一般的三次方程x 3 一b x = c 时确切地提出 了( 1 2 ) ，故此方法也被称为n e w t o n r a p h s o n 方法。 关于( 1 2 ) 的理论推导及几何解释有很多，例如将t 厂( z ) 在x k 处进行t a y l o r 展 开，取线性部分作为厂的近似，u 口f ( x ) 竺f ( x k ) + 厂7 p 七) 一x k ) ，解f ( x ) = 0 ，令 浙江大学博士学位论文 求得的z 为x k + 1 ，便得y ：u ( 1 2 ) 。另外，通过计算n e w t o n 定理中的不定积分也可以 得到解一元方程的n e w t o n 法( 1 2 ) ，即在 ，( z ) = ，( z ) + ，7 ( t ) d t ， ( 1 4 ) 中用零阶的n e w t o n - c o t e s 求积公式( 矩形公式) 计算不定积分 ，7 ( t ) d t 竺( 茁一x k ) f 弘奄) 再令厂( z ) = 0 ，求出的z 便是新的值x k + ，即( 1 2 ) 。 从求积公式推导n e w t o n 法最初在 2 中提到，直到w b e r a k o o m - f e r n a n d o ( 3 】) 一文的出现才引起人们的重视，很多学者对此进行深入研究，得到许3 3 阶迭代 收敛格式以及重要的理论结果。在 3 】中，作者用一阶n e w t o n c o t e s 求积公式( 梯 形公式) 舱掣旷) + ，k ) 】 计算( 1 4 ) 中的不定积分，得到隐方法 坼- 一一砥鬻 并用，7 ( z 辞。) 替代厂7 ( 。七+ - ) ，这里z 玉。为牛顿迭代 z + k + l = x k 一怒 这样得到显式的3 阶收敛的迭代方法便是 毗- 2 驴而万2 瓦f ( x 礴k ) f r o n t i n i - s o r m a n i ( 4 ) 用其它一阶n e w t o n c o t e s 求积公式( 中点求积公式或 一个节t 约g a u s s - l e g e n d r e 公式) ，即 班竺x - - x k 矿( 竿) 计算( 1 4 ) 中的不定积分，得到隐式的迭代法， 厂( z 路) x k + l 一扩万南 第一章绪论 用，7 ( 华) 替代厂7 ( 丝鲁坐) 得到显式的3 阶收敛的迭代法 f ( x 七) z k + l2 一百i 面 j “甩 2 f 7 ( k ) ， 关于这些迭代格式的理论分析，作者在f 3 1 中证明了即使用更高阶的差值型求积 公式计算( 1 4 ) 中不定积分，通过类似方法得到的迭代法最多是3 阶收敛的，并 对x 4 是t 厂的重根的情况进行了讨论( 5 】) 。h o m e i e r ( 6 ) 将一维情形推广到多维情 形，在 7 】中将n e w t o n 定理用在y = ，( z ) 的反函数z ( ) 上，即 一 x ( y ) = x ( y k ) + z 7 ( 叩) 却 ! ，七 通过类似的方法，证明了当用至少一阶的差值型求积公式计算上式中的不定积 分时得到的迭代法最多是3 阶收敛的。 从数值计算的角度来看，n e w t o n 法具有收敛快的优点，在计算时每步计 算只与前一步有关，误差不传播，是自校正的，因此，在理论和实际应用上都是 一种重要方法。但是每一步都要解一个线性方程组( 1 3 ) ( ，( z 惫) 1 很少能写成显 式表达式) ，这可能比较困难，特别是对从偏微分方程中提出的问题，其中方程 组的阶可能是几千。另外，对f ：形一形来讲，每步要算佗2 个分量偏导数值 和n 个分量函数值，故工作量较大。针对这些缺点n e w t o n 法有不少改进的算法。 ( 1 ) 在实际使用n e w t o n 法时，为了避免计算厂7 ( z ) ，通常可用差商代替 偏导数o j f i ( z ) ，设这些差商近似组成的矩阵为j ( x ，h ) ，若j ( x ，危) _ 1 存在，离 散n e w t o n 法可写为 z 七+ l = x k j ( x k ，h k ) 一1 厂( z 彪) ，k = 0 ，1 ， ( 2 ) 为了减少n e w t o n 法的计算量，通常可用简单n e w t o n 法( m o d i f i e dn e w t o n m e t h o d l ，即 x k + l = x k 一，7 ( z o ) f ( x k ) ，k = 0 ，1 ，( 1 ，5 ) 这种方法除开始计算厂7 ( z o ) _ 1 外，以后每步只需计算一个函数值，减少计算量， 但这个方法只有线性收敛，所以效率较低。 ( 3 ) 模减原则是可以加于任何迭代法的一项要求，所谓模减是指在某种范数 下l l f ( x k + i ) i i i i f ( x k ) l i ，k = 0 ，1 ，为使n e w t o n 法适合这个要求，给出下面形 式的修正： o 七+ l =一u 七f 7 () f ( x k ) ，k=0xk x kx k，1 ， o 七+ l2一u 七【) ，2 ，l ， 3 浙江大学博士学位论文 若厂7 ( x k ) 本身是奇异的，我们可以选取a 七保证，7 ( x k ) + 入南，非奇异，于是有下面的 变形： x k + 1 = x k 一( ，7 ( x k ) + 入知j ) 一1 f ( x k ) ， k = 0 ，1 ， ( 4 ) 计算效率有明显提高的变形，当属导数滞后计值的n e w t o n 法和导数超 前计值的n e w t o n 法，分别介绍如下： 导数滞后计值的n e w t o n 法由下式定义 x k + 1 = x k 一，7 ( 吻( ) ) _ 。f ( x k ) ，k = 0 ，1 ， 其中p ( 忍) 是某个不大于k 的整数，易知p ( k ) = 忍时就是n e w t o n 法，而p ( 岛) = 0 时 便是简单n e w t o n 法。现在假定每m 步重新计算一次，7 。如果将各次迭代重新编 号，用z 七表示第k m 次迭代，那么这个迭代法等价于 x k ，05x k ，x k + l2x k ，m ， x k ，i = x k 卜l 一，7 ( z 七) f ( x k ，t 一1 ) ，i = 1 ，m 该迭代法可看成由一步n e w t o n 法和( m 一1 ) 步简单n e w t o n 法合成，而这也是生 成高阶方法的一个途径。 另外导数超前计值的n e w t o n 法( 8 ， 9 】) 定义如下： y 0 = z o ，x k + 1 = x k 一厂7 ( 可七) 一1 f ( x 七) ， y k + 1 =一7()f(xa+1)，k=0xk+l- jy kx k + 1 ) ，1 ， + 12 一 【j ，5 ，上， 二 它由r f k i n g 和w w e r n e r 先后在同一家杂志上提出，我们也称其为k i n g - w e r n e r 迭代。该方法的计值量与n e w t o n 法相同，组合计算量增加一倍，而 有1 + 以阶收敛速度。 由k i n g w e r n e r j 迭代法将得到两个序列 z 七) 和 玑) ，若令y 惫= ；( z 七+ z k ) ，再 引进序列 ，这样迭代格式可写成下面更对称的形式： z 知+ l = z 凫一，7 ( 可知) 一1 f ( x k ) ， z k + 1 = x k + 1 一，( 玑) 一1 f ( x k + 1 ) 王兴华和郭学萍 1 0 研究了上面两种方法的收敛性。 4 第一章绪论 n e w t o n 法还有种种高阶推广。最重要的推广之一是e u l e r 族迭代和h a l l e y 族 迭代。e u l e r 族第k 个迭代映射是厂在z 的局部逆1 在l 厂( z ) 的t a y l o r 展开当自变量 取零值的k 阶部分和 k 1 取，加) = z + 击( 1 ) 歹( m ) ) ( 一m ) ) j = l j 当k = 1 时，就得到n e w t o n 迭代映射e 1 ，( z ) = ，( z ) = z 一，( z ) - 1 ，( z ) 。 当x = y = c 或r 时，h a l l e y 族第k 个迭代的迭代映射凰，( z ) 是厂在x 的一 个p a d e 逼近的零点，这个逼近的分子是线性式而分母是k - 1 次多项式。凰，( z ) 与 古典b e r n o u l l i 算法有某些联系，经这种联系的诱导能把它写成b a n a c h 空间通 行的形式( 1 1 】) 。当= 1 时再次得到n e w t o n 迭代映射h 1 ，( z ) = ，( z ) 。e k ，( z ) 和风，( z ) 的表达式中都出现厂直至阶的导数在x 的值，它们都有k + 1 阶收敛， 这是基于标准信息集 ，( z n ) ，厂7 ( z n ) ，厂( 庇) ( z 礼) ) 的最大阶( 1 2 】) 。 1 2 论文的组织 本论文的组织如下 第二章介绍用n e w t o n 法求解f ( x ) = o 的一些理论结果，尤其是其半局部收 敛性定理的研究和发展。作为解方程算法现代研究的起点，k a n t o r o v i c h 定理的 条件、收敛性结果、收敛球及唯一性球半径以及误差分析吸引了大批学者对此 进行研究，从而涌现出大量结果。其中w a n g ( 1 3 ) 中给出的n e w t o n 法的半局部 收敛性定理有很强的概括性，它将k a n t o r o v i c h 型条件和s m a l e 型条件统一起来。 这里我们给出这个结果新的应用，可以推出a r g y r o s ( 1 4 ) 中给出的含，的m 阶导 数信息的半局部收敛定理( 即定理2 1 3 ) ，并对其结果进行改进。 第三章介绍不精确n e w t o n 法的收敛性研究。首先介绍不精确n e w t o n 法的定 义及已有的一些局部收敛性定理，分析了余项以及控制序列的选取对其渐近收 敛速度的影响，具体介绍了现有的效率较高的控制序列的选取办法。其次，我们 对其已有的半局部收敛性结果进行介绍，包括m y s o v s k i i 型定理和k a n t