（应用数学专业论文）热方程紧差分格式的区域分解算法.pdf

d i s s e r t a t i o no fc o l l e g et e a c h e r s t u d y i n g i n s e r v i c ef o rm a s t e rd e g r e e ，2 0 1 0 c o l l e g ec o d e ：10 2 6 9 s t u d e n ti d ：9 1 0 6 0 6 0 11 0 5 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 mf o rc o m p a c t d i f f e r e n c es c h e m e so fh e a t e q u a t i o n u n i v e r s i t y ： e a s tc h i n an o r m a l u n i v e r s i t y d e p a r t m e n t ： m a t h e m a t i c s m a j o r i t y ：a p p l i e dm a t h e m a t i c s d i r e c t i o n n u m e r i c a ls o l u t i o no 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 s u p e r v i s o r ：p r o f e s s o r d a n p i n gy a n g c a n d i d a t e ：h o n g m e iz h a n g m a y , 2 0 1 0 s h a n g h a i 郑重声明 东师范大学攻 华东师范大学学位论文原创性声明 1 1 1 1 1 1111 1i i i ii ii i i iiii y 17 4 3 3 3 0 热方程紧差分格式的区域分解算法，是在华 学位期间，在导师的指导下进行的研究工作及 取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表 或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了 明确说明并表示谢意。 作者签名： 日期：2 0 f d 年s 月l 召日 华东师范大学学位论文著作权使用声明 热方程紧 导师指导下完成 法系本人在华东师范大学攻读学位期间在 学位论文，本论文的研究成果归华东师范大 学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部 门和相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版： 允许学位论文进入华东师范大学图书馆及数据库被查阅、借阅：同意学校将学位论 文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘 要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文奉， 于年， 月 日解密，解密后适用上述授权。 o 力2 不保密，陋用上述授权。 导师签名* 本人签名j 殛。绉l ” 2 0 f d 年s 月2 富日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位论 文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为自效) ，未经上述 部f - j 审定的学位论文均为公丌学位论文。此声明栏不填写的，默认为公开学位论文，均适用 张红梅硕士学位论文答辩委员会成员名单 姓名职称单位备注 宋宝瑞教授上海交通大学主席 倪明康教授华东师范大学 任寒教授华东师范大学 汪志鸣教授华东师范大学 刘兴波副教授华东师范大学 袁海荣副教授华东师范大学秘书 摘要 近年来，区域分解算法已成为求解偏微分方程的有效算法之一，区域分解方法把复杂或 大型的区域分解成若干重叠或非重叠的子区域，再在子区域上利用各种算法求解子问题， 借助于区域分解，各个子区域之问的计算可以并行，这种方法一方面由于容许在不同的子 区域上针对子模型特征使用不同的离散方法，而有利于提高精度，另一方面由于可以在每 个子区域上独立求解定解问题，又使计算速度大大提高用区域分解法来求偏微分方程数值 解已有大量研究，但是对紧差分格式的区域分解算法还是比较少见的，因此本文在前人工 作的基础上，主要对热方程的紧差分格式介绍了非重叠和重叠的两种区域分解法全文共三 章第一章为引言，简要介绍了区域分解算法的概况及该论文所讨论的基本内容第二章， 首先给出d a w s o n 等人求解热传导方程区域分解算法及误差估计，然后主要将此算法推广到 热方程紧差分格式上，此算法是非重叠型区域分解算法，在这种算法中通过引进内边界点 将求解区域分成若干个子域，子区域之间的内边界点值用大步长显格式计算，在各个子区 域内点的计算采用隐格式小步长，子区域步长也可不同，一旦内边界点值被计算出来，各 子区域间计算可完全并行，并给出相应的先验误差估计式第三章，主要对热方程紧差分格 式运用一种熏叠性区域分解算法，该算法是一类新型的计算熟传导方程数值解的并行差分 算法，算法基于区域分解和子区域校正，在每个子区域上进行残量修正，各子区域之间可 以并行计算证明了算法的收敛性 关键词：热传导方程，区域分解，子区域校正，单位分解，并行计算 a b s t r a c t a b s t r a c t ： i nr e c e n ty e a r s ，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 mf o rs o l v i n gp a r t i a ld i f f e r e n t i a l e q u a t i o n sh a sb e c o m eo n e o ft h ee f f e c t i v em e t h o d d o m a i nd e c o m p o s i t i o nm e t h o di su s e dt om a k e c o m p l e xo rl a r g e - s c a l ed o m a i nd i v i d e di n t os e v e r a lo v e r l a p p i n go rn o n - o v e r l a p p i n gs u b - d o m a i n s ， a n dt h e nt h ep r o b l e mc a nb es o l v e db yu s i n gv a r i o u sa l g o r i t h mi nt h es u b d o m a i n b ym e a n so fd o m a i nd e c o m p o s i t i o n ，t h ec o m p u t a t i o no nt h es u b - d o m a i n sc a nb ep a r a l l e l e d t h i sa p p r o a c ho no n e h a n da l l o w sf o rt h ed i f f e r e n ts u b r e g i o n so nt h es u b - m o d e lf e a t u r e su s i n gd i f f e r e n td i s c r e t em e t h o d s ，w h i c hh e l pt oi m p r o v ea c c u r a c y , o nt h eo t h e rh a n di tc a nb ei n d e p e n d e n to fe a c hs u b - d o m a i n m e t h o dt os o l v et h ei s s u e ，w h i c hg r e a t l yi n c r e a s e st h ec o m p u t a t i o n a ls p e e d d o m a i nd e c o m p o s i t i o n m e t h o df o rs o l v i n gp a r t i a ld i f f e r e n t i a le q u a t i o n sn u m e r i c a l l yh a v eb e e ne x t e n s i v e l ys t u d i e d ，b u to n t h ec o m p a c td i f f e r e n c es c h e m ef o rt h ed o m a i nd e c o m p o s i t i o nm e t h o di ss t i l lr e l a t i v e l yr a r e ，s ot h i s p a p e rb a s e do nt h eb a s i so fp r e v i o u sw o r k ，m a i n l yi n t r o d u c e st 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 da n do 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 df o rt h ec o m p a c t d i f f e r e n c es c h e m e o fh e a te q u a t i o nn u m e r i c a l l y t h i sp a p e ri sd i v i d e di n t ot h r e ec h a p t e r s t h ef i r s tc h a p t e ri sa n i n t r o d u c t i o n ，b r i e fo v e r v i e wo 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 m sa n dt h eb a s i cc o n t e n to ft h e d i s c u s s i o np a p e r c h a p t e ri i ，i ti sf i r s t l yp r e s e n t e dt h a td a w s o na n do t h e r sf o rs o l v i n gh e a te q u a t i o n d o m a i nd e c o m p o s i t i o nm e t h o da n de r r o re s t i m a t e s ，t h e ne x t e n dt h i sa l g o r i t h mt oc o m p a c td i f f e r - e n c es c h e m eo fh e a te q u a t i o n t h i sa l g o r i t h mi sn 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 ，i n w h i c ha l g o r i t h mt h ed o m a i no v e rt h ep r o b l e mi sd i v i d e di n t os u b d o m a i n sb yi n t r o d u c i n gi n t e r f a c e p o i n t i n t e r f a c ev a l u e sb e t w e e ns u b - d o m a i n sa r ef o u n db ya ne x p l i c i td i f f e r e n c ef o r m u l aa n db i g s p a c es t e pw h i l et h ei n t e r i o ro ft h es u b d o m a i n si ts a t i s f i e sa ni m p l i c i td i f f e r e n c ef o r m u l a a n ds m a l l s t e p ，p o s s i b l yd i f f e r e n t ，o n c e i n t e r f a c ev a l u e sa r ec a l c u l a t e d ，s u b d o m a i np r o b l e m sc a nb es o l v e di n p a r a l l e l ，a n dt h e ng i v et h ec o r r e s p o n d i n gap r i o r ie r r o re s t i m a t i o n c h a p t e ri i i ，m a i n l yu s i n go 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 mf o r t h eh e a te q u a t i o nc o m p a c td i f f e r e n c es c h e m e ，w h i c h i sa ne f f i c i e n tp a r a l l e lf i n i t ed i f f e r e n c es c h e m eb a s e du p o 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 nt h e a l g o r i t h mi sb a s e du p o nt h ed o m a i nd e c o m p o s i t i o na n dt h es u b s p a c ec o r r e c t i o nm e t h o d ，t h er e s i d i i u a li sm o d i f i e do ne a c hs u b s p a c e ，a n dt h ec o m p u t a t i o ni sc o m p l e t e l yp a r a l l e l o p t i m a lc o n v e r g e n t r a t ei sp r o v e d k e yw o r d s ：h e a te q u a t i o n ，d o m a i nd e c o m p o s i t i o n ，s u b s p a c ec o r r e c t i o n ，p a r t i t i o no f u n i t y ，p a r a l l e lc o m p u t i n g i i i 目录 第一章引言1 第二章热方程紧差分格式非重叠型区域分解算法3 第一节紧差分格式非重叠区域分解算法3 第二节变步长的区域分解算法8 第三节多个子区域情形1 0 第三章热方程紧差分格式重叠型区域分解算法1 2 第一节热传导方程及其紧差分格式1 2 第二节并行区域分解差分算法1 6 第三节算法的收敛性分析1 9 附录2 4 参考文献2 5 后记2 7 i v 第章引言 第一章引言 数学物理及工程问题，如油，气藏的勘探与开发，大型结构工程等， 无不归结于求解大型偏微分方程近年来，区域分解算法作为求解偏微分方 程的一类有效新算法，受到人们的普遍关注，成为计算数学的一个热门研 究领域区域分解算法目前仍处于发展阶段，根据对求解区域的不同剖分， 形成不同的区域分解算法，例如不重叠区域分解算法、重叠区域分解算 法、虚拟区域法、多水平方法等等区域分解方法主要是把复杂或大型的区 域分解成若干子区域，再在子区域上利用各种算法求解子问题，借助于区 域分解，各个子区域之间的计算可以并行，这种方法一方面由于容许在不 同的子区域上针对子模型特征使用不同的离散方法，而有利于提高精度， 另一方面由于可以在每个子区域上独立求解定解问题，又使计算速度大大 提高算法的关键在于如何给定子区域边界值和如何拼接各子区域的解使其 成为原问题的一个合理近似 基于求解区域划分有无重叠的几何结构来看，有重叠区域分解算法和 非重叠区域分解算法，关于重叠和非重叠区域分解算法的研究工作已有很 多： 1 】中c n d a w s o n 等人提出了热传导方程的有限差分区域分解方法，这 是一个关于非重叠的区域分解方法，其思想是在分解后的子区域上使用隐 格式，内边界点处使用大步长显格式，这种显隐结合的方法具有很好的稳 定性，之后这种结论也在很多文献【2 6 】中用到；【1 8 c 9 田敏，羊丹平对于 重叠性的区域分解方法，提出一类修正的并行子空间校正有限差分算法， 第一章引言 其思想是引入单位分解函数，合理的分配重叠部分的校正量，在迭代几次 后达到最优的收敛精度而上述这些方法研究的较多的还是关于其向前向 后e u l e r 格式及c n 格式，对于其紧差分格式研究比较少见，因此本文主要 是将上两种区域分解算法的思想用于热传导方程的紧差分格式，从非重叠 和重叠两种方法对区域进行分解，进而研究其稳定性条件和误差估计，得 到有意义的结论 2 显格式大步长h ，在每个子区域内使用隐格式求解，空间差分步长为h ，并 且h 为h 的整数倍这种显隐格式区域分解法较古典显格式的稳定性和收敛 性限制条件放宽了些，给出了稳定性条件和误差估计本章主要研究将空间 区域分解成两个子区域，在两个子区域上取相同的时间和空间步长，采用 隐式差分格式；在内边界点取空间大步长，采用显式差分格式如此内边界 点各时间层的值容易求出，再对两个子区域并行求解然后对此显一隐格式研 究其稳定性和误差估计，并将其推广到多个子区域情形 第一节紧差分格式非重叠区域分解算法 1 差分格式及区域分解算法 设钆( z ，t ) 是如下热传导方程的解 f 瓦o u 一面0 2 u = o ， z ( o ，1 ) ，亡( 0 ，卅， 钆( z ，o ) = u o ( z ) ， z ( o ，1 ) ， ( 1 1 ) iu ( o ，t ) = 饥( 1 ，t ) = 0 ，z ( 0 ，1 ) ，t ( 0 ，邪 3 第二章热方程紧差分格式非重叠型区域分解算法 设h = d h ，d 为正整数，且假定h 0 称网格点为内边界点，除上述以外的点统称为内点 d a w s o n 等人【1 】给出的求解问题( 1 1 ) 的有限差分区域分解算法为 叼= u ? 于边界点，( 1 2 ) 叼一6 x 2 , h 叼= 0 于内边界点，( 1 3 ) 叼一2 u i n = 0 于内点 ( 1 4 ) 其中u p 为数值解这样，在由时间层t = t n 一1 到t n 的计算中，可在如 下条件亡三日2 下首先计算内边界处的函数值，此后两个子区域上的计算 化为两个独立的分段隐式计算，算法的近似解u p 有下面先验误差估计 定理1 【l 】当亡三日2 时，求解问题( 1 1 ) 的有限差分算法( 1 2 ) 一 ( 1 4 ) 中给出的近似解满足： m 。m a x iu ( 如，俨) 一u pi 丢o o a 亡+ 2 + 2 h ( 亡+ 日2 ) 】， 其中岛：删丢蛩嗉i ，去警l 象1 ) 上述定理记h = d h ，当d 有界时，上估计式右端的最后一项为 比a t 和h 2 更高阶的无穷小量，设h 2 日3 则估计式变为 4 第二章 热方程紧差分格式非重叠翟域分解算法 m a xiu ( x i ，t n ) 一叼i 青岛 亡+ h 2 + h 3 】， 取得精度为o ( a t + h 2 ) 这个结果反映了此算法在条件满足时并没有给整体 计算的逼近阶带来本质的不利影响 下面我们对热方程的紧差分格式建立其显一隐算法 e h 7 可得其紧差分格式 壶( 弘。钆2 1 + 1 0 0 a 。钆+ 弘。钆耳1 ) 一2 ， u ? 一= o ， 且差分格式当万a t = 石1 时为显格式，且等价于 弘“一酲i i l 乱? 一= 0 因此给出问题( 1 1 ) 紧差分格式区域分解算法为： 叼= u 于边界点，( 1 5 ) o a t v r 一2 日u l n 一1 = 0 于内边界点， ( 1 6 ) 壶( 喂1 + l o o 。叼+ 如。略1 ) 一鹾， 嵋一；= o 于内点( 1 7 ) 其中叼为此算法数值解，这样，在由时间层t = t n 一1 到t = t 礼的计算 中，可在条件a t = 去日2 下首先用显格式计算内边界处的函数值u 毒，此后， n 一 两个子区域( 0 ，牙) 和( 牙，1 ) 上的计算化为彼此独立分段隐式计算，可并行计 算算法的近似解有下面的先验误差估计： 定理2 当a t = 妻日2 时，求解问题( 1 1 ) 的有限差分算法( 1 5 ) 一 o 5 由( 1 9 ) 式簪去( 稿一2 z t - 1 + 殁n - 拗i 0 ， 得缎( 1 一雨2 a t ，厶斧n1 + 币a t ( 缎易+ 缎n - + 1 。) o ， 设r = 币a t 由( 1 1 。) 式得 6 第二章 热方程紧差分格式非重叠型区域分解算法 ( 击一三r ) 碾。+ ( 善+ r ) 刀+ ( 圭一三r ) z h 。 = ( 壶+ 丢r ) 列+ ( 石5 一r ) 召- 1 + ( 击+ 三r ) 1 ， 当r = 石1 时，刁o 故对所有主和佗廊f f z ? o 肛h x i ( 1 - 孟, ) , 0 x i _ x k ，= 且岛= 风= 0 ，则鹾， 屈= 0 ，0 i n ，i k ，一鹾，日艮= 1 引理3 【1 】设离散函数仇= 三鼢( 1 一鼢) ，o i ，且= 目= o 则一鹾 眈= 1 ，0 i 下面给出定理2 的证明： 证明：令e = 钆一叼，则有 e = 0 于边界点， ( 1 1 1 ) o a t e 一鹾日e l n - 1 = c ? ( a t 2 + h 4 )于内边界点，( 1 1 2 ) 壶( e 礼- 1 + l o o 群+ e 耳1 ) 一a 三, h e ? = 四( t 2 + 于内点，( 1 1 3 ) 其中i 四i c o 由上两引理令留= e 一岛，g = c o o i ( a t 2 + h 4 ) + z i ( a t 2 + h 4 ) 】， 由于刃满足引理1 条件，故刃0 ，于是e n i 6 ， 7 第二章热方程紧差分格式非重叠型区域分解算法 秤令么；= 一e 一q ，贝u 伺一e s ( i ， ie i g ， 上引理可推知 o 仇丢，o 屈百h ， 旧i 例丢( t 2 + + h ( a t 2 + 】 丢c o z x t 2 + 4 + 2 h ( a 亡2 日4 ) 】 三c o z x t 2 + 危4 + 日5 】 注1 ：估计式中令人感到鼓舞的是出现了日5 项，这个结果反映了算法设计 中显格式隐格式耦合的优点，局部大步长显式计算在上条件满足时不影响 整体计算的逼近阶 第二节变步长的区域分解算法 上一节我们讨论的是在两个子区域取相同的空间步长h ，整个区 域上取的是统一的时间步长，我们也可讨论在内边界上取时间步 长为a t i ，在两个子区域上时间步长分别取为屯和a t r ，可以不 同，a t i 是a t l 和a t r 的正整数倍，仇l 和m r 为左右子区域的时间 层数，在估计从( n 一1 ) a t ，和n a t x 的值，运用显格式( 1 6 ) 时间步 长亡，和空间大步长h ，然后在左右子区域上采用时间步长a t l 和a t r 及隐 格式( 1 7 ) ，内边界中间时刻上的值可通过线性插值获得 8 第二章热方程紧差分格式非重叠型区域分解算法 我们也可以在左右子区域采用不同的空间步长，但是内边界处的步 长h 应该分别是左右子区域步长的整数倍，用h l 和h r 表示左右子区域的步 长，如果我们用岛l 和g r 表示击r 学i 雾l + 丢警i 菇l 和去警i 丽0 6 ui 在左右子区域上的约束，用g 表示在区域iz 一牙l h 上的类似约束，那我们可得到类似定理2 中的误差估计 特别，我们定义 ( z ) = c o 厶铊( z ) ( 亡至+ 磋) + 岛r p 冗 ) ( 亡灸+ 袅) + g ( z ) ( 亡；+ h 4 ) ， 这里0 l 是连续可微的函数，定义o l ( o ) = o l ( 1 ) = 0 ，且 一9 l ”c z ，= 三：三至三三 ： 0 r 可类似的定义，( z ) 满足 p ( z ) = h x ( 1 - 2 ) , o x _ 2 , 先，都是非负函数，其和满足互1 z ( 1 一z ) 百1 i ? 一叼i 已( ( 亡至+ 亡磊+ 危芝+ 尼刍+ 日5 + h a t 2 ) ( 1 1 4 ) 在( 1 1 4 ) 式的证明中，所使用的极大值原理表述为引理4 ，其证明类 似引理l 的证明 9 第二章热方程紧差分格式非重叠型i x 域分解算法 引理4 假设z 是定义在左右子区域( a t l ，h l ) 和( a t r ，h r ) 上的网格函 数，包含所有边界点设z 在边界上满足： 才0在边界点上，弘t 芎一酲，日才一1 0 在所有内边界点上， 圭( 九。雄1 + l o o t 才+ 九t 缮1 ) 一鹾， 才一5 o 在所有内点上，当亡= 屯或a t = a t 兄及h = h l 或h = h r 也成立，也假设对于t = n a t l 和1 仇m 己，有 三鱼蔓三! 焉会拶一鹾，日z ( 牙，亡) 。， ( 1 1 5 ) 此不等式对m a t r 也成立，那么有当亡，= 等时，在所有网格点 有z 0 成立 注2 ：方程数值近似解u 满足( 1 1 5 ) 式，当用线性插值来定义t + m a t 三，m = 1 ，m 工上值时，用等式代替不等式 第三节多个子区域情形 前面我们讨论的都是分成两个子区域的情形，定理2 中的理论也可 被拓展到多个子区域情形，假设我们在整个区域中和第一节一样用同一个 时间步长亡和相同的空间小步长h ，设0 h 牙1 i 2 牙l ， 1 一日，它们都是h 的正整数倍，即而= j h = z ，用叼表示区域分解算法 差分解，显然引理1 在此仍然成立特别是在a t = 每，及定理2 中的约 o 束条件下，有 1 0 第二章热方程紧差分格式非重卺犁x - 域分解算法 m a xi 乱( 娩，t 扎) 一叼i 去c o a t 2 + h 4 + 2 j h ( h 4 + a t 2 ) 】( 1 1 6 ) 一v 上式说明除非j 日非常小，否则算法的逼近阶会受到影响，当j 比较小 时，内边界的误差是相当小的 d a w s o n 等人提出的这种算法，在计算空间区域的内边界点处使用空间 大步长h - - - d h ( d 为大于1 的正整数) 的古典显格式把通常整体计算区域 上的隐式计算化为多个子区域上彼此独立操作的隐式计算，是成功的有限 差分区域分解算法本文中将此算法运用到热方程紧差分格式上得到的定 理2 和( 1 1 6 ) 式表示了此算法在条件满足时的收敛性，若考虑到逼近阶估计式 中右端项中量的平衡，可设渐进关系a t 2 h 4 日5 成立，在此假定下定 理的逼近阶为o ( h 4 ) ，对分解为多个子区域情况下的区域分解算法，数值解 逼近阶为o ( j h 4 ) = d ( 专危3 ) ，这表明为了使算法数值解叼对解u ( x i ，t n ) 有 一个好的逼近，我们在进行算法设计时，应该使子区域的个数相对于网格 分点数不要太多 第三章热方程紧差分格式重叠型域分解算法 第三章热方程紧差分格式重叠型区域分解算法 重叠型区域分解算法的思想来源于经典的s c h w a r z 交替法，这种方法本 是串行的为了使s c h w a r z 交替法的计算并行化，出现了加性s c h w a r z 方 并行子空间校正算法，d r y j a ，p a s c i a k ，xcc a i 许进超，吕涛等皆提出不 同的算法 1 1 1 6 】，但是，一般的加性s c h w a r z 方法和并行子空间校正算法很 难直接判断收敛性，不能直接用于数值求解代数方程组，一般只被用作预 处理共轭梯度法的预处理器 本文对热方程的紧差分格式运用一类修正的加性s c h w a r z 有限差分方法 ( 或称修正的并行子空间校正有限差分算法) ，这一算法在 1 7 2 0 中都有 很好的应用，并且得到算法的收敛估计基本思想是引入单位分解函数，合理 地分配重叠部分的校正量理论分析表明这种方法具有完全的并行性 第一节热传导方程及其紧差分格式 考虑热传导方程初边值问题： ) ，z q ，t ( 0 ，列， z 0 f l ，t ( o ，卵， ( 2 1 ) z q 作为模型问题，不妨考虑一维情形设q = ( a ，6 ) ，a b 是两个 端点用有限差分方法求解，首先对区间( a ，b ) 进行均匀网格剖分， 设剖分步长为h = ( b a ) i n q 上的全部网格点集记为网格区域 1 2 ， ，弋 = 0 吨 = 忙 地力 第三章热方程紧差分格式重叠型域分解算法 q = x i ；x i = n + i h ，0 i ) ，全部内点的集合记为q ；l = x i ；z i = a + i h ，1 i n 一1 ) ，边界点集合为f h = x o ，x n ，设时间步长为7 - ，时间 层t n = 礼7 ，对函数v ( x ，t ) ，定义嵋= v ( x i ，t n ) ，及差分算子： 靠叼= 牮，聊= 气 - 记v ：- i 2 ：v n _ - 厂v n 一- 1 ，我们考虑紧差分格式： 辞嵋= 叼一钉 一1 7 叼(ovu：n_ul碍-i-1。辞叼+辞v子1)一12靠如unl-12i 2 f n - 一l l 2 1 + ，1 。芹一1 2 + i v 2 ， 此格式是绝对稳定的，并且有最优的误差估计0 ( 7 2 + h 4 ) ，这在【7 】中已有叙 对q ，l 上的网格函数u 扎和俨，我们定义离散内积和离散范数： 一1 ( u ，秒) = u t v n h ， i = 1 i i 扎i i h = ( 乱，u ) m ； 一1 ( u ，v ) l = ( u 2 1 + 1 0 u 7 + 让i n + 1 ) u 尼， i = 1 下简单说明( u ，u ) l 是对称的 一1 ( 啦! + 1 0 u + u 髯1 ) v n h i = 1 iu ，l = u ，乱) ：尼 一1一l一1 = h 钆互1 叼+ 1 0 h u i n 嵋+ h n + l 口 i = 1i = 1i = 1 1 3 1 i n 一1 ( 2 3 ) 对任意的v v h ，( 2 3 ) 式两端同乘以k 危，并对i 求和 一1一1 h ( u n 一1 + 1 0 叼+ 曙1 ) m 一6 t h 既靠叼k i = 1 i = 1 = 丁 譬( 店们+ 1 0 片叫2 + 篇m ) + 6 丁九窆靠蜣叼一1 k i = 1i = 1 1 4 对任意u ，v v h 定义双线性形式： a ( u ，v ) = ( u ，v ) l + 6 7 - ( 酝乱，如u ) ， 易知a ( u ，v ) 是对称有界的，从而可以定义范数： | lul i a = ( a ( u ，乱) ) m = ( u 2 + 6 7 | i5 h u m ， 则差分格式( 2 2 ) 可改写成离散变分形式：求u n v h 满足 a ( u n ，v ) = a ( u n ，v ) + 7 - ( 广一m ，y ) 1 1 2 r ( 5 元u n ，5 h v ) ( 2 6 ) 在下节中，我们将构造解此方程组的并行区域分解算法 1 5 第三章热方程紧差分格式重叠犁l x 域分解算法 第二节并行区域分解差分算法 为了并行求解差分方程，我们首先作离散区域分解，定义 0 = i l i 2 k l i 3 k 2 i j k j 一1 k j = n ， 3 令= ( x i j ，z 如) ，1 j j ，则q - - - q 歹构成q 的一个重叠型区 j = l 域分解其中子区域与+ 1 的重叠单元数为向一i j + l ，我们记h = 九1 9 翌1 ( k j i j + 1 ) ，称h 为离散区域分解的重叠度定义 q j = ( x i j ，x i j + l ，z 向) ， 1 j z 。， 从而得到的一个离散区域分解：q l i = 2 j 由单位分解定理可知， 我们可以构造q 的一个开覆盖 o j 是1 和单位分解函数集 咖) 暑1 ，使得 d jnq 踢，并且c j ( j = 1 ，2 ，j ) 满足： 3 咖= 1 ，0 奶1 ，s 唧巾( 咖) cq ，i i 咖i i r o o c h 一 j = l 下面从子区域校正的角度考虑并行算法设d 为差分格式( 2 2 ) 的已 知近似解，则残量为 d ， = 丁( 三1 2 + 1 0 f i 一1 2 + f ；1 1 2 ) + 6 t 6 h s h u $ 一1 + u 与1 + 1 0 叼一1 + u ；n t - 1 一( 昭d ，+ 1 0 d ，t + 昭蚋+ 1 6 丁如晚d ，t ) ， 1 i n 一1 若t o l d 达到足够小，我们就直接令u n = u o f d n ，否则，我们分别在每个小 子域上近似求解残量方程： 1 6 第三章热方程紧差分格式重卺型区域分解算法 勺，t 一1 + l o e j ，t + e j ，i + 1 6 v s h s h e j ，i = r o l d ，i ，i j i 巧， 设其解为弓然后我们就可以校正近似解： 孵t s e 伽= 。n d + 3 蝻 j = l 由此我们得到改进的加性s c h w a r z 算法( 或改进的子区域校正算法) 并行区域分解差分算法：设在每一时间层上的迭代次数为仇，o 是对 初始函数的逼近对几1 ，假设前n 一1 层上的值w 七( 尼= 0 ，1 ，佗一1 ) 已 知取初始值诏= w n ，分三步来求w n 第一步：对i = 1 ，2 ，m ，在j 个子区域上作同步并行迭代 求舒z , 3 - 瑶( q ) ，j = 1 ，2 ，j ，满足： ( a ) ( b ) 锡，七一1 + l o 复j ，七+ 弓，膏+ 1 6 t s h s h 彦i i j ，七= 7 ( 髭n 一- 1 1 7 2 + 1 0 2 1 7 2 + n + - 1 1 2 ) + 6 t s h s h w 孑一l + w n 一- 1 1 + 1 0 管一1 + 名矗 一( 垛1 ，七一1 + 1 0 面n _ 1 ，七十彩0 1 ，七+ l 一6 7 s h s h w n _ l ，七) ， 笱，巧= 锡，如20 i j + 1 k 一1 ( 2 8 ) 第二步：关于j ( j = 1 ，2 ，了) 求和 w i n = w 。, n l + 1 7 3 奶 j = l ( 2 7 ) 式重叠型区域分解算法 层迭代 校正的项定义为： 个子域上分别得到校正，所以上式中 叠区域上的校正是原残量的两倍因 敛的而与经典的子域校正法相比，本 文提出的算法不同之处在于：在第二步校正过程中，我们引入了单位分解函 数 咖) 刍l ，合理的分配重叠子区域上的校正量，使得算法具有很快的收敛 性下面的定理给出了算法的收敛性结果 定理3 设问题( 2 1 ) 的真解u 充分光滑，w n 为并行区域分解算法 的解贝0 当7 - 适当小时，有误差估计： l l 矿一w nii h c o b - 2 + h 4 + ( c 1 h _ 1 ) m 】( 2 9 ) 其中m 2 是每一时间层上的迭代次数，日是区域分解重叠度c ；0 和c l 是 依赖于u 的正常数，但与迭代次数m ，空间网格剖分参数h ，时间步长7 - 及 子区域重叠度日无关 注4 ：定理3 的结果给出了迭代次数与逼近精度之间的关系我们可以看 出：当子区域重叠度有不依赖于h 和7 - 的正的下届时，在每一时间层只需迭 代几次就可以达到与标准差分格式相同的最优逼近阶在下节中，我们将给出 定理3 的证明 1 r 勺 j 芦 + 第三章热方程紧差分格式重叠犁f x i 域分解算法 第三节算法的收敛性分析 在本节中，我们给出收敛性定理的证明我们首先给出标准差分格式的解 的误差估计 引理5 设问题( 2 1 ) 的解u 充分光滑，u n 为标准有限差分格式 ( 2 2 ) 的解，则有： i | u n u nl i h c ( 7 2 + h 4 )( 3 0 ) 和 n 丁i i 辞( 乱七一v k ) 怄c ( t 4 + h s ) ， k = l 进一步我们可得存在常数c ，使得 ( 3 1 ) 丁i i 辞u 后旧c ( 3 2 ) k = l 定理3 的证明： 注意到 u n w 礼= ( 乱n u n ) + ( u 竹一彬礼) ， 由引理5 可知，我们要证明( 2 9 ) 式，只需考虑并行子区域校正算法 的解n 与标准有限差分方法的解纱n 之间的误差即可 我们首先来推导误差方程对任意v v h ，( 2 7 ) 式两端同乘以k 尼并关 于i 求和。由离散的格林公式可得：vv v h , j ， 4 ( ，y ) = ( w n ，y ) l + 7 ( ，n 2 , y ) a 一6 r ( 5 h w u - l , 靠y ) 一a ( 访礁1 ，y ) 1 9 3 a ( 磅一醺l ，y ) = a ( 军) j e i , j ，y ) ， j = l 33 a ( 咖，y ) = ( 咖，y ) - + 6 丁( 靠咖，晚y ) j = lj = l 2 0 j = l ( 3 3 ) ( 3 4 ) 2 暑m ( ? 咖y ) + 6 7 - ( ( 晚咖，晚y ) 一( 晚，y 甄咖) ) 】 2 暑【a ( w n 一嘹1 ，咖y ) + 6 7 - ( ( 靠奶，如y ) 一( 如，y 晚咖) ) 】 j = a ( w n w 墨1 ，y ) + 6 7 j = l ( ( 酝奶，靠y ) 一( 6 五，y 靠咖) ) ， 即有 j 4 ( 磅一谚翌。，y ) = a ( 妒一碰。，y ) + 6 丁( ( 如咖，靠y ) 一( 如，y 如咖) ) ， j = l 2 1 第三章热方程紧差分格式重叠型区域分解算法 进而有 3 a ( 面一w 礼，y ) = 6 丁( ( 靠咖，如y ) 一( 靠，y 如咖) ) 而圭酝咖 壹何甄y + 妻佩y 百酝咖 何甄y + 、6 丁如y j = l l = ll = l 而壹晚矽， 妻( 醒7 ) 2 + 壹( 何靠醒，) 2 ，2 妻( 何晚y ) 2 + 壹v v 2 】1 2 百壹晚咖 ( 醒歹) 2 + ( 何靠) 2 12 ( 而晚y ) 2 + 2 】1 2 f = 1i = 1i = 1 l = l 1 2 1 c h 一1 面i i 舒z , 3 iv i i a 在上不等式中取v = 叼一妒，得 i i 面一妒幢c 日一1 厮i i 舒z , 3 面一妒i i a ， i iw n 一研i i a - c h 一1 i i 妒一醺li i a ， 递推，并由w n = 砩，w n 一1 = 丽可得： 注意到 i i 妒一w n c ( h 一1 ) m | i 妒一旷。1 碉p w n 一1 = ( 飞矿一u n ) + ( u n u n 一1 ) + ( u n 一1 一w n 一1 ) ， 2 2 第二章热方程紧差分格式重叠型区域分解算法 所以我们有： 1 1w n u nli a i l 彬n w 竹1 1 4 + 1 1w n u nii a c ( v 7 h 一1 ) m | | w n w n 一1i i a + i lw 札一纱ni