（计算数学专业论文）发展方程的重叠型区域分解并行算法.pdf

发展方程的重叠型区域分解并行算法 张建松 ( 山东大学数学学院，济南，2 5 0 1 0 0 ) 指导老师：羊丹平教授 摘要 区域分解算法是上世纪八十年代崛起的新方向由于该方法能将大型问题分解为 小型问题、复杂边值问题分解为简单边值问题、串行问题分解为并行问题等其它方法 无可比拟的优越性，而一举成为计算数学的热门领域尤其是近些年，随着并行计算 机和并行算法的迅速发展，区域分解算法正成为解决具有复杂区域或复杂过程的现实 生活问题的强有力的工具 区域分解算法大致可以分为两类：重叠型区域分解算法和非重叠型区域分解算法 子区域的选择主要考虑区域形状的可计算性以及问题的物理背景尤其是后者，特别 适用于在不同物理子区域上有不同控制方程的复合问题非重叠型区域分解算法实现 起来比较直观易用，而重叠型区域分解法的理论分析较为容易些本文我们的研究重 点就是重叠型区域分解算法 重叠型区域分解算法是一种重要的求解偏微分方程的数值方法，在工程领域中有 着广泛的应用最早的重叠型区域分解算法源于经典的s c h w a r z 交替法近年来建 立在s c h w a r z 交替法基础上的区域分解法在理论分析和实际应用中取得令人注目的 发展，已成为一种有效的迭代方法对于椭圆型问题，许多基于重叠型区域分解的数 值方法已经建立 1 6 ，1 7 ，2 0 ；l i o n s 8 2 ，8 3 对热传导方程提出了的一类建立在两个子 区域基础上的s c h w a r z 交替算法，给出了收敛性结果，但没有给出误差估计；x c c a i 1 9 ，州】构建了一类加性s c h w a r z 算法和乘积性s c h w a r z 算法，并证明了算法的 收敛性，但作者没有详细讨论收敛率对离散参数的依赖性；芮洪兴教授和羊丹平教授 2 6 ，2 7 ，2 8 ，2 9 ，3 0 ，3 1 ，3 2 ，3 3 3 4 论证了在每一时间层上收敛性及误差估计对子区域长 度、空间网格步长、时间步长和迭代次数的依赖性经典的s c h w a r z 交替法不是并行 的，随着并行计算的发展，出现了多种可完全并行化的加性s c h w a r z 算法m d r y j a ， o b w i l d u n d ，t m s h i h 等 拢，2 3 ，2 4 ，2 5 皆独立提出不同的算法，这些算法可克 服交替方法的串行性，更利于并行处理j x u “，的】系统地介绍了求解对称正定问 题的各种迭代方法，主要是利用区域分解和子区域校正法从理论上建立了并行子区域 校正和串行子区域校正这两类算法关于此类方法x c t a i 也做了大量的研究工作 山东大学博士学位论文 【3 6 ，3 7 ，3 3 9 1 文献f 4 4 1 中，结合一般g a l e r k i n 有限元方法，杨建华和羊丹平教授将 并行子区域校正算法应用于抛物型方程，并得到了收敛阶o ( 占”) ，其中0 j 1 在导师羊丹平教授的悉心指导下，本文作者对重叠型区域分解并行算法做了部分 研究工作基于徐进超教授提出的并行子区域校正算法( p s c ) 思想，结合一些熟知的 数值方法，如经典混合有限元方法、分裂正定混合元方法、最小二乘方法等等，利用 单位分解函数的特性，合理地分配重叠区域上的校正量，对抛物问题、双曲问题、时 间依赖的对流扩散问题及多孔介质中相容驱动问题等分别构建一类新的区域分解并行 算法从理论上分析了算法的收敛性，论证了在每一时间层上的误差收敛阶对子区域 重叠度、空间网格步长、时间步长及迭代次数的依赖性理论分析和数值算例都表明， 算法具有高度的并行性，并且在每一时间层上只需迭代一次或两次就能达到收敛的最 优阶 全文共分四章 第一章，对一般的二阶抛物型方程提出一类新的区域分解并行算法首先，运用 羊丹平教授【均】提出的分裂正定混合元方法( s p d f m e ) 思想，我们构造了抛物方程 的全离散分裂正定混合元格式，此格式方程系数矩阵是对称正定的其次，基于此混 合元格式，结合徐进超教授提出的并行子空间校正算法，我们建立抛物问题的并行混 合有限元算法i ( p m f ea l g o r i t h mi ) 分析了全离散分裂正定混合元格式及并行混合 元算法i 的收敛性，并给出相应的误差估计对于并行混合元算法i ，一些算例被给出 从这些数值结果中可以看出，在每一时间层上只需要迭代一次或两次就能达到理论最 优阶，这正和理论分析的结果一致此外，基于抛物问题的一般混合元格式，在本章最 后一部分，我们还提出了抛物问题的另一并行算法：并行混合有限元算法i i ( p m f e a l g o r i t h mi i ) 运用前面的一些理论分析结果，研究了此并行算法的收敛性并给出相 应的误差估计 第二章，着重研究多孔介质中的相容驱动问题区域分解并行算法我们知道，对 于对于多孔介质中的相容驱动问题，羊丹平教授提出了分裂正定混合元方法【均】此 方法中，方程的系数矩阵对称正定，并且压力方程与流函数方程分离这样使得我们 能够不依赖于压力方程而单独求解流函数和饱和度本章算法的思想就是基于与压力 无关的流函数方程和饱和度方程，运用第一章中抛物型方程的并行混合有限元算法i 的思想，建立一种新的并行混合有限元算法，从而并行地求解流函数及饱和度研究 了此算法的收敛性并给出了误差结果从误差估计中我们能够看出在每一时间层上只 需要迭代二次就能达到收敛的最优阶在2 1 中介绍了问题的物理背景以及研究的目 的和动机在2 2 中我们给出多孔介质中的相容驱动问题的全离散分裂正定混合元格 式，并形成二个并行混合有限元算法在2 3 中我们给出用以证明并行算法收敛性定 山东大学博士学位论文 理的一些重要引理在2 4 中，我们证明并行算法的收敛性定理本章的一些结果已 经发表在山东大学学报( 理学版) 上( 见 5 8 ) 第三章，主要研究时间依赖的对流扩散方程的区域分解并行最小二乘算法目前， 已经有大量的文献是关于最小二乘有限元格式及它们在椭圆边值问题的应用，一些椭 圆问题的对称理论和逼近解的收敛性理论被建立，见文献 6 2 ，6 3 ，6 4 ，6 5 ，6 6 ，6 7 ，6 8 ， 6 9 ，7 2 ，7 4 ，7 6 ，7 7 ，7 8 最s j 、- - 乘有限元方法也被扩展到时间依赖的问题，如 7 1 ，7 3 ， 7 5 ，7 9 ，8 0 ，8 1 本章中，运用羊丹平教授在文献 7 9 中提出的时间依赖的对流扩散方 程的最p j 、- - 乘格式i 和格式i i i ，我们提出了两种并行最小二乘算法：并行最小二乘算 法i 和并行最t j 、- 乘算法i i 算法基于重叠区域分解和子空间校正，通过引入单位分 解函数，合理地分配重叠区域的校正量算法在每个子域上分别进行残量校正，各子 域之间可以并行计算分别分析了并行最小二乘算法i 和并行最t j 、- 乘算法i i 的收敛 性，并给出相应的误差估计本章的最后，给出了数值算例，对最s j 、- - 乘格式与并行最 小二乘算法进行了比较，分析了收敛率对离散参数及迭代次数的依赖性本章的部分 主要结果已经投递刊物( 见【6 0 ) 第四章，研究了二阶双曲方程的区域分解并行混合有限元算法我们知道，双曲方 程描述了自然界中的波动现象，在物理、化学、生物等不同领域都有着非常重要的意 义。对于二阶的双曲方程，已建立了大量的数值求解方法 8 5 ，8 6 ，8 7 ，8 8 ，8 9 ，90 1 对于 双曲方程的并行算法，目前也有大量研究工作y h w u ，x c c a i 和d a v i de k e y e s 研究了一阶双曲问题的加性s c h w a r z 方法【4 u 】田敏在其博士论文 4 6 中研究了二阶 双曲方程的并行有限差分算法，论证了在每一时间层上的收敛性及对子区域重叠度、 空间网格步长、时间步长及迭代次数的依赖性本章我们研究的目的是，运用第一章 提出的抛物方程的重叠区域并行混合元算法的思想，构建一种新的并行算法求解双曲 方程分析了此并行算法的收敛性并给出相应的误差估计在4 1 中，我们陈述了本 章的研究目的和动机在4 2 中，运用羊丹平教授在 1 5 】中提出的分裂正定混合元思 想，我们给出双曲方程的一个分裂正定混合元格式，并依此为基础构造该问题并行混 合元算法在4 3 中，给出一些重要的引理，我们将用来分析双曲方程并行混合元算 法的收敛性在4 4 中，我们分析并行算法的收敛性，并给出相应的误差估计本章 的部分结果已经被( ( n u m e r i c a lm e t h o d sf o rp a r t i a ld i f f e r e n t i a le q u a t i o n s ) ) 接受( 见 f 5 9 ) ， 关键词：区域分解；子域校正法；混合有限元；分裂正定系统；最小二乘；收敛性 分析；数值算例 山东大学博士学位论文 o v e r l a p p i n gd o m a i nd e c o m p o s i t i o n p a r a l l e l a l g o r i t h m sf o re v o l u t i o ne q u a t i o n s z h a n gj i a n s o n g ( s c h o o lo fm a t h e m a t i c s ，s h a n d o n gu n i v e r s i t y ，j i n a n2 5 0 1 0 0 ) s u p e r v i s o r ：p r o f y a n gd a n - p i n g a bs t r a c t d o m a i nd e c o m p o s i t i o nm e t h o d sw e r en e wr e s e a r c hd i r e c t i o nw h i c hg r e wu pi n 1 9 8 0 s b e c a u s et h e yh a v em a n ya d v a n t a g e s ，s u c h8 8t h e yc a n d i v i d el a r g e - s c a l ep r o b - l e m si n t os e v e r a ls m a l lo n e s ，c o m p l e xb o u n d a r yp r o b l e m si n t os e v e r a ls i m p l eb o u n d a r y o n e sa n ds u c c e s s i v ep r o b l e m si n t op a r a l l e lo n e s ，e t c ，w h i c ho t h e rm e t h o d sd o n th a v e ， t h e yr a p i d l yb e c o m et h eh o tf i e l do fc o m p u t a t i o n a lm a t h e m a t i c s e s p e c i a l l yi nr e c e n t y e a r s ，w i t hr a p i dd e v e l o p m e n to fc o m p u t e ra n dp a r a l l e la l g o r i t h m s ，d o m m nd e c o m p o s i - t i o nm e t h o d sa r eb e c o m i n gp o w e r f u lt o o l st oh a n d l er e a l h f ep r o b l e m sw i t hc o m p l i c a t e d d o m a i n so rc o m p l e xp r o c e s s e s d o m a i nd e c o m p o s i t i o nm e t h o d sm a yb ep a r t i t i o n e di n t ot w of a m i l i e s ：o v e r l a p p i n g d o m a i nd e c o m p o s i t i o nm e t h o d sa n dn o n o v e r l a p p i n gd e c o m p o s i t i o nm e t h o d s ，t h es e - l e c t i o no fs u b - d o m a i n sm a yb eb a s e d0 nt h ea v a i l a b i l i t yo ft h ec o m p u t a t i o n a ld o m a i n a n dt h ep h y s i c a lb a c k g r o u n do ft h ep r o b l e m s t h el a t t e ri s i np a r t i c u l a r ，a p p h c a b l e t oc o m p l e xs y s t e m sw h i c hc o n s i s to fp o s s i b l yd i f f e r e n tg o v e r n i n ge q u a t i o n si nd i f f e r e n t p h y s i c a ls u b - d o m a i n s o v e r l a p p i n gd o m a i nd e c o m p o s i t i o n sb e c o m eh a r d e rt oi m p l e - m e n ti ns u c has e t t i n g ，w h i l et h en o n o v e r l a p p i n gd o m a i nd e c o m p o s i t i o nm e t h o d sm a y b em o r ed i r e c t l ya p p h c a b l e i na d d i t i o n ，t h et h e o r e t i c a la n a l y s i so ft h en o n o v e r l a p p i n g d o m a i nd e c o m p o s i t i o nm e t h o d sa r em o r ed i m c u l t i nt h i sd i s s e r t a t i o n ，o u rr e s e a r c h e s a r ef o c u s e do no v e r l a p p i n gd o m a i nd e c o m p o s i t i o nm e t h o d s t h ei n i t i a li d e ao fo v e r l a p p i n gd o m a i nd e c o m p o s i t i o nm e t h o d sc a m ef r o mt h e c l a s s i c a ls c h w a r za l t e r n a t i n ga l g o r i t h m i nr e c e n ty e a r st h et h e o r e t i c a lr e s e a r c h e sa n d a p p l i c a t i o n so nd o m a i nd e c o m p o s i t i o nm e t h o d sb a s e do i ls c h w a r za l t e r n a t i n ga l g o - r i t h mh a v eb e e nd e v e l o p e da d e q u a t e l ys ot h a tt h e s em e t h o d sb e c o m ev e r yp o w e r f u l a n de m c i e n ti t e r a t i v em e t h o d s as y s t e m a t i ct h e o r yh a sb e e nd e v e l o p e df o re l l i p t i c f i n i t ee l e m e n tp r o b l e m si nt h ep a s tf e wy e a r s ( s e e 【1 6 ，1 7 ，2 0 】) l i o n sp r e s e n t e d ak i n do fs c h w a r za l t e r n a t i n ga l g o r i t h mi nt w os u b - d o m a i nc a s ef o rh e a te q u a t i o n s x 山东大学博士学位论文 a n dg i v e sac o n v e r g e n c er e s u l tb u td o e sn o tg i v ea n ye r r o re s t i m a t ei n 8 2 ，8 3 i n 1 9 ，2 0 ，x c c a ic o n s t r u c t e dak i n do fa d d i t i v es c h w a r za l g o r i t h ma n dm u l t i p l i c a - t i v es c h w a r zm e t h o da n dp r o v e dt h a tt h ec o n v e r g e n c er a t ei ss m a l l e rt h a no n ef o r p a r a b o l i ce q u a t i o n s ，t h e r et h ea u t h o rd i dn o tc o n s i d e rt h ed e p e n d e n c eo ft h ec o n v e r g e n c ea n dt h ed i s c r e t i z a t i o np a r a m e t e r s h r u ia n dd p y a n gc o n s i d e r e dh o wt h e c o n v e r g e n c ea n d t h ee r r o re s t i m a t ed e p e n do nt h ed i a m e t e ro fs u b - d o m a i n s ，t h es p a c i a l m e s h - s i z e ，t h et i m es t e pi n c r e m e n ta n dt h en u m b e ro fi t e r a t i o n sa te a c ht i m el e v e l ( s e e 【2 6 ，2 7 ，2 8 ，2 9 ，3 0 ，3 1 ，3 2 ，3 3 ，3 4 ) t h ec l a s s i c a ls c h w a r za l t e r n a t i n ga l g o r i t h m i sn o tp a r a l l e l w i t ht h ed e v e l o p m e n to fp a r a l l e lc o m p u t i n g ，m a n ya d d i t i v eo rp a r - a l l e ls c h w a r za l g o r i t h m sh a v eb e e nd e v e l o p e d m d r y j a ，0 b w i l d u n d ，t m s h i h ， e t c ，p r o p o s e dd i f f e r e n ta l g o r i t h m sr e s p e c t i v e l yi n 【2 2 ，2 3 ，2 4 ，2 5 t h e s ea l g o r i t h m s c o n q u e r e dt h el i m i t a t i o no fs e r i a ld a t at r a n s f e r ，w h i c hi si nf a v o ro fp a r a l l e lc o m m u n i c a - t i o n j x ui n 4 2 ，4 3 g i v e sas y s t e m a t i ci n t r o d u c t i o nt oan u m b e ro fi t e r a t i v em e t h o d s f o rs y m m e t r i cp o s i t i v ed e f i n i t ep r o b l e m s t h em a j o rc o n c e r ni si nt h et h e o r e t i c a la s p e c to ft h ea l g o r i t h m st h a ta r ec l a s s i f i e di n t ot w og r o u p s ，n a m e l ys u c c e s s i v es u b s p a c e c o r r e c t i o n ( s s c ) m e t h o da n dp a r a l l e ls u b s p a c ec o r r e c t i o n ( p s c ) m e t h o db yu s i n g d o m a i nd e c o m p o s i t i o na n ds u b s p a c ec o r r e c t i o n i n 4 4 ，j h y a n ga n dp r o f d a n p i n g y a n ga p p l i e dt h i sm e t h o dw i t hg a l e r k i nf i n i t ee l e m e n ts c h e m et op a r a b o l i ce q u a t i o n s a n do b t a i n e dt h ec o n v e r g e n c er a t eo ( a m ) w i t h0 6 0 满足 22 。oz 等a 巧( z ) 已白比r 2 ，z q ( 1 1 2 ) i = l i , j = l 本章结构安排如下首先，在1 2 1 中，我们给出抛物问题的全离散分裂正定混 合元格式，并依据此格式形成并行混合有限元算法i ；然后，在1 2 2 中，我们给出一 些预备知识和引理，这些对证明并行算法的收敛性是非常重要的；在1 2 3 中，我们 分析了并行混合有限元算法i 的收敛性并给出了相应的误差估计；在1 2 4 中，我们 给出一些数值算例去验证我们的理论分析；在1 3 1 中，基于经典的混合有限元格式， 我们形成抛物问题的另一种并行混合有限元算法：并行混合有限元算法i i ；在1 3 2 中，我们研究了并行? 昆合有限元算法i i 的收敛性并给出误差估计 1 2 并行混合有限元算法i 整篇文章中所用到的s o b o l e v 空间中的一般定义、符号和范数同 1 ，2 k 表示一 般正常数，在不同的地方取值可能不同 1 2 1 并行混合有限元算法i 的形成 引入范函空间h ( d i v ；q ) = u l 2 ( q ) 】2 ；d i v w l 2 ( q ) ) 和l 2 ( q ) 或 l 2 ( q ) 】2 中的内积 ( u ，w ) = v w d x v v ，w l 2 ( q ) ， p ) - 萎小出o , 0 3 e 陋2 ) 】2 通过引入未知变量盯= 一v u ，问题( 1 1 1 ) 可被写成如下的变分形式： i 求( 乱，训l 2 ( q ) h ( d i v ；q ) 满足 ( a ) ( u t ，”) + ( v 仃，口) = ( ，口) v v l 2 ( q ) ，( 1 2 1 ) 【( b ) ( 露o ，u ) 一( u ，v u ) ：o v u h ( d i v ；q ) ， 山东大学博士学位论文 这里= - 1 是矩阵的逆 从( 1 2 1 b ) 我们能够推得 。 ( 衫仃t ，u ) 一( u t ，v u ) = 0v u h ( d i v ；q ) ( 1 2 2 ) 在( 1 2 1 a ) 选取u = v u ，u h ( d i v ；q ) 并把它带入( 1 2 2 ) ，我们可以得到一个新的 混合变分形式： f 求( u ，o r ) l 2 ( q ) h ( d i v ；q ) 满足 ( a )( 嗣结t ，u ) + ( v 盯，v u ) = ( f ，v u ) ，v u h ( d i v ；q ) ， ( 1 2 3 ) 【( b ) ( 饥，u ) + ( v 仃，u ) = ( f ，u ) ，v v l 2 ( q ) 设7 - 为时间步长，t n = 仡7 - ，矿= u ( t n ) ，矿n = 仃( 亡竹) 我们可以把问题( 1 2 3 ) 重新 写成如下形式： a ) b ) ( 衫掣，u ) + ( v ，v u ) = ( f n 一1 + r 2 ，v u ) + ( r 3 ，u ) ，v u h ( d i v ；q ) ， ( 1 2 4 ) ( 掣，口) + ( v 矿几，u ) = ( ，n - 1 + r 1 + r 2 ， ) ，v 可l 2 ( q ) ， 这里 匀， r 1 = ，n 一，p 1 = o ( 7 _ 等) ， 耻u n - - 一u n - - 1 一寰_ 。( 丁 耻衫( 生一豢) 刊丁等) ， 为了构造并行混合有限元格式，我们首先做一个区域分解假设( q 。r ，。n ：，是区域q 得一个非重叠区域分解为了获得一个重叠型区域分解，对1 i n ，我们扩展每一个 子区域q ：到一个更大的区域皿，且满足q ：cq icq 和出s 艺( a q ：a q ，a q a q ) h ， 这里日就是所谓的重叠度设五。和五。为定义在区域q 上的两类拟正则有限元 剖分，对应的网格参数分别为h u 和h 仃对1 i n ，假定五“= 五。nq i 和 五新= 五，n 吼是q i 的两个剖分设m h 。cl 2 ( q ) 和协，ch ( d i v ；q ) 分别是定义 在剖分五。和五，的有限元空间 定义如下的双线性形式： a ( e r ，) = ( 。彭盯，) + 7 - ( v 盯，v u ) 基于( 1 2 4 ) 和 1 5 ，我们定义一个全离散分裂正定混合元格式 3 山东大学博士学位论文 全离散分裂正定混合元格式：给定一个初始逼近值( w o ，口2 ) m h 。xh ，对 凡= 1 ，2 ，3 ，求解( 叫嚣，巳z ) m h 。xu 。满足 ( a ) 4 ( 配u ) _ ( j 多n ，- 10 ) h ) + 7 - ( ，”1 ，v u h ) ，v u 魄一， ( 1 2 5 ) ( b ) ( 叫嚣，v h ) + 丁( v 口n ，v ) = ( 叫嚣一1 ，v h ) + 7 ( 厂n 一1 ，v h ) ，v v h m k 、。 注1 1 很容易看到，对于在声，玩z8 ，w 中定义的经典混合元空间要求的匹配关系 ( 即l b b 条件) 在这里不需要从计算的观点看，在这里我们也可以选取一般的连续 有限元空间 接下来，我们建立系统( 1 2 5 ) 的区域分解并行算法定义有限元子空间： 朋：。= v h m h 。；= 0 i nq q t ) ，1 t n 和 1 壤，= d r h ，oo h = 0i nq q i ) ， 1 i n 显然 m h 。= m k + m 乞+ + m 乞， 魄，= 睨，+ 魄，+ + 垅 易知存在区域q 的一个有限开覆盖 o ) 篓1 满足0 nq cq t 由单位分解定理 我们知，存在一个单位分解 仇) 些1 使得 ( a ) s u p p ( l p t ) c0 ，0 妒t 1 ，l j 妒i i i ，。c h 一，1 ； ( b ) 妒1 + 妒2 + + 妒= 1 ， i nq 设妒i 。和妒乞，是分别定义在有限元剖分网格五。和磊，的分片线性插值，磊。和 磊，表示定义在m h 。和协。的插值算子下面，我们形成并行子空间校正算法 基于( 1 2 5 ) ，我们构造一个并行混合有限元算法 并行混合有限元算法i ：设仇表示每一时间步上的迭代次数给定初始值( u o ，盯2 ) m h 。xh ，对7 = 1 ，2 ，通过下面八步求解( u 嚣，盯嚣) m kx 。： 第一步：令矛孑= o h n 一1 ，j ：= 1 ； 第二步：对i = 1 ，2 ，n ，并行求解巧魄，满足 a ( 茑，u h ) = ( 磊嚣- 1 ，磊一( 妒乞叫 ) ) + 丁( ，n ，v 磊。( 妒：。u ) ) ( 1 2 6 ) 一a ( 方二1 ，磊。( 妒；。u 九) ) ，v u h 垤，； 、。 4 山东大学博士学位论文 第三步：令 ( 1 2 7 ) 第四步：如果歹 0 ，满足，对1 冬q 。和v w h ( d i v ；q ) n w 件1 9 ( q ) 2 ， u 般，一岫删】2 k h ；+ 1 1 1 u i i t w 帅( 晰 i 蜒i l v ( u u h ) l l l a ( n ) k h yl i v u l i a ( q ) ， u h t v h 口 i n f i i u u h i il 口( q ) k 危：+ 1i i u l l w * + z ，。) ，v 秽三2 ( q ) n 彬+ 1 口( q ) ， v h e , l u “ ( 1 2 1 3 ) 这里若有限元为b d f m 元 5 1 、b d m 元1 6 或b d d f 元1 8 1 时，r 1 = r ；若为n e d e l e c 元【7 】或r t 元【9 】时，r 1 = r + 1 为了分析全离散分裂正定7 昆合元格式的收敛性，我们引入几个算子我们知道，在 任一种经典混合元空间中，存在一个从h ( d i v ；n ) 到，的算子i i h ( 见i s ，6 ，7 ，8 ，9 ) ， 满足，对1 q 。， ( a )( v ( 盯一h 盯) ，v u h ) = 0 v u ，； ( b )i l 矿一i i 仃| | 【l 。( q ) 】。k h 1 l l 盯l l 【w 件，。( q ) 】：； ( c ) i i v ( 仃一n h ) l l l 。( q ) k h ； l l v 盯i l w 。( q ) ； ( d )l l ( 仃一n h 口) t l l 【朋( q ) 】：墨k 1i l 盯t l l w 件- ，e ( n ) 】。 我们还定义一个l 2 投影算子p m ：l 2 ( q ) _ m k 使得 ( a ) ( b ) ( c ) ( u p m u ，u h ) = 0v u l 2 ( q ) ，v h m h ； i i u 一尸打乱l l l 。( q ) k ：+ 1 i i u l l 日t + - ( q ) v u 日七十1 ( q ) ； 1 1 ( u p m u ) t i i l 。( q ) k 九1i l u 。i i h * + i ( q ) v u h 七十1 ( q ) ( 1 2 1 4 ) ( 1 2 1 5 ) 引理1 4 假定h ，是卢，反z 艿，彰中的一个经典混合有限元空间设( 仃n ，u n ) 和 ( 鲸，叫嚣) 分别是问题以2 彳) 和“2 的解，则我们有下面的估计 8 ( a ) m 。a x1 1 , 7 n 一醛临( q ) 】。 竹 。 + 丁i i v ( 仃竹一鲸) 嵫q ) k h y l + 7 2 ) ， ( b 1 m n a xl l u - 伽帅n2 ( q ) k 孵+ 2 + 危芗1 + t 2 ) ( 1 2 1 6 ) 证明令p n ：盯n _ i l h o n ，p n = 口嚣一i i h o - n ，丌= u 扎一砌u n ，( = 叫嚣二尸m u n 由 山东大学博士学位论文 ( 1 2 5 ) 减( 1 2 4 ) ，我们可得 和 ( a ) ( ( b ) ( 我们知 臼n p 竹一1 7 ，u ) + ( v 伊几，v u ) 书( 爹一竿+ 竿h ) + ( ，f n - 1 _ _ f nv ( o h ) ) ( 1 2 1 7 ) 与池) = ( 塞一_ u n - - _ u n - - 1 + 车胁) i ( - ( 瓦& r + ( ，n 一1 一，n ，u ) + ( v ( 盯n p z ) ，v h ) 0 - n _ _ o - n - - 1 1 p n 7 - _ _ f p n - 1 ) ，u h ) t ”一“7 k 丁 孤幢2 ( j n ； l 2 ( f ：) 2 ) - i - t i 尝慨一l l 2 。q ) 】2 ，) + 扫扔蚓) 】2 这里j n = ( ，竹一1 一，n ，v u ) i 冬i i f n 一1 一，礼l ll l v u h i t 俨1 ，亡礼 k 丁l i 瓦a f | 1 l 2 ( 2 ，咿( q ) 】2 ) + a l l y u 慨n ) 在( 1 2 1 7 a ) 取u h = p n ，我们有 三 ( 砌n ，9 竹) 一( a g e n - 1 矿一1 ) ) + r i l v 妒慨q ) ( 彳话n 一口n 一1 ，p n ) + 7 l i l v 护n i l 2 州丁l i 铷孙肛：( q ) 】2 ) + l l 矿1 l l 】： + 舢幢。；脚舻，刮l 豢 + 面t 峥互1 圳琵z ( q ) 】。+ 圳v 选取6 = 1 2 ，我们能够得到估计 嵫( j 。；昭q ) 一 川慨n ) ( d e n ，e n ) 一( d e n - 1 , 口几一1 ) + 1 - i i v 圳至。( q ) k 丁例铷至：( 邶：( q ) 】2 ) + i l ，1 慨n ) 】2 + 手11 1 凤慨邶：( q ) 】2 ) 刊i 豢慨一脚) 】2 ， + 割谚渺n ) 】2 从1 到钆求和，我们有 ( d e ”，曰n ) + 丁i l v 刚羔。( q ) i = 1 9 山东大学博士学位论文 ( 砌。，口。) + k 2 叶t 优：g f 22 ( 叫懈( q ) 】2 ) 圳丽c 9 2 0 - 慨吣懈( n ) 】2 ) + 丁刭广1 慨刚。+ i i 砒z ( 0 舻】2 ) ) + 三盟i i 旃慨刚。 因此我们很容易地得到下面的估计 觚l i e nj i 琵z ( q ) 】：+ 丁i i v p n ij 至。( q ) sk h 2 , + 2 + 7 - 2 ) 运用( 1 2 1 4 ) 和( 1 2 1 8 ) ，我们便得到估计( 1 2 1 6 a ) 下面，我们证明估计( 1 2 1 6 b ) 成立 在( 1 2 1 7 b ) 中取v h = ( 竹，运用上面的技巧，我们可以推得 岭怖( q ) 一k n - 1 怯c n ) k 丁例豢慨n 纠n ) ) + i b - 州慨q ) + 扣肥( n 酬q ) ) + 叫“丽0 2 u 慨2 n 职q ) ) + 崂a f 慨n 础q ) ) + 丁i i v ( 矿“一酬2 ) + 寺州i 至。( q ) 从1 到扎求和并运用估计( 1 2 1 5 ) ，我们可得 i i c 慨n ) k 纠l i 丽c q 2 u 忆22 ( o , t n ；l 2 ( t 2 ) ) + f f 铷至：( o 北职 + 允擎+ 2 竹i ，i i v ( 仃一酬羔：( q ”互1 嚣i 至。( n ) 从而，运用( 1 2 1 6 a ) ，我们能够推得 m 舰a xl l n i f 主。( n ) s + 2 + 芗1 + 丁2 ) ( 1 2 1 8 ) ( 1 2 1 9 ) 因此，利用( 1 2 1 5 ) ，我们获得估计( 1 2 1 6 b ) 故而我们完成了引理1 4 的证明 1 2 3 收敛性分析 在这一节中，我们研究并行混合有限元算法i 的收敛性我们有如下的结论 一 定理1 1 假定h ，是膨玩z8 ，即中的一种经典混合有限元空间设 u , r t 盯n ) 和 ( 孔嚣，矿嚣) 分别是问题p 2 钏和并行混合有限元算法，的解，则我们有估计 ( a ) m 。a x1 1 , , - n 一仃嚣j i 乙z ( q ) j 。 佗 一、一，j ( b ) 1 0 斗 v ( 盯n 一仃嚣) 慨固k 旧- + 丁2 + ( 豢+ 币t ) 饥) ， i 扎n 一“别至：。n ， 忍罗，+ 2 + 丁2 + ( 豢+ 等+ 豪) m ) ( 1 2 2 0 ) 凡：i f 山东大学博士学位论文 很容易看到并行混合有限元算法i 等价于运用迭代算法求解如下问题：给定初值 ( u ：，盯h n - 1 ) ，求解( 诹，簖) m 札坛，满足，对任意的( v h ，o ) h ) m h 魄， ( a ) ( b ) a ( 分嚣，u ) = ( 。孑盯嚣一1 ，u h ) + 7 ( 厂n 一1 ，v u h ) ， ( u a f t , ，v h ) =