（计算数学专业论文）解非线性方程的若干迭代算法的收敛性分析.pdf

摘要 摘要 在利用数学手段研究社会现象和实际问题或解决科学工程技术问题时，往 往把这些问题归结为求解b a n a c h 空间巾非线性方程f ( x ) = 0 的算法问题，这个 重要的问题一直是数值工作者所研究的核心问题而迭代法是求解非线性方程的 一个重要算法，迭代法的选择直接影响到解决各种非线性问题的效果，所以迭代 法的研究有着十分重要的科学价值和实际意义 在众多的迭代法中，首先最著名、最常用的迭代法莫过于n e w t o n 法，它具有 二阶的收敛性，以及多种变形的n e w t o n 法：其次，还有三阶收敛的h a l l e y 迭代， c h e b y s h e v 迭代，超h a l l e y 迭代及其变形；另外，还有四阶收敛的j a r r a t t 型迭代等 等，本文主要对变形的n e w t o n 法以及一族免二阶导数计值的迭代法的收敛性进 行了分析，并给出数值例子，全文共分为四章 第一章，主要对几种迭代法的收敛性进行了讨论，总结了它们的收敛条件及 证明各种迭代法收敛性的技巧 第二章，主要讨论了解多项式方程的修正牛顿法的进一步改进，即 用c h e b y s h e v 迭代法对其作一次修正，并分析改进的迭代法的收敛性 第三章，主要讨论了从带一个参数的迭代族出发，构造了一族免二阶导数计 值的带两个参数的迭代族，并给出了这族迭代法的收敛理论 第四章，数值例子 关键词：迭代，收敛性，牛顿法，迭代族，修正的牛顿法 a b s t r a e t 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 lp h e n o m e n aa n dp r a c t i c a l p r o b l e m s ，o rs 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 e s ep r a c t i c a l p r o b l e m sa st h ea l g o r i t h mp r o b l e m so fs o l v i n gn o n l i n e a re q u a t i o n si nb a n a c hs p a c e t h i si m p o r t a n tp r o b l e mh a sb e e nt h ec o r eo fs t u d i e so fn u m e r i c a lw o r k e r s ，a n dt h e i t e r a t i o na l g o r i t h mi st h em o s ti m p o r t a n tm e t h o do fs o l v i n gt h en o n l i n e a re q u a t i o n s w h e t h e rt h en o n l i n e a rp r o b l e m sw i l lb es o l v e dw e l lo rn o ti sd i r e c t l ya f f e c t e db yt h e c h o i c eo f i t e r a t i v em e t h o d s s o ，i ti sv e r yi m p o r t a n ta n dm e a n i n g f u lt od ot h er e s e a r c h o fi t e r a t i v em e t h o d s a sw ea r ea l lk n o w n ，f i r s t ，t h ew e l l - k n o w ni t e r a t i o ni sn oo t h e rt h a nn e w t o n s i t e r a t i o n ，i th a ss e c o n d o r d e rc o n v e r g e n c e ，s e c o n d ，t h e r ea r et h i r d o r d e rc h e b y s h e v s i t e r a t i o n ，h a l l e y si t e r a t i o n ，s u p e r h n l e y si t e r a t i o na n dt h e i rd e f o r m a t i o n s b e s i d e s ， t h e r ei sf o u r t h o r d e rj a r r a t t si t e r a t i o na n ds oo n t h ed i s s e r t a t i o nc o n t a i n sf o u rc h a p t e r s ，m a i n l ym a k e sa n a l y s e so nt h ed e f o r m a t i o n so fn e w t o n sm e t h o da n dc o n v e r g e n c eo faf a m i l yo fi t e r a t i o n sw i t hc u b i co r d e r w h i c hc a na v o i dt h ec o m p u t a t i o no f t h es e c o n df r e c h e t d e r i v a t i v e i nc h a p t e r1 ，w ed i s c u s ss e v e r a li t e m t i v em e t h o d sa n dt h e i rc o n v e r g e n c ec o n d i t i o n s w h i l e ，w ea l s op r e s e n tt h et e c h n i q u e si np r o v i n gt h ec o n v e r g e n c et h e o r e m i nc h a p t e r2 ，w es t u d yt h ei m p r o v e m e n to fam o d i f i e dn e w t o nm e t h o df o rp o l y - n o m i a l sa n da n a l y s ei t sc o n v e r g e n c e i nc h a p t e r3 ，w ed e r i v et h es e c o n d o r d e r - d e r i v a t i v e f r e ei t e r a t i o n sw i t ht w op a r a m e t e r sf r o mt h et h i r d o r d e ri t e r a t i o n sw i t ho n ep a r a m e t e rt oa p p r o x i m a t et h er o o t so f n o n d i f f e r e n t i a b l ee q u a t i o n si nb a n a c hs p a c e ，a n dw ea l s og i v ea n dp r o v et h ec o n v e r - g e n c et h e o r e m i nc h a p t e r4 ，w eg i v es o m en u m e r i c a le x a m p l e s k e yw o r d s ：i t e r a t i o n ，c o n v e r g e n c e ，n e w t o nm e t h o d ，af a m i l yo fi t e r a t i o n s ， m o d i f i e dn e w t o nm e t h o d s i i 第章综述 第一章综述 设x ，y 同为实或复的b a n a e h 空间，f ：d x y 为非线性算子，求解非 线性方程 的算法问题，不仅从理论上很多数值工作者对它作了大量的研究工作，而且在解 决实际问题中也受到广泛的重视有很多数值工作者从自己的兴趣或需要出发， 对它做了不同角度的研究和分析并运用到解决实际问题中，由于非线性方程求 解问题无论在理论上或者解法上都不如线性方程成熟和有效因此对非线性方 程解的存在性及寻找有效的数值方法均存在很多问题，需要进一步研究与解决 到目前为【e ，解非线性方程f ( x ) = 0 的问题，最著名、最常用的方法 是n e w t o n 迭代法： x n + 1 = z 。一f 7 ( z 。) f ( x 。) 它具有二阶的收敛性，对此迭代法，很多数值工作者作了许多的研究工作，并积 累了大量的文献 除此之外，还有三阶收敛的h a l l e y 迭代法，c h e b y s h e v 迭代法和凸加速法 即超h a l l e y 迭代法及它们的变形另外还有四阶收敛的j a r r a t t 型迭代等等方 程( 1 1 ) 的解的唯一性和各种各样迭代法的实现性、收敛性、收敛速度和误差估 计是研究方程( 1 1 ) 和各种迭代法的主要内容这些迭代法主要概括成以下的形 式 y n = x 。一f ( z 。) 一1 f ( x 。) z 。+ 1 = 。一妒( s 。) f ( z 。) 一1 f ( z 。)( 1 2 ) s 。= f ( z 。) 一1f of ”( z 。+ o ( y n z 。) + 她( 一z 。) ) d t f 7 ( 。) 一1f ( z 。) 0 0 ，1 a 0 ，1 ( 1 ) 当妒( s 。) = 1 时，( 1 2 ) 式就是著名的n e w t o n 迭代法( 王兴华等的 1 】， 2 1 ，【3 以 及y a m a m o t o 的 4 ) ( 2 ) 当妒( s 。) = 1 + j s 。 1 一a s 。 ，a 0 ，1 时， ( a ) s 。= f ( z 。) 一1 f ”( z 。) f ( 。) 一1 f ( z 。) 第一章综述 ( 1 2 ) 式变为族具有三阶收敛的迭代法( 5 】， 6 】) ，这族迭代法包 括c h e b y s h c v ( o = o ) 迭代法，h a l l e y ( a = ) 迭代法，j 超h a l l e y ( a = 1 ) 迭代法等 等 ( b ) s n = f 7x 。) 一1 詹f 7 协。十她( 。一z 。) ) d t f 忙。) f ( x 。) = f 7x 。) 一1 i 1 f 7 ( 。) 一f ( 。+ a ( 聃。一。) 】， a f 0 ，1 】 是对( a ) 中的迭代法的修正，在这族迭代法中避免了二阶f r e e h e t 导数的计值，但 同时又保持三阶收敛的速度( 7 】， 8 ) ( 3 ) 当妒( s 礼) = 1 + ；s 。 1 8 n 】- 1 时 ( a ) = f ，( z 。) 一1 詹f ”( z 。+ ；t ( 一x ) ) d t f 7x 。) f ( x 。) = j 3 f x 。) 一1 f x 。) 一f 7 ( z 。+ ；( 鲰一x n ) ) 】 为具有四阶收敛的j a r r a t t 型迭代方法( 【9 ， t o l ，【1 1 】) ( b ) s 。= f 7 ( 。) 一1 f ”( z 。+ ；( 一x n ) ) f 7 ( 。) 一1 f ( x 。) 也是具有四阶收敛的迭代方法 下面将介绍几种变形的n e w t o n 法 尽管n e w t o n 法是一个很强有力的方法，但是在解决各种实际问题中，由于导 映照的计值及其求逆的计算代价可能会很大，这样在应用中带来诸多不便，所以 为了减少或避免n e w t o n 法中导映照的求逆，对它进行了一系列的变形 这里用a 。代替p 7 ( z 。) ，a 。：f e 的一个映照， x n + l = z 。一a 。r ( x 。) 主要有以下几种取法： 1 当a 。= f 7 ( z 。k ) ，即 x n + l = z 。一f 7 ( z 。k ) 一1 f ( x 。) ，礼= m k ，m 尼+ 1 ，m k + m 一1 ，ken 这里m 是一个取定的自然数，就是说，我们不需要在每一步迭代都计算导映照 并求逆，而是每隔m 步计算一次，并将其逆保留使用m 步，这种方法称为减少导 映照计值次数的变形的n e w t o n 迭代法，m = l 时，其为n e w t o n 法f 。 是减少导 映照计值次数的n e w t o n 迭代法产生的且收敛于方程( 1 1 ) 解的迭代序列，其子序 列f x m k 的收敛阶为m + l ，所以这种迭代法比平常的n e w t o n 迭代能提高渐进效 率 2 当a 1 = 2 a 。一a 。f 7 扛n + 1 ) a 。，即 2 第一章综述 茁。+ 1 = z 。一a 。f ( x 。) ， a 。+ 1 = 2 a 。一a 。f 7x 。+ 1 ) a 。，v n n i x = 里a o 任意指定，使之接近于f 7 ( t o ) 这种迭代法称为避免二阶导数求逆的变 形的n e w t o n 法其原理是借鉴当年没有除法硬件的计算机中求导数的迭代法以 求f ，( z 。) 的逆尽管避免导数求逆的变形n e w t o n 法求得解的速度比n e w t o n 法稍 慢，但是它不用求导数的逆，并且仍能保持2 阶收敛 3 当a 。= f 7 ( 厶) ，厶比z 。有一个适当的超前量： x n + 1 = o n 岛+ 1 = 厶一 一f 7 ( 矗) _ 1 f ( 茁。) ， ；f 7 ) f ( x 叭) 称为导映照超前计值的变形的n e w t o n 法( 1 2 ， 1 3 1 ) ，最早由r f k i n g 和w w e m e r 先后提出的，所以也称为k i n g w e m e r 迭代它没有增加计算量，但收敛 阶却从2 提高到1 + j 若令厶= ( z 。+ 鼽) ，得到变形的n e 叭o n 法： z n + 1 = z ” ! n + 1 = z n + 1 f ( ! 学) f ( x 。) ， f ，( ! n 产) 。f ( z 。+ 1 ) 以上讨论的非线性算子f 是可导算子，若f 是不可导算子时，以上迭代法便不能使 用现把f 分成两部分，一部分可导记为h ，另一部份不可导但李普希兹连续记 为g ，因此求解非线性方程f ( x ) = o ，变为求解方程 日( 口) + a ( z ) = 0 j 吆n e w t o n 迭代法：z 。+ 1 = z 。一f 7 ( z 。) - 。f ( x 。) ，相应地变为 x n + l = 。爿7 ( z 。) 一1 ( h ( z 。) + g ( z 。) ) ，n = 0 ，1 ，2 对于后者文献( 1 4 1 ， 1 5 ) 进行了讨论，并建立了相应的收敛理论 自从迭代法问世以来，许多迭代法的收敛性条件一直是人们关注和数值工 作者研究的核心和重点 对于n e w t o n 迭代法的收敛性，k a n t o r o v i c h 最先提出了它的收敛性条件，成 为计算数学的研究中心和研究起点，g 口k a n t o r o v i c h 型收敛条件其他迭代法的 收敛性条件也都是由它拓展开的，他给出的收敛条件为： 第一章综述 ( 1 1 假定f 是由b a n a c h 空间x 的一个非空凸集q 到同型空间y 的f r e c h e t 可微算 子 ( 2 ) r ；j 于点z o q ，假设f 7 ( z o ) - 1 存在，并且满足| jf ，( ) 一1 f ( x o ) i f a ( 3 ) l lf ( z o ) 一1 ( f 7 ( 茁) 一f 7 ) ) l i bl lz yi i ， 茁，y q ( 4 ) a b sj 1 ( 5 ) 取i 丽q ，其中r = 生出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 ) 也发生 相应的变化 王兴华( 【3 】) 引进的关于l 平均的l i p s c h i t z 条件对半局部收敛性理论的研究产 生了重大影响，它将k a n t o r o v i c h 条件与s m a l e 的条件统一了起来( 3 7 ) 在一阶导数的l i p s c h i t z 条件中： 当l ( “) ：k 时为k a n t o r o v i c h 型条件； 当l ( 乱) = 2 7 ( i 一1 “) 一3 时为s m a l e 型条件； 当上= p k t p _ 。，p ( 0 ，l 】见文献( 1 6 ) 作为特例 另外，a p p e l ( 1 7 ) 和a r g y r o s ( 1 8 ) 用一个给定的实函数u ，使f ，满足 f 7 ( z o ) 一1 ( f 7 ) 一f 7 ( 可) ) 0 “( i | z 可l i ) v x ，y n 但是，该条件具有局限性 对于二阶导数l i p s c h i t z 条件，如( 3 7 】) 所述 j | 1 厂7 ( z i l ) ，”( z 0 ) l i57 ， il i f 7 0 i 1 ) ( ，”( z ) 一，”( 茁7 ) ) sc i l 茁一z 7 王兴华首先在讨论班上指出收敛的判定界，即 f o2 再丽2 6=黟3(-+、 2 + 2 f ) 2 利用这个判定界，韩丹夫、黄正达、梁可维等在k a n t o r o v i c h 型条件下研究了不 少具体迭代法的半局部行为 王和郭的文章( 【1 9 1 ) 将( 3 1 ) 中的条件和唯一性定理的条件加以了统一，存一 股的条件下，给出了方程( 1 1 ) 的解的唯一性及n e w t o n 法的收敛性定理 a 唱y r o s 在文献( 2 0 】， 2 l 】) 中提出了下面的两个收敛条件： 4 第一章综述 ( 1 ) ( a ) | | f 7 ( z o ) - 1 f ( x o ) 怪q ( b ) l if ，( z o ) _ 1 f ( ( z o ) jj o t ，i = 2 ，m ，m 2 ( c ) | 1f 7 ( z o ) 一1 f ( m ( z ) 一f ( m ( z o ) 】i | q m + 1 | | x x o1 1 ，v z n ( d ) p ( s ) = 焉葺奇s “+ 1 + 鬻s ”+ + 譬s 2 一s + qs 0 ， 卵0 ，。20 ，o l 2 o ，m 2 ，3 i m + 1 ，s 叩 ( 2 ) ( a ) o 0 ( c ) ljf 7 ( z o ) 一1 7x ) 一f i ( z o ) j j dj iz z o 玑峙k q ( d ) 2 a ks1 ，其中k = m a x c ，6 + 2 a d ， 或满足，( ) = t 3 2 d r 2 一( 2 d b 2 ) t + 2 d ( b + a d ) 的两个正根h ，也， b ，b + 2 b d 七1 ，k 2 ，那么三c ，k b ，b + 2 a d 对于其他迭代法的研究不象研究n e w t o n 法那么繁多，它们大都是从n e w t o n 迭代法的收敛条件中加以拓展的，下面列出几个三阶收敛的迭代法的收敛条件： ( 1 ) ( a ) 对于点q ，假设f ( z o ) q 存在 0 0 ) 1 lf 7 ( 。o ) 一1 ( f ”x ) 一f ”扫) ) i l 尼| | z y 叭茁，y q ，0 ( c ) | | f 7 ( 黝) q f ( x o ) 临a ，| if 7 ( ) _ 1 f ”x o ) 临b f d ) z 次多项式 p ( t ) = ；t 3 + ! t 2 一t + 。 有一个负根和两个正根， 0 洧两个正根，k = 0 或满足 ( 2 ) ( a ) 对于点z o q ，假设f x o ) 一1 存在 ( b ) i if ”( 。) | | m ，l if ”( z ) 一f ( 可) 0 i iz y ，v x ，y q ( c ) | jf 7 ( z o ) 一1j 卢，| | f 7 ( 。o ) 一1 r ( x o ) l i 叩 ( d ) ( m 2 + 丽2 n ，z 1 _ 自，h = 七卢叩 不同的迭代法对( 2 ) 中的( d ) 有不同的形式，j 2 酬h a l l e y 迭代的收敛条件 或满足 5 一 第一章综述 ( 3 ) ( a ) 对于点x o q ，假设f 7 ( z o ) _ 1 存在 c o ) l if 7 ( z o ) 一1 f ( 。o ) l i 茎卵，| | f 7 ( z o ) 一1 f ”( x o ) l l 2 7 ( c ) l lf 7 ( z 。) 一1 f 7 ”( z ) 1 | i i 岛，v z q ，i iz z 。l l ( 1 一去) ； ( d ) h ( ) = ”一t + 丁兰，当q = 叩7 3 2 讵时，函数有两个根， 除此之外，还有很多数值工作者在研究新的更好的三阶收敛的迭代法的收 敛条件，以及更高阶的迭代法的收敛条件 证明迭代法的收敛性的一个很好的技巧是优函数技术，这是k a n t o r o v i c 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 + 叮 后来也有人用它证明三次收敛的迭代法的收敛性( 2 2 ) ，但是与三次多项式相比 它就显得有些欠缺，在证明二阶和三阶收敛的迭代法的收敛性时，三次多项式是 比较常用的优函数( 【2 3 】， 2 4 ， 2 5 1 ) p 2 ( t ) = 3 t 3 + t 2 一t + 叩 在证明h 6 l d e r 条件下的迭代法的收敛性时，优函数变为实函数证明l + p 阶收敛 时，用的优函数的形式为 p 3 ( ) = 南1 + 9 一t + q 证明具有2 + p 阶收敛时，优函数的形式为( 2 6 ) p 4 ) = 石桶产+ p + i t 2 一t + 叩 有理多项式也是证明各种迭代法收敛的一种比较好的优函数，它的形式为 p 5 ( t ) = 叩一t + 禹 它是s m a l e 提出由王兴华和韩丹夫完全改进，而后被应用证明各种迭代法 在s m a l e 点估计判据下的收敛性( 王和韩的 2 7 】， 2 8 1 ) 另一种证明迭代序列收敛的技巧是递归法对此，g u t i e r r e z $ 口h e m a 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 迭代年1 j a r r a t t 型达代的收敛性进行 了一系列的研究工作( 2 9 ， 3 0 1 ， 3 l 】) 最近许多数值工作者在尝试不同的更好的 证明方法 6 第二章解多项式方程的修正r 顿法的改进 第二章解多项式方程的修正牛顿法的改进 2 1 引言 设有多项式方程 - 厂( z ) = x “+ a n - i x ”一1 + + a l x + a o( 2 1 ) 其中n 是多项式方程的n 个根，且n 7 j ( i j ) 众所周知，多项式方程的求解有很多应用背景对于多项式的迭代求解已经 有丰厚的成果，特别是王兴华等人的论文( 3 2 1 ， 3 3 1 ) ，对多项式零点的求解理论 开辟了新的领域，作出了巨大的贡献，这方面的研究可见( 3 4 l 3 5 1 ， 3 6 1 ) 在王和李 的( 3 7 ) 这篇综述l 卜就有多种迭代方法对多项式的整体行为的相关讨论，这篇文 章也是王和其他专家对于迭代法的局部行为、半局部行为和，为多项式时的整体 行为的研究进展及其在非光滑优化中的应用的回顾 牛顿法是一种常见的数值迭代方法，大量文献讨论了牛顿法的各种改进，包 括用于求解多项式方程时的变形 解多项式方程( 2 1 ) 的牛顿法为： z ? + 1 = 。；一，7 ( z ? ) 一1 ，( z ? ) ，i = 1 ，2 ，n ，k = 0 ，1 ， ( 2 2 ) 牛顿法具有二阶收敛性，文【3 8 】对其进行变形为： 吒k - r l 一_ _ h 怒1 _ 怨，磊；去 ( 2 3 ) 此式是没有用n - 阶导数且三阶收敛的迭代法，此迭代式同样可同时决定多项 式方程的全部单根，且比牛顿法的收敛速度更快，在计算机上的算法实现也较容 易 文【3 9 】又进一步讨论y ( 2 3 ) 的一种修正牛顿法的收敛性，其迭代法如下介绍： 记 丐k = 巧k 一怨 ( 2 4 ) 第一章解多项式方程的修萨牛顿法的改进 现将( 2 3 ) 式中的苟用蝣代替，则得到进一步改进的牛顿法 矿1 罐一 怨】 一髂，塞。南 ( 2 s ) 事实上，此迭代法是由迭代式( 2 3 ) 与牛顿法结合产生的，先比较( 2 3 ) 式 和( 2 5 ) 式，无论这两个式子中的哪一个都需要计算等基的值，有了这个数值， 用( 2 4 ) 式求钆的数值就很方便，而且这是每一步迭代的主要计算量，所以( 2 5 ) 式 的计算量几乎没有增加，但是它的收敛速度却提高了一阶，由原来的3 阶提高 到4 阶本文还是从“? 出发，将对它进行另一种变形，也就是用c h e b y s h e v 迭代法 对( 2 3 1 式作一次改进 现记 其中 谚= 巧k 一( 1 + 上，( z ；) ) ，( z ；) 一1 f ( x k ) l ，( z ；) = ，协；) _ 1 ，”( 苟) ，；) - 1 ，( z ；) 现将( 2 3 ) 式中的z ；用劣代替，得到另一种改进的牛顿法 ( 2 ，5 ) ( 2 7 ) 吒k + l 叫一硒m 1 仇t 一鸽，塞。去 仁s ， 事实上，此迭代法是用c h e b y s h e v 迭代法对( 2 3 ) 式中的z ；作了一次修正，即( 2 8 ) 式 是1 t ( 2 3 ) 式同c h e b y s h e v 迭代法结合产生的，此迭代法的收敛速度比( 2 5 ) 式还要 高，而且在计算机上的算法实现也较容易，下面将讨论此迭代法的收敛性及其证 明 2 2 主要引理 现将( 2 8 ) 式两边同时减去n ，将( 2 8 ) 式改写成 b 一羔b ； 其中磁= 。：一r i ，i = 1 ，2 ，n ，k = o 1 ( 砖一n ) ( q 一毋kj j ”t k r d ( x ? 一劈) j = 1 j t 一8 一 ( 2 9 ) 第二章解多项式方程的修正牛顿法的改进 引理2 1 设西通过以下迭代得到 ( 2 1 0 ) 毋= x j 一( 1 + l f ( x j ) ) f 7 ( q ) 。1 f ( z i ) 其中l i ( x j ) = ，协) - 1 f ”( x j ) f 7 ( q ) _ 1 ，( ) 则存在与j 无关的常数m 0 ，5 o ，且满足m 6 2 0 ，m j 0 ，且有霹 1 ，当l q r j i 屯时，有 g j r j ism j x j q 1 3 现令m2 燃。 m j ) ，62 勰 岛) ，j t n 2 = m 5 2 2 ( n 一1 ) 其中m ，6 为引理1 中确定的数，n 是多项式方程的次数 下面定理及其证明中的s ，d ，i n ，5 由引理2 1 ，2 2 确定 第_ 二章解多项式方程的修正十j i 顷浊的改进 2 3 主要结果及其证明 定理2 1 当迭代初值司0 = 1 ，2 ，n ) 满足i z ? 一qj ；时，且n 个根所在的 邻域是两两互不相交的，则由( 2 8 ) 式产生的序列 苟) 器。收敛于吩，且收敛阶至少 为5 证明：由题意知 由引理2 1 知 i 掣l z ? 一吩l = = i z ? 一7 1 曼! d ， i z ? 一n + r 一q l ! d q 一鳄l 茎mj z ? 一0 1 3 茎基拳= ； 其中鳄为选初值。? 进行c h e b y s h e v 迭代得到继而有以下式子成立 由式( 2 1 0 ) 可得 令 鳄一z ? l l 鳄一吩+ o r + n z ? l 气呈d 矧，塞i 簧墨，塞；高两2 显然0 q 1 ，从而有 p = 耳可n - i 面1 ，q = 6 ， 碰1 i 端嘲曼q l b 。l ； 互 我们假设i 磷f ；，( i = 1 ，2 ，n ) 成立，即z ? o ( q ，其中迭代次 数0 ，贝0 由日i 理2 1 矢口 所以有 。一劣ls m i 。；一q 1 3 l o 第二章解多项式方程的修正牛顿法的改进 矧j = l d # 。蔫互1 亿 l 矽1 i 踽l 磷l q l b ? 茎。d ( 2 1 2 ) 即有。+ 1 o ( r - j ，6 ) 成立由数学归纳法知，对于任意迭代次数，( 2 1 1 ) ， ( 2 1 2 ) 式总成立 反复利用( 2 1 2 ) 式得 l 讲l q i b 一1 i g l 霹j ：q 因为o q 1 ，所以i 磷i 一0 ，当七一o o 时即 z ；一r ，( i = 1 ，2 ，n ) 记 刚2 m 。a x i b ：l = 0 ，l ，) ， 则由f 2 1 0 ) 得 i a ：i 若箱i b 1 4 所以 l 磅+ 1 i 啬管錾例5 故( 2 8 ) 式至少是5 阶收敛的，证毕 由此可知对z ；用c h e b y s h e v 迭代法作一次修正，引算量没有增加多少的情况 下，收敛阶却至少提高2 阶 对迭代式( 2 8 ) 应用g a u s s s e i d e l 技巧可以得到 矿1 刊一鹅 1 一怨( 蕃i - 1 南+ 。塞。砑1 ) 】仨 将( 2 1 3 ) 式改写成 第二章解多项式方程的修正1 ：顿法的改进 其中 ( z ? ( z ? 定理2 2 当初值满足 b = 蕞艘 。? 一r i i 10 = 1 ，2 ，n ) r 2 1 4 ) 祟 ( 2 1 5 ) 9 7j 迭代式( 2 1 3 ) 收敛于n ，且收敛阶至少为5 i t n ： 当初值满足f 霹l = i 司一r j ：0 = 1 ，2 ，n ) 时，由于在迭代求 解z 时并未使用g a u s s s e i d e l 技巧，所以由定理l 的证明知 b i q l b 2 q 由定理1 证明中的式子确定 假设1sjsz l 时j 目i 茎q f b y f 成立，则利用引理2 1 ，引理2 2 不难得出 郎霎高等+ j 塞= i 。 由此得 因此对j = l ，2 ，n 均有 蔫2 ) d 高8 南2( s 一1 ) ( s 一2 一( 一1 ) ( s 一) b j f 茎q i b ? l ， f 磅isq l b y l j 由类似于定理2 1 中的数学归纳法总有 磁l 墨口i 骘一1 1 ； 1 2 f 2 1 6 ) 吁一砖m hn 一巧 二一 可 。讲盟圹 二 q 一哆h hn 一0 “赳 = 第一章解多项式方程的修正午顿法的改进 上式对任意整数0 均成立 反复利用( 2 1 6 ) 式得i 谫l ：矿，令一o o 得骘一o ，即苟一吩j = 1 ，2 因此收敛性得证 下证收敛阶，与上式类似得 进而 故有 钟l o ，使得 在( 0 ，i ) 上 似) 0 证明由 协) = l t 一1 令f = ，则f 即为所求 引理3 2 设f 如引理3 1 所述， z b ( 茁+ ，i ) ，t = i | 一z i i | | f 7 ( z + ) _ 1 f 7 ( 。) 一f 7 净) 】| | lf 7 一zl ，v x ，z 7 b ( 矿，i ) ， ( 3 4 ) , l j f 7 ( z ) - 1 存在， l if ) 一1 f 7 ( z + ) 0 一f l 7 0 ) 一1( 3 5 ) 证明：由假设及引理3 1 有 l i 一f 7 ( z + ) 一1 f ( z ) 1 i = 1 lf ( z + ) 一1 i f 7 ( z + ) f ( z ) | 】 sll lz z + i l = 1 + h t ( t ) 1 故v h b a n a c h 引理知f ，( z ) _ 1 存在，且 f lf ( z ) 。f ) 1 1 可再书p 丽s 一( ) 。 证毕 引n 3 3 设y ( x 4 ) = 0 ，z 口( 。+ ，矿) ，其中r 是关于t 的方程t + t 2 一 l t h 协) 一 2 = i 在( o ，f ) 上的唯一解，t = | i 。一x + | | ，则 | | ，协) _ 1 f ( x ) 怪 2 一l t h 讹) _ 1 】， h ( x ，y ) j i 一百l 7 0 ) 一1 2 一l t h ( t ) 一1 】 第三章避免二阶导数计值的迭代族的收敛性 证明： f ( x ) = f ( x ) 一f ( x + ) = f 7 ( z ) ( 。一。+ ) + 詹 f 7 ( 。+ + r ( z z + ) ) 一。f ( z ) d r ( z z 4 ) 故由( 3 ，4 ) ，( 3 5 ) 有 | | f 7 扛) 一1 f ( x ) l i = 1 lz z + + 詹f 7 ( z ) 一1 f 7x + + 7 _ ( z z + ) ) 一f 7 ( z ) d r ( z z 4 ) | | 。一z + | | + 詹f if ( z ) 一1 f ( x + ) if 7 ( z + ) 一1 f 7 扛4 + 7 _ 扛一z ) ) 一f 7 扛) 】 d 7 _ | i2 9 一矿| | 茎| | x z + j l 一 7 ( ) 一1 l 层0 ( 1 r ) ( z 一。+ ) | | d r | | 。一z + l = t h m ) 1 鲁t 2 = ； 2 一l t h 心) 。】 再证下式 所以 h ( x ，y ) = f 7 ( z ) 一f 7 ( z + ) f 7x + ) 一1 f ( z a f ( z ) - 1 f ) ) 一f 7 ( 。) 】 | | z a f 7 ( z ) 一1 f ( x ) 一z + | | 1 l 。一x + i i + a | if 7 ( z ) 一1 f ( x ) i i t + 入( 亡一号t 2 ( t ) 一1 ) f i if 7 ( z + ) 一1 f 7x 一凡f ) 一1 f 扛) ) 一f 7 忙) 】i i ll i 九一 ) 一1 r ( x ) i ih ( x ，) 0 一0 ) 一1 l i t 一譬h 7 ( t ) 一1 】 = 一考t 危也) 。1 ( 2 一l t h 心) 1 ) 则引理3 3 得证 记 厶( ) = 2 + a l t h 俅) _ 1 ( 2 一l t h ( t ) _ 1 ) t o ，f ) ( t ) = 一九 ) 一1 譬一 ”) 一1 坐铲 t o ，尹) 尹 于 引理3 4 设f 和矿分别如引理3 1 和引理3 3 所设则 ( i 耽( 玎有最小正不动点； ( i i ) r 。 矿； 第三章避免二阶导数计值的迭代族的收敛性 即有 现设 ( i i i ) 当t = i lx x + i | 时，l la h ( x ，可) i l r + u ( t ) = t + j 2 一l t h ( t ) 一1 】，t ( 0 ，f ) 取o t = ( 3 3 v 悟) 3 ，并注意到f = 1 l ，则有 u ( 口f ) = f ( 2 n + 南) = f 故u ( n f ) f ，从而r + ( 0 ，n 补由u ( 广) = f ，可得 则有 2 一l r + h 7 ( r ) 一1 = 2 ( 暑一1 ) ，一九( r + ) 1 五= i 一2 r + m ( r ) = f 一2 r 一2 l r * - 生l q - a l l ( f - r * ) 芝i 一2 r + + 幕蔫 下面证明上式最后一项大于r + ，先考虑不等式 1 9 第三章避免二二阶导数计值的迭代族的收敛性 可知此式等价于 由于 f 一2 t + 丽l ( e - t ) 2 ，t o ，f ) ( 3 6 ) 9 ( t ) = f 一3 t f l t + 3 l t 2 + l p 一) 2 0 ， 【0 ，f ) 9 ( t ) = 一3 一f 上+ 6 l t l ( f t ) 矿( t ) = 6 l + l = 7 l 所以在( o ，i ) 上，9 ”( t ) 0 ，故9 协) 严格单增：而9 7 ( o ) 0 ，因 此存在唯一的t o ( 0 ，i ) ，使得9 ( t ) 在 o ，如】上严格单减，在 f o 司上严格单增由 于g ( f ) = o ，所以在 t o ，i ) 上9 ( t ) o ，故有矿a f o 从而= 矿时，( 3 6 ) 式成立，得到p 。( r + ) r ( i i i )f h ( i ) 的证明知，当t = i ix 一矿i l r 。 尹时，于是由引理3 _ 3 的两个不 等式得到 a h ( z ，口) 临鼍笋 1 由此引理3 4 得证 3 3 主要结果及证明 定理设x ，y 是b a n a c h 空间，d 是x 的非空凸集，f 是空间d 到同型空间y 的非 线性算子，假定f ( 茁) 满足( 3 4 ) ， t f ( x 4 ) = 0 ，是p 。( t ) 的最小正不动点，$ 1 j v x o b ( + ，r 。) ，由( 3 3 ) 式产生的序列 。) 2 阶收敛于方程( 3 1 ) 的唯一解z + ，且有 其中 z 。一z + l i q 2 “一1 | | x o x + | | n = 0 ，1 ，2 ， ( 3 7 ) g = 潭，如= 1 1z 。一矿。 ( 3 8 ) 证明：由于t o ，故由引理3 4 的证明得 第三章避免二阶导数计值的迭代族的收敛性 a = 、掣 、掣划 现用数学归纳法i 正n ( 3 ，7 ) 式成立，从而t ，。= | | z 。一z + l f h ， v n 1 当n = 0 时，( 3 7 ) 式显然成立 先假设( 3 7 ) 式对n 成立，下证对n + l 也成立 由f 3 3 ) 式及t a y l o r 公式得 z n + 1 一x + = x 。一矿一f 7 ( z 。) f ( x 。) + 去f 7x 。) 一1 i f 7 ( z 。一a f 7 ( z 。) 一1 f ( x 。) ) 一f ( z 。) 】 1 + a h ( x 。，) r 1f ，( z 。) f ( x 。) = 爿f 7 ( 。) 一1 f 7 ( g 。) 一f 7 扣+ + r ( z 。一矿) ) d 7 - ( z 。一矿) + 去f 7x 。) 一1 f 7 ( z 。一a f 7 ( 。) 一1 f ( x 。) ) 一f 7 ( z 。) ，+ a h ( x 。，蜘) -