（计算数学专业论文）基于粗细网格的有限元区域分解算法求解抛物方程.pdf

d i s s e r t a t i o no fm a s t e r2 0 1 0 c o l l e g ec o d e ：1 0 2 6 9 r e g i s t e rn u m b e r ：5 1 0 7 0 6 0 1 0 5 6 e a s tc h i n an o r m a lu n i v e r s i t y af i n i t ee l e m e n td o m a i n d e c o m p o s i t i o n a l g o r i t h m f o rp a r a b o l i c e q u a t i o n s d e p a r t m e n t ： m a t h e m a t i c s s p e c i a l t y ：c o m p u t a t i o n a lm a t h e m a t i c s d i r e c t i o n ： f i n i t ee l e m e n tm e t h o d s a d v i s o r ：p r o f d a n p i n gy a n g n a m e ：z o uj i a m a y , 2 0 1 0 s h a n g h a i i 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文基于粗细网格的有限元区域分解算法求解抛物方 程，是在华东师范大学攻读鳃左博士( 请勾选) 学位期间，在导师的指导下进行的研 究工作及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经 发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了 明确说明并表示谢意。 作者签名： 日期) 口i 口年r 月1 日 华东师范大学学位论文著作权使用声明 基于粗细网格的有限元区域分解算法求解抛物方程系本人在华东师范大学攻读 学位期间在导师指导下完成的鲍芷博士( 请勾选) 学位论文，本论文的研究成果归华东 师范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管 部门和相关机构如国家图书馆、中信所和“知网 送交学位论文的印刷版和电子版；允 许学位论文进入华东师范大学图书馆及数据库被奋阅、借阅；同意学校将学位论文加入 全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版， 采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 。经华东师范大学相关部门审查核定的“内部或“涉密”学位论文木， 于年月日解密，解密后适用上述授权。 ， ( 扔2 不保密，适用上述授权。 导师签名 本人签名酱l 办l 。年厂月7 日 幸“涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上 述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用 上述授权) 。 叠。， 一i + 0 、 ：- 邹佳硕士学位论文答辩委员会成员名单 姓名职称单位备注 王元明教授华东师范大学主席 詹兴致教授 华 东 师范大学 潘建瑜副教授华东师范大学 r 一 摘要 抛物方程是描述物理现象的一类重要方程，差分方法和有限元方法是求其数值 解的两类主要数值解法而不论哪种方法最终都归结为大规模方程组的计算当维数 很大、精度要求很高时，传统的求解方程组的方法面临着计算规模大、迭代次数多， 导致耗费时间长传统的单机计算已经很难解决计算规模越来越大与精度要求越来 越高之间的矛盾并行机的出现很好的解决了这一矛盾并行计算随之发展起来，它 是一种高效的计算形式，人们对它的研究也有了大量成果【l ，2 】 在偏微分方程数值解中，区域分解是一类特别适合于并行计算的数值求解方法 它通过将求解区域划分为若干个子区域，从而把大规模的计算化为若干个小规模的 计算，小规模计算之间存在独立性，可以通过并行计算同时求解，从而大大地缩短了 计算时间方法的难度在于子区域边界值的确定和数值解对真解合理的逼近此外区 域分解不仅具有可并行计算的优势，在有限元方法中还具有灵活性大的优势：可以 使用局部拟一致网格对区域进行剖分；甚至可以在各个子区域上使用不同的离散方 法 大部分区域分解的研究是针对椭圆型问题虽然这些算法可以比较容易地转化 为抛物方程的算法，只需在每个时间层上给出类似椭圆方程的区域分解算法即可 但是，由于这些算法均为迭代算法，在每一时间层作大量迭代，导致总体计算量十分 巨大因此，针对抛物问题的特性，构造无需迭代的算法，在应用和理论上都是十分 有意义和重要的d a w s o n 等人已经在抛物方程的区域分解算法领域有了早期的研 究 8 ，1 】他们用无重叠区域的区域分解结合差分或有限元方法求解了一维和二维 抛物方程二维时他们用粗细两种网格剖分区域，同时将求解区域分为两个子区域， 子区域内界点上的值，应用粗网格形成古典显格式求解，得到内界点上的数值解得 到后子区域的边界条件便都可知，之后分别在两个子区域上并行求解内节点上的 数值解通过引入粗网格放松了格式的稳定性条件为参 该算法的误差阶为： o ( a t + h 2 + h h 2 1 1 n h i + h 3 ) 关于抛物方程的有限元法在t h o m e e 的专著【6 】中作了全面的综述d a w s o n 等 人的算法及其理论分析，局限于一个串式结构不能适应复杂的区域本文结合有限 元和区域分解方法求解抛物方程，在d a w s o n 等人已有算法【8 】基础上进行修正提出 和分析非串式结构的算法作为例子，本文将两个子区域增为具有田字结构的四个子 区域，并给出和分析了算法田字结构的四个子区域的算法困难是如何首先设计算法 求出中心节点上的数值解，然后将中心节点的数值解结合边界条件求出内界点的数 值解，进而并行求出四个子区域的内点的数值解文中是通过在x 方向和y 方向上同 时引入粗网格，来克服这一困难的求解过程如下： 第一步，对区域进行粗细网格剖分，并在两种网格上分别建立分片线性有限元空 间 第二步，求中心点上的数值解利用石和y 两个方向上的粗网格，构造了显格式算 法求中心点的数值解，迭代初值护由方程的初始条件沪( 工，y ) 给出 第三步，求区域内界点的数值解利用第二步求得的中心点的数值解以及方程的 边界条件，可以构造显一隐格式迭代求出内界点上的数值解 第四步，求子区域内部节点的数值解利用第二、三步求得的中心点和内边界上 的数值解，再配合方程原有的边界条件，那么每个子区域的边界值便可知进而可构 造四个迭代格式，分别求每个子区域内点的数值解子区域通过内部临界边耦合在一 起并且具有高度并行的特性，可以并行求解，提高计算效率 文章最后一章对该算法的误差进行分析，得到了数值解的口模误差估计本文提 出的算法和分析很容易推广到任意多个具有网状结构的区域分解的情形。 关键词：区域分解，有限元，并行计算，基函数，界面基函数，内边界点 h p a r a b o l i ce q u a t i o ni sa l li m p o r t a n tk i n do fp a r t i a ld i f f e r e n t i a le q u a t i o n sw h i c hc a nd e s c r i b em a n yi m p o r t a n tp h y s i c a lp h e n o m e n a d i f f e r e n c ea n df i n i t ee l e m e n tm e t h o d sa r et w o m a i nm e t h o d st og e tn u m e r i c a ls o l u t i o n sf o rp a r a b o l i ce q u a t i o n s f i n a l l yb o t l lo ft h et w o m e t h o d sc o n v e at os o l v es y s t e m so fe q u a t i o n s u s u a l l yt h ed i m e n s i o n so ft h es y s t e m sa r e h i g e ，b u th i g ha c c u r a c yi ss t i l lr e q u i r e d f a c i n gh i g ed i m e n s i o n sa n dh i g ha c c u r a c y ，j u s t s i n g l ec o m p u t e ri sf a ra w a yf r o md e a l i n gw i t ht h ec o n t r a d i c t i o n t h a n k st ot h ep a r a l l e lc o m p u t e r s ，t h ec o n t r a d i c t i o ni sa l l e v i a t e d a sa ne f f i c i e n tf o r m o fc o m p u t i n g ，p a r a l l e lc o m p u t i n g i sg r o w i n gr a p i d l y r e s e a r c h e r sh a v eg o tm a n yv a l u a b l ec o n c l u s i o n s 1 ，2 】 i nt h ef i e l do fn u m e r i c a ls o l u t i o n so fp 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 ，d o m a i nd e c o m p o s i - t i o nm e t h o d ( d d m ) i sf i tt oa p p l yp a r a l l e lc o m p u t i n g t h ed o m a i n so nw h i c ht h ee q u a t i o n s a r ed e f i n e da r ea l w a y sl a r g ea r e aw i t hh i g hd i m e n s i o n s b yd i v i d i n gl a r g ed o m a i ni n t os e v e r a ls m a l ls u b d o m a i n s ，t h es o l u t i o n so ft h eo r i g i n a lp r o b l e m sc a nb et r a n s l a t e di n t os o l v i n g t h eq u e s t i o n so nt h es u b d o m a i n sr e s p e c t i v e l y t h a tm e a n sl a r g e s c a l ec o m p u t i n gi sc o n - v e r t e dt os m a l l - s c a l ec o m p u t i n gw h i c ha r ei n d e p e n d e n t b e c a u s eo ft h ei n d e p e n d e n c ew e c a ns o l v et h es u b d o m a i n - p r o b l e m si np a r a l l e l t h ed i f f i c u l t yo ft h ed d ml i e sh o wt od e t e r - m i n eb o u n d a r yv a l u e so ft h es u b d o m a i n sa n dt h er a t i o n a l i t yo ft h en u m e r i c a ls o l u t i o n s b e - s i d e so ft h ea b o v ea d v a n t a g eo fp a r a l l e lc o m p u t i n g ，c o m b i n i n gw i t hf i n i t ee l e m e n tm e t h o d d d mh a sh i g hf l e x i b i l i t y ：f i r s t l y , l o c a lq u a s i u n i f o r mg r i di sp e r m i t t e d ，a n dt h ew h o l eq u a s i u n i f o r mg a di s n ti nn e e d ；s e c o n d l y , d i f f e r e n td i s c r e t em e t h o d sc a nb eu s e di nd i f f e r e n t s u b d o m a i n s m o s td d mi sa b o u te l l i p t i ce q u a t i o n sa n di si t e r a t i v e i fw eu s ei t e r a t i v em e t h o d s o ne a c ht i m el e v e l so fp a r a b o l i ce q u a t i o n s ，t h ec o m p u t i n gs c a l ew i l lb eh u g e a c c o r d i n g t ot h ep r o p e r t i e so fp a r a b o l i ce q u a t i o n s ，w ed e s i g na l g o r i t h m sw i t h o u ti t e r a t i o nw h i c ha r e m e a n i n g f u li na p p l i c a t i o na n dt h e o r y d a w s o n ，e t c h a v ed o n em u c h r e s e a r c ho nd d mf o r i i i p a r a b o l i ce q u a t i o n s 【8 ，11 】r n l e yu s ed d m w i t h o u t o v e r l a p p i n gs u b d o m a i n sc o m b i n e dw i t h d i f f e r e n c eo rf i n i t ee l e m e n tm e t h o dt os o l v eo n ea n dt w od i m e n s i o n sp a r a b o l i ce q u a t i o n s i nt w od i m e n s i o n s ，t h e ym a d et w od i f f e r e n c em e s h e s ：c o a r s ea n df i n e ，t h e nd i v i d e dt h e d o m a i ni n t ot w os u b d o m a i n s p a ya t t e n t i o nt h ec o a r s eg d d sa r e j u s ti n 工d i r e c t i o n u s i n g t h ec o a r s e 鲥d st h e yf o r m e da nc l a s s i c a le x p l i c i tp r o c e d u r et os o l v en u m e r i c a ls o l u t i o n s o ni n t e r f a c ep o i n t s a f t e rt h a t ，t h eb o u n d a r yv a l u e so fe a c hs u b d o m a i n sa r ek n o w n u pt o n o wb o u n d a r yv a l u e so fe a c hs u b d o m a i na r ek n o w n f i n a l l yi ne a c hs u b d o m a i nt h e yu s e d i f f e r e n c e0 1 f i n i t ee l e m e n tm e t h o dt os o l v et h en u m e r i c a ls o l u t i o no fi n t e r i o rp o i n t s ，i n p a r a l l e l b e c a u s eo ft h ec o a r s eg r i d s ，t h es t a b l er e s t r i c t i o ni sr e l a x e dt o 等 t h eo r d e r o fe r r o rf o rt h ea l g o r i t h mi s ：o ( a t + h 2 + h h 2 i l n h l + h 3 ) t h o m e eh a v em a d ec o m p r e h e n s i v ee x p o s i t i o na b o u tf i n i t ee l e m e n tm e t h o df o rp a r a b o l i c e q u a t i o ni n 【6 1 b u tt h ea l g o r i t h mi ss e r i a l ，s od o e s n tf i tt oc o m p l i c a t ed o m a i n s t h i sp a p e rc o m b i n ef i n i t ee l e m e n tm e t h o da n dd d mt os o l v ep a r a b o l i ce q u a t i o n t h ea l g o r i t h mm a d es o m em o d i f yb a s e do n 【8 】w ed e s i g na a l g o r i t h mw i t hn o n - s e r i a l s t r u c t u r e a sa ne x a m p l e w ei n c r e a s e dt w os u b d o m a i n st of o u rs u b d o m a i n sl i k e ”田”t h e d i f f i c u l t yo ft h ea l g o r i t h mi sh o wt od e s i g nap r o c e d u r et os o l v et h en u m e r i c a ls o l u t i o no f t h ec e n t e rp o i i l t i nt h i sp a p e r , w ei n t r o d u c ec o a r s eg r i d si nb o t ho fza n dyd i r e c t i o n st o o v e r c o m et h ed i f f i c u l t y d e t a i l sa sf o l l o w ： f i r s ts t e p ，d e c o m p o s et h ed o m a i nw i t hc o a r s e - f i n e 鲥d sa n dc o n s t r u c tf i n i t ee l e m e n t s p a c eo nt h et w om e s h s e c o n ds t e p ，s o l v en u m e r i c a ls o l u t i o no nt h ec e n t e rp o i n t u s i n gt h ec o a r s eg r i di nx a n dyd i r e c t i o n s ，w ec a ng e tn u m e r i c a ls o l u t i o no nt h ec e n t e rp o i n tb ya ne x p l i c i tp r o c e - d u r ew h o s ei n i t i a li t e r a t i v ev a l u e 沪i sg i v e nb yi n i t i a lc o n d i t i o nu 0 ( 石，y ) o ft h ep a r a b o l i c e q u a t i o n t h i r ds t e p ，s o l v en u m e r i c a ls o l u t i o n so ni n t e r f a c e p o i n t s u s i n gt h ec e n t e ra n db o u n d a r yv a l u e ，w ec a l lc o n s t r u c t i m p l i c i ti n 工，e x p l i c i ti ny o r ”i m p l i c i ti ny ，e x p l i c i ti n 工 i v ”p r o c e d u r e st og e tt h en u m e r i c a lv a l u eo nt h ef o u r i n t e r f a c ee d g e s f o u r t hs t e p ，s o l v en u m e r i c a ls o l u t i o n si ns u b d o m a i n s a sar e s u l to fs e c o n da n dt h i r d s t e p s ，b o u n d a r yv a l u e sf o r e a c hs u b d o m a i na r ek n o w nc o m b i n i n gw i t ht h ei n i t i a lc o n d i t i o n t h e nw ec a nc o n s t r u c tf o u rp r o c e d u r e st os o l v en u m e r i c a ls o l u t i o n so fi n t e r i o rp o i n t si n f o u rs u b d o m a i n s ，i np a r a l l e l i nt h el a s tp a r to ft h ep a p e r , w ea n a l y s et h ee r r o ra n dg e tt h e 驴n o r n le s t i m a t e k e y w o r d s ：d o m a i nd e c o m p o s i t i o n ，f i n i t ee l e m e n t ，p a r a l l e lc o m p u t i n g ，b a s i cf u n c t i o n ，i n - t e r f a c ef u n c t i o n v 目录 1 导论 1 1 1s o b o l e v 空间范数的定义 1 1 2预备知识 1 2 抛物方程常用的离散算法及相关结论 3 2 1 有限差分离散理论 3 2 2 有限元离散理论 4 2 2 1有限元方法 4 3二维区域分解算法 6 3 1 两个子区域的情况 6 3 2 四个子区域的情况 7 3 2 1粗细网格的形成。 7 3 2 2 有限元空间的构造 9 3 2 3 中心节点数值解的算法 1 1 3 2 4 内边界点数值解的算法 1 2 3 2 5 子区域内点数值解的算法 1 3 3 3 误差分析 1 4 3 3 1数值解梯度的误差估计 1 6 3 3 2数值解的误差估计2 0 v 1 1 导论 i is o b o l e v 空间范数的定义 为了分析计算方法的收敛性和对近似解作误差估计，需要有适当的度量对于有 限元方法最自然的度量是能量范数本文中主要应用的s o b o l e v 空间范数如下【9 】：q 是，l 维欧氏空间础中的区域( 本文中n = 2 ) ( 1 ) s o b o l e v 空间胛( q ) 和职( q ) 分别装备有范数i i 珊和1 1 p 特别p = o o 时，范 数为l i i | m 。 ( 2 ) b a n a c h 空间上尸( q ) ，装备有范数i i p 特别p = 2 ，o o ，分别装备l 2 范数i i 和r 范数i i 为了体现范数与时间的相关性，我们做如下定义： 若【口，6 】c 【0 ，刀是一个时间段，x = x ( q ) 是一个b a n a c h 或s o b o l e v 空间，则定义该空 间为l p ( a ，6 ；幻，所配范数为| | ( 口，扫特别地记l p ( o ，丁；抑为胪( 嗣 1 2预备知识 为了使后文误差分析的叙述简洁易懂，下面介绍与本文相关的定理【9 】 定理1 1 ( 嵌入定理) 设m 0 为整魏1 p o o ，设q 是r n 中的有界开的连通区域 且具有l i p s c h i t z 连续边界l1 0 1 则下述嵌入关系成立： 昭( q ) q 矽( q ) ，古= 石1 一署，勃 ； 口( q ) ，y q 【l ，o o ) ，勘= ；当p = 1 赋q 可取 嚎罟( q ) ， 若； m i n + 1 嚷( q ) ，v o 口 1 ，翻= ；+ 1 c ? ( q ) ，若；+ 1 0 ，使得i l u ( x ) l l msc m l u ( x ) i 州，v 1 ，瑶( q ) 其中 l u ( j ) i m = ( 矿圳2 户 l a l = m 下面介绍在误差分析时用到的基本不等式【2 l 】： 引理1 1 ( f r i e d r i c h s i n e q u a t l i t y ) 若q 是连通区域那么当“哪( 渤时 “一f i i h , p ( q ) c i 吣( q ) 其中 厅= 丽1 上比 ( 1 1 ) 引理1 2 ( m i n k o w s k i si n e q u a t l i t y ) i ，+ g l l v ( n ) i i f l l t ：( o ) + i i g l l l ( n ) ， 工g 上尸( q ) ，1 ps ( 1 2 ) 引理1 3 ( h o l d e r si n e q u a t l i t y ) 若p ，q 满足：万1 + ；= 1 ，1 p ，q ，其中，上尸( 渤 ，g 口( 鳓，那么f , g l 1 ( q ) 并且有： f i f g l i i f l l p ( q ) i l g l l 驴( 1 3 ) j n 引理1 4 ( s c h w a r z i n e q u a t l i t y ) 这是h o l d e r si n e q u a t l i t y 在p = q = 2 肘的特殊情况，若 f l 2 ( 渤，g 驴( q ) ，那么 g l 1 ( q ) 并且有： j ! ：| ，g i si i f l l l l g i i ( 1 4 ) 2 2 抛物方程常用的离散算法及相关结论 文章中讨论如下具有初边值条件的二维抛物方程的基本模型： 磐一a u = 0 ( 五) ，) q ，t ( o ，刀 ( ) ，0 ) = “。( 五) ，) ，( x ，) ，) q ( 2 1 ) u ( o ，y ，0 = u o ，y ，t ) = 0 ，y ( 0 ，1 ) ，t ( 0 ，t 】 “0 ，f ) = u ( x ，1 ，力= 0 ，工( o ，1 ) ，t ( o ，t 】 其中q = ( o ，1 ) ( o ，1 ) ，a = 器- i - 筹 在数值求解偏微分方程领域中，有限差分法和有限元法是两类重要的数值方法 有限差分具有一些突出的优点，如：格式构造简单，网点上差分方程的局部性；在与 其它方法同样精度的条件下，计算量较小；有限元以一种大范围，全过程的数学分析 即变分原理【3 】为出发点，采用了分片多项式逼近来实现离散化过程，它依赖于由小支 集基函数构成的有限维子空间有限元方法具有广泛的适用性，特别适合几何与物理 条件比较复杂的问题，便于程序标准化，从而适用于工程应用由于有限元的上述优越 性，近年来作为一种独立的数值计算方法得到了广泛关注和迅速发展 下面介绍一些与本文有关的有限差分和有限元理论 1 2 ，1 6 ，1 7 1 2 1 有限差分离散理论 对初边值问题( 2 1 ) 应用差分方法求解的基本步骤如f ： 第一步，求解区域离散化空间维度上用平行线族x i = i h j ，y j = 以，将区域q 进行网格划分；时间维度上也进行划分a t = 磊，则岛= n a t 第二步，微分方程离散化用一阶向后差商代替雾，用二阶中心差商代替二阶导 数貉和貉，相应的误差阶如下： ( 害) ：，= 掣堋m 亿2 ， 3 f 堕o x 2 l 七i , j = 毕+ 。( h b ( 2 3 ) ( 雾) 2 = 塑挚堋砖， 亿4 ， 本文对时间的偏导采用向后差分进行离散：岛尸l = t f n _ f n - i ，该差分格式的误差 阶为o ( a t ) 第三步，初边值条件离散化 第四步，解差分方程组将微分方程和初边值条件的离散化方程联立可以将问题 转化为求解一个较大规模的线性系统 可见有限差分方法的基本思想是：将二维求解区域采用矩形网格剖分，根据方 程和初边值条件等，将连续性方程利用t a y l o r 【7 】展式在网格节点处作离散化处理，解 差分方程组获得所有网格节点处的数值解，差分方法的关键是构造好的实用的差分 格式 2 2 有限元离散理论 有限元方法是在古典的r i t z g a l e r k i n 变分方法【6 】的基础上，以分片插值多项式 为工具构造有限元空间的一种求解偏微分方程的数值解法本文采用有限元方法求 抛物方程数值解它广泛应用于热传导、流体力学、电磁场等连续性问题基本出发 点是将结构离散化，用有限的单元、节点来解决无限维的问题因此，我们先简单回 顾经典的有限元理论及相应的结论 2 2 1 有限元方法 1 、给出( 2 1 ) 的变分形式 由g r e e n 从式 1 9 1 ，可以得到方程雾一a u = 0 对应的变分形式为：求“硪，使 得( 蜥，v ) + ( v “，v ，) = ( 赛，d 对y v 硪都成立其中，砩为s o b o l e v 空间 4 2 、选定单元形状，对求解区域q 进行剖分 有限元网格的生成是有限元分析中重要的技术，对二维区域的网格生成法已经 基本成熟常用的方法有：映射法 1 3 ，1 4 、d e l a u n a y 三角化算法等本文对区域q 作矩形剖分 3 、构造基函数或单元形状函数，形成有限元空间 有限元方法中，有限元空间多由分片多项式来构成，一维时线性元的基函数是分 片的山形函数。这也是本文中构造二维有限元空间基函数的基础 v i ( x ) = 盟，麓一l 工莉 一i i 一“i x i x i o 型，以 j 诉l，一i “l 十i + i x i 0 ， e l s e w h e r e ( 2 5 ) v i ( x ) 是节点x i 上的基函数，可见在每个单元【x i ，x i + l 】上v i ( x ) c 1 ( q ) 有限元空 间朋= s p a n l v l ( 力，v 2 ( 曲，( 曲1 4 、形成有限元方程并求解 根据变分方程可得有限元离散形式为：求u 朋，满足： ( 警，功+ ( v u , v v ) = ( 鬻以y v 朋 ( 2 6 ) 方程的求解从无限维空间转化为有限维空间的求解当y 取遍朋的基时，由有限元 离散方程2 6 可以得到一个三对角的线性方程组，然后利用消去法或迭代法【5 】，求出 方程组的解即可 5 3二维区域分解算法 在偏微分方程数值求解领域中，区域分解算法是一种高效实用的方法，它具有很 大的优越性，首先，它把大问题化为若干小问题，提高了工作效率其次，如果子区域 形状规则( 如矩形) ，已经形成了很多快速算法，如f o u r i e r 变换【4 】、谱方法等而且 计算可以在各子区域独立进行。即算法是高度并行的c n d a w s o n ，q i a n g d u 等人 已经在该领域有所研究，设计了针对抛物方程的无重叠的区域分解算法 3 1 两个子区域的情况 c n d a w s o n 和q d u 等人在文【8 】中及【l l 】中分别应用有限元和有限差分区域分 解算法将二维区域分解为两个串行子区域求抛物方程的数值解为便于后文中四个 子区域的算法介绍及比较，下面简要介绍c n d a w s o n 等人的有限元区域分解算法 问题求解空间仍为：q ( 0 ，t 】首先，在工方向上取j ，则直线j = j 将q 分 为左右( q f ，q ，) 两个子区域其次，在工和y 方向进行细网格剖分，矿：0 = x o x i x n x + 1 = l ，步长埘= x i + i 一而，f - 0 ，1 ，该剖分满足存在矿，( 1 k x n x ) ，使x k x - - = j 类似定义y 方向( 0 ，1 ) 区间的细网格剖分：0 = y o y i ) ，胪+ l = l ，则6 = 矿固为二维区域q = ( o ，1 ) x ( o ，1 ) 的细网格剖分 点瓴y ) 施称为边界点，记为集合r 点( j ，y ) 称为内边界点，记为r x ；除此外 的点称为内点，记为q 则所有网格点可以表示为：锄= ful uq 下面构造q 的粗网格首先定义与剖分矿相关的粗网格参数，满足 h x m i n ( j ，l 一劝，并且j h x ，j + h x 矿也即存在矿使h x = 矿缸那么 o ，j 一皿曩j + h 1 o 构成对q 的粗网格剖分 、， 令朋为细网格上的有限元空间，饰，分别为子区域q ，q ，上的细网格有 限元空间，并且朋国oa 4 f 1 , c 朋朋为粗网格对应的有限元空间，并且胼c 朋抛 物方程的数值解记为，其中嵋= 咯 6 算法描述如f ： ( 1 ) ( 以，y j ) f ：2i l ：，( f - o ，n x o r j = o ，n y ) ( 2 ) ( 船， ) l ：( o r ，”+ ( v ，v 功= 0 ， v 朋 ( 3 ) 阮，y j ) 9 ：( o t u i ”, j ，叻+ ( v ，v ”= 0 ， v 怕 协，y j ) g ：( o r u 。n ，叻+ ( v ，v n = 0 ， v ， 算法中( 2 ) 可以得到一个关于j 【方向是显格式，关于y 方向是隐格式的迭代格式， 通过求解一个三对角方程就可以得到内界点上的数值解内界点上数值解已知的情 况下，两个子区域的边界条件便可知，算法中( 3 ) 在两个子区域上并行求出两个子区域 内节点e 的数值解 3 2 四个子区域的情况 d a w s o n 等人的算法，局限于一个串式结构不能适应复杂的区域本文结合有限 元和区域分解方法求解抛物方程，在d a w s o n 等人已有算法【8 】基础上进行修正提出 和分析非串式结构的算法作为例子，本文将两个子区域增为具有田字结构的四个子 区域。并给出和分析了算法田字结构的四个子区域的算法困难是如何首先设计算法 求出中心节点上的数值解，然后将中心节点的数值解结合边界条件求出内界点的数 值解，进而并行求出四个子区域的内点的数值解下面将对区域的剖分以及有限元空 间的选取给出详细介绍和说明 3 2 1 粗细网格的形成 将方程( 2 1 ) 的求解区域q = ( o ，1 ) ( 0 ，1 ) 在工和y 方向上分别取贾和夕，并利用 x = j ，y = 夕将q 分成四个矩形子区域，形如”田”字结构： a l = ( 0 ，劝( 0 ，夕) ，a 2 = ( j ，1 ) x ( 0 ，刃 a 3 = ( 0 ，劝x ，1 ) ，a 4 = ( 量1 ) ，1 ) 7 具有”田”字结构的区域剖分示意图 同时也产生了四条区域内部的内边界： e 1 2 = ( x , y ) l x = t o y 夕 ，h = ( 工，y ) l y = 歹，j 工 1 e 1 3 = ( 葺y ) l y = y , o 工 斟，e 3 4 = ( 五y ) i x = 只夕 y 1 构造q 的细网格剖分：将z 和y 方向的区间( 0 ，1 ) 进行细网格剖分，矿：0 = x o x l 挪+ 1 = 1 ，步长w = x i + l x i ，f = 0 ，l ，胪该剖分满足存 在矿，( 1sf n x ) ，使x k x = j 类似定义y 方向( o ，1 ) 区间的细网格剖分 矿：0 = y o y l ) ，胪+ 1 = l ，同样要求存在k y ，( 1 矽sn y ) ，使弦= 夕则 6 = 矿o 即为二维区域q = ( 0 ，1 ) ( 0 ，1 ) 的细网格剖分 节点( x i ，y ) 讹称为边界点，边界点集合记为r 节点o ，) 称为内边界 点，其中x 方向i 的内边界点集合，记为l ：方向的内边界点集合，y记为ervuy特别地，点 佤夕) 称为中心点，记为r 除此外的点成为内点，内点集合记为q 8 构造q 的粗网格剖分：首先定义与剖分扩相关的粗网格参数，满足 i i l i n ( j ，1 一劝，并且j h x ，j + 俨扩也即存在扩使h x = d x a x 类似定义和 扩，满足夕一彤，夕+ 和= y 那么 o ，j 日j ，j + 日1 ) o o ，夕一h , y ，夕+ e1 ) 构成对q 的粗网格剖分 3 2