（计算数学专业论文）抛物问题时空同时并行算法研究.pdf

摘要 摘要 本文研究的主要内容为抛物问题时间和空间方向同时并行算法。该时空同 时并行算法在时间方向考虑j l l i o n s 等人于2 0 0 1 年提出的时间p a r a r e a l 算法， 在空间方向考虑区域分解方法。针对时间p a r a r e a l 算法，本文提出了两种改进的 p a r a r e a l 传播算子，分析了它们的性质并证明了收敛阶。改进p a r a r e a l 算法在时 间粗细步长比例分配上比原算法更加灵活，从而可以更好的利用有限的处理器资 源。两种改进的传播算子分别在加速比和稳定性上要稍好于原传播算子。改进算 法与原算法的加速比本质上是相当的。我们将时间p a r a r e a l 并行算法应用到普林斯 顿海洋模式( p o m ) 并对渤海海域进行了数值模拟，数值结果验证了改进算法的 优点。空间方向主要考虑了重叠型区域分解方法和非重叠型区域分解方法。文章 给出了一个新的描述重叠型区域分解方法的一般框架，并在此基础上提出了与时 间p a r a r e a l 算法结合的时空同时并行算法。对于非重叠型区域分解方法，除了给出 与时间p a r a r e a l 算法结合的时空同时并行算法外，理论上还给出了抛物问题调和延 拓算子的定义，证明了抛物问题s c h 盯补矩阵的条件数为0 ( 而t 2 ) 阶。本文提出的时 空同时并行算法的程序实现比较复杂，因此，介绍了基于软件g i d 、f e a t f l o w 和g m v 开发时空同时并行算法程序的过程。这些软件分别用来进行前处理、并 行求解和后处理，其中并行求解部分是作者基于f e a t f l o w 开发的并行计算软件 包。基于该软件包，给出了模型问题时空同时并行算法的数值算例。验证了时空 同时并行算法比单纯时间并行或者空间并行算法具有更高的加速比，且时间方向 的加速比提升与空间方向的加速提升互不相关。 关键词p a r a r e a l ，p o m ，f e a t f l o w ，g i d ，并行，区域分解，加速比 a b s t r a c t a b s t r a c t t h em a i nc o n t e n to ft h i st h e s i si sa b o u tt h et i m ea n ds p a c ed i r e c t i o ns i m u l t a n e - o u s l yp a r a l l e la l g o r i t h m s p a r a r e a la l g o r i t h mw h i c hw a sp i o n e e r e db yj l l i o n se t a la t2 0 01i sa d o p t e di nt i m ed i r e c t i o na n dt w om o d i f i e dp r o p a g a t o r sa r ep r o p o s e di n t h i sp a p e r t h em o d i f i e da l g o r i t h m sh a v em o r ef l e x i b i l i t yi nt h ec o n f i g u r a t i o no ft h e t i m es t e pr a t i ob e t w e e nt h ec o a r s ea n dt h ef i n et i m es t e p s 。t h es e c o n dp r o p a g a t o rm a y b e h a v ei nam o r es t a b l em a n n e ri ns o m ea p p l i c a t i o n s t h ee s s e n t i a ls p e e d u pe f f i c i e n c i e sa r ec o m p a r a b l ef o ra l lo ft h et h r e ep r o p a g a t o r s t h e s ea l g o r i t h m sa r ea p p l i e dt o p r i n c e t o no c e a nm o d e l ( p o m ) a n dap r a c t i c a lp r o b l e mo fb o h a is e ai sc a l c u l a t e d t h e n u m e r i c a lr e s u l t sv e r i f yt h et r u t ho ft h ea d v a n t a g eo fm o d i f i e dp a r a r e a la l g o r i t h m s i n s p a c ed i r e c t i o n ，t h eo v e r l a p p i n ga n dn 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 n m e t h o d s a r ec o n s i d e r e d an e wg e n e r a lf r a m e w o r kf o rd e s c r i p t i o no ft h eo v e r l a p p i n gd o m a i n d e c o m p o s i t i o nm e t h o d si sp r o p o s e d b a s e do nt h i sf r a m e w o r k ，t h et i m ea n ds p a c e d i r e c t i o ns i m u l t a n e o u s l yp a r a l l e la l g o r i t h m sa r ep r e s e n t e d f o rn o n o v e r l a p p i n gd o m a i n d e c o m p o s i t i o nm e t h o d s ，t h es i m i l a rt i m ea n ds p a c ed i r e c t i o ns i m u l t a n e o u s l yp a r a l l e l a l g o r i t h m sa r ep r e s e n t e d m o r e o v e r , a m o r es p e c i f i ce x p r e s s i o no ft h eh a r m o n i ce x t e n - s i o nf o rp a r a b o l i cp r o b l e mi sp r o p o s e d t h ec o n d i t i o nn u m b e ro ft h es c h u rc o m p l e m e n t m a t r i xo fp a r a b o l i cp r o b l e mi sp r o v e dt ob et h eo r d e ro fo ( 蕞) t h ei m p l e m e n t a t i o n o ft h et i m ea n d s p a c ed i r e c t i o ns i m u l t a n e o u s l yp a r a l l e la l g o r i t h m si sac h a l l e n g i n g t a s k w ep r e s e n ta na p p r o a c hb a s e do nt h es o f t w a r eg i d ，f e a t f l o wa n dg m v t h a tm a k e s i tw o r k s t h em a i np a r to ft h ep a r a l l e li m p l e m e n t a t i o no ft h ea l g o r i t h m si sd e v e l o p e db y t h ea u t h o rb a s e do nt h ep a c k a g eo ff e a t f l o w t h ee x p e r i m e n tr e s u l t so ft h em o d e l p r o b l e ma r ep r e s e n t e di nt h el a s ts e c t i o n f r o mt h er e s u l t s ，w ec a ns e et h a tt h es p e e d u p o ft i m ea n ds p a c ed i r e c t i o ns i m u l t a n e o u s l yp a r a l l e la l g o r i t h m si sh i g h e rt h a no n l yu s i n g t i m ea n ds p a c ep a r a l l e la l g o r i t h m ss e p a r a t e l y f u r t h e r m o r e ，t h es p e e d u pi n c r e m e n t so f t h et i m ep a r a l l e la n ds p a c ep a r a l l da r ei r r e l e v a n tw i me a c ho t h e r k e yw o r d sp a r a r e a l ，p o m ，f e a t f l o w , g i d ，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 n ， s p e e d u p 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 卅问哪 侧孑年r 月伽e t 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 纠国咽 佩年丁月日 第一章引论3 第一章引论 在人们实际生产、生活中提出的科学与工程问题，如天气、海洋预报，油、气 藏的勘探与开发，新型药物的研制，蛋白质、d n a 等高分子的计算，航天飞行器 的设计，大型水利设施的修建以及核电站的建设等等，其大部分数学模型都是偏 微分方程。这些问题涉及的偏微分方程的未知量从几百万到上千万亿的规模。求 解如此大规模的问题一方面要靠高性能的计算机，另一方面要有适合高性能计算 机的算法。近几十年来，高性能并行计算机的发展突飞猛进，其计算能力已经远 远超过高速串行计算机。由于高性能并行计算机硬件上是由几乎独立的串行计算 机组合而成，因此其制造难度、周期以及速度的提升空间、性价比是相同计算能 力的高速串行计算机所不能比的。目前世界排名最前的超级计算机绝大多数都是 并行计算机。相应于并行计算机的发展，偏微分方程并行算法也在快速发展之中。 如何有效提高算法本身的并行效率一直是偏微分方程并行算法研究的核心问题。 空间方向的区域分解并行算法发展较早，特别是从上世纪8 0 年代以来，已经有了 较成熟的发展。时间方向的并行算法在2 0 0 1 年以后才开始出现，而时空同时并行 算法在2 0 0 3 年才有文章对此进行了初步研究。显然，时空同时并行算法能够有效 地提高并行计算效率。基于以上背景，本文对时空同时并行算法进行了详细的研 究。 1 1 偏微分方程并行算法介绍 2 1 世纪前，偏微分方程并行算法主要集中在空间区域分解算法上，其最原 始的思想可追溯至u1 8 7 0 年德国数学家h a s c h w a r z 提出的著名的s c h w a r z 交替法。 s c h w a r z 本意是借用交替法论证非规则椭圆型方程解的存在性和唯一性，稍后 n e u m a r m 注意到这种思想可以用于求解两个重叠区域的d i r i c h l e t 问题。1 8 9 0 年 p i c a r d 进一步发展了s c h w a r z 的思想，用于解非线性椭圆型偏微分方程，并把该 算法定名为s c h w a r z 交替法。上世纪8 0 年代，随着并行计算机的出现和发展， 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 方法作出全新解释当归功于e l l i o n s 。他在首届国际区域分解算法会 4 第一章引论 议的论文中巧妙地把s c h w a r z 方法与投影方法联系起来，使那些看来复杂的收敛 性证明，简化为对投影算子的估计。对于多个区域重叠的情形，甚至非线性问题 的s c h w a r z 方法皆在统框架下得到处理。此后，基于s c h w a r z 交替法，人们提 出了大量的重叠型区域分解法。另一类被广泛关注的区域分解法是非重叠型区域 分解法。非重叠型区域分解法的子区域之间是互不重叠的。该方法主要考虑的是 子区域内边界上的界面条件以及相应的s t e k l o v p o i n c a r 6 界面方程的求解问题。根 据界面方程的迭代求解方法的不同，可以分为d i r i c h l e t n e u m a n n ( d n ) 方法、 n e u m a n n n e u m a n n ( n - n ) 方法和r o b i n 方法等。非重叠型区域分解法较重叠型 区域分解法的工作量要小，更易于处理复杂的实际问题，例如间断系数问题、复合 材料问题等，但非重叠型区域分解法的理论分析更复杂。这两类方法是区域分解 法中的基本方法，已有很多专著和教材对它们进行了讨论，例如【1 】、【2 】和 3 】等。 除了上面提到的区域分解法外，还有很多其他类型的区域分解方法，主要包括； 子结构方法、虚拟区域法、多水平方法等。 子结构方法是将整个求解区域分解为不重叠的子结构，这样有限元刚度矩阵 可以按照子结构分解为块结构形状，然后使用g a u s s 块消去法导出容度方程求解。 相关参考文献有【4 】、【5 】、【6 】和【7 等。子结构方法也属于非重叠型区域分解方 法，一般非重叠区域上的迭代方法就是来源于这种思想。另外，非重叠区域分解 方法还包括我国学者康立山等人的对称区域分解方法，见【8 】、【9 】。 虚拟区域法很多工作基本上都是由前苏联学者完成的，虚拟区域法把不规则 区域上的问题用长方形区域上的问题取代，然后使用快速算法求解，再结合迭代 方法从而求出原问题的解。相关参考文献有【1 】、【1 0 】、【1 1 、【1 2 、【1 3 1 、 1 4 1 和 【1 5 1 等。 多水平方法的相关参考文献有【3 】、【1 0 】、【1 6 、【1 7 和【1 8 】等。多水平方法基 于有限元空间的多水平分裂，而分裂后的子空间“几乎”是正交的。随后，b r a n b l e ， j h ，p a s c i a k , j e 和x u ，j 引入多水平结点基，克服了三维情形多水平方法的缺 点。 关于区域分解方法更详细的介绍，可以参考这方面的专著，包括【1 】、【3 】和 【2 】等。专著 1 】主要介绍了各种问题的非重叠型区域分解方法；专著【3 】详细介绍 了各流派的研究成果；专著【2 】比较全面的介绍了重叠型区域分解方法和非重叠 型区域分解方法以及最近的研究成果，包括平衡n e u m a n n n e u m a n n 方法、f e t i 方 法等。 第一章引论5 时间p a r a r e a l 并行算法首先由l i o n s ，m a d a y 和t u r i n i e i 于2 0 0 1 年提出( 见 1 9 】) 。最早时间方向并行算法的研究可以追溯到1 9 6 4 年n i e v e r g e l t 的文章【2 0 ， 只不过当时研究的是常微分方程，加上还没有发明并行计算机，所以没有引起广 泛的关注。2 0 0 1 年，时间p a r a r e a l 方法提出后，相关的研究论文开始大量出现。关 于p a r a r e a l 算法稳定性和收敛性的研究见【2 1 、【2 2 、【2 3 和 2 4 ，用于空间非 线性偏微分方程的p a r a r e a l 方法见【2 5 和【2 4 1 ，用于n a v i e r - s t o k e s 方程的p a r a r e a l 方 法见【2 6 】、 2 7 、【2 8 和 2 9 ，时间和空间同时并行的研究见【3 0 ，随机常微分 方程见【3 1 1 。另外，时间p a r a r e a l 方法还应用于很多实际问题，例如：美式期权问 题 2 5 ，分子动力学方面【3 2 ，流体和结构力学中的研究和实验 3 3 】，蓄水池的 模拟【3 4 ，量子控制 3 5 1 等等。国内的研究有 3 6 。p a r a r e a l 算法最新的研究进展 有：自适应p a r a r e a l 方法 3 7 ，对偶p a r a r e a l 方法 3 8 1 ，抛物型最优控制问题的块对 角p a r a r e a l 预条件子 3 9 等。 时间和空间结合的时空同时并行算法的研究在2 0 0 3 年的文章【3 0 1 中开始有初 步讨论。目前还没有发现其他的时间依赖偏微分方程时空同时并行算法研究的文 献。但值得注意的是，关于时间依赖偏微分方程的并行算法已有很多研究，一种 方法是先考虑时间离散，然后空间方向使用区域分解法，一般是有迭代过程的并 行算法( 见【4 0 1 、【4 1 1 、【4 2 1 、【4 3 】、脚】、【4 5 】和 4 6 】) ，另一种方法是无迭代的 显隐区域分解方法( e i d d ) 和各种改进方法( 见【4 7 、【4 8 】、【4 9 、【5 0 、【51 、 【5 2 和【5 3 】) ，但它们都仅涉及空间方向的并行。 另外，关于区域分解法的研究，国际上每一年半召开一次区域分解法国际会 议。1 9 8 7 年在法国召开了第一届区域分解法国际会议。1 9 9 5 年在北京召开了第八 届区域分解法国际会议。这也是该国际会议第一次在发展中国家召开。区域分 解法国际会议历次的会议论文涵盖了大部分已有区域分解算法和区域分解算法 的最新研究进展。区域分解法国际会议的详细信息和最新动态可以到其官方网 站h t t p ：w w w d d m o r g 上了解。 1 2 本文研究的主要内容和创新之处 本文研究的主要内容为抛物问题时间和空间方向同时并行算法。该时空同时 并行算法主要是结合时间p a r a r e a l 并行算法和空间区域分解方法来构造的。理论 部分主要以热传导方程为模型问题进行讨论。第二章介绍了基本的空间区域分 解方法，包括重叠型区域分解方法和非重叠型区域分解方法。第三章介绍了时间 6 第一章引论 p a m r e a l 并行算法，并提出了两种改进的p a r a r e a l 并行算法的传播算子，分析了改 进传播算子的性质并证明了它们的收敛阶。改进p a r a r e a l 并行算法在时间粗细步 长比例分配上比原算法更加灵活，从而可以更好的利用有限的处理器资源。两种 改进的传播算子分别在加速比和稳定性上要稍好于原传播算子。改进算法与原算 法的加速比本质上是相当的。然后我们将原p a r a r e a l 算法和改进的p a r a r e a l 算法 应用到普林斯顿海洋模式( p o m ) 并对渤海海域进行了数值模拟，数值结果验证 了改进算法的优点。第四章是本文的主要内容，介绍了时空同时并行算法。空间 方向主要考虑了重叠型区域分解方法和非重叠型区域分解方法。给出了一个新的 描述重叠型区域分解方法的一般框架，并在此基础上提出了与时间p a r a r e a l 算法 结合的时空同时并行算法。对于非重叠型区域分解方法，除了给出与时间p a r a r e a l 算法结合的时空同时并行算法外，理论上还给出了抛物问题调和延拓算子的定义， 证明了抛物问题s c h u r 补矩阵的条件数为d ( 蔫) 阶。第五章讨论了时空同时并行算 法的程序实现问题和数值算例。介绍了基于软件g d 、f e a t f l o w 和g m v 开 发时空同时并行算法程序的过程。这些软件分别用来进行有限元计算的前处理、 并行求解和后处理，其中并行求解部分为作者基于f e a t f l o w 开发的并行计算软 件包。基于该软件包，给出了模型问题时空同时并行算法的数值算例。验证了时 空同时并行算法比单纯时间并行或者空间并行算法具有更高的加速比，且时间方 向的加速比提升与空间方向的加速提升互不相关。 本文讨论的时空同时并行算法中，空间区域分解方法主要为重叠型区域的 加性和乘性s c h w a r z 方法，非重叠型区域的d n 和n n 方法，对于其它区域分解方 法，我们这里暂不考虑它们与时间p a r a r e a l 算法的结合问题，但是这些方法与时 间p a r a r e a l 算法结合一般来说不会有很大的困难。其他类型的时间依赖问题，例 如非定常的对流扩散、s t o k e s 和n a v i e r - s t o k e s 等问题，仍然可以使用我们提出的时 空同时并行算法类似处理，但是空间分解方面可能会更复杂一些，例如对流扩散 问题中可能需要考虑对流项的处理，n a v i e r - s t o k e s 问题需要考虑如何处理速度和 压强的关系以及非线性项等等。关于这些问题时空同时并行算法的文章目前还没 有，因此有很大的研究空间。 本文创新之处： ( 1 ) 给出了两种改进的时间p a r a r e a l 算法，主要是提出了两种改进的传播算 子，并分析了它们的性质和误差阶。改进的p a r a r e a l 算法的优点是计算时处理器的 分配更加灵活，且第二种改进的传播算子具有更好的稳定性。同时将这些时间并 第一章引论7 行算法应用到普林斯顿海洋模式( p o m ) 中，对渤海海域进行了数值模拟，数值 结果验证了改进算法的优点。 ( 2 ) 给出了重叠型区域分解方法更一般的描述框架，并在这个框架下构造了 时间和空间同时并行的计算格式。 ( 3 ) 对于非重叠型区域分解方法，除了给出时空同时并行的格式之外，还 给出了抛物问题的调和延拓算子和s t e k l o v p o i n c a r 6 算子更加明确的形式，并证 明了空间两子域情形下s c h u r 补矩阵的条件数为o ( 譬) ，多子域时条件数为o ( 丽7 - 2 ) ， 其中7 - 为时间步长，丑为子区域的最大直径，h 为有限元剖分单元的最大直径。 ( 4 ) 利用软件g i d 、f e a t f l o w 和g m v 开发了一套适用于时空同时并行计 算的软件包。通过算例，分析了若干时空同时并行算法的收敛性和加速比。 第二章空间区域分解法介绍 9 第二章空间区域分解法介绍 空间区域分解法根据子区域是否重叠，可以分为重叠型区域分解法和非重叠 型区域分解法。重叠型区域分解法以s c h w a r z 交替法为基础，在网格的同一水平剖 分下或者是不同水平剖分下的子区域之间构造迭代解法。根据子区域间迭代初值 的依赖关系，重叠型区域分解法又可以分为加性或乘性s c h w a r z 方法。重叠型区 域分解方法一般引入投影算子来进行收敛性分析。非重叠型区域分解法主要考虑 子区域内边界上的界面条件以及相应的s t e k l o v p o i n c a r 6 界面方程的求解问题。根 据界面方程的迭代求解方法的不同，可以分为d i r i c h l e t n e u m a n n ( d n ) 方法、 n e u m a n n n e u m a n n ( n n ) 方法和r o b i n 方法等。本章分为两节，分别介绍重叠 型区域分解法和非重叠型区域分解法的基本内容。本章暂不考虑其他类型的空间 区域分解方法，例如子结构方法、虚拟区域方法和多水平方法等。 2 1 重叠型区域分解方法 重叠型区域分解方法的原始思想来源于1 8 7 0 年h a s c h w a r z 提出的经典s c h w a r z 交替法，但该方法当初是用交替迭代的方法来论证某些非规则区域椭圆型问题 解的存在唯一性的，并没有涉及到并行计算。直n 2 0 世纪7 0 年代，p l l i o n s 把 s c h w a r z 法与投影方法联系起来，使得该方法的收敛性分析大大简化，同时也为 后来区域分解法的发展奠定了理论基础。 2 1 1 经典加性、乘性s c h w a r z 方法 考虑齐次d i r i c h l e t 边值问题： ：全乙2 ，篓暑q ( 2 - ) 其中q 为具有l i p s c h i t z 连续边界的d 维区域，其边界为a q 。将q 剖分为两个重 叠的子区域q 1 和q 2 ，满足：q 1nq 2 d ，f 2 = q 1uq 2 。记r 1 = 0 f 2 1nq 2 ，r 2 = a q 2nq 1 ，q 1 2 = q 1oq 2 。s c h w a r z 交替迭代方法可以定义如下： 加性s c h w a r z 方法 给定初值“o ，满足让o i o a = 0 。令u o = u o l a 。和u 2 = u o i q 。对k o ，分别求解如 1 0 第二章空间区域分解法介绍 下两个方程，得到解序列 u ! “) 和 u 纩1 ) 。 f 一让p l _ f i nq 1 乱：“= 钆l o nr 1 ( 2 2 ) 【u ：+ 1 = 0 o na q lf 7a q f 一乱! + 1 = ，i nq 2 罐+ 1 = 瞄 o ? zr 2 ( 2 3 ) iu ! + 1 = 0 o na q 2na q 我们注意到这两个问题没有求解顺序上的依赖关系，因此可以并行求解。 乘性s c h w a r z 方法 给定初值u o ，满足护l a q = 0 。令u o = u o i q ：。对岛0 ，顺序求解如下两个方 程，得到解序列 钆r 1 ) 和 u 1 ) 。 f - - a u ：+ 1 = 厂i nq 1 仳! + 1 = 遽 o nr 1 ( 2 4 ) iu ：+ 1 = 0 o r sa q lna q f 一乱f 1 = f i nq 2 谚“= u p l o nf 2 ( 2 5 ) i u ! + 1 = 0 o na q 21 7a q 如果区域q 1 和q 2 的大小和形状满足一定条件，对乘性s c h w a r z 方法可以得到 下面的收敛性估计( 见 1 】) ： i j uj q 。一珏：+ 1i i l - 。( q 。) 嘴c 堂j j 让一u o i i l o o ( r 。) l l 乱l q 2 一u ；+ 1i i l * ( q 2 ) 讲+ 1 谚l i “一u o i l l * ( r 2 ) 其中g 和q 为迭代的压缩因子，当两个区域重叠度越大时，它们的值越小，反 之就越接近于1 。同样，可以给出加性s c h w a r z 方法的收敛性估计，具体结果可 见【5 4 】、【5 5 1 和【5 6 。 下面给出加性和乘性s c h w a r z 方法的变分表示，然后引入投影算子，给出它们 的投影解释以及与迭代法的联系。首先引入如下记号： y 叩 k + ( w ，勘) o ( t u ，v ) ( w i ，忱) a i ( w i ，v i ) ：= 硪( q ) ：= 明( q t ) ：= v y l v = 0i nq q t ) ：= j q w v ( 2 6 ) ：= ( v w ，v v ) ：= 厶tw i v i ：= ( v w i ，v v i ) n t 第二章空间区域分解法介绍 其中i = l ，2 。 加性s c h w a r z 方法的弱形式 给定初始解u 0 v ，对k 0 ， 求w y o ，满足： 求磁昭，满足： 置 a l ( 趔 ，u 1 ) = ( ，可1 ) q l a l ( u 七，留1 ) v v l 畔 ( 2 7 ) 口2 ( 伽；，v 2 ) = ( f ，v 2 ) a 2 一a 2 ( u 七，u 2 ) v v 2 昭 ( 2 8 ) 乱膏+ 1 = 乱知+ 叫 + 叫 乘性s c h w a r z 方法的弱形式 给定初始解u o v ，对k 0 ， 求w y o ，满足： 置 ( 2 9 ) a l ( 伽 ，秽1 ) = ( ，v 1 ) q l a l ( u 七，秽1 ) v v l 岬 ( 2 1 0 ) u k + l 2 = 乱七+ w 求钮；昭，满足： 口2 ( 叫；，z 7 2 ) = ( ，v 2 ) a 2 一a 2 ( u 知+ 1 2 , 秽2 ) v v 2 5 0 置 ( 2 1 1 ) ( 2 1 2 ) u 七+ 1 = u k + 1 2 + 叫 ( 2 1 3 ) 其中叫 = 霹叫 ，砰：k o _ k ，i = 1 ，2 为延拓算子。 变分形式与原问题的等价性容易验证( 见【1 】) ，下面介绍s c h w a r z 方法的投影 解释。定义投影算子芹：= v _ w ，即对伽v ，有 a ( f ? w ，v ) = n ( 叫， ) ，v v k ( 2 1 4 ) 定义五为k + 到y 的浸入，这样五秒y 且五钉= 口，帕 。我们令只：= 五耳， 则p ：v y 也是投影算子。利用投影算子的定义我们可以给出加性和乘性s c h w a r z 方 法的投影表示。 1 2 第二章空间区域分解法介绍 加性s c h w a r z 方法的投影表示 对v v k + ，i = 1 ，2 ，有： a ( w k ，口) 因此叫? = 只( 让一u k ) ，i ： u k + l 其中q n d ：- - - - - 只+ p 2 。记e 豇 e k + l 1 ，2 ， = u = a i ( 磅，口i q 。) = ( ，钉i q 。) q ；一a i ( u 知，u i q 。) = ( 厂，v ) 一a ( u 七， ) = a ( 乱一矿，钉) 则 仳七十叫 + 叫 乱七+ p 1 ( 让一u 如) + 恳( u 一钆七) 钆知+ ( p 1 + 岛) ( 让一u 惫) 钍南+ q 口d ( u 一南) 一乱膏为误差，有： u 一( u 南+ ( p 1 + 恳) ( u 一乱七) ) 其中，为单位算子。这个误差关系是证b 凋s c h w a r z 方法收敛性的基础。 因此 乘性s c h w a r z 方法的投影表示 类似地，由于 u k + l = u k + l 2 一铲= w = 只( u 一让南) u 七+ 1 一u k + l 2 = 伽= 马( u u k + l 2 ) u k + l 2 + w i u 民+ w + 叫5 “+ p l ( 钍一u 知) + p 2 ( u u k + 1 2 ) f 2 1 5 ) ( 2 1 6 ) ( 2 1 7 ) 毯七+ 户1 ( 让一锃七) + 最( 珏一( 戡七+ 研) ) ( 2 1 8 ) u 知+ p 1 ( u u 知) + 岛( 钆一( u 砖+ p 1 ( 乱一u 七) ) 乱南+ ( 只+ p 2 一p 1 恳) ( u 一乱知) + q m 札( 珏一趾七) 其中q 砌：= p l + p 2 一p 1 p 2 。其误差方程为： e 抖1 = ( j p 1 ) ( j p 2 ) e 七( 2 1 9 ) 第二章空间区域分解法介绍1 3 对于多子域情形，例如将区域q 剖分为( 2 ) 个重叠子区域蹉，可以类似 地构造问题( 2 1 ) 的加性和乘。l 生s c h w a r z 方法。在多子域情形下，加性s c h w a r z 方法 的投影算子为： n h q 以= f 只 ( 2 2 0 ) i = 1 乘性s c h w a r z 方法的投影算子为： q 舢= i 一互钍 ( 2 2 1 ) 其中u = ( i 一) ( j 一局) 。 关于收敛性和更详细的介绍见文献 1 】。 2 1 2 两水平方法 经典区域分解方法的收敛率随着子区域数量的增加而降低，原因是由于信息 只是在相邻的子区域之间传递而缺少全局的信息交换，通过加入一个粗网格上的 全局解的办法可以提高收敛率。两水平方法正是基于这个思想提出来的。两水平 方法的两层网格之间可以是加性关系也可以是乘性关系。如果再在细网格子区域 之间采用加性或乘性s c h w a r z 方法求解，则得到两水平加性和乘 生s c h w a r z 方法。 这样组合起来我们可以得到4 种方法，即： ( 1 ) 两水平加性s c h w a r z 法：粗细网格之间和细网格子区域之间都是加性关系； ( 2 ) 两水平乘性s c h w a r z 法：粗细网格之间和细网格子区域之间都是乘性关系； ( 3 ) 混合方法1 ：粗细网格之间是乘性关系，细网格子区域之间是加性关系； ( 4 ) 混合方法2 ：粗细网格之间是加性关系，细网格子区域之间是乘性关系。 为讨论简单起见，假设qcr d ( d = 2 ，3 ) 是一个多边形( 或多面体) 。 q t ) 为区 域q 的正则剖分( 不重叠) ，h 为剖分直径，即q i ( z = 1 ，) 中的最大直径。我 们称q t 为子结构， q t ) 为粗网格或h 一水平剖分。然后将每一个q t 做更细的剖分， 记为刁( 歹= 1 ，) 。这样 碍) 成为了对整个区域q 的一个剖分，剖分直径记为h 。 我们称 霄) 为细网格或者h 水平剖分。针对粗细网格剖分，分别定义分片线性有 限元空间： 瞻= v h i v h 伊( 豆) ，v h i r 2 1 尸1 ( q t ) ，v i ，铅= 0o na q ) y h = 地i c o ( 丽) ，i 专p 1 ( 刁) ，歹，v h = 0o na q ) 其中p 1 ( ) 为定义在q 。或膏上的一次多项式全体。 1 4第二章空间区域分解法介绍 下面我们考虑两个有限元问题： 求u h v h 满足： a h ( u h ，v h ) = ( ，v h ) v v h v h 求u h 垤满足： a h ( u h ，v h ) = ( f ，v h ) v v h 瞻 其中o h ( ，) 与。日( ，) 分别为k 和上的双线性形式。如果给定k 与上的基 函数0 = 1 ，g h ) 与咖( f = 1 ，日) ，我们可以写出对应上面双线型形式的 矩阵： ( a h ) s j ：= a h ( 垆j ，妒。) ( a 日) 棚：= a l l ( o p t ，妒m ) 在给出两水平方法之前，我们需要引入一个联系两层网格之间的插值算子i h ：= _ 。一般来说，厶是线性插值算子。我们用兄五表示其矩阵形式。厶的伴随 算子定义为研：= y h _ ，即 ( i t w h ，v h ) v h = ( w h ，h v ) v h ，v w h v h ，v h 垤 有了以上准备，根据粗细网格之间的加性和乘性关系，我们可以给出两水平 加性方法和两水平乘性方法的描述，下面我们以矩阵形式给出： 两水平加性方法 求叫备满足方程： q w k = ，一a h u k i 1( 2 2 2 ) 求训h k i 网- - 足方程： q 叫= 厂一a h u ( 2 2 3 ) 置 蚶1 冀：嚣q h l 岛。川础， 亿2 4 ， = 让l + (+ q i l ) ( ，一a 钍2 ) 两水平乘性方法 求伽备满足方程： q 日叫备= f a h u k h( 2 2 5 ) 置 u k 7 l + 1 2 ：乱+ 磊 ( 2 2 6 ) 第二章空间区域分解法介绍 1 5 求镏满足方程： q w 2 = ，一a 仳：+ 1 2 ( 2 2 7 ) 置 u 矿1 = u 1 2 + 伽2 = u + 叫备+ 叫 ( 2 2 8 ) = u + ( q 日- 1 + q i l 一q i l a h q h l ) ( f a 九u ) 其中q 日与q 九分别为a 日与a 的预条件矩阵，q ：= r h q h l 磁，砌鲁：= 兄】 l t 昱k 。 另外，两水平方法可以扩展到多水平上，参考 5 7 】。 最后我们给出两水平方法与s c h w a r z 方法的结合算法( 见 2 】) 。如果我们将前 面的子区域q t 向外扩张，扩张后的区域记为q ：( q ：的边界不穿过任何h 水平的有 限单元) ，且存在常数0 o 为参数。 p h i 2 = q q 日+ q m t ( 2 3 3 ) 1 6第二章空间区域分解法介绍 2 1 3 s c h w a r z 方法若干求解问题 由加性和乘一 生s c h w a r z 方法的投影表示，我们可以知道，它们分别相当于求解 下面问题的r i c h a r d s o n 迭代过程( 见 1 】) ： q 砌乱= 夕：= q 删g ， q m 缸铭= g ：= q m u a f 另外，加性和乘，t 生s c h w a r z 方法的矩阵表示可以理解为块j a c o b i 迭代和块g a u s s - s e i d e l 迭代过程。事实上，以乘。陛s c h w a r z 方法为例，弱形式( 2 1 0 ) 一( 2 1 3 ) 离散后，得 到矩阵方程组： u蝴三uk+r+ta砑1筒r1(1f岛-(f_auka)uk+l u k + l 2 u 2 ) ( 2 3 4 ) = + 磁a i l r 2 ( f a u 七+ 1 2 ) p 7 其中a ：r i a r t ( i = 1 ，2 ) ，a 为整个问题的刚度矩阵，r t * n p k ( i = 1 ，2 ) 分别为 延拓和限制矩阵。定义矩阵 磁= ( 五b i ) ( 2 3 5 ) 它对应于离散的微分算子l ( 这里l ：一) 在子区域q t 上的限制，分量五为子区 域哦内结点之间的耦合关系，鼠为内结点和边界r 结点之间的耦合关系。则( 2 3 4 ) 口- i 以写为： 和 ( 五 ( 五 b ，) ( ：莓：) = 矗，u r k + ，l ：= 碟u 2 c 2 3 6 ， b 2 ) ( 蒜：) 巩u k + l 砷i f i ：) u p 亿3 7 ， 其中碟和删为线性算子，分别将子区域内部结点的值插值到相应的边界结点上。 由( 2 3 6 ) 和( 2 3 7 ) 可以得到： ( 2 3 8 ) 这正好是求解下面方程组的两块形式的g a u s s s e i d e l 迭代方法： ( 鑫b 瓮, i ( 2 1 炯) = ( 乏) 亿3 9 ， 知2 七1 u u 群璎 b b 一 一 矗如 = l i + + 忌l 砖2 u u 五五 第二章空间区域分解法介绍1 7 类似地，加性s c h w a z 方法可以解释为块j a c o b i 迭代方法，参考 5 8 1 。 加性和乘。t 生s c h w a m 方法以及两水平方法和它们的混合方法都可以作为某种 迭代解法的预条件子。例如加性s c h w a r z 方法，我们定义矩阵： 只。：= ( r t a - f 1 r 1 + p 4 a 2 r 2 ) 一1 = ( q 1 + q 2 ) 一1 并且记 圪1 a = b + 局 则只。可以作为一个预条件矩阵，求解如下问题： 石1 a u = 屹1 f 这里咒是对称正定的，可以作为共轭梯度法的预条件矩阵( 见【1 】) ，即给定迭代 初值u o ，令r o ：= f a u ，p o ：= z o ：= 圪1 r o ，对k 0 ： ( z 月，r ”) ；布百南 ：= u 知- i - a 七p 知 幺嚣p 奄 ( 2 4 0 ) ：= 圪1 1 1 ”7 ：= 祥 ：z k + i + 反+ 】p k 在多子域情况f ，加性预条件子为： ：= ( 冗与1 尼) 一1 = ( q t ) 一1 预条件后的矩阵为： 屹1 4 ：= 只= 钆 这时预