（应用数学专业论文）抛物方程的有限差分区域分解算法.pdf

山东大学硕士学位论文 抛物方程的有限差分区域分解算法 赵良 山东大学数学与系统科学学院，济南，2 5 0 1 0 0 摘要 在自然科学的许多领域中，很多现象是用抛物型方程或者方程组来描述的，如描述 热传导、扩散等物理现象的热传导方程就是最典型的抛物型方程用最传统的有限差分 方法来求解这样的抛物型方程，经受着越来越大规模计算的考验因此，将求解的区域 划分为若干小的子区域，用并行有限差分方法来求解抛物型问题具有重要的理论意义和 应用价值 本文首先对区域分解算法给出一个简要的介绍区域分解算法是上个世纪八十年代 崛起的新方向，它是并行求解大型偏微分方程的有效方法区域分解算法特别受关注是 因为它具有其它方法无法比拟的优越性区域分解算法目前仍处于发展阶段，美国、苏 联、法国、意大利都形成了自己的流派根据对求解区域的不同剖分，形成不同的区域 分解算法，例如不重叠区域分解算法、重叠区域分解算法、虚拟区域法、多水平方法等 等许多物理和力学的问题都可归结为抛物型方程的求解，上个世纪九十年代以来，抛 物方程有限差分区域分解算法得到了发展c n d a w s o n ，q i a n gd u 和t f d u p o n t n ， 袁光伟、沈隆军和周毓麟 3 1 ，张宝琳，万正苏【5 】等人先后都对抛物方程作了比较详细和 深刻的研究最后，简要的介绍了我们给出的抛物方程的区域分解算法 一维抛物方程： l 甓一貉= 0 ，z ( 0 ，1 ) ，t ( o ，卅， u ( z ，0 ) = t l o ( z ) ，z ( o ，1 ) ， i i 札( o ，t ) = u ( 1 ，t ) = 0 ，t ( 0 ，卅， 其中n 是抛物方程的解 在给出d a w s o n 等人抛物方程算法的基础上，文章针对抛物方程提出一种新的高精度 的区域分解方法，在时间上采用有限差分，在空间上，对求解区域进行剖分，从而形成多个 子区域，在子区域的内边界点上关于z 的二阶偏导数利用空间大步长d uf o r t f r a n k e l 格式，在子区域的内点采用三点中心差分全隐式格式，并对此进行并行化实现和分析 山东大学硕士学位论文 我们构造的格式具有良好的稳定性下面给出算法， 算法： 叼= 钍? ，于边界点 叼+ 1 一叼_ 1曙d 一( 叼+ 1 十叼以) + u ；n d 2 7 日2 于子区域内边界点， _ u t _ 1 _ - - 一u t 一u i - + l _ 2 u 万? i + 1 + r r n + l ：。， = 0 n = 1 ，2 ，m 于内点，n = 0 ，1 ，m ， _ v t t + i - u l 一堕立擎：0 ，” 1 1 于子区域内边界点，n = 0 ， 本文针对上述算法进行稳定性和收敛性进行理论分析和数值算例的模拟充分证明 了此算法是一个具有并行本性的差分格式，而且还具有与全隐格式相同的二阶精度当 网格比很大时，此算法格式仍然比较稳定这比较适合大型科学工程计算的要求 二维抛物方程： 1 象一“= 0 ，( z ，y ) q ，t ( o ，t i ， t ( z ，y ，t ) = 0 ，a q ，亡( 0 ，刁， l 乱( z ，y ，0 ) = u 0 ，( z ，y ) q ， 其中u 是抛物方程的解，且让= 0 2 u o x 2 + 0 2 u o y 2 ，q = ( 0 ，1 ) x ( 0 ，1 ) 将在维得到的格式推广到二维，得到一个新的二维有限差分显式格式，发展了新 的算法 算法： = 铭易， 于边界点 堕1 二堕：一= ! 盟：监坐坠 一竖n 正当+ i 产n “- - i 二塑n ：0 ， 于内边界点，礼= i ，2 ，m 堕二堕一：r r 业n + l _ o r r n 。+ l a ：f r l 二n + 幺l 一盟乜譬竺趋：0 ， 于内点，n1 10 ，l ，m ， i i 山东大学硕士学位论文 堕堕一坠黝二! 臻坠纽 一监! = 避：0 ， 于子区域内边界点，n = 0 ， 此算法格式仍然是一个具有良好稳定性的并行本性的差分格式。 全文共四章，组织结构如下。 第一章为引言，简要介绍了区域分解算法的发展和热传导方程有限差分区域分解算 法的概况以及本文所讨论的基本内容 在第二章，我们首先给出d a w s o n 和盛志强等人的内边界点处理方法，得到关于求 解一维常系数抛物方程区域分解算法的误差估计在给出d a w s o n 等人抛物方程算法的 基础上，本文针对抛物方程提出一种新的高精度的区域分解方法，在时间上采用有限差 分，在空间上，对求解区域进行剖分，从而形成多个子区域，在子区域的内边界点上关 于z 的二阶偏导数利用空间大步长d uf o r t f r a n k e l 格式，在子区域的内点采用三点 中心差分全隐式格式，并对此进行并行化实现和分析我们构造的算法格式具有良好的 稳定性和具有与全隐格式相同的二阶精度最后证明了这些很好的性质 第三章研究了二维抛物问题我们首先将在一维得到的格式推广到二维，得到一个 新的二维有限差分显式格式，它和全隐格式有相同的精度，在时间上采用有限差分，在 空间上，对求解区域进行剖分，从而形成多个子区域，在子区域的内边界点上关于z 的 二阶偏导数利用空间大步长d uf o r t f r a n k e l 格式，在子区域的内点采用三点中心差 分全隐式格式，并对此进行并行化实现和分析对二维抛物问题设计了一个区域分解算 法它的稳定性条件和精度仍然很好 第四章我们提供了一些数值实验的结果，并且考察了新算法对一定测试问题的稳定 性，精度以及并行性 关键词：区域分解，抛物方程，有限差分，显一隐格式，并行计算 i i i 山东大学硕士学位论文 af i n i t ed i f f e r e n c ed o m a i nd e c o m p o s i t i o na l g o r i t h m f o rp a r a b o l i ce q u a t i o n z h a ol i a n g s c h o o lo im a t h e m a t i c sa n ds y s t e ms c i e n c e s l8 h a n d o n gu n i v e r s i t y j i n a n , 2 5 0 lo o , s h a n d o n gp r o v i n c e p r c h i n a a b s t r a c t i nm a n yf i e l d so ft h en a t u r a ls c i e n c e ，m a n yp h e n o m e n a sa r ed e s c r i b e db yp a r a b o l i c e q u a t i o no re q u a t i o n s h e a te q u a t i o ni st h em o s tt y p i c a lo n eo fp a r a p o l i ce q u a t i o n s ，w h i c h d e s c r i b e sm a n yp h y s i c a l - p h e n o m e n a s ，s u c ha sc o n d u c t i o n ，d i f f u s i o n ，e t c w ea r ee x p r e r i - e n c i n gi n c r e a s i n gt r i b u l a t i o n sb yu s i n gt h et y p i c a lf i n i t ed i f f e r e n c em e t h o d st os o l v et h o s e p a r a b o l i c e q u a t i o n s h e n c e ，i ti sv e r ym e a n i n g f u lt od i v i d et h ed o m a i no v e rw h i c ht h e p r o b l e mi sd e f i n e di n t os u b d o m a i n s ，a n ds o l v et h es u b d o m a i np r o b l e mi np a r a l l e l f k s t ，ab r i e fi n t r o d u c t i o ni sg i v e nt ot h ed o m a i nd e c o m p o s i t i o na l g o r i t h m d o m a i n d e c o m p o s i t o na l g o r i t h mi san e we f f e c t i v em e t h o dd e v e l o p e dt os o l v et h ep a r t i a ld i f f e r e n - t i a le q u a t i o ni np a r a l l e l l o t so fa t t e n t i o ni sp a i dt ot h ed o m a i nd e c o m p o s i t i o na l g o r i t h m f o ri t sn u m e r o u sa d v a n t a g e s m a t h e m a t i c i a n sf r o mt h ew h o l ew o r di n c l u d i n ga m e r i c a ， r u s s i a ，f r a n c ee t c a r ei n t e r e s t i n gi nt h em e t h o da n dd e v e l o p i n gt h e i rg e n r e s a c c o r d i n g t ot h e i rd i f f e r e n td e c o m p o s i t i o no ft h ec o m p u t a t i o nd o m a i n ，d o m a i nd e c o m p o s i t i o na l - g o r i t h ma r ed i v i d e di n t ou 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 na l g o r i t h m ，o v e r l a p i n gd o - m a i nd e c o m p o s i t i o na l g o r i t h m ，d u m m yd o m a i nd e c o m p o s i t i o na l g o r i t h m ，m u l t i p a r a l l e l d o m a i nd e c o m p o s i t i o na l g o r i t h me t c l o t so fp 1 1 y s i c a la n dm e c h a n i c a lp r o b l e m sc o u l db e e n d e di n t ot h es o l u t i o no ft h ep a r a b o l i c a le q u a t i o n f i n i t ed i f f e r e n c ed o m a i nd e c o m p o - s i t i o na l g o r i t h mo ft h ep a r a b o l i c a le q u a t i o ni sd e v e l o p i n gr a p i d l ys i n c e1 9 9 0 s p a r t i c u l a r a n dp r o f o u n dr e s e a r c ha r eg i v e nb yc n d a w s o n ，q i a n gd ua n dt f d u p o n t 1 1t ot h e p a r a b o l i c a le q u a t i o nb yu s i n gd o m a i nd e c o m p o s i t i o na l g o r i t h m ab r i e fi n t r o d u c t i o no f o u ra l g o r i t h m sf o rp a r a b o l i ce q u a t i o ni sg i v e na tt h ee n d i v 山东大学硕士学位论文 t h eo n es p a c ed i m e n s i o n a lp a r a b o l i c a le q u a t i o n ： 象一貉= 0 ，z ( o ，1 ) ，t ( o ，卅 u ( z ，0 ) = u o ( z ) ，z ( 0 ，1 ) ， u ( o ，t ) = 乱( 1 ，t ) = 0 ，t ( 0 ，州， ui st h es o l u t i o no ft h ep a r a b o l i c a le q u a t i o n b a s e do nt h ea l g o r i t h mf o rt h ep a r a b o l i ce q u a t i o nw i t hc o n s t a n tc o e f l i c e n tb yc i v d a w s o n e t c ，w ed e v e l o pan e wa l g o r i t h mf o rp a r a b o l i c a le q u a t i o n t h ed o m a i nd e c o m p o s i t i o n m e t h o db a s e do nd uf o r t f r a n k e ls c h e m ea tt h ei n t e r f a c ep o i n ta n df u l l yi m p l i c i t s c h e m ea ti n t e r i o rp o i n t sf o rt h ep a r a b o l i ce q u a t i o n a n dt h ep r e c i s i o no ft h en e wa l g o - r i t h mi se q u a lt ot h ep r e c i s i o no ft h ei m p l i c i ts c h e m e s ，s ow ed e s i g nan e wa l g o r i t h mf o r t h ep a r a b o l i c a le q u a t i o n t h es t a b i l i t y - c o n d i t i o na n dp r e c i s i o na r ew e l l a l g o r i t h m ： 叼= t ， 叼+ 1 一叼一1 2 r 叼+ 1 7 a tb o u n d a r yp o i n t s ， 一堡垒2 二( 鲨：鲨二：2 坠2 ：o h 2 7 a ti n t e r f a c ep o i n t s ，n = 1 ，2 ，m 一鲨二! 孥：堕：o ， 2 1 a ti n t e r i o rp o i n t s ，礼= 0 ，1 ，m ， w + 1 一叼u h d 一2 叼+ 唯d 1-h2 = 0 ， a ti n t e r f a c ep o i n t s ，扎= 0 ， i nt h i sp a p e r ，w e ud i s c u s st h ea l g o r i t h ms t a b i l i t ya n dc o n v e r g e n c e ，a n da l s ot h e n u m e r i c a le x a m p l e so fs i m u l a t i o na r eg i v e n s o m ec h a r a c t e r sa x ep r o v e db yn u m e r i c a l e x p e r i m e n t si nt h i sp a p e r b yp e r f o r m a n c ea n a l y s i so fp a r a l l e ln u m e r i c a le x p e r i m e n t s ， t h em e t h o dw i t hi n t r i n s i cp a r a l l e l i s mh a st h es a m ea c c u r a t ea st h ef l f l l yi m p l i c i ts c h e m e ， w h i c hs u i tl a r g es c a l es c i e n t i f i cc o m p u t i n ga n de n g i n e e r i n gc o m p u t e r 巨- 篙z x u = 0 , ( x , y 蔷) e f q , t 巩 v 山东大学硕士学位论文 ui st h es o l u t i o no ft h ep a r a b o l i ce q u a t i o n ， a u = 0 2 u o z 2 + 伊u 西2 ，q = ( 0 ，1 ) ( 0 ，1 ) w eg i v eas t r a i g h t f o r w a r dg e n e r a l i z a t i o no ft h eo n e d i m e n s i o n a lr e s u l t st ot w os p a c e d i m e n s i o n s ，g e tan e wa l g o r i t h m ： a l g o r i t h m ： = 喝， 盟二堕：一 2 r 时1 一 u n + 1 一 下 a tb o u n d a r yp o i n t s ， 三! i n 2 ；i 二：i ：2 + 1 ：! ! n 泣- - 1 ：二：! n = 2 ；j 舶 竖n 正当+ l 产n n - - 1 三皑n = 0 ， a ti n t e r f a c ep o i n t s ，n = 1 ，2 ，m u n 上+ 域l o _ 二r r 捌n + l - l 二1 _ u 二n = + 正i 盟塑芦：0 ， a ti n t e r i o rp o i n t s ，佗= 0 ，1 ，m ， 堕2 ：i = ! 翌坠黝 u 2 4 + 1 2 u 2 , 4 + u ：d - x ：0 ， a ti n t e r f a c ep o i n t s ，佗= 0 ， w ea l s od i s c u s s e dt h ea l g o r i t h ms t a b i l i t ya n dc o n v e r g e n c e w ec a nd r a wt h ec o n c l u - s i o nt h a tt h ea l g o r i t h mf o rt w os p a c ed i m e n s i o n a lp a r a b o l i c a le q u a t i o ns u i tl a r g es c a l e s c i e n t i f i cc o m p u t i n ga n de n g i n e e r i n gc o m p u t i n g t h i st h e s i sw i l lb ed i v i d e di n t o4c h a p t e r s ，o r g a n i z e da sf o l l o w s ： i nc h a p t e rl ，t h ed e v e l o p m e n t so ft h ed o m a i nd e c o m p o s i t i o na l g o r i t h ma n df i n i t ed i f - f e r e n c ed o m a i nd e c o m p o s i t i o na l g o r i t h mf o rn u m e r i c a ls o l u t i o no ft h ep a r a b o l i c a le q u a t i o n h a v eb e e ni n t r o d u c e d ，a n dt h em a i nw o r ko ft h i sp a p e ri sa l s od e s c r i b e d i nc h a p t e r2 ，f i r s tw ei n t r o d u c et h ed i f f e r e n c ed o m a i nd e c o m p o s i t i o na l g o r i t h mf o r p a r a b o l i ce q u a t i o nw i t hc o n s t a n tc o e f f i c e n ta ti n t e r f a c ep o i n t sd e s i g n e db yc n d a w s o n a n ds h e n gz h i q i a n ge t c a n dt h ee r r o re s t i m a t er e s u l t s i nt h i sp a p e rw ed e v e l o pan e w a l g o r i t h mf o rt h ep a r a b o l i ce q u a t i o n ，t h ed o m a i nd e c o m p o s i t i o nm e t h o db a s e do nd u f o r t f r a n k e 2s c h e m ea tt h ei n t e r f a c ep o i n ta n df u l l yi m p l i c i ts c h e m ea ti n t e r i o rp o i n t s f o rt h ep a r a b o l i ce q u a t i o n a n dt h ep r e c i s i o no ft h en e wa l g o r i t h mi se q u a lt ot h ep r e c i - s i o no ft h ei m p l i c i ts c h e m e s s ow ed e s i g nan e wa l g o r i t h mf o rt h ep a r a b o l i c a le q u a t i o n v i 山东大学硕士学位论文 t h e s t a b i l i t y - c o n d i t i o na n dp r e c i s i o na r ew e l l h e n c ew ec a l lu s eal a r g e rt i m es t e p ，w h i c h c a ns a v eal o to fc o m p u t a t i o n a lw o r k sf o rt h ep a r a l l e ls o l u t i o no ft h ep a r a b o l i cp r o b l e m a n dt h en e wa l g o r i t h ms u i tl a r g es c a l es c i e n t i f i cc o m p u t i n ga n de n g i n e e r i n gc o m p u t i n g i nc h a p t e r3 ，w ed i s c u s s e dt h et w os p a c ed i m e n s i o n a lp a r a b o l i c a le q u a t i o n w eg i v ea s t r a i g h t f o r w a r dg e n e r a l i z a t i o no ft h eo n e d i m e n s i o n a lr e s u l t st ot w os p a c ed i m e n s i o n s ，g e t an e wa l g o r i t h mf o rt w os p a c e d i m e n s i o n a lp a r a b o l i c a le q u a t i o n ，a n dw ep r o v et h es t a b i l i t y a n dc o n v e r g e n c eo ft h en e wa l g o r i t h mf o rt h et w os p a c ed i m e n s i o n a lp a r a b o l i c a le q u a t i o n i nc h a p t e r4 ，w eg i v ean u m e r i c a le x a m p l ea n dn u m e r i c a lr e s u l t st ov a l i d a t et h ea l - g o r i t h m 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 ，p a r a b o l i ce q u a t i o n ，f i n i t ed i f f e r e n c e ，e x p l i c i t i m p l i c i ts c h e m e ，p a r a l l e lc o m p u t a t i o n v i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 所取得的成果除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果 和集体，均已在文中以明确方式标明 对本论文的研究作出重要贡献的个人 本声明的法律责任由本人承担 论文作者签名：嫠匿日期：趟。足 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留 或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅；本人授权山东大学可以将本学位论文全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 论文作者签名： 第一章引言 1 1 区域分解算法 数学物理及工程问题，如油、气藏的勘探与开发、大型结构工程、航天器的设计、天 气预报、反应堆计算等，无不归结于求解大型偏微分方程计算区域往往是高维的、大 范围的，其形态可能很不规则，给计算带来很大困难区域分解算法是上个世纪八十年 代崛起的新方向，它是并行求解大型偏微分方程的有效方法，并随着并行计算机和并行 算法的发展得到了进步蓬勃发展 简而言之，区域分解算法是把计算区域q 分解成若干个子区域：瓦= u _ t ，子域 = 1 g 的形状尽可能规则，于是原问题的求解转化为在子域上求解区域分解算法特别受关 注是因为它具有其它方法无以比拟的优越性： 1 它把问题化为若干小问题，缩小计算规模 2 子区域形状如果规则( 如长方形) ，其上或者允许使用熟知的快速算法，如快速 f o u r i e r 变化( f f t ) ，谱方法，7 方法等；或者使用解这类问题的高效率软件 3 允许使用局部拟一致网格，无需用整体拟一致网格甚至各个子域可以用不同离 散方法进行计算这对于形态极不规则的问题，如锅炉燃烧问题；炉体部分与烟筒部分 几何尺寸相差很大，整体计算为了对付烟筒部分，不得不把网格加得很密，而区域分解 算法可以把这两部分分别处理，具有很大的灵活性其它如建筑结构中的板、梁组合结 构、轧辊设计等也有类似情况 4 允许在不同子域选用不同的数学模型，以便整体模型更适合于工程物理实习情 况，例如，油、气藏模拟中，靠近管部分流速快，应服从非d a r c y 流规律，而远离井管处 则服从d a r c y 流规律，分解区域时应考虑在不同子域选用不同的数学模型；又如气体绕 飞行体流动，在边界层附近为粘性流，在边界层外为无粘流，二者有不同的数学模型， 使用区域分解算法易于在不同子域选用更适合实际的模型；再如对数学中颇为棘手的混 合型方程，如果我们把区域的椭圆型部分与双曲型部分作为两个子域考虑，在子域内进 行计算，就简单多了 5 算法是高度并行的，即计算的主要步骤是在各子域内独立进行的因为区域分解 算法可以把大型问题化为小型问题，复杂边值问题分解为简单边值问题，串行问题分解 为并行问题，因此对这种方法的研究非常活跃，其具体方法也是多种多样的 i - - 2 9 j 山东大学硕士学位论文 区域分解算法目前仍处于发展阶段，美国、苏联、法国、意大利都形成了自己的流 派根据对求解区域的不同划分，形成不同的区域分解算法下面简要的介绍几种区域 分解算法 不重叠区域分解算法，该算法的特征是先对区域作初始割分 吨) ，q 间互不重叠，我 们主要考虑二色问题，即各子域能用两种颜色区分如图1 1 ，均是不重叠的区域划分， 不同的是图前者没有内交点，后者有内交点无交点情形，d i r i c h l e t n e u m a n n 可以移 植并得到与h 无关的收敛速度；有内交点情形，处理较难，必须使用专门的顶处理方法 图1 1 不重叠区域划分 重叠型区域分解算法，该算法是以s c h w a r z 交替法为理论依据的1 8 7 0 年德国数学 家疗a s c h w a r z 首次用交替法论证了两个相互重叠区域( 如图1 2 ) 的和集上l a p l a c e 方程d i r i c h l e t 问题解的存在性之后，n u e m a n n 、p i c a r d 、s o b o l e v 、m i k h l i n 等人又进步发展了s c h w a r z 算法，该算法对于求解非矩形区域有着很好的优势，它把 复杂区域分解为若干个相互覆盖的子区域，在子区域上可以用快速算法求解，这就大大 增加了人们研究的兴趣我国康立山教授首先认识到s c h w a r z 算法在异步并行计算中 的应用，法国g l o w i n s k i 等应用s c h w a r z 算法加速共轭梯度法，并在流体力学计算上 取得成功，然而对s c h w a r z 算法提出全新解释的当归功于p l l i o n s 他首先巧妙地把 s c h w a r z 方法与投影方法联系起来，从而使那些看来复杂的收敛性证明，简化为投影算 子的估计对于多个重叠区域情形，甚至非线性问题的s c h w a r z 方法皆在统一框架下得 到处理。l i o n s 又提出s c h w a r z 算法的随机解释，把位势理论、布朗运动和s c h w a r z 交替方法联系起来，这种多学科问渗透引起人们极大的兴趣总之，以s c h w a r z 算法为 2 山东大学硕士学位论文 基础的重叠型区域分解算法，目前正由于p l l i o n s 的卓越贡献得到新的认识，成为构 造新算法的理论依据为了适合并行计算的需要，所谓加性s c h w a r z 算法得到发展， w i d l u n d 、吕涛、石济民、林振宝等皆独立提出不同算法，这些算法可克服交替算法的 串行性，更利于并行处理 图1 2 重叠区域划分 虚拟区域法，前面讨论的区域分解法是把形态复杂的区域上的问题转化为形态规则 的子域上的问题来计算，而虚拟区域法，则是把形态复杂的区域扩张为一个规则区域( 通 常为矩形或者长方体) 来求解显然，对于一个曲边区域，一般不可能分解为规则子域 ( 矩形) 的合集，但总可以找到一个矩形包含它，从这种意义上讲虚拟区域法似乎更有 普遍意义 多水平方法是后崛起的新方向一般来说多水平方法应包括多层网格法与基于多水 平空间分裂的预处理方法两方面内容所谓多水平分裂，就是在平面多角型g 初始粗三 角剖分的基础上，通过逐步加密生成一族嵌套剖分 3 山东大学硕士学位论文 1 2 抛物方程区域分解算法 许多物理和力学的问题都可归结为抛物型方程的求解，其数值模拟已有很多的差分 方法，最常用的差分方法有古典显式、古典隐式和c r a n k n i c o l s o n 格式1 1 8 - 2 1 】从 并行计算观点看，古典显式应该是最理想的并行算法，适合予各种类型的并行机，但这 种格式是条件稳定的，特别是在多维问题中，稳定性条件更苛刻，计算的时间步长受到 严格的限制，因此在实际应用问题中通常采用隐式差分格式隐式差分格式之所以被广 泛的应用是因为它是无条件稳定和绝对收敛的，对任意的网格比都能保证对计算误差的 控制然而求解隐式格式需要求解一个代数方程组，并且它所求解的方程组的阶数与划 分节点个数是一样的，这样随着计算节点的增加计算量越来越大，甚至难以计算下去 尽管单机的计算速度和内存容量变得很大，但仍难以完全满足需求，其有效的解决方法 就是构造良好的具有并行本性的区域分解方法有限差分区域分解算法是在并行机上求 解偏微分方程数值解的一种差分方法，该方法先将偏微分方程的求解区域剖分成几个子 域，然后在每个子域上利用差分格式并行求解构造求解大型科学与工程计算中出现的 抛物方程初边值问题的并行差分格式，应追求如下几个目标； 争取将对步长限制的稳定性和收敛性条件适当放宽，允许放大时间步长； 要求格式设计简单，最好是两层差分格式，易于在并行机上实施，且易于将已有的 串行程序并行化； 具有高并行度。能够自由的划分分解区域，便于实现负载平衡，并且所要求的通讯 是局部的，仅在相邻处理器之间进行通讯，尽量减少并行开销 有限差分区域分解算法就比较符合上面的几点要求区域分解算法是在并行机上求 解偏微分方程数值解的一种较自然的方法，该方法先将偏微分方程求解区域划分为若干 个子区域，然后在各个子区域并行求解方法的难点就在于子区域边界值的确定和数值 解对真解合理的逼近 上个世纪九十年代以来，抛物方程有限差分区域分解算法得到了发展在文 1 】中， g n d a w s o n ，q i a n 9d u 和t f d u p o n t 1 1 ，针对常系数抛物方程构造了一种区域分解算 法在子区域的内边界处采用空间大步长古典显式格式计算出内边界点酶值，将其作为 子区域的内边界处的d i l i c h l e t 边值条件，然后在子区域内部用古典隐式并行计算该算 法中显式格式的稳定性限制条件得到了放宽在文f 1 2 】中，盛志强等人，针对常系数抛 物方程提出了两个具有改进稳定性限制条件的新显格式与经典显格式相比，稳定性限 制条件分别对两维抛物问题放宽了4 倍，对一维问题放宽了2 倍，同时它的精度与经典 全隐格式的相同在文f 9 l 中，李长峰文给出了变系数抛物模型的区域分裂差分法，在内 4 山东大学硕士学位论文 边界点采用了粗网格显格式，虽然也是条件稳定的但其稳定性条件要比全局显格式稳定 性条件弱了许多在文【4 】中，g u a n g w e iy u a n ，s h a o h o n gz h u 和l o n g j u ns h e n 构造 的格式在子区域的边界处采用组显( g e ) 格式求解，稳定性步长与古典显式相比，放大 了8 倍在文【5 】中，张宝琳，万正苏平行于d a w s o n 等人的做法，在子区域的边界处采 用小时间步长非对称格式和组显格式求解在文 6 】中，q d u ，m m ua n dz n m u 构 造的格式在子区域的边界处采用小时间步长显式格式和大空间步长古典显式组合格式求 解在文【1 0 】中，张宝琳和申卫东考虑在子区域的左、右内边界点处分别使用s a u l 7 y e v 的非对称差分格式，将由此算出来的值再作为子区域的内边界处的d i l i c h l e t 边值条件， 然后在子区域内部用古典隐式并行计算 5 第二章一维抛物方程有限差分区域分解算法 2 1d a w s o n 等人的算法和结果 2 1 1预备知识 我们研究求解下述一维常系数抛物方程初边值问题的有限差分区域分解算法： l 甓一貉= o ，z ( 0 ，1 ) ，t ( o ，列， u ( 。，0 ) = u 0 ( z ) ，。( 0 ，1 ) ， ( 2 1 1 ) l ( o ，t ) = u ( 1 ，t ) = 0 ，t ( 0 ，卅， 其中心是抛物方程的解 一 用差分方法来求解问题( 2 1 1 ) ，首先，把区域( o ，1 ) 分解为两个子区域( 0 ，- ) 和 ( ，1 ) ，设为正整数，h = l ，甄= i h ，i = 0 ，l ，而且假定这里的虿= x k 0 又设h = d h ，d 为正整数，且假定h m 伽忙，1 一虿) ，又设7 - = a t = t m ，m 为正整 数，并令t n = n a t ，h 和丁分别称作空间步长和时间步长定义口= ，( 戤，t ”) 及差分算子 删= 盟掣， 如舴) ：丛掣， 锑胁) ：丛盟名笋皿型， 若i = 0 或，或者n = 0 ，则称( a ，t n ) 为边界点；当忍= 虿且不是边界点的网格点 称为内边界点；上述以外的点则统称为内点 再微分方程离散化，由t a y l o r 展式可知，在节点( i ，礼) 处微商和差商有下述关系： j 血幽事业逍= 【象】+ d ( 丁) ， i 血型止坐h 业2 出虹世= l 砸0 2 u “l n + d ( 2 ) 叼是u ( 以，t n ) 的近似值，则用差商近似代替式( 2 1 1 ) 中的微商后，即得相应的差分方 程。亦称差分格式： 鲨：l 二兰! 一坚! 二等兰鱼：o ， 山东大学硕士学位论文 i = l ，2 ，一l ；礼= 0 ，1 ，2 ，m 一1 此格式称为解抛物方程( 2 1 1 ) 的古典显格式 若我们采用向后差分格式，那就是无条件稳定的古典隐式格式： 竽n - - _ u ? - - i 一鱼挚= 0 ， i = l ，2 ，一l ；礼= 1 ，2 ，m 我们知遭其截断误差d ( 丁+ h 2 ) 2 1 2d a w s o n 等人设计的算法和结果 e n d a w s o n ，q i a n gd u 和t f d u p o n t 1 j 针对常系数抛物方程在子区域的内边界 处采用空间大步长古典显式格式计算出内边界点的值，将其作为子区域的内边界处的 d i r i c h l e t 边值条件，然后在子区域内部用古典隐式并行计算，构造了一种新区域分解 算法 算法l ： 叼= 乱? ， 于边界点 ( 2 1 2 ) a ，w 一畿叼- 1 = 0 ， 于内边界点 ( 2 1 3 ) 岔，a t w 磋，i 叼= 0 ， 于内点( 2 1 4 ) 其中c 9 为数值解是对精确解u = u ( 戤，t n ) 的近似在由时间层t = t n q 到t = t “的计 算中，可在稳定性条件： a t 日2 2 ，( 2 1 5 ) 下进行首先计算内边界处的函数值己，然后在两个子区域( o ，_ ) 和( - ，1 ) 上的计算化 为彼此独立的分段隐式计算他们得到算法1 中差分解逼近的先验误差估计结果： 定理2 1 ：当a t h 2 2 时，求解问题( 2 1 1 ) 的区域分解算法l ：( 2 1 2 ) 一( 2 1 4 ) 给出的近似解卵满足： m a x l u ( x t ，t n ) 一叼l 墨- 宰( a t + h 2 + h 3 ) ( 2 1 6 ) 一； 其中，c o = m a x 1 a 2 u l & 2 l ，击i 伊u 锄4 b 定理2 1 中值得注意的两点是： 一、由于在内边界处使用了空间大步长h = d h 的古典显式格式，与通常步长h 的 显格式比，稳定性条件放宽了d 2 倍； 二、局部一点的大步长显式格式计算一般并不会使该算法1 数值解的整体逼近性质 变坏，因为在( 2 1 6 ) 中仅多了含日3 的误差项 8 山东大学硕士学位论文 在文【l o 】中，张宝琳等人考虑在子区域的左，右边界点处分别使用s a u l 7 y e v 的非 对称差分格式，构造由两个内边界点虿和雾= 虿+ h 把区域( 0 ，1 ) 分成两个子区域的算 法，其中虿= z 七，蚕= z 知+ l ，且假定h m i n - z ，l 一罨 算法2 己? = 嵋， 于边界点 ( 2 1 7 ) 1 侥，i 叼一- f f 。( 。，日职囊1 一允，日叼) = 0 ， 于内边界点虿