（计算数学专业论文）解抛物问题的一类新的瀑布型多重网格法.pdf

硕士学位论文 摘要 瀑布型多重网格法是多重网格法中的一类，不要求粗网格校正，故又称单步 多重网格法最近，石钟慈和许学军对椭圆问题提出了一类新的瀑布型多重网格 法，即在粗网格和最细网格上使用不同的有限元空间，利用粗网格上简单的有限 元空间去处理最细网格上复杂的有限元离散因为粗网格上定义的有限元空间仅 起到校正的作用，这一新方法对一些工程上常见的复杂有限元离散可大大减少计 算工作量 本文推广石钟慈、许学军提出的一类新的瀑布型多重网格法到抛物问题，建立相应 的理论结果我们以线性二阶抛物型偏微分方程初边值问题为模型问题构造了新的瀑布 型多重网格法( n c m g ) ，对网格转移算子、磨光算子等作了适当的假设，在此基础上 作出了关于收敛阶和工作量估计的一般性定理然后将此定理应用于二阶抛物问题的两 个非协调元逼近，第一个是在最细网格上用p 1 非协调元，在粗网格上用l a g r a n g e 线性 元；第二个是在最细网格上用w i l s o n 非协调元，在粗网格土用l a g r a n g e 双线性元这两 种情形都得到了相应的瀑布型多重网格法的最优性( 一维时为拟最优的) 最后，对第 一种情形进行了数值实验，分别采用r i c h a r d s o n 迭代、s o r 迭代和共轭梯度法( c g ) 作 为磨光算子数值结果表明，本文构造的算法是有效的 关键词：抛物问题；瀑布型多重网格法；最优性 a b s t r a c t c a s c a d i cm u l t i g r i di san e w t y p eo fm u l t i g r i dm e t h o d s ，w h i c hr e q u i r e sn oc o a r s e g r i dc o r r e c t i o n sa t a l la n dm a yb ev i e w e da sa o n e w a y ”m u l t i g r i d r e c e n t l y , s h i z h o n g c ia n dx ux u e j u nh a v ec o n s t r u c t e dan e wc a s c a d i ca l g o r i t h mf o rs o l v i n ge l l i p t i c p r o b l e m s t h i sa l g o r i t h mp e r m i t st h eu s eo ft w od i f f e r e n tf i n i t ee l e m e n ts p a c e so nt h e c o a r s ea n do nt h ef i n e s tm e s hl e v e l s t h ea d v a n t a g eo ft h i sa p p r o a c hi st h a tw ec a nu s e r a t h e rs i m p l ef i n i t ee l e m e n ts p a c eo nc o a r s em e s h e st o c a r r yo u te f f e c t i v ec a s c a d i c i t e r a t i o n sf o rs o m e c o m p l i c a t e df i n i t ee l e m e n td i s c r e t i z a t i o np r o b l e m s an e wc a s c a d i cm u l t i g r i dm e t h o dp r o p o s e db ys h iz h o n g c ia n dx u x u e j u nf o re l l i p t i c p r o b l e m sh a s b e e ne x t e n d e di nt h i sp a p e rt op a r a b o l i c p r o b l e m s w e c o n s i d e rt h es e c o n do r d e r l i n e a r p a r a b o l i cp r o b l e m s w ep r o p o s ea p p r o p r i a t ea s s u m p t i o n so nt h ei n t e r g r i d t r a n s f e r o p e r a t o ra n ds m o o t h i n go p e r a t o r t h e nw ee s t a b l i s hag e n e r a lt h e o r e mo ft h ec o n v e r g e n c e o r d e r a n dt h e c o m p u t a t i o n a lc o m p l e x i t y t h e t h e o r e mh a sb e e nu s e dt ot r e a tt w o n o n c o n f o r m i n gf i n i t ee l e m e n t s i nt h ef i r s tc a s e ，w eu s ep 1n o n c o n f o r m i n ge l e m e n to nt h e f i n e s tm e s hl e v e la n dl i n e a rl a g r a n g ee l e m e n t so nt h ec o a r s em e s h e s i nt h es e c o n dc a s e ，w e c o n s i d e rw i l s o nn o n c o n f o r m i n ge l e m e n to nt h ef i n e s tm e s hl e v e la n db i l i n e a rl a g r a n g e e l e m e n t so nt h ec o a r s em e s h e s i ns u c ht w oc a s e s ，t h eo p t i m a l i t yo ft h ec o r r e s p o n d i n g c a s c a d i cm u l t i i g r i dm e t h o d si sd e r i v e d 阳n l yq u a s i o p t i m a l i t yi so b t a i n e df o r1 - dc a s e ) w e c a r r yo u tt h en u m e r i c a le x p e r i m e n t si n t h ef i r s tc a s eb yu s i n gr i c h a r d s o nm e t h o d ，s o r i t e r a t i o na n dt h ec o n j u g a t eg r a d i e n tm e t h o d ( c g ) a ss m o o t h e r s ，r e s p e c t i v e l y n u m e r i c a l e x p e r i m e n t ss h o w t h a tt h em e t h o di se f f e c t i v e k e y w o r d s ：p a r a b o l i cp r o b l e m ；c a s c a d i cm u l t i g r i d ；o p t i m a l i t y i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：砖彰改 日期：锄斗年r 月9 日 学位论文版权使用授权书 作者签名：声至芬苏日期：帅毕年r 月。7 日 导师签名：励衍日期：吖年月岁日 引言 随着科学技术和生产的发展，计算方法的研究日益显得重要事实上，以计算 方法为基础的科学计算已成为科学研究的三个基本要素之一，它已经成为继伽利 略与牛顿开创的试验与理论两大方法后的第三种科研方法，并以前所未有之势推 动技术革命现在，科学计算可以大大降低科学实验的成本，为新的科学理论的诞 生奠定基础，一项技术、产品或工程的先进性也很大程度上取决于计算的先进性 可以预见，科学计算在科技、经济和社会发展中必将发挥越来越重要的作用 研究高效率的计算方法在过去、现在和将来都是提高计算能力的重要途径由 于实践中提出的科学与工程问题，其数学模型皆属高维、大范围的偏微分方程， 因此，科学计算的核心就是如何计算偏微分方程问题实际中提出的问题规模越来 越大，对解的精度要求越来越高，从2 0 世纪7 0 年代后期开始，有一大批数值分 析专家致力于研究在这样的条件下，如何改造原有的算法或构造全新的算法，以 提高数值解法的计算质量和效率多重网格法就是这一历史的产物 多重网格法( m u l t i g r i dm e t h o d ，简称m g 法) 是求解偏微分方程边值问题的 一种有效的迭代解法，其基本思想早在2 0 世纪6 0 年代就由前苏联计算数学专家 r ef e d o r c n k o 提出，但当时并没有引起人们的很大注意7 0 年代中期以色列数学 家a b r a n d t 教授和德国数学家w h a c k b u s h 对它进行全面的创造性的研究，提出 了一些新的观点，使人们重新认识多重网格法的效率，这一方法受到了普遍的重 视尤其在8 0 年代之后，世界各国的计算数学界都在这方面投入了大量的人力、 物力，使得这个方法的理论研究取得了重要的成果，出现了一系列的多重网格法 的文章( 见文献【1 1 2 】) ，同时也出版了专著，其中有代表性的是参考文献 1 3 1 5 利用经典的迭代法( 如g a u s s s e i d e l 迭代法) 求解椭圆型方程边值问题，人们 发现一个现象，即开始迭代几次，近似解的有效数字变化很大，随着迭代次数的 增加，近似解的有效数字变化越来越小，收敛速度越来越慢为了确保计算解满足 一定的精度要求，一般应将网格尺寸取得比较小，这样，迭代的次数非常大，费 时计算数学家对这一现象进行了深入的研究，找出了问题的症结所在：相对网格 尺寸误差可以划分为高频摆动分量和低频光滑分量，经过迭代以后，初始误差向 量中的高频误差部分很快消失，整个迭代的缓慢收敛性完全是由于低频误差分量 引起如何有效地消去低频误差分量是提高收敛速度的关键所在考虑到细网格上 的低频误差分量可以看成为粗网格上的“高频”误差分量，这就启示人们构造粗 网格以有效地消去光滑误差分量这种构造粗网格( 网格尺寸从h 一2 h ) ，在粗网格 上用迭代法以磨光相对于粗网格上的“高频”误差分量来实现加速的方法就是多 重网格法 目前它已越来越受到科学计算工作者的重视，被广泛应用于求解线性和非线 性偏微分方程问题与其它迭代法相比，多重网格法的最大优点是它的计算工作量 与未知量的总数同阶因此，对大型问题它能成千上万倍地减少计算工作量，大大 地加快收敛速度 瀑布型多重网格法是一类新的多重网格法，不要求粗网格校正，故又称单步 多重网格法它产生于二十世纪九十年代中期，并得到迅速发展b o r n e m a n n 和 d e u f l h a r d 等人研究了用p 1 协调元离散二阶椭圆问题的瀑布型多重网格法( 见文献 【1 6 。1 9 】) ，已证明：对三维问题，若采用标准的迭代法，例如j a c o b i ，g a u s s s e i d e l ， r i c h a r d s o n 迭代法作为光滑子，则该法是最优的，但对二维问题仅是拟最优的若 采用共轭斜量法作为光滑子( 见文献 2 0 1 ) ，则对二维和三维问题都是最优的石钟 慈和许学军把上述结论推广到更一般的协调和非协调有限元( 见文献 2 1 2 2 1 ) ，考 察了板问题的瀑布型多重网格法( 见文献 2 3 1 ) ，证明了此时若采用共轭斜量法作 为光滑子，该法是拟最优的，而传统的光滑子不能使用，还讨论了抛物问题( 见 文献【2 4 】) b r a e s s 和d e h m e n 将此方法应用于求解s t o k e s 方程( 见文献 【2 5 1 ) t i m m e r m a n ng 等将此方法应用于求解非线性椭圆边值问题( 见文献 【2 6 。2 7 】) 曾金平和姜英军将此方法应用于求解非对称椭圆边值问题( 见文献 2 8 】) 他们提供的数值实验结果表明，瀑布型多重网格法应用于上述不同问题都是有效 的 从多重网格法的理论可知，粗网格上定义的有限元空间仅起到校正的作用， 对一些工程上常见的复杂有限元离散，没有必要在粗网格上使用同样复杂的有限 元空间，可以使用比较简单的有限元空间作校正，从而减少计算工作量石钟慈和 许学军对椭圆问题提出了一类新的瀑布型多重网格法( 见文献 2 9 】) ，该方法的要 点是在粗网格和最细网格上使用不同的有限元空间，利用粗网格上简单的有限元 空间去处理最细网格上复杂的有限元离散将这一类新的瀑布型多重网格法推广 到抛物问题有一定的理论和实践意义 本文推广石钟慈、许学军提出的一类新的瀑布型多重网格法到抛物问题，建 立相应的理论结果主要研究这一新算法的最优性，以及新算法对一些二阶问题的 应用 本文以下内容组织如下：第1 章，介绍我们所讨论的模型问题及其离散形式， 构造可直接用于计算机编程的算法，并建立相应的收敛性理论和误差估计，讨论 算法的最优性，这是对算法计算性态的理论研究；第2 章，将这一新方法应用于 p 1 非协调元( c r 元) 和w i l s o n 有限元( 见文献 3 0 4 4 】) ，并讨论其算法的最优 性，得出了相应的理论结果；第3 章，给出数值实验结果，以验证算法的有效性 第1 章问题与算法 本章我们简要介绍所讨论的模型问题及兵离散形式，构造可直接用于计算机 编程的新的瀑布型多重网格算法( n c m g ) ；对网格转移算子、磨光算子作了适当的 假设，讨论新算法的最优性，得到了关于收敛阶和工作量估计的一般性定理 1 1 模型问题及其有限元逼近 本文考虑如下模型问题： f 峨一“；，g ，r l0 ，f ) q x o ，r 】 “g ，t ) 0 ，0 ，f ) a q 【o ，r 】 ( 1 1 1 ) i h b ，o ) 一u o g l z q 其中。为r 一中有界多角域，d = l ，2 ，3 ，r ( q ) 问题( 1 _ 1 1 ) 的弱形式为：求 “日；( q ) ，“g ，0 ) = u 0 0 ) 使 0 。，v ) + n 0 ，v ) t ( ，v lv v e h ：晒l f o ，t 】 ( 1 1 2 ) 其中 2 p 眦，( ，y ) 。1 1 f 触 取t 。= 0c t ，c c t 一r ，f 。一t 。一t n - 1 ，l l ，n 采用尤拉向后格式，得到半 离散格式：求“h ：心) ，使 巧1 仁n ，v ) + 口- ”，v ) 一( g ，y ) ，v v 月：( q l 刀- 1 , ，n ( 1 1 3 ) 其中 g ，一f ，+ f ? n “。 于是求解( 1 1 3 ) 的问题化为求解带参数f 的椭圆问蕊：求w 日：( q ) ，使 f 一1 ( w ，v ) + 口( w ，v ) - ( g ，v ) ，v p 日：( q ) ( 1 1 4 ) 作拟一致剖分l ，不妨设 ，= h h 2 例如，对l 。三角形单元，连接三边中点 即得四个1 - i 三角形单元；对r f _ l 矩形单元，连接对边中点即得四个0 矩形单元设巧 为r ，对应的有限元空间，巧c r ( q ) 又设，巧。为r o ，0 。对应的有限元空 间，y ，c | l 2 ( q ) ，j o 工，j 一1 我们的目的是求最细网格上的有限元解，即求w j 巧， 使 _ r 1 ( ，v ) + 乃( ，v ) ；b ，v ) ，v v v , ( 1 1 5 ) 其中 q ( ) 。荟f 毗 当巧为协调有限元空间时，q ，v ) = n ，v ) 类似可得较粗网格上问题( 1 1 4 ) 的有限元方程： f “沁，v ) + n ，( w ，v ) = ( g ，v ) ，( 1 1 1 6 ) 其中j = 0 ，1 ，j 一1 1 2 新的瀑布型多重网格法 设j 土。为哆一。到的网格转移算子，c ，为上的线性迭代算子，且设存在线性 g q ：s ，使w 一c ，v = s ，( w 一v j ，其中v _ ，w ，为( 1 1 5 ) n ( 1 1 6 ) 之解，即c ，的不动 点 算法n c m g 第l 步用直接法求解j ：o 时的( 2 1 6 ) ，得w o ，令w o ，。- w 0 ； 第2 步对j 1 ，作： ，o 。j 如 。h ，w ，口，一c 7 7 w j ，o ； 第3 步输出w j ， 上述算法中第2 步的磨光次数m 。要求满足 优，芦。一， ，一1 ，一1 ( 1 2 1 ) 其中卢，1 为取定的常数，在后面的讨论中将加以限制( g ( 1 3 3 1 ) 1 3 算法的最优性 1 3 1 概念与假设 为了讨论新算法( n c m g ) 的最优性，我们引入一些概念和假设 求解问题( 1 1 4 ) 的多重网格法称为最优的，如果在能量范数下w m 与 w j - w i 。同阶，并且计算工作量为d ) ，此处n ，一d i m v , ( 见文献【4 5 4 7 ) 对问题( 1 1 5 ) ，能量范数为 i l v l l 。一f r 。1 p ，v ) + q ，v ) 】心，协巧 而问题( 1 1 4 ) 的能量范数为 m f 。： 一1 ( y ，v ) + n p ，v 疗胆，v v 口j ( 西) 类似地，可定义问题( 1 1 6 ) 的能量范数叫， 。；- i d ，v ) + n ，p ，v ) ”，v v _ 其中，= 0 ，j 一1 对网格转移算子j ；。作如下假设 假设，) ( i ) i ，；卅。墨c t l v l l 小。， 协巧一t ( i i ) h j 厶一。扎sc 碍| | g i i 。 其中c 与h ，j ，r 无关( 以下均设c 如此) 对磨光算予作如下假设： 假设( 日：) ( i ) 炒屯s 州小j 7 ( 1 + a v 碍) _ 叫2 批，铷巧 ( i i ) 渺儿( 1 + 口。f 。i l ；) _ ”v v 巧 其中盯己0 ，1 2 5y5 1 ，a 0 对w j 吐。作如下假设： 假设，) h ：一小sc 艺- 1 ，m 弛少力| f g l f 。 其中口，y 同前，y o 0 1 3 2 主要理论结果 下面来估计能量范数下算法n c m g 的误差m - - w j 。 引理1 3 i 若，) ，) 成立，则 j i 。一。，1 i ，s c 骞h i m j 7 ( 1 + r 。尸，j l k f l 0 证明由于m 。= c 7 7 f 一，w j 一。- l 故由s ，的定义知 怫一w j , m ，b 。渺b 叫j - n ，m ， s l 掣，b 一一，m 一，k ，+ l 眇m , 。jb 一，一w j ，。址， ( 3 ，) 解抛物问题的一类新的瀑布型多重网格法 由( h ：) 一o ) 与( h 。) 一) 可得 i s y 。一，j 一，m 。u ，s c h ；1 州，( 1 + a _ 1 f 。1 碍) - m j u 2 i 一，；一。m 。k 由于一m j 仃2 弓0 ，故 s c h ，州，( 1 + 口。砰) _ m i “2 h 。 ( 1 + 口一k w ) ”州2s ( 1 + 广p 。) ；1 另一方面，由( h ：) 一缸) ，。) 一( f ) 与( h ，) 可得 1 s 户，工，( w 一。一w 。一。札。s ( 1 + a k “ ；) - ”p j 。沁。一”。一。一。j l f ， s c 1 1 w , 一，一w j 。，一， ；c 芝 ，( 1 氓尸川i i m 7 s c ，7 ( 1 氓f 一 综合上式和式( 1 3 1 ) 、( 1 3 2 ) ，可得 1 1 w ，一h 。b = i l 霹，b 一吐，m 却。u s 炒7 h 一吐，m 1 1 。+ 炒。t ，b r 。吐。u s c h , m j r ( 1 + a 4 砖) - m 1 0 1 2 m 。 + c 篁 ，m j ，( 1 少7 i i+ c 艺 m j 7 ( 1 + r 。广“一7 l l g 。 s c 砉磊芦( 1 p 悯 。 引理1 3 2 设。) 一( t t ，) 成立，m 满足( 1 2 1 ) ，且卢7 ( 1 + 广，2 ，则 一w l , m j i i 。5 c h u m r i 一2 卢一，( 1 岷) 一寸| | g | 。 证明 由卢7 ( 1 + 7 0 ) 。 2 ，m j , o - - j m j ，可知 2 卢一7 ( 1 + y o ) 1 ， 一6 一 川j 7s 卢一，( j - s ) m ( 1 3 2 ) 又 j = 2 s - j h j 此时由引理1 3 1 ，得 i h 一。嘶bs c 毫2 川幻一r 。一，k j 7 ( 1 + y 。) 柏- j i i 占t l 。 c h ，m 7 m 。薹幽( 1 氓) ”j j 一1rv s c h ，疗，j r i 一2 j b r1 + t o ) 一。 1 i i 占i i 。 由此即得所求证 引理1 3 3 设以= d i m v ，m j 一忙川m jj + 1 ，ja 1 ，j ，则算法n c m g 的计算 工作量当芦c2 4 时满足 砉m ，n ，c ( 1 一z p ) - 1 肌， 证明 由于m ，一h 埘，+ 1 ，此时卢h 小，m j 墨2 卢牌，由文献【1 q 引理1 4 知 2 埘c 一1s h 一m i n 0 ，则算法n c m g 为拟最优的 证明( 1 ) 当1 2 墨y 1 ，d = 3 时， 由于 2 ( 1 + y 。) ；【2 ( 1 + y 。) 一呷s2 2 ( 1 + y 。) 。 总可选取卢，使 2 2 ( 1 + r 。) 。 p 0 时，由于 2 ( 1 + y 。) 一4s 2 ( 1 + y 。) 一4 1 7 r s 2 2 ( 1 + r 。) 一2 口 或 2 z ( 1 + r 。) 。量e 2 ( 1 + r 。) 一。】“；2 ( 1 + r 。) ” 总可选取口，使 2 2 ( 1 + ) 。“ 2 2 或 2 ( 1 + r 。) 0 时，由于 ( 1 + y 。) c 1 总可选取芦，使 昱、 + q 2 r _tj 口 ror + h 卜 乜 口 r0 y + “卜 2 2 或 2 ( 1 + y 。) 一 声( 2 根据文献【16 】i ；l 理1 4 ，知当声= 2 时， 砉叩，s c ( j + ，h n ， 即计算量为o ( n j l o g n j ) ，因此算法n c m g 为拟最优的此处0 1 解抛物问题的一类新的瀑布型多重网格法 第2 章对两个非协调元逼近的应用 本章我们以墨非协调元和w i l s o n 有限元为例，考虑算法n c m g 对二阶抛物问 题的应用，得到了相应的瀑布型多重网格法的最优性 2 1p 1 非协调兀 设 k ) 为q 的拟一致三角剖分族，定义相应的墨非协调元空间( 见文献【3 7 】) ： 吒= v ：v 在r k 的每个单元e 上为线性函数且在其每边中点连续， 当此中点在a q 上时，v 在该点为o 取圪为只非协调元空间( 即c - r 元) ，一。工，一1 为最协调元空间，所 以k c v , c 巧一，匕巧并取土l ，t 1 ，j ，为恒等算子 由第1 章我们知道，为了证明定理1 , 3 1 的正确性，仅需验证条件，) 一( i - i ，) 首先引入两个引理，见文献 3 7 1 引理2 1 1 若9 6 l e ( q ) ，则( 1 1 4 ) 之解w 日2 ( q ) ，且满足 i w l l ：s c l l g 【| 。 其中 i | i ：为h2 范数，c 与昏f 无关 引理2 1 2 设“。，“分别为( 1 1 3 ) ，( 1 1 4 ) 之解，则 i i - n + l l ：sc h 。p 啊+ 1 门 陋一“。0 。sc ；b 。2 + 1 m ：， 其中常数c 与h 。，百无关，且 以- 学慨) ，眦一k ：“，“肛 n ：0 ，v ) ；a 。0 ，v ) + r - 1 0 ，v ) 情形1 ：取r i c h a r d s o n 迭代为磨光算子 下面验证条件( 1 ) 一慨) ，j 一，为恒等算子，显然l 一, v i i 。5 叫l ，。，v v 巧。条件，) 一g ) 成立 由引理2 。1 1 和引理2 1 2 ，可得有限元误差估计： 卜b 国；( 1 盯1 _ i 鲫叫l ： 墨c 碍【1 + f 1 _ l l 彻g l l 。 因此，若 f c + h ；( 2 1 - 1 ) 则 卜w 川。主劬；( 1 + f 4 挑l i 。 s o ；5 + c ”1 。 s 凸船扎 ( 2 1 2 ) 对算法n c m g 而言，条件( 2 1 1 ) 容许取大的时间步长f ，从而不是一个实质性的 限制，由( 2 1 2 ) 推出 1 h 一，j 。w j 。0 。- 9 m m 一- 忆 车8 w j 一酬。+ l l w , 。- , q l 。 c h ；l l g l l 。 即( 风) 一) 成立 若取迭代算子c ，= 1 ，为r i c h a r d s o n 迭代，则 s j j 。妇j 2 + 一) - 1 a j ， ( 2 1 3 ) 其中a i 满足 0 产，v ) k - 1 ( i t ，v ) + 口，0 ，v ) ， v u ，v ( 2 1 4 ) 引理2 1 3 当芑2 时，对r 一1 1 2 ，盯- 1 ，若磨光算子0 ，一1 ，为 r i c h a r d s o n 迭代，则条件：) 对p 1 非协调元成立 证定义算子一a i ：乃一巧如下： i 布，v ) - n ，“，v ) ，y u ，v 巧 设v 一姜q 鼹，霹v ；萋c 觑, k - 1 ，肘，其中仇也，和戗记t 分别为石的特征值 和相应的特征向量，即 j 为i 。 伊；，慨，妒，) - 6 。 这里氏是k r o n e c k e r d e l t a ，f ，- 1 ，推j ，0 s t s 首先证明下面等式 跏一酗6 一轨仃1 炳2 仃1 汀 ( 2 1 5 ) 用归纳法讧：明( 2 1 5 ) 式 解抛物问题的一类新的瀑布型多重网格法 田r ，识) 。( - - ( 砷j ：+ z 一- ) _ 1 4 ，l ，纯) ；( p - - 产+ r 一- - 1 a j v ，竹) = 0 舰) 一j 2 + r 一1 ) - 1 v ，讫) ：，驴；) 一妇j 2 + z n ) - 1 t 1 和，) + 口，觋) ) 。o ，卿) 一j ：+ f - 1 ) - 1 0 ；+ 晦，吼) ) ：。；一i z + f - 1 ) - 1 0 q + i ； 一( 一伉盯1 k 2 吩 5 c l l 因此 跏；乳仍6 一伉仃- 胁：+ , c - 1 n s ；q 一伉仃1 炳2 + h 假设七= z 时，有 s ；y 。芝c ；仍6 一仇+ f 一1 x t ；t h j 2 + , r - 1 ) _ 1 y 对于l i = f + 1 ，由于 s ，- ，铣) ；帖一g 酊：+ f - 1 ) - 1 爿，b ；v ，讫) b j n 砚) 一协j 2 + - r 4 ) - 1 “s j v ，锻) 0 ；n 铣) 一j ：+ r _ 1 ) - 1 0 一，0 ；v ，纯) + n ，0 j v ，识) ) 。6 一k ：仃t - i r - i k v 魄) 一j ：+ - r 。1 ) - 1 沁识) ；6 一( 吐j i j 2 + r - 1 ) _ ，f 。l i 6 一阮+ f t 胁j z + r t r l 7 一( y h j + t - i ) - 1 托6 一饥+ f 一胁；z - ) - 1 y 一6 一k 2 + f 。) - 1 伉+ r 。) 7 “。， = q + i o 故 影i + 1 v 一誓c ，仍6 一伉+ f 4 k 町。+ z t ) 。7 “ 即等式f 2 1 5 ) 得i y 因此 粉啦。，f 。1 妇u 妒v ) + 4 ，s r , v , s ；，) a - r 4 耄q 6 一伉+ f 1 k 2 + r 4 ) - 1 f k ，印v ) + 蓦q 8 一“+ r 1 k 2 + r 一寸1 ，q k ，妒，) 一誓哿6 - 伉仃1 k k 一1 广产 + 萋q 6 一伉+ r 一1 胁2 + f 一1 ) - 1 广7 q ；薹6 - 轨汀1 k 2 盯1 胪伉4 * r - i ) t 哳2 + f 。1 凌孑6 一轨+ r t 垴v ：+ f 。) 。1 r 4 k + f 一) g 町2 + f 。2 ，1 ( 1 一口一碍丑p “( 1 + 口一j 矗知一， - m l s 。1 凑c ；( 1 盯k w p m 嘛a x 。x ( 1 一工p s c 嘶2 小j 1 ( 1 + a 一1 砖) - “，| h b啊2 即条件：) 一( f ) 成立 由于 1 一伉+ - r 1 胁了2 + f 寸1 。协，：一 k 7 。+ f 寸1 s 如j 。z + f q ，1 解抛物问题的一类新的瀑布型多重网格法 因此 ( t 一( ”一1 b f 一1 广) 挑s k 2 协 f _ 1 ) - 1 严 ；( 1 + a 一，r 一碍) - 2 ” 卜黔一脚一伉仃1 胁 f 一1 旷7 s g + f - l 口。 ；) _ “7 萋( + f 。1 l ? - ( 1 + 口。砖。”眦。 即条件：) 一) 成立 综合上述，条件：) 成立 事实上，对s ，j ；1 ，j 一1 ，类似可得 忙删“s 6 订k 4 n 妒“，v v v j i p ? 7 v 0 ，s c h ；l m ； 7 2 ( 1 + a 。1 f 4 j ) - ”一2 i i v 0 。 引理2 1 4 若磨光算子为r i c h a r d s o n 迭代，对条件( 2 i 1 ) ，选取y 。，0 ，使 r s k y 。) 。露( 参见文献【2 4 】) ，j l ( n 。) 对p 1 非协调元成立 证 y ，为e 协调元空间，j = 0 1 ，j 一1 则 | | m 一。一m 吐。一。tl m 一。一c 7 _ i 1 m 吐。 一f 降? r 。吐擅 一0 躜- b r 仁j - ：1 m 一：i i ， 刊s 一 1 1 ( 、w 。一m - 24 一：一m 吐。：址 s l l s 盈( w ，。一m 一：犯+ 忙翌i 1w j 一：一m z 札：址 ；c 巧! 两z 1 + 5 - k 一研。) _ ”胆- l _ m 扎 + 1a - 1 r - 1 2 ) - ”4 rm 喝一l 硕士学位论文 = = = = = = = = = ! = = = = = = = = = = = ! = = = ! = = = = ! = = = = = ii i i = = = = = = = = = = = = = = = = = = = = = ! = = = = = = = = = = = = ：= ! 由引理2 1 1 和引理2 1 2 ，得 r m 扎- f l w - w j 扎+ 怙一w j 挑 s c 碍一。【1 + 口。f 一智一，】j g i | o 由上面两个不等式，得 1 1 w j r 。s 吼。- 野1 1 ( 1 + 口i 2 卜他“龇 + ( 1 + 口w 一。p “h ：一w j t 。l l s c 一。坼2 ( 1 + a k 一1 砖。) - ”2 “i k 扎 + c ( 1 + a - l z - l h ，2 。) - ”h j 卅普( 1 枷- 1 r - l h 。2 ) - ”2 雎“。 + ( 1 + 口- i r - i 2 - ”4 ( 1 埘- 1 1 r - l h ；一。严2 r m 却。n 主c j - 1j l ，卅- 1 ，：竹( 1 + a t 埘2 。- m 2 一( 1 + 口- 1 。- 1 。，2 ) - m “ 主c 菩 ，卅- 1 心i ：l ( 1 铲埘。“( 1 + 口r 引一“。 这里，我们规定n ( 1 + d - 1 f 。砰一，”，- 1 由h t 一1 2 ，m 产p 川嘶，鸭王2 ，得知 - - m ，2 + 1 0 ， 因此 ( 1 + 口k w “1s l ， ( 1 + 口一磕i ) 嘶墨( 1 + 口4 h 。2 ) _ 1 e - 赣m 电m 矾一p j ! ：i - - i ( 1 ；。p 量霄m 钠l ) - 1 s 茸m v 碍) 1 s c ( 1 + y o r “一 1 5 解抛物问题的一类新的瀑布型多重网格法 于是 i w j r b 一。s c j - 1 h i m ( 1 饥) 7 。 综合上述，对r i c h a r d s o n 迭代，条件。) ，) 满足，且( 1 3 3 ) 成为 4 ( 1 + 7 。) l l s ：也，弓c h j l m j l ( 1 玎1 f 嘞扩i i i t 咖巧 ( i i ) 阿v l 州b v v f - v j 证设妒，妒。，是巧的正交基，且4 妒，一九札，p = 1 ，码，其中 o s s s 九，a x 寸v v e v , ，有 忙岁7 v 忙，；f 1 b v ，s t v ) + n ，p p v ，s 7 。v ) 。霹饥s 7 ，v ) = c 4 j 蛇，x ，v ) ； ) 弘n 妒，如) 一( 4 弘妒。k 。“一叫 一隆妒，k ，轨，饥v ) 。n l 以筑。k i v ，妒，) 2 s 乃，+ 1 ) 。2 釜( v ，妒，p 一( 2 j ，l ，+ 1 ) _ 2 ” 一( 加，+ 1 ) 以h ： 5 “+ f x 2 m ，+ 1 ) - 2 l l v l l ： s 叻产m ( 1 + a 一1 f w 】呲 弦v 融一k s v ，s 7 7 v ) = 芝以蜕。k x v ，吼p s 萱九) z 1 7 此处珊蜘，b 1 1 垣0 ，州一” 解抛物问题的一类新的瀑布型多重网格法 = n v ) 刊b 验证条件慨) 先定义线性算子s 歹7 一九胪，“) ，一】，一1 ，九一，只，九，( o ) = 1 类似得 ( i ) 陟s 7 | | 1 ，sc h ；1 m j l m 。1 扩1 1 v 1 1 。，w 一 ( i i ) 黟v h s i t , l l 叫，v v e v j 引理2 1 7 若磨光算子为共轭梯度方法，则在非实质性限制条件( 2 1 1 ) 下， ( h 。) 对p 1 非协调元成立 证设m 。一c ? m ，u j = 1 ，j 一1 ，则 | | w j 一，一 。，。k = i h ，一q 譬m 吐。n 2 z ! ) _ 。忙- 托r 趣 s l 巨辫沁。一城 = 粉i t 沁r m 也一l f 一0 姥? b 。一。- z + m 一：一 也。驰 s 归卫i 1 ( 一，一m 一：犯+ 0 躜沁一：一m 屯。：1 1 ， s c h ；l _ l m ；1 _ ，( 1 + 口一k 一1 仰2 一。y 胆| | m 一。一m 一：i i 。 + b 一：一m 吐。，。k 由引理2 1 1 和引理2 1 2 ，得 i h 一，一m 一：ks | | w w j 。忆+ l l w w j 一：l | 。 s c 碍一。q + a 一1 r 。1 巧2 一，1 1 9 1 1 。 由上面两个不等式，得 硕士学位论文 | f w j 一。一。l 。t , j - 1s c 一。，町! 。( 1 + 口一k 一1 乃2 一。7 ”“蚓f 。 + 8 m 一：一m t 。k s 吼，啊( 1 + 口一一1 2 。y 2 + 1 。 + 吼一。畦：( 1 + 口k 一1 2 ，：7 2 + 1 。 + i f t 吩一，一w j ，。f 【 s c j - 1 ，掰尹( 1 + 口- 一坼7 ，2 + 1 龇 s c ，掰尹( 1 + 口一一坼7 ，2 + l 龇 由( 2 1 1 ) 式，得 l + a k 。；) j ( 1 + c 口一i n ，- 2 n ，2 ) s ( 1 + c 口_ 1 ) 从而 k 。一m 饥i l l 。c j - 1 ，m 刺i 。 最后看条件( 1 3 3 ) 对共轭梯度迭代，当d = 2 ，3 时，可取卢满足2 p c 2 , 1 ，从而 算法n c m g 有最优性 2 2w l is o n 非协调元 r o 是q 的一个矩形剖分，氏是所有矩形的最大直径假设 0 和氏- ：r o 给定， ，= 2 - h o ，jz 1 ，j ，剖分r ，一：0 是由连接r ，中每个矩形对边的中点而生成的，最 细网格上的剖分记为l 在每层j 上，定义下列w i l s o n 非协调有限元空间： 在每个单元e r ；上，w i l s o n 元的形函数是二次多项式p b ，y ) ，一般形式为： p 0 ，y ) - n + 缸+ 9 + 奶，+ d 2 + 痧2 此处a ，b ，c ，d ，e ，f 是待定的常系数，它由p g ，y ) 在矩形单元4 个顶点上的值和i o z p 及 一0 2 p 唯一确定 解抛物问题的一类新的瀑布型多重网格法 本节我们假设定义在割分e 上的w i l s o n 有限元空间为巧，粗网格校正空间 ( ，= 1 ，j 一1 ) 为双线性协调元空间易知k c k c c 巧一，c 巧选择恒等算子作 为网格转移算子f 一，：巧一。一巧 情形1 ：取r i c h a r d s o n 迭代为磨光算子 下面验证条件( h 1 ) - 。) 对任意的矩形e j 一，r j 。上述剖分是拟一致剖分，e j 一。分为四个等面积的小矩形 e ? r r ，i ；1 , 2 , 3 ，4 ，如图所示： 由于 对聊嵋。 所以 勺。互p 毗， 吼- 。盏。p 呷池， 善i v 瓢出- e 善。嬖。瓢幽 ；i t - 1 ( v ，v ) + 。，扣，硝“ g p 一- 一，v + ar q d ，v ) 1 胆 即肌叱，式h 叫1 ，条件t ) 一( i ) f i l k l f 由于 l u n 。“ls 伪i i e , l i ： m = 0 ，1 ，( 2 - 2 1 ) 其中忆。为h ”( e ) 的半范数，1 - i k 为k 的插值算子 w i l s 。非协调有限元仍成立( 见 文献