（计算数学专业论文）关于牛顿类迭代法的收敛性和误差分析.pdf

关于牛顿类迭代法的收敛性和误差估计 中文摘要 在利用数学手段研究自然现象和社会现象，或解决工程技术问题 时，往往可以将不少的实际问题归结为b a n a c h 空间形如： f ( z ) = 0 的非线性方程的求解问题n e w t o n 法是求解非线性方程的一个最基本而 且十分重要的迭代方法，目前使用的很多有效的迭代法，都是以n e w t o n 法为基础，并由它而得到的。 本文中，引入了一种新的n e w t o n 类迭代方法，由此引申出了变形的 n e w t o n 类迭代方法。并且分析了在o s t r o w s k i - k a n t o r o v i c h 条件下，这两类 迭代方法的半局部收敛性和相应的误差估计全文分为四个部分： 第一章：主要总结了n e w o t n 迭代和它的几种变形方法，以及综述了 自k a n t o r o v i c h 条件被提出来后，人们对其中的条件给出的各种修正 第二章：借助于动力系统的李雅普诺夫方法，构造了一种新的n e w t o n 类迭代方法。这种迭代法保持了经典n e w t o n 迭代法的收敛速度，克服了 f ( x ) o 的苛刻条件 第三章：通过运用优函数的方法，建立了n e w t o n 类迭代法在o s t r o w s k i - k a n t o r o v i e h 条件的收敛性定理，并给出了相应的误差估计。 第四章：为了将第三章中的n e w t o n 类迭代法的收敛阶从二阶提高到 三阶，通过两次迭代，产生了变形的n e w t o n 类迭代方法，同时对它也建 立了o s t r o w s k i k a n t o r o v i c h 条件下的收敛性定理，并给出了相应的误差估 计 在文章的最后，我们给出了两个数值例子 关于牛顿类迭代法的收敛性和误差估计 a b s t r a c t w h e nw eu s em a t h e m a t i c a lm e t h o d st os t u d yn a t u r a la n ds o c i a lp h e n o m e n a o rt os o l v ee n g i n e e r i n gt e c h n i q u ep r o b l e m s ，w eo f t e nr e g a r dt h ea l g o r i t h mo fm o s t p r a c t i c a lp r o b l e m sa so n e o fn o n h n e a re q u a t i o n si nf o r mo f f ( 茁) = 0 i nb a n a c hs p a c e n e w t o ni t e r a t i o ni st h em o s te l e m e n t a r ya n di m p o r t a n tm e t h o d f o rs o l v i n gn o n l i n e a re q u a t i o n a tp r e s e n t ，m a n ye f f e c t i v ei t e r a t i o n sa r ea l ld e r i v e d f r o mn e w t o nm e t h o d i n t h i sp a p e r ，w ei n t r o d u c en e w ”n e w t o n - l i k e ”m e t h o d sa n dt h e i rd e f o r m a - t i o n s t h i sd i s s e r t a t i o nc o n s i s t so ff o u rc h a p t e r s ，w h i c hm a i n l ya n a l y z et h es e m i c o n v e r g e n c ea n de r r o re s t i m a t eo ft h e s et w oi t e r a t i o n su n d e ro s t r o w s k i - k a n o r o v i c h c o n d i t i o n s i nc h a p t e r1 w es u m m a r i z en o to n l yn e w t o ni t e r a t i o na n ds o m ed e f o r m e dm e t h - o d s ，b u ta l s ot h ev a r i o u sc o r r e c t i o n so fl i p s c h i t zc o n d i t i o ns i n c ek a n o r o v i c hc o n d i - t i o nw a sp u tf o r w a r d i nc h a p t e r2 , w ed i s c u s sn e w ”n e w t o n - l i k e m e t h o d sw h i c ha l ef o u n d e do i l t h eb a s i so fl i a p u n o v sm e t h o d so fd y n a m i cs y s t e m t h e s en e wm e t h o d sp r e s e r v e q u a d r a t i cc o n v e r g e n c ea sw e l la sr e m o v et h em o n o t o n e i t yc o n d i t i o nf ( x ) 0 i nc h a p t e r3 w ee s t a b l i s hc o n v e r g e n c et h e o r e mu n d e ro s t r o w s k i k a n o r o v i c h c o n d i t i o nf o rn e w t o n - l i k em e t h o db yu s i n gm a j o r i z i n gm e t h o d m o r e o v e ra ne 卜 r o re s t i m a t ei sg i v e n ， i nc h a p t e r4 w ei n t r o d u c et h ed e f o r m e dn e w t o n l i k em e t h o d sw h i c ha r ec u b i c a l l yc o n v e r g e n t u n d e rt h es a m eo s t r o w s k i - k a n t o r o v i c ha sf o r n e w t o n - l i k e ” m e t h o d ，w ee s t a b l i s hc o n v e r g e n c et h e o r e ma n dg i v ea a 2e r r o re s t i m a t e f i n a l l y ，w eg i v et w on u m b e r i c a le x a m p l e s 一t t 致谢 衷心感谢我的导师韩丹夫教授在这两年多来给予我悉心的 指导! 导师的辛勤指导和谆谆教诲使我顺利完成学业并不断取 得了进步。韩老师严谨治学的学风，精益求精的精神和言传身 教的作风使我终身收益，并将成为我为人治学的楷模。 深深感谢所有曾经关心、支持和帮助过我的老师、同学和 朋友们，正是你们的关心和帮助，才使我的学习、工作和生活 变得更加精彩，并促成本文的完成。 持。 同时感谢我的家人，感谢你们多年来对我的体谅和默默支 关于牛顿类迭代法的收敛性和误差估计 第一章综述 现在科学技术的发展使数值计算日趋重要，数值计算方法是研究数 学问题的数值求解方法，包括科学计算，系统模拟等领域。在很多的实 际中，许多问题可归结为： 设x ，y 同为实或复的b a n a c h 空间，f ：d x y 为非线性算子， 求解非线性方程 f ( x ) = 0 ( 1 1 ) 的算法问题有两个事实为数值工作者致力于求解非线性方程的有效算 法的研究提供了充足的理由，其一：理论上高于4 次的方程不存在由方 程系数确定的根的解析表示；其二：大多数与方程根有关的问题并不要 求得到方程的真实解，而只满足于获得根的近似值。当然，这个近似解与 真实解之间的误差应当被控制在具体问题所能容忍的范围之内因此历 来这不只是专业数值分析者的研究课题，几个世纪以来，许许多多工程 技术人员、纯粹的数学家都曾从自己的需要或兴趣出发，对它做了不同 角度的研究。在研究这个课题的数学家中，不少还是当时数学的代表人 物，他们在这个课题的工作上，也反映了各个时代的数学面貌。在创立 微积分的十七世纪，n e w t o n 和h a l l e y 发明了新的数学工具来解方程，这 种工具就是现在普遍以他们的名字命名的迭代法；到后来c h e b ) ，s h e v 也发 明了以他自己名字命名的迭代法在微积分技巧蓬勃发展的十八世纪， e u l e r 和l a g r a n g e 级数的部分和形成了成员众多的迭代族；在开始注重分 析严密性的十九世纪，c a u c h y 建立了优级数技巧，这个技巧不断地被以 后的事实证明：对于研究方程近似解序列的收敛性是卓有成效的。 n e w t o n 迭代法 z 。+ 1 = z 。一( z 。) 一1 f ( a 。) ，n = 0 ，1 一l 一 关于牛顿类迭代法的收敛性和误差估计 一直是求非线性算子方程( 1 1 ) 最重要和最著名的迭代方法，它具有二阶 的收敛阶。关于n e w t o n 迭代法，许多的学者作了很多的研究工作，并且 积累了很多的文献( 【6 f 9 【1 1 1 2 2 0 2 1 1 2 5 2 7 3 0 3 3 3 6 3 8 3 9 1 4 2 4 3 4 6 4 9 5 0 5 1 1 ) 。尽管n e w t o n 迭代法是一个很强有力的方法，并且收敛速度也很快， 但在解决各种实际问题中，映照的计值及其求逆的计算代价可能会是很 大的。为了减少或避免n e w t o n 迭代法中导映照的求逆，产生了一大类变 形的n e w t o n 迭代法： x n + i = z 。a 。f ( x 。) ，v n n 这里用以代替f ( x 。) - 1 的映照a 。：f e 有如下一些取法： 1 当a 。= f 7 ( z 。k ) 一，即 。+ 1 = 2 2 。一f ( z m k ) 1 f ( x 。) ，佗= m 七，m k + 1 ，m k + m 一1 ，k n 这里m 是一个取定的自然数就是说，我们不需要在每一步迭代都 计算导映照并求逆，而是每隔m 步计算一次，并将其逆保留使用n l 步，这种方法称为减少导数计值次数的变形的n e w t o n 迭代法( 【4 4 1 ) 。 当m = 1 时，其为n e w t o n 迭代 。) 是减少导映照计算次数的n e w t o n 迭代产生的收敛于方程( 1 1 ) 的迭代序列，则其子序列 z m ) 的收敛 阶是m + l 。所以这种迭代法比平常的n e w t o n 迭代能提高渐近效率 2 当a ”l = 2 a 。一a 。f 托。+ 1 ) a 。，即 x n + i = 。一a 。f ( x 。) ， a 。+ l = 2 a 。一a 。f 7 ( 。+ 1 ) a 。， v n n 这里：山任意指定，使之接近于f ( x 。) 。这种迭代称为避免导数求 逆的变形的n e w t o n 迭代法( 【4 4 ) 其原理是借鉴当年没有除法硬件 的计算机中求导数的迭代法以求f 协。) 的逆尽管避免导数求逆的 变形的n e w t o n 迭代法求得解的速度要比n e w t o n 迭代法稍微慢些， 关于牛顿类迭代法的收敛性和误差估计 但它却不用求导数的逆，并且它仍然能保持平常的n e w t o n 迭代的2 阶收敛 3 当a 。= ( 靠) ，矗比z 。有一个适当的超前量： 矗+ - = 茁。+ - 一；a 。f ( z 。+ - ) 即： z 。+ l = 茹。一f 7 ( ( n ) 1 f ( x 。) ， 厶+ 。：厶一：f ，( 厶) 一- f ( x n + 1 ) z 称为导映照超前计值的n e w t o n 迭代法( 5 9 ) ，它是r f k i n g 和w w e r n e r 先后在同一家杂志上提出的，我们也称其为k i n g - w e r n e r 迭代它没 有增加计值代价，但其收敛阶提高到了1 + 以 若令厶= ；( x nq - ) ，得到变形的n e w t o i l 迭代法( 【3 0 ) ： x n + l = z 。一f ( 堡 塾) 。1 f ( z 。) ， 叭，= ，一一( ! q 导) 一1 f ( ，) 以上讨论的非线性算子f 是可导算子，若f 是不可导算子，n e w t o n 迭代法便不能使用一种僻决方案便是把f 分成两个算子之和，可导部 分记为h ，不可导但l i p s c h i t z 连续部分记为g 。由此求解非线性方程 f ( x ) = 0 变为求解方程日( z ) + c ( x ) = 0 那么n e w t o n 迭代法 g 。+ l = z 。一f ( z 。) 一1 r ( x 。) ，n = 0 ，1 ， 变为 。+ 1 = z 。h ( 。) 一1 ( 。日( z 。) + c ( x 。) ) ，礼= 0 ，1 ，2 ， 对于后者文献( 2 9 】) 和( 4 l j ) 都进行了讨论，并建立了相应的收敛理论 关于牛顿类迭代法的收敛性和误差估计 自从迭代法问世以来，该方法的收敛性、误差估计及其在实际应用中 的收敛快慢程度一直是人们努力研究的目标之一。 可以说：k a n t o r o v i c h ( 4 ) 关于n e w t o n 迭代法收敛性的著名工作是解 决方程算法现代研究的起点他给出的条件( 人们称之为k a n t o r o v i c h 条 件) 为： ( 1 ) 假定f 是由b a n a c h 空间x 的一个非空凸集s 2 到同型空间y 的f r c h e t 可微算子； ( 2 ) 对于点n ，假设f 协o ) - 1 存在，且i ( z o ) 一1 f ( 茹。) | | s 。； ( 3 ) ir e 7 ( 。o ) 一1 ( f 7x ) f ( ) ) 1 1 b l l x 一1 1 ，茹，y n ； ( 4 ) a b j ； ( 5 ) 丽n ，其中r ：1 - v 压- - 一2 a b 自从k a n t o r o v i c h 条件提出后，有大量的文献对上述条件中的( 3 ) 进行 了研究，给出了不少修正条件来减弱k a n t o r o v i c h 条件，当然相应的条件 ( 4 ) 、( 5 ) 也会产生变化。a o k e ( p 8 ) 就定义了导数f 怡) 满足( 耳，p ) 一h s l d e r 连续条件 l l f ( z o ) 一1 ( f ( z ) f ( 口) ) i | g l l x 一l p ，z ，q ，p ( 0 ，1 来代替( 3 ) 中的l i p s c h i t z 连续条件。而更一般地，a p p e l ( 5 ) 和a r g y r o s ( 6 ) 用一个给定的实函数w ，使f 满足 i | f ( z o ) 一1 ( f x ) 一f 7 ) ) | is 训( i l 茁一可l i ) ，v x ，y n 最近，g u t i e r r r e z 和h e r n a n d e z ( 2 5 ) 通过减弱k n a t o r o v i c h 条件中的( 3 ) 给出了一个新的结果。 ( 1 ) 假定f 是由b a n a c h 空间x 的一个非空凸集q 到同型空间y 的f r d c h e t 可微算子； 关于牛顿类迭代法的收敛性和误差估计 ( 2 ) 存在点跏i 2 f 假设f x o ) 。存在，且jj f 协o ) f ( x o ) i l5a ( 3 ) f 7 ( ) 一1 ( ，7 ( z ) 一f ( 锄) ) i l k ( 1 l x x o l l ) ，v x n ( 4 ) h a k s ( 1 4 4 6 ) 2 5 = o 1 6 8 0 8 1 6 。 ( 5 ) 两鲫，其中：r ：鲨刍镰旦竺 之后，h e r n a n d e z ( 3 6 ) 利用一给定的实函数u 使得条件( 3 ) 更一般化 了 另一方面，w a , n g ( 4 1 ) 提出了更一般的解唯一的条件 l i f ( z o ) 一1 f 7 ( z ) ，f 。o p ( z ) l ( 札) d “，v x 百彳i i 可 和n e w t o n 法收敛的条件 l i e 强0 ) - 1 ( f ，一f 铀圳l 露狮胁， v x 口( 印，r ) ，v y 取巧= 而万 这里p ( x ) = 峪一x 0 ，j d ( h ) = p ( x ) + 怕一z l | t l 为正的单调非减的可积函 数岫缸 后来，弊学萍( 4 3 】) 将上述收敛性和唯一性定理的条件加以了统一， 在一般的弱条件： 愀x o ) 帅f ( 。) 圳l ( ) d u ，比而丽 ( 该条件包括了著名的经典k a n t o r o v i c h 条件) 下给出了方程( 1 1 ) 解的唯一 性及n e w t o n 法的收敛性定理 由于上面的任何一种假设条件下，n e w t o n 迭代序列 z 。) 都收敛到方 程的一个解矿，所以很自然地可以先假设解。+ 存在，从而可将上面的 k a n t o r o v i c h 条件换成：f 协+ ) _ 1 f 满足l i p s c h i t e z 条件( 2 7 5 1 ) ： f 7 ( 茁+ ) 一1 ( f 7 ( z ) f 7 ( ”) ) i l g l l x 一| i ，v x 百丽 关于牛顿类迭代法的牧敛性和误差估计 文( 3 9 】) 中，又分别将解的唯一性条件放宽到： l i e ( 。+ ) 一1 f ( z ) 一i i j ( 9 。l ( “) d 让，v xe 丽 并将n e w t o n 法的收敛性条件放宽到： l i f ( z + ) 一( f 7 ( 石) 一f ( z r ) ) | | ，9 7 ：l ( u ) d u ，v x b + ，r ) ，o 茎r 茎1 j r p ( z l 这里z 7 = z + + r 一x 。) 。 后又将上述收敛性和唯一性统一了起来，在条件： i i f ，( 。+ ) 一- f ，( z ) i i i 州“l ( ) d u ，比乏呵i i 可 j 0 下给出了n e w t o n 法的收敛性。 在上面的任何一种假设下，仅考虑了f 的l i p s c h i t z 条件。黄正达( 3 1 ) 指出f 的更高阶的导数是有用的，如果f 有更高阶的导数，同时文( 3 1 ) 弥补了k a n t o r v o i c h 条件不能判断从某个指定点出发的n e w t o n 迭代在解 某个方程时是否收敛，引进了如下的条件 i f 协o ) - 1 f ”( 跏) 1 l ，y ， | | f 7 ( z o ) 一1 ( f ”( z ) 一f ”白) ) | 1 k l t x y l l ，z ，y s 2 g u t i e r r e z 和h e r n a n d e z ( 2 6 ) 将此条件改进为 i i f ( z o ) 一1 f ”( o ) | | 7 ， ij f ( z o ) 一1 ( f “( z ) 一f ”( 勒) ) j i q l x x oj i ，z q 可见，l j p s c h i t z 条件中因有一点固定了而得到减弱 此后，文( 5 2 ) 对此条件进行了修改： i i f ，x o ) 一t ( f ( z ) 一f ”x o ) ) j ，烈l ( “) d u ，v x b ( x o ，r ) j 0 此外，a r g y r o s 在文献( 1 0 m 2 】) 中提出了下面的两个收敛条件： 关于牛顿类迭代法的收敛性和误差估计 1 ( a ) l i 。p ( z o ) 1 f ( 。o ) | f 墨叩； ( b ) lj f 7 ( 勘) q f ( ( 。o ) i i5n i = 2 ，m ，m 2 ； ( c ) il f ( z o ) 一1 i f ( ”( 茁) 一f ( ”( z o ) 1 曼o c m + l i l 。一z o ，v z n ； ( 帅5 高南s ”1 + 鲁扩+ + 署s 2 一s + ” 0 ，m 2 ，3 i 竹l + 1 ，s 叼 2 ( a ) 0 o ； ( c ) j i f ( z o ) 一1 i f ”( 。) 一f ”( z o ) 】j 冬d l l x x o lj ，、口o q ； ( d ) 2 k a 冬1 ，其中k = l g t a x c ，b 十2 a d ， 或满足f ( t ) = t 3 2 d t 2 一( 2 d b 2 ) t + 2 d ( b + a d ) 的两个正根七l ，2 ，f b ，b + 2 6 d c ( k l ，也 ，那么k c ，k 6 ，b + 2 0 d 对于其它迭代法收敛条件的研究，不像研究n e w t o n 迭代法那样多 它们大都是从n e w t o n 迭代法的收敛条件中加以推广的 证明迭代法的收敛性一个很不错的技巧是优函数技术，这是k a n t o r o v i e h 为了证明b a n a c h 空间内的n e w t o n 迭代法的收敛性而提出来的。随后它 被广泛地应用于证明各种迭代法的收敛性k a n t o r o v i c h 最初用的优函数 为二次多项式 p l ( t ) = 去b t 2 一t + 卵 用它的最大好处是可以得到精确的显式误差估计。后来也有人用它证明 三次收敛的迭代法的收敛性( 3 5 1 ) ，但是与三次多项式相比它就显得不足 了在证明二阶和三阶收敛的迭代法的收敛性时，三次多项式是比较常 用的优函数( 2 2 ，【2 4 ， 4 8 ) 础) = 百k 。3 + 互b t 2 一抖町 关于牛顿类迭代法的收敛性和误差估计 在证明h 6 1 d e r 条件下的迭代法的收敛性时，优函数变为实函数证明具 有1 + p 阶收敛时，用的优函数的形式为( 8 ) p 3 ( ) = 而b 舻一h 叩 证明具有2 + p 阶收敛时，优函数的形式为( 3 5 j ) a ( 。= 西南垆十9 + ；z 2 一t + 叩 有理多项式也是证明各种迭代法收敛性的一种比较好的优函数，它的形 式为 ，f 2 p 5 ( t ) 27 7 叫+ 芒i 它是由s m a l e 提出的，由w a n g & h a n ( 5 3 1 ) 完全加以改进，而后被应用于 证明各种迭代法在s m a l e 点估计判据下的收敛性( 【3 2 o 】， 4 5 4 7 1 ) 另一种 证明迭代序列收敛的技巧是递归法对此g u t i r r e z 和h e r n d n d e z 等人对 h a l l e y 迭代、c h e b y s h e v 迭代、s u p e r h a l l e y 迭代、j a r r a t t 型迭代的收敛 性进行了一系列工作( 1 3 - 14 】 1 6 - 1 9 2 3 f 2 8 】 3 4 ) 。 关于牛顿类迭代法的收敛性和误差估计 2 1 引言 第二章对牛顿迭代法的一个修改 在求解b a n a z l l 空间中的非线性方程r ( x ) = 0 的问题，已有了各种 各样的求解方法其中最著名的有n e w t o n 迭代方法、h a l l e y 迭代方法、 c h e b y s h e v 迭代方法等n e w t o n 迭代方法应用的最广泛，原因是它只要计 算f ( z ) 的逆就可以了。自从它问世已来，许多的学者作了很多的研究工 作，并对它作了诸多的修改。但是为保持它的收敛速度要求，在所考虑 的含根区间内，f 协) 0 这一苛刻条件却至今尚未去掉。是否有可能从 另外的途径来考虑问题：即在保持牛顿法收敛速度和计算效能不变的前 提下，重新构造出新的“牛顿类”方法来克服牛顿迭代法的这一致命弱 点。 我们可以借助于动力系统方法成功地解决了这一问题。 2 2 求根问题与动力系统 为求方程 f ( 茁) = 0 在【a , b 内的单根矿，令 g 扛) = e 肛f ( 。) ，p o ，i 肛f + 。 则卫。也是方程g ( z ) = 0 在【a , b 】内的单重根。反之亦然。 为缓引动力系统的结果，令 巾) 纠叩l _ 鬈) ，剁嚣 则当茁 n ，b 】时，”( z ) 0 ，并且等号当且仅当茁= 。时成立。 ( 2 2 ) ( 2 3 ) 关于牛顿类迭代法的收敛性和误差估计 假设在【a ，6 上有p f ( x ) + f 协) 0 成立，我们引入一个动力系统 d x g ( z )f ( x ) 一d t2 一虿丽。一万砑诵 x ( o ) = x 0 ，x 0 a ，6 ，( 2 4 ) 则显然非线性方程( 1 _ 1 ) 在 a , b 】内的解z + 是动力系统( 2 4 ) 的平衡点，反 之亦然 定理2 1 设对k 卅，有日( 。) = 一面犏满足l - 条件， f ( a ) f ( b ) 0( 2 6 ) 并且矿是方程( 2 1 ) 在 a ，b j 内的难一解。 定理2 1 ( 1 ) 指出了在h ( x ) 满足l 一条件，胪( z ) + f 协) 0 及f ( a ) f ( b ) 0 ，z 【a ，6 的条件下，取【a , b 内任一点黝为初始点的运动( 2 6 ) 都趋于 方程( 2 1 ) 在 a ，6 】内的唯一根。这实际上导出了一类具有区域收敛性的连 续性方法 特别地，如果允许( 2 2 ) 中取p = 0 ，则立刻得到连续牛顿法的结果， 但本定理的条件比较宽松。 2 3 新的牛顿类方法 动力系统( 2 4 ) 给数值求解非线性方程( 2 1 ) 提供了各种可能性利用 不同的数值方法求解( 2 4 ) 时，可以得到不同的求根方法我们用最简单 的e u l e r 法来解初值问题( 2 4 ) ，得到： z 。+ - = z 。一 。瓦j 飞( 礼。，1 ，2 ，) ( 2 7 ) 关于牛顿类迭代法的收敛性和误差估计 其中h 。为积分步长，它的选取和牛顿下山法一样应满足 r ( x 。+ 1 ) f i f ( x 。) i ，o 0 这意味着眠( t ) 是单调递增的当t 0 ，t + ) 由归纳法，能证 明 t k 冬t k + z = n h ( “) h ( t + ) = t + 因此序列讯) 单调递增并收敛由迭代公式( 3 5 ) ，可得l i r a t t = t + ，结 论成立。 弓l 理3 3 ：若a 1 2 ，t k + 1 = i ( “) ，t o = 0 ，k = 0 ，1 ，男b 么 、2 k t t k ! ；i i ! ! ( t + t + ) ， ( 3 8 ) 其中， 罱娶，口= 岩黼 慨。， 1 4 关于牛顿类迭代法的收敛性和误差估计 证明：记a k = t + 一t k ，b k = t ”2 t k 爿b 么 h ( t 后) = 百k 。曲女，( “) = 一百k ( 。 + 6 ) ， ( 3 1 0 ) 因此，有 =一再丽akbkak+l a k 2 。2 k a k + 生b k - # a k b b ( 3 1 1 ) 2 一i 再i 面瓦2 o 。 1 ) 同样， 吣，- 6 t 一再丽a k b k = 6 ：再( 3 1 2 ) 根据式( 3 1 1 ) 和( 3 1 2 ) ，可得 瓦a k2 等( 等) 2 兰一( 爸) 2 9 + 限 。1 + 2 + + 2 一1 ( 等) 2 = ；( a ) 2 k 注意到：b k = t “一t + + a t ，从式( 3 1 3 ) 中解出a t ，结论成立。 3 3 主要结果 设f ：dcx y 是由实的或复的b a n a c h 空间x 到同型空间y 的非线性算子，如果f 在某个凸集d 中是一阶f 一可导，并且满足 i i f 7 ( 口) 一，( 耖) j jsm i i x 一掣8 ， v x d ( 3 1 4 ) 对于固定的f 和x ，又设p ( f ) z ) ：dcx l ( x ，y ) 是一个线性算子， 并且存在常数芦0 使得 i i 卢( f ，z ) | | 弘， v f , z ( 3 1 5 ) 考虑如下的迭代格式 。k + 1 = z k 一( f 7 ( 。k ) + 卢( f ，x k ) f ( x k ) ) 一1 f ( x k ) ， 七= 0 ，1 ，( 3 1 6 ) 一1 5 关于牛顿类迭代法的收敛性和误差估计 如果初值卫。使得p ( z o ) _ 1 存在，且 f 7 ( z o ) 一1l l 卢， t f 7 扛o ) 。f 如o ) i l 曼叩( 3 1 7 ) 男5 么，有 定理3 1 ：对于满足式( 3 1 4 ) 、( 3 1 5 ) 和( 3 1 7 ) 的f 和p ( f z ) ，若a = 砌s ；，k2m + 等，那么由式( 3 1 6 ) 产生的以z 。为初值的迭代序列 有意义，且收敛于f 在s ( t + ) 中的惟一零点z + 进一步有 、2 k 1 1 茁k 石+ | l ! ! t + _ t k ! ；i i i ! j i i i ( t + + t ) ，k = ：0 ，1 ， ( 3 - 1 8 ) 其中0 ，a 由式( 3 , 9 ) 定义，并且s ( r ) = 倒l i x x o i l r ) 3 4 定理的证明 设f 和肛( f 】x ) 满足式( 3 1 4 ) 、( 3 1 5 ) 和( 3 1 7 ) ，为了证明定理，需要 几个引理 引理3 4 ：若n 1 2 ，忪一t o i i 南及m k ，那么f ( z ) _ 1 存在 且 i i f ( z ) 1 忙一而士丽( 3 a 9 ) 证明：由于f i f 7 ) - 1 | | 卢及l i x 一印f | v ( k z ) ，因此 l i f ( 。) 一f ( z 。) l i m l l x - x o l l 茎k h x - x o l l = ( i i = - z o l l ) + 西1 万1 根据b a n a c h 引理，可得( z ) 。存在且 | | f ，( 矿1 1 t - 研而珊稚一而 引理得证 引理3 5 ：设序列 ) 由式( 3 1 6 ) 生成，有 如 岫瓣竺扩瞄 似 队嘶 嘲。 “ 地 关于牛顿类迭代法的收敛性和误差估计 证明：根据迭代公式( 3 1 6 ) ，有 因此， 。+ l x 七= 一( f ( z 七) + 卢( f ，x k ) f ( z 七) ) 一1 f ( 茁k ) + ，1 ( f ，( z k + t ( z + 。 j 0 + o l ( f 7 ( x k + t ( z 。+ ，一z 一) ) 一f 7 ( z e ) ) 出( z e + t z m ) 引理得证。 引理3 6 ： 若n 1 2 ，筹+ m sk ，有 a ) x k s ( x o ，t + ) b ) 1 1 。 + 1 一z k | i t k + l 一“； c ) i i f ( z t ) 1 1 曼) 及i i f ( 圳一而1 ( 3 2 1 ) 其中序列 t * ) 由式( 3 5 ) 生成。 证明：对于k = 0 ，a ) ，b ) 和c ) 显然成立假设a ) ，b ) 和c ) 对k 兰n 成立。 首先由b ) ，可得 因此，x 。+ 1 s ( ，t + ) f 协。+ 。) _ 1 存在，并且 z j l i 兰t j + l t j = 。+ 1 冬t j = o 即a ) 对k = n + 1 仍成立。 l i e ( ) 。1 恪一志 一1 7 一 同时根据引理4 ，可得 ( 3 2 2 ) 关于牛顿类迭代法的收敛性和误差佰仃 一 根据归纳假设和引理3 5 ，有 i i f ( z 。+ 。) 1 1 曼一元可躺+ 等( t n + - 一k ) 2 ：( 叫吣n ) + 似) 十等) 一蝴2 =f 一2 卢( ( 如) + t t h ( 。) ) + 可m + p ( ( t 。) + p ( k ) ) ) ( k + 1 t 。) 2 s ( 等+ i m 州忡卅删铀) ) 一2 ( 等+ 砌协。) + 州) ) ( “ ：赢辈掣羔十等( “。一t 。) 。：h ( t 州) = 砾了而十百p 计1 叫一 n + l ， 因此 这就是说b ) 和c ) 对k = 竹十1 仍成立引理得证。 定理的证明：由引理3 6b ) ，可得序列 ) 是一个c a u c h y 序列因而有 极限，设其为矿，于上式令一。，推出 z - 一z b i i t 4 一t ( 3 - 2 3 ) 由f ( 正) 的连续性知，f ( 矿) = 0 ，即矿是方程( 3 1 ) 的解。结合引理3 3 ，得 到了定理的( 3 1 8 ) 式定理证毕 分析上述“牛顿类”迭代方法，当p = o ，即为牛顿迭代方法，用相同 的优函数危( t ) ，可以得到它的误差估计为 、2 k i l 。+ 茁1 11 ；t + t ! ! 南( t t + ) ， 可见：可以通过适当调整p 的值，使得“牛顿类”迭代法产生的序列 f 孤 比牛顿法产生的序列具有更高的精确度 一1 8 关于牛顿类迭代法的收敛性和误差估计 同时发现：当f ( x + ) = 0 ，f x ) 0 ，f ”( z ) 存在且肛( e z ) ；p 时，那 么由式( 3 1 6 ) 产生的以x 0 为初值的迭代序列z t 至少是二阶收敛的，并且 有 熙糌群；锱( 3 2 4 ) 当取值使得式( 3 2 4 ) 为零时，将会具有比牛顿法更快的收敛速度和更 高的收敛精确度 关于牛顿类迭代法的收敛性和误差估计 4 1 引言 第四章“变形牛顿类”迭代的 收敛性和误差估计 设f ：dcx y 是由凸集d 上实的或复的b a n a c h 空间x 到同型空 间y 的非线性算子，并且，是一阶f r e c h e t 一可导，求解算子方程 f ( x ) = 0( 4 1 ) 的经典方法首推牛顿迭代 x k 十1 = , t k f ( 钆) - 1 f ( ) ( 4 2 ) 对牛顿迭代法，有许多的科学家对它作了大量的修改工作，在文献【1 】中 导出了新的“牛顿类”迭代公式： x k + l = z t j 百i ，p 。， ( 4 3 ) 2 z 一j 百石瓦了；= _ 确p 之”， 【4 3 j 在上一章里，已经建立了在b a n a c h 空间中，这种“牛顿类”迭代公 式在o s t r o w s k i k a n t o r o v i c h 条件下的收敛性定理，并给出了比牛顿迭代更 好的误差估计 为了将迭代方法( 4 3 ) 的收敛阶从二阶提高到三阶，在本章中，我们 利用经典牛顿方法的变形手段( 【3 0 ) ，给出了另一种变形的“牛顿类”迭 代公式： 舻一丽鬻， z t + t = y k i l i ，肛。 ( 4 4 ) 并且在b a n a c h 空间中建立了此变形叫；顿类”迭代方法，在o s t r o w s k i k a n t o r o v i c h 条件下的收敛性定理及相应的误差估计。 美于争顿类逐戎洼鲤牧袭挂秘莰差结诗 4 2 优函数及其性质 对予 # 负实数k ，岁，块考露二次伐露数 ( t ) 一；k t 2 - 1 岔虽。 ( 4 5 ) 设肚0 ，将h 运用到迭代公式( 4 ) ，我们可以得到相应的实序列 s * ) 鼗 投 ： s 一= “矾西h 巧( t a 丽) 丽，t o = o 3 5 “研西i 乃面， 沁l 刮而，p n ( 4 6 ) 刮r 研万享面可丽 p up o 霉l 瑾碡1 ：墨8 一k i l n 兰露，纛( ) 有薄令歪投 矿i 一- i y - - - - - - 钉，r + 。! 亚至哼 ( 4 ，7 ) 引理4 2 ：当k23 弘? 7 卢2 和a = 彪砌曼 时，有 0 = t o = s o t 七 船 o j 艮沁l 蹰 巍鳢纳法可碍弓l 理结论+ 引理4 3 ：若a = n 砌兰1 2 ，迭代序列 k ) 由下列“牛顿类”迭代公式 产生， s 一。一甄鬻， 关于牛顿类迭代法的收敛性和误差估计 那么 其中， a = 目 沁- 毡一丽等，t o = o , k = o , 1 品旷卅 1 一、压巧 1 + 1 2 0 ( 4 1 1 ) 吲舞器筹哥产 嘲 证明：记u = t + 一t ，v k = t ”一t k ，a 女= t + 一8 ，b 女= t ”一s k 那么 因此，有 同样， ( 4 1 3 ) ( 4 1 4 ) 。一一一再老蠢卅丢芸 均 一i 五蕊；i 瓯前 5 ) 铋一万石ukvkbk骊卅去善 r i 而= 甄獗刮；i 而三甄蕊 根据式( 4 1 5 ) 、( 4 1 6 ) ，可得 同理， n k 6 k a k b k “r i 面孺 u k + 一2 i 上u 钉 - 2 靠一i 而a 孺k b k u k 十魄一：于“喉 将式( 4 1 5 ) 和( 4 1 6 ) 分别代入式( 4 1 8 ) 、( 4 1 9 ) 得到 吣- = 赢3 杀攀k 斋2 ( - 一警扎棚m ( - 一竽刚) ( 4 1 6 ) ( 4 1 7 ) ( 4 1 8 ) ( 4 1 9 ) ( 4 2 0 ) 巩 + + b k 一0 k 一0 一 一 = = 蝴 ，【，l k 一0一0 = = 瞄 啪 m m 关于牛顿类迭代法的收敛性和误差估计 帅= 毋# 鬻泰池( ，一等咖扩删一铎咖岫 z ) 根据式( 4 2 0 ) 、( 4 2 1 ) ，可得 一u k + l ：垡! ! 二擎坐塑唑! ! 二竺坐塑：丛! 二擎坐塑堕 v k + l u 2 ( 1 一譬札1 ) ( v k (