（计算数学专业论文）高阶收敛的修正chebyshev方法.pdf

摘要 本文共分四章，在第一章中概述了多项式方程求根的发展历程，总结了产 生并行迭代的几种主要方法。 第二章，利用d u r a n d k e r n e r 逼近对c h e b y s h e v 方法进行加速，在此基础上 引入一个修正项，从而推出一个5 阶收敛的方法 磊=磊一堕等玉牟瓣，i=1,-1 g 1 , iw g ，n 却一唧 ( +) 3 +3 ， 并给出了它的收敛阶证明。 第三章，在对一类迭代法的收敛性作出分析的前提下，具体给出这种方法 的初始收敛条件，该条件仅依赖于多项式方程的系数、次数和初始逼近点。 第四章，将该方法推广到整个h a n s e n p a t r i c k 族，并给出收敛阶证明。文章 的最后，我们给出了两个数值例子，验证了本文推出的方法具有较高的收敛阶和 计算效率 a b s t r a c t t h i st h e s i sc o n s i s t so ff o u rc h a p t e r s i nc h a p t e ro n e ，w eo f f e ra g e n e r a ls u r v e y o ft h es i m p l eh i s t o r i c a lp r o c e s so fs e l v i n gp o l y n o m i a le q u a t i o n s ，a n ds u m m a r i z e s e v e r a lm a i nm e t h o d so fs i m u l t a n e o u si t e r a t i o n i nc h a p t e rt w o ，b yu s eo fd u r a n d k e r n e ra p p r o x i m a t i o n ，w ec o n c l u d eam e t h o d o ff i v eo r d e rb a s e do nt h ea c c e l e r a t e dc h e b y s h e vm e t h o d 磊= 乏一旦笔；牟专i 锹，t = ，n a n dg i v et h ep r o v e rf o ri t sc o n v e r g e n c eo r d e r i nc h a p t e rt h r e e ，u n d e rt h eg e n e r a la n a l y s i sf o ri t e r a t i o nm e t h o d s ，w eg i v ei t s i n i t i a lc o n v e r g e n c ec o n d i t i o nc o n c r e t e l y , w h i c hd e p e n d so n l yo nt h ep o l y n o m i a l c o e f f i c i e n t s ，i t sd e g r e ea n di n i t i a la p p r o x i m a t i o n s i nc h a p t e rf o u r ，w ee x t e n dt h em e t h o dt ot h eh a n s e n - p a t r i c kf a m i l y , a n d g i v et h ep r o v e rf o ri t sc o n v e r g e n c eo r d e r i nt h ee n d ，w eg i v et w on u m e r i c a l e x a m p l e s w h i c hv a l i d a t et h em e t h o dw i t h1 1 i g ho r d e ra n dc o m p u t i n ge f f i c i e n c y 第一章绪论 计算数学中，求解多项式方程的问题占有相当重要的地位。数学的各种现 代理论如：系统控制论，系统稳定性，非线性环道，转换函数分析，数学模型， 微分差分方程，特征值问题等都体现出多项式求根在理论研究和实际应用中的 重要性。但基于g a l o i s 工作( h e m t e m ，1 9 6 4 ，第5 6 节) 的一个著名结论是：次数5 的一元多项式方程不存在直接方法求根，即其根一般不可能由多项式系数通过 初等函数的形式表达出来。事实上在实际应用中我们需要的多为满足精度要求 的数值解，而不一定要求得根的解析表达式。鉴于此，求解多项式的迭代方法 成为一类广泛应用的数值计算方法。 设，( z ) 是首项系数为l 的具有几个相异复根6 ，厶的n 次复系数多项式， 即： n f ( z ) = 。”+ a n _ 1 z “一1 + + 0 1 z + a o = l1 0 一白) ( 1 1 ) j = l 求其根的迭代方法可分为：单步迭代、多步迭代以及圆盘迭代、并行迭代等，其 中几种代表性的迭代法有超线性收敛的割线法、经典的二阶收敛的n e w t o n 迭代 法、三阶收敛的h a l l e y 迭代法和c h e b y s h e v 迭代法、四阶收敛的j a r r a t t 型迭代法 等等。 由于逐个地求复多项式全部零点所存在的固有困难【1 】，并行迭代法，即同 时求解多项式方程全部零点的迭代法日渐受到重视 2 5 1 综观数学家们得出的研 究成果，最重要的三种产生并行迭代的方法是： 其一是采用圆盘迭代方法。自n i c k e l 2 在1 9 6 9 年提出在复平面上用复 圆盘代替复区问的建议后，寻求复方程解的圆盘迭代法得到了发展。首 先h e n r i c i 和g a r g a n t i n i 3 - 6 并i j 用圆盘算术，对寻求复多项式的零点问题提出 了一些很有实际意义的圆盘迭代法。由于他们一系列卓有成效的工作的 影响，相继出现许多好的算法，如圆盘l a g u e r r e 方法，圆盘s c h r o e d e r 方法以 及b r a e s s 、h a d e l e r 和p e t k o v i c 等利用高阶插值为工具导出的圆盘迭代方法( 见 王德人| 7 1 ) 。王兴华等 8 】为了进一步提高以上算法的收敛速度，提出了圆 盘h a l l e y 法，并给出文【3 】中算法的收敛性条件1 9 】。2 0 0 4 至2 0 0 5 年间，朱灵 1 0 - 2 高阶收敛的修正c h e b y s h e v 方法 1 3 】又巧妙地运用不等式，针对圆盘d u r a n d - k e r n e r 方法和圆盘s c h r o e d e r 方法， 提出了更好的初始收敛条件。 其二是直接构造法。国内有王兴华等 1 4 - 1 6 在1 9 8 5 至1 9 9 0 年间提出了一 系列的快速并行迭代方法，其中他们利用b e l l 多项式对h a l l e y 迭代族进行 并行化改造所形成的迭代族在诸多并行迭代法中最为系统和丰满，并 被作为l e c t u r en o t 器i nm a t h e m a t i c s ( 1 3 8 7 ) 1 7 e p 第五章的基本内容。国外 有w e i e r s t r a s s 1 8 在1 8 9 1 年所提出的二阶收敛w e i e r s t r a s s 并行迭代方法： 磊= 荔一w ；，i = 1 ，2 ，n ，( 1 2 ) 此处 职2 躺， ( 1 3 ) j t 而五表示对6 的逼近，磊是指对g 的新一轮逼近0 = 1 ，2 ，n ) 。为简便起 见，本文中的兀，n ，全部用，兀，代替。这个方法 又不断被d u r a n d 1 9 ( 1 9 6 0 ) ，d o c h e v 2 0 ( 1 9 6 2 ) 、和k e r n e r 2 1 ( 1 9 6 6 ) 重新发现。因 此该方法也称做d u r a n d - k e r n e r 方法，或简称为d - k 方法。此后，人们对d u r a n d - k e m 臼迭代法进行加速，得到更高阶的没有导数的并行迭代方法。其中比较有 名的有b s r s c h - s u p a n 2 2 】和n o u r e i n 2 3 提出的 吲舶一嚣扣1 ) 柚( 1 4 ) 以 f 1 n o u r e i n 2 4 稍后提出的 毫“) ：z 一_ _ = 簪，t ：1 ，几( 1 5 ) 1 + 至再鳓 ，t 1 ”、7 其三是由已经存在的单点迭代法加上并行技巧得到相应的并行迭代方法， 这样得出的迭代法的收敛阶一般较原单点迭代的更高。王兴华和韩丹夫研究了 第一章绪论3 这个问题，并在文【2 5 1 中给出一般性的并行化技巧：设，为n 次首一多项式，那 么这个生成方法是把给定的迭代函数依次应用于复变量翰的函数： 胍= 甜岛扣k 棚 巨袈w j ，嘲 6 ， 1 酱_ ( - 1 ) l _ 丢网，嘲 u 。6 最近，文献【2 6 ，2 7 】也通过n e w t o n 逼近和h a l l e y 逼近对已有的迭代方法进行加 速，得到收敛阶比相应方法分别高出2 和3 的新方法。 另外，也有的是采用子步迭代法对现有的并行迭代进行加速，得到新的并行 迭代，其基本的方法是将一步扩展成几个并行子步。这样在计算工作量增加不 多的情况下，使计算效率大大提高。或有的是综合各种方法的优点，克服其缺 点，从而大大提高计算效率。 第二章主要方法及收敛阶分析 2 1 引言 本文只考虑，( z ) 是首项系数为1 的具有n 个相异复根( 1 ，厶的n 次复多 项式的情况，即 ，( z ) = z n + a n 一，矿一1 + + 0 1 z + d 0 = i i o 一白) 卜，= 甜岛， 卜= 嘉南， 江k - ， ( 2 1 ) 卜= 磊f 南， 坼) = 眦坤叫( 1 + 两w j ) ，m ( 2 2 ) 期醐为州垆，+ 嘉南， h 7 ( 扣一z 暑尚，归1 n 将z = z i 代入上述k ( z ) ，蟛( z )醪( z ) ，得 = 1 ，n ( 23 ) 用( 2 3 ) 中的 ，( 五) ，噬( 磊) ，蟛) 分别替换经典f l c l h a n s e n p a t r i c k 族【2 8 】 乏：五一一! 竺! ! ! ! 兰! ，( 2 4 ) 五2 五一孑两= 刀霞乒雨辛丽丽 弘4 j q 岛 一一 垂游 h 6高阶收敛的修正c h e b y s h e v 方法 中的，( 乞) ，7 ( 磊) ，”) 得 客= 五一：石j j ；i 丁至弋刁辜革 ；萼拿芊i 丽，t = ，n ( z s )2 五一：石j _ 否i 丁至弋万亍军i i 翥亍军亏霞i # 彳厩。2 l “五 此即文【2 9 】中，用w e i e r s t r a s s 方法对h a n s e n - p a t r i c k 族进行加速所得到的4 阶收 敛的方法。对其中的n 取特定的值，可以得到很多己知的迭代方法： o s t r o w s k i l i k e 方法( 口= 0 ) ： 乏= 忍一一x ( 1 + g i , , 些) 2 + 2 w i g a i ，江1 ， 五2 忍一7 5 2 2 2 2 2 2 2 2 2 2 1 2 l 。n c h e b y s h e v - l i k e 方法 = 1 ) ： 2 眠 毛2 盈一( 1 + g , i ) 土g 2 ( 1 2 + 2 2 g 2 l , 2 i ) 2 22 + 2 4 2 w 2 i 0 2 2 。, i 。21 ， n l a g u e r r e - l i k e 方法忸= 击) ： ，、 2 五2 盈一石j i 丢j j _ 了虿i 三面币：f 否i 乒亏i 焉i i 巧而露。2 l ，”， h a l l e y - l i k e 方法( n = 一1 ) ： 。m ( 1 + g 1 ， ) 磊2 磊一( 1 + g 1 l , i ) 2 + 二! w 2 i g 一2 , i b s r s c h - s u p a n 方法( o _ o o ) - =一i：；=_丽wizzi ，i = 1 ，n -2 一矿，z 2 ，n - ，+ 嘉鹗 对其f i b i 拘c h e b y s h e v l i k e 方法用幂级数展开除去根号，则得到加速后的c h e b y s h e v 迭代法： 2 ：一焉w 黔i 如 1l x w , g a 彰i , ，n 仁。， = 一旦! 丛! 专辛铲，。一l 。“弘0 第二章主要方法及收敛阶分析 7 这和用( 2 3 ) 9 的乜( 盈) ，蟛) ，蟛协) 分别替换经典的c h e b y s h e v 迭代法： 磊= 磊一怒( ，+ 怒糍叶棚， ( 2 ，) 中的，( 五) ，亿) ，”亿) 所得到的结果相同。 我们来分析一下( 2 6 ) 式的收敛阶。设f ( z ) = 0 的1 个单根为c 1 ，厶；z l ，z n 为这几个根的相应迭代点。迭代产生的误差为旬= 盈一g c i = 1 ，n ) ，并 用磊= 磊一厶( i = 1 ，n ) 表示新一轮迭代产生的误差。若存在正数m ，使 得无穷小量q 和口满足仁lsm ，则称q 和p 是同阶无穷小量，并用a = o m ) 来 表示，这里o j l f 指一个与n 和卢无关的有界量。在本文的分析中，假设所有的 误差1 ，矗是同阶的无穷小量，即矗= d m ( 勺) ( i ，j = 1 ，扎) ，且e e 1 ，n ) 满足 i - 。i 旬! ，、 _ 1 ，竹 ie = o k ( 矗) ， 77 由( 2 1 1 有 g 卸峨= 嘉南+ 善再意铲 = 善芒z j ) c 去十去，i 1 棚，。2 8 ，磊( 盈一 一1 、五一勺。刁一幺7= ，n ，() ：f! 亟： 磊( 勺一6 ) ( z 一白) = k + 1 t ， 将z = 6 代入k ( z ) 有 k ( 6 ) = 0 ， i = 1 ，n ， 从而由( 2 2 ) 得 胍= e ；( 1 一) ， i = 1 ，n ( 2 9 ) 另外，由于 比比蚓婴薯，n ， t 。 8高阶收敛的修正c h e b y s h e v 方法 当磊一。时，i i 罢一1 ，所以 3 杠q 一j fm ： i g 篾k , i 三 l 至尚地， j f = 1 ，棚( 2 1 0 ) 至f 品地， 由( 2 6 ) 式 磊一g = 盈一c 一旦兰丛三专罕铲，t = ， 将( 2 9 ) 式代入，即 最一一业掣崭产 e i ( g l , i + 1 ，；+ 矗g 2 ，i + 2 g ，t + 2 e 1 ，t g l 一2 e i l l ，i g 2 + g + l _ t 研4 ) 2 丌丽习广一 矗( a + 鼠+ g ) 2 研刁i r 根据( 2 8 ) 式有 a = g 1 j + e 1 j + e i g 2 ，i = 矗2 i + e t g 2 f = 曾3 i = o m ( d ) ， 鼠= 2 研+ 2 1 t g l l 一2 e i l , i g 2 ，t = 2 ，m g f 一2 e i i e l , i g 2 f 2 1 1 1 = 2 矗( ( g 2 j + 1 ， 2 ，) 一( 1 ，i g 2 ，i + 1 i 2 ，t ) ) 、。 = 2 e ；，一2 审l ， 3 j = o m ( e 4 ) ， q = g 2 j + e 研 = e t 2 ；g ； = o m ( e 4 ) ， 第二章主要方法及收敛阶分析 9 所以，可得估计 磊= 盟鲁裂掣，n 当e 1 ，e 。趋向于o 时，分母中( 1 + g 1 , t ) 3 ( i = 1 ，n ) 趋向于1 ，则( 2 6 ) 式所定 义的迭代序列是4 阶收敛的。所以类似- 7 = 3 0 】，我们希望通过( 2 8 ) 式来提高分子 中a 的收敛阶，从而提高整个方法的收敛速度。 2 2 主要方法及定理 我们在( 2 6 ) 的分母中引入修正项h 乍g 3 ，i 推出方法 磊：盈一旦；錾兰毒善每字三掣，t ：1 ，n ( 2 1 2 ) 2 盈一i r 干t i ：= j 芋干了霄。2 l ，n 【。2 1 印 则有 定理l 若初始点z ”，毋充分靠近其相应的零点a ，厶，则方 法( 2 1 2 ) 所定义的迭代序列是5 阶收敛的 证明：由( 2 1 2 ) 式有 磊一6 = 一6 一旦等釜 亳i 涨，t = ， 将( 2 9 ) 式代入，即 6 一一业裂黯掣 矗( g l ，：+ ：， + 岛g 2 ，；+ e ；舀3 ，t + 2 研 + 2 1 。g 1 。一2 e i e l ，；g 2 ， ) ( 1 + g 1 ，。) 3 + 乍g 3 ； 岛( g 。+ l t 研，t 一2 ? 1 。g 3 t + l e j ，。g 3 ，) ( 1 + g 1 ；) 3 + w 乍g 3 ， 矗( a ：+ 鼠+ g + d i ) ( 1 + g 1 ) 3 + h 乍g 3 t 1 0高阶收敛的修正c h e b y s h e v 方法 根据( 2 8 ) 式有 戌= = - = = di= g 1 t + l 一+ e t g 2 i + ；g 3 j e t 2 1 + e i g 2 j + s ；g 3 i e ；e 3 j + e ；g 3 i ；e 4 j d m ( e 4 ) ， 一2 碍e 1 ，g 3 ，。+ 矗：，g 3 ，i o m ( e 4 ) ， 鼠和a 同( 2 1 1 ) ，将鬈，最，g ，取代入( 2 1 3 ) 式，得估计 反= 高糕一 矗2 t 丽蔚幸舞瓦一_ 1 川。 当e l ，矗趋向于。时，分母中新加的那项卵g 3 ，i a = 1 ，凡) 也趋近于o ， 而( 1 + g l ) 30 = 1 ，n ) 趋向于1 ，所以整个分母趋近1 。则 磊= o m ( e 5 ) ，i = 1 ，n 从而方法( 2 1 2 ) 所定义的迭代序列是5 阶收敛的。证毕。 第三章收敛性分析 3 1 一类迭代法的收敛性分析 大多数同时逼近多项式所有零点的迭代方法都可以写成这种形式： z ”+ 1 = z ”一c ：( z i 嘲，毋) ，i = 1 ，n ；m 0 ( 3 1 ) d 神= q ( z ”，) 被称为迭代校正项，为了简便起见，我们省略索引指 标m ，并用来表示第m + 1 次迭代所得到的相关结果。这里考虑的是g 可写成如 g ( 晌) = 揣，t - 1 ，( 3 2 ) 的迭代方法，此处只( z l ，z n ) 必须满足如下要求： 1 只( ( 1 ，白) 0 ， 2 r ( 2 1 ，) 0 ，【，) ，i = 1 ，n ， 3 f t ( z l ，磊) 伊， 其中u ( 丘) 为g 的一个邻域。 令 邪，= 筹锱蛊 s ， 引理1 3 1 】： 假设g ( z ) = 瓦之警譬丽。= 1 ，n ) ，为迭代校正，且只( z ) 满 足上述1 3 ，z i o ) ，押分别为对，( z ) = o 的零点6 ，白的初始逼近，若对于 任意i ，j = 1 ，n ；m 0 ，存在卢( 0 ，1 ) 满足： 1 i c j ”+ 1 i p i c ”i ， 2 i i 一z ，i 9 ( p ) ( j c ：( o ) 1 + i c ；( o ) i ) ，o j ) 1 2高阶收敛的修正c h e b y s h e v 方法 则迭代方法( 3 1 ) 是收敛的 证明：首先，我们定义一系列的圆盘d p ：= 乏r e + 1 ) ；i q ”m i = 1 ，n ；m 0 ，这里毫”1 和d ”就是( 3 1 ) 中新的逼近和迭代校正项。 对于固定的l 1 ，n ) ；m 0 ，我们有 d p = 2 呻一d ) ；l d 呻1 ) = 妒。) 一c 呻一c 一1 ) ；i c 神1 ) = 一c m c ! n 一c 神；l c 呐i ) c 蠢o ) ；r ：呻) ， 此处 神= l d o l + i 四1 l + + l 毯m - 1 ) i 十2 i i 假定条件2 是成立的，则根据条件1 有i d 砷l 胪l d o i = l ，2 ，；卢 1 ) 所以 r ：” i c 。i ( 1 + p + 矿+ 矿) 9 ( p ) ( i g ( o ) i + i g ( o ) i ) = r a d s i + r “岛a j ) ， 所以各个圆盘最是互不相交的，即序列 z ”) 0 = 1 ，n ；m o ) 收敛且只收敛 到多项式方程( z ) = 0 的一个零点。证毕。 3 2 记号及引理 设w 2 增m a ! x 。i w d ，d 2 l ! 。恕。判l 五一刁l o = 1 ，n ) ，几表示需要求解方 程的次数，因为n = 1 ，2 的情形很简单，下面我们讨论的都为n23 的情况。 引理2 ： 若w g d ，g = i 而1 ，n 3 ，则 ( 1 ) 曩俐 | c ：i | 1 2 0 7 0 v 旷， ( 2 ) i 眦l 寺l 磁i ， 忙1 ，n ( 3 )谚 g 玉 这里g = a ( 2 1 ，磊) 指引理1 中的迭代校正项。 证明：由( 2 1 ) 式和引理给出的条件，得估计 g = 磊尚s 学 ( ) g 1 1 + g x , i is1 + j g l i l 1 一( n 一1 1 i c ； 毗g 2 ，“ 喜鼍i 眦i ， 此即( 1 ) i z i 一l i 磊一盈 d a i w , l d a c , , d 2 7 n 3 + 4 3 4 n 2 + 2 4 4 9 n + 4 6 9 0 2 7 n 3 + 4 5 9 n 2 + 2 6 0 0 n + 4 9 1 4 磊一弓i l 磊一句i i 磊一磊l i 弓一勺 i = 1 ，n ，( 3 6 ) ( 1 - 2 a c n ) d i = 1 ，n ( 3 7 ) 鲨27n3篙459寰n2篇2600n 4 9 1 4 d ， + 一 勺 一 一磊 和 第三章收敛性分析 化) - ( 1 + w jm i i 刊= i 捕i ( 一勺) ( 瞰心刊( 1 + 萎兰) ) ， 将z = 乏代入上式，并在两边同时除以兀( 磊一弓) ，有 ， i w 一, i 刮磊刊( 1 + 尚) 疆麓i 刚铲训1 + 尚) l 疆l 罄l ( 3 8 ) 川删l + 高) l 婴l 翳i ， 姐+ 两w j 肛l h 尚+ 嘉尚l 2 卜广丽( 1 + g l , i ) 3 + w ? g 3 # + 萎尚一萎尚i = i 一等1 谶g 1 鼯h i 躺l( +， ) 2 一w g 2 ti 。象l ( 磊一乃) ( 五一句) i l f ! 垡! ! 1 2 堡堡! ! ! 竺竺堡! ! ! l + 5 - i 堕! 垒二墨2i 3 l 研刁哥c 两百_ j 十角l 酉j 丽再习l ，【l + 【仃一1 ) ( 靠j 【n 一1 ) c 篇+ 【n l j ( 东【礼一l j 乙 ( 五 、 ( 1 一( 几一1 ) c n ) 2 一( n 一1 ) 嚷一1 一a m ，( 5 n + 1 6 ) ( n 一1 )( 2 5 n 2 + 1 5 1 n + 2 2 4 ) ( n 一1 ) 、4 + 4 ) ( 9 n 2 + 1 0 1 n + 2 9 0 ) 。4 m + 4 ) ( 2 7 n 3 + 4 3 4 n 2 + 2 4 4 9 n + 4 6 9 0 ) 旦i 磊z i 一- - 弓z j 2 里1 1 + 黛z i - - z 3 i 竺惫艺川。p 。 ( 1 + 丽车舞寿高彘) ”1 ( 3 9 ) ( 3 1 0 ) ( 3 1 1 ) 1 6 高阶收敛的修正c h e b y s h e v 方法 这里( n ) = a dx e 在n = 2 0 时取到最大值，即 1 搿( n ) 2y ( 2 0 ) = o 0 4 8 6 斋， 所以 i 藏i 嘉l 眦i ， 扛1 ，n 1 l t b p ( 2 ) 由( 3 7 ) d = i 磊一弓i2 ( 1 2 a g ) d ， i = 1 ，竹， 所以 则 m i ds 2 7 n 3 + 4 5 9 n 2 + 2 6 0 0 n + 4 9 1 4 1 7 ( 1 - 2 a c , 。) o 2 06 2 7 n 3 + 4 3 4 n 2 + 2 2 9 8 n + 4 4 6 6 在n = 3 时取最大值o 0 5 5 7 1 ，则 此即( 3 ) 的值随n 的增大而减小并趋向于0 0 5 ，并 显然 w 一, l c j , i = 1 ，仡 3 3 收敛性定理及证明 设w ( o ) = 粤眵l 州o ) i ，d = 叫n 。i z 们一z 1 t n 。l i j n t ， o 定理2 若 g d ，c k = i 石1 ；可，_ n 3 ，则方法( 2 1 2 ) 所定义的迭代 序列是收敛的 证明：根据引理2 的( 3 ) w c d ji 藏l c j , 笺一 第三章收敛性分析 1 7 则对所有i = i ，竹；m 0 有 i 叫”l i 去l 叫i ， 和 c “) = j 矿”一煳 o 接下来我们证明序列唾”0 = 1 ，n ；m2o ) 是单调递减的。应用引理2 的( 1 ) 、( 2 ) 和( 3 ) 有 a i 1 2 0 7 0 谚。 1 0 0 万 5 = 2 7 l l w , i 嗽( ( 1 + g “) 2 一m g 2 ，。) 1 再虿了研否f 弋可而习 面可 ( 1 + g l ) 3 + 孵g 3 i 牙5 1 c , i 4 m + 4 ) - i 2 。7 。c 。( o i 2 兰丛鼍手型( 1 c j i + j c j m = 1 ，几 三学 3 7 8 9 ( 0 脚) 2 8 0 1 2 ， z 一弓o l d ( o ) 9 ( 0 6 4 a ) ( i c l i + i c j 。i ) ， i = l ，n = t a d & + r a d s j ， 因此各圆盘s “= 1 ，扎) 是互不相交的，这样便证明了引理2 的第二个条件， 因而方法( 2 1 3 ) 所定义的迭代序列是收敛的。证毕。 注：其实，对于确定的n ，因为文中的a 和e 是随n 递增的数，而b 和d 是随礼 递减的数，定理中的参数c ：还可以取得更好些。本文为了给出一个完整的证明 第三章收敛性分析 1 9 过程，将g 统一取为而经过具体计算，g 可取为如下表中的值 l n c i 1 0 2 14 n + 6 7 9 ，2 2 n2 6 4 n + 5 5 ，6 ，2 7 3 0 4 n + 4 4 ，3 1 3 4 4 n + 3 3 3 5 3 74 n + 2 3 8 3 94 n + 1 4 0 4 n 第四章方法的推广和数值实例 4 1 对h a n s e n - p a t r i c k 族的推广 如前所述，h a a s e n - p a t r i c k 族可以表示为 ( n + 1 ) m ， 磊2 盏一：石j = _ 否i 了：_ 了币f f 雹i i 手干亏霞亍军彳丽一2 l ，。，n 设t t = 可学虽，i = 1 ，则由( 2 1 。) 岛= o m ( d ) 类似c h e b y s h e v 方 法，对于h a n s e n - p a t r i c k 族，我们引进的修正项为 推出方法( b 1 ，n ) z 42 五 = 盈一 ( 口+ 1 ) 孵g s 一杀南 定理3 若初始点2 p ，拶充分靠近其相应的零点( 1 ，厶，则方 法( 4 1 ) 所定义的迭代序列是5 阶收敛的 证明 设z 是一个复数且满足l z i 1 ，根据幂级数展开，有 订再= 1 + ；一百z 2 + 和雨1 = 1 一z + z 2 一z 3 + ， ( 4 2 ) 高阶收敛的修正c h e b y s h e v 方法 由方法( 4 1 ) ，并用( 4 2 ) 对其中的t 。进行幂级数展开，有 五2毛一(1+gl,i)(a+1+(a+1)tl。二+om(t2i)+(a+1)w2g卫s,i(1 1+tiot ； ( + 1 ) 嗽 可 嗽 一意( 1 。一w v 2 , i 慨) ，n = 磊一可w i ( ( 砭1 + 砑g l , i 可) 2 - 丽w i a _ z i ) + ( e 5 ) ， 上式带有大括号的部分已在定理1 中证明了是5 阶收敛的，因而整个迭代序列 是5 阶收敛的。证毕。 4 2 数值实例 本节，我们给出两个数值例子，它们的计算结果验证了本文推出的迭代方 法( 2 1 2 ) 具有较高的收敛阶和计算效率。 例1 ：设 ，( z ) = z 9 - 4 - 3 2 8 3 2 7 9 + 3 2 5 + 9 2 4 + 9 9 2 3 2 9 7 2 2 1 0 0 z 一3 0 0 ， ( z ) = 0 的零点为一3 ，4 - 1 ，：t ：2 i ，士2 士i 选取的初始值为一3 3 + 0 2 i ，一1 2 0 瓤，0 2 + 1 孔，一1 - 8 + 1 跏，- 1 8 一o ，7 i ，2 3 + 1 2 l ，1 8 一o 孔，1 2 + 0 瓢，0 2 2 3 i 计算结果如下表( 其中e ( ) = 粤8 磊l 乏一0 i ) ： l ( i 9 。 ke ( ) k = 10 1 9 0 4 七= 20 0 1 5 9 k = 31 1 5 0 1 e - 0 0 4 k = 46 7 3 4 3 e - 0 0 9 k = 51 1 1 0 3 e - 0 1 6 第四章方法的推广和数值实例 例2 ：设 f ( z 1 = 一一1 ，( z ) = o 的根为a = l ，已= 一1 ，( 3 = l ，( 4 = - 4 选取的初始值为z o ) = 0 5 + 0 5 i ，毋1 50 鼠，毋= 0 3 5 + 1 6 5 i ，眢= 0 2 6 0 6 6 i 计算结果如下表( 其 中e = l 舢一岛1 ) ： k e e 手e 字e 乎 k = 1o 3 4 8 00 3 7 1 50 2 8 9 40 3 1 5 7 k = 20 1 7 0 60 1 7 6 70 3 9 2 40 2 7 6 7 k = 30 0 6 1 90 0 4 4 70 ，0 5 8 60 1 0 7 6 k = 40 0 0 6 3 0 0 0 4 4 0 0 0 6 40 0 1 4 9 k = 57 6 7 5 0 e _ 0 0 55 0 9 4 2 e - 0 0 58 0 6 8 缸0 0 51 9 4 3 9 e _ 0 0 4 k = 61 2 1 3 0 e _ 0 0 87 1 9 1 0 e - 0 0 91 1 7 0 0 e _ 0 0 83 1 7 8 佴0 0 8 k = 72 7 9 5 9 e - 0 1 61 4 6 5 3 e - 0 1 62 2 8 9 融0 1 68 1 4 2 8 e - 0 1 6 k = 81 ，2 3 2 6 e - 0 3 1 7 3 9 5 6 e _ 0 3 249 3 0 4 e _ 0 3 21 9 7 2 2 e - 0 3 1 参考文献 1 1 】1j h w i l k i n s o n ，r o u n d i n ge r r o r si na l g e b r a i cp r o c e s s e e n g l i s hc l i f f s ，n e w j e r s e y ：p r e n t i c e - h a l l ，1 9 6 3 【2 】k n i c k e l ，t r i p l e x - a l g o l a n d a p p l i c a t i o n s i n ”t o p i c si n i n t e r v a l a n a l y s i s ” ( e h a n s e n ，e d ) o x f o r du n i v p r e s s ( c l a r e n d o n ) ，l o n d o na n dn e wy o r k ，1 9 6 9 【3 】i g a r g a n t i n i ，p h e n r i c i ，c i r c u l a ra r i t h m e t i ca n dt h ed e t e r m i n a t i o no fp o l y n o - m i a lz e r o s n u m e r m a t h 1 8 ( 1 9 7 2 ) ，3 0 5 - 3 0 9 4 ji g a r g a n t i n i ，f u r t h e ra p p l i c a t i o n so fc i r c u l a ra r i t h m e t i c ：s c h r o e d e r - l i k ea l - g o r i t h m sw i t he r r o rb o u n d sf o rf i n d i n gz e r 0 6o fp o l y n o m i a l s s i a mj n u - m e t a n a l 1 5 ( 1 9 7 8 ) ，4 9 7 - 5 1 0 【5 】i g a r g a n t i n i ，p a r a l l e ls q u a r e - r o o ti t e r a t i o n s b e r l i n ：s p r i n g e rv e r l a g ，( 1 9 7 5 ) ， 1 9 6 - 2 0 4 【6 】i g a r g a n t i n i ，p a r a l l e ll a g u e r r ei t e r a t i o n s ：c o m p l e xc a s e n u m e r m a t h 2 6 ，( 1 9 7 6 ) ，3 1 7 - 3 2 3 m 王德人，张连生，邓乃扬，非线性方程的区间算法上海科技大学出版 社，( 1 9 8 7 ) f 8 】王兴华，郑士明，确定多项式所有零点的并行圆盘h a l l e y j 塞代法，高等学校 计算数学学报，4 ( 1 9 8 5 ) ，3 0 8 - 3 1 4 【9 】w a n g ，x i n g h u a ，z h e n g ，s h i m i n g ，t h eq u a s i n e w t o nm e t h o di np a r a l l e l c i r c u l a ri t e r a t i o n j c o m p u t m a t h 2 ( 1 9 8 4 ) ，3 0 5 - 3 0 9 【1 0 】z h u ，l i n g ，am o d i f i e dn e w t o nm e t h o di np a r a l l e lc i r c u l a ri t e r a t i o no fs i n g l e - s t e pa n dd o u b l e - s t e p c o m p u t m a t h a p p l 5 0 ( 2 0 0 5 ) ，1 5 1 3 - 1 5 2 4 【1 1 】z h u ，l i n g ，o nt h ec o n v e r g e n tc o n d i t i o no fn e w t o n - l i k em e t h o di np a r a l l e l c i r c u l a ri t e r a t i o nf o rs i m u l t a n e o u s l yf i n d i n ga l lm u l t i p l ez e r o so fap o l y n o - m i a l i i a p p l m a t h c o m p u t 1 6 8 ( 2 0 0 5 ) ，6 7 7 - 6 8 5 高阶收敛的修t c h e b y s h e v 方法 【1 2 】z h u ，l i n go nt h ec o n v e r g e n tc o n d i t i o no fd u r a n d - k e r n e rm e t h o d i np a r a l l e l c i r c u l a ri t e r a t i o no fm u l t i s t e p a p p l m a t h c o m p u t 1 6 9 ( 2 0 0 5 ) ，1 7 9 - 1 9 1 【1 3 1z h u ，l i n g ，o nt h ec o n v e r g e n tc o n d i t i o n so fd u r a n d - k e r n e rm e t h o di np a r - a b e lc i r c u l a ri t e r a t i o no fs i n g l e - s t e pa n dd o u b l e - s t e p a p p l m a t h c o m p u t 1 5 7 ( 2 0 0 4 ) ，6 2 3 - 6 3 6 【1 4 1w a n g ，x i n gh u a ，z h e n g ，s h im i n g ，af a m i l yo fp a r a l l e la n di n t e r v a li t e r - a t i o n sf o rf i n d i n gs i m u l t a n e o u s l ya l lr o o t so fap o l y n o m i a lw i t hr a p i dc o n - v e r g e n c e ( c h i n e s e e n g l i s hs u m m a r y ) m a t h n u