抛物问题的显—隐有限差分区域分解并行算法

论文摘要

数学物理及工程问题,如油气藏的勘探与开发、航天飞行器的设计、大型水利设施的建筑、空气动力学、天体物理学等等,无不归结为求解高维的大型偏微分方程模型问题,这些问题往往是高维的,计算规模大而且计算区域形态不规则,给计算带来很大的困难,与此同时,我们对计算精度的要求越来越高,而单机计算的速度已远远不能满足实际的需求,随着大规模科学计算的需要和并行计算环境的发展成熟,区域分解方法已成为数值求解偏微分方程最有效的方法之一。简而言之,区域分解方法就是把计算的区域分裂成若干子区域,子区域的形状尽可能的规则,从而原问题的求解转化成在各个子区域上分别解决问题,区域分解算法具有很多其他方法无以比拟的优越性:首先,它把大型的问题转化为若干小型问题,缩小计算的规模;其次,它各子区域上的计算是并行的,缩短计算的时间;再次,它允许在不同的子域上选用不同的数学模型,以便整体模型更适合于工程物理的实际情况;然后,它允许使用局部拟一致网格,无需用整体拟一致网格,甚至各子上可以采用不同的离散方法进行计算;最后,若子区域的形状足够规则,可使得其上或者已有熟知通用的快速算法,或者已有解这类规则问题的高效软件备用,当然,区域分解方法还有其他的优点,但以缩小规模及并行计算尤为根本。用区域分解法来求偏微分方程数值解已有大量研究[35,47,48,50,51,52],他们把这种方法应用于求解椭圆问题[59,60]、对称正定线性系统[61]以及抛物问题[31-34,44]等.同时,区域分解方法也是构建预条件子的有效方法之一[41],区域分解算法的主要困难在于:如何定义内边界点的值和在子区域上选取合理的计算解去近似,于是,区域分解方法划分为两类:重叠型区域分解法和非重叠型区域分解法,子区域的选择主要考虑区域形状的可计算性以及问题的物理背景,尤其是后者,特别适用于在不同物理子区域上有不同控制方程的复合问题,非重叠型区域分解方法,比重叠型区域分解方法实现起来比较直观易用,但它的理论分析往往比较困难。重叠型区域分解法的原始思想来源于经典的Schwarz交替法,近年来建立在Schwarz交替法基础上的区域分解法在理论分析和实际应用中取得令人注目的发展,从椭圆方程到抛物方程,从加性或乘性Schwarz算法发展到并行或串行子区域校正算法,从混合元到特征差分[12-16,36],此类算法已成为一种行之有效的迭代方法,然而,由于其子区域的部分重叠性,也在一定程度上使得并行计算有所牵制,非重叠型区域分解法将计算区域分解成若干个独立的不同子区域,具有高度并行、更适合模型要求和网格剖分灵活等优点,对于此方法,内边界上的预处理方法是必须要考虑的,显-隐格式区域分解方法就是以显格式计算出相邻子区域相交内边界的近似值的一种方法,显-隐格式区域分解方法综合了二者的优点,借助前一层效值解的信息,用显格式给出在这一层的子问题的未知内边界条件,把—个整体区域上的问题化为若干个子区域上的子问题,在每个子区域上用隐式方法求解,从而实现了并行,由计算角度而言,就是把—个整体的大型方程组分解为若干个小型方程组,实现了并行,由于给出子区域间内边界条件的方法利用了上一层数值解的信息,具有显性性质,导致了算法需要一个稳定性条件,但这个稳定性条件没有显式方法那么严格。关于各类区域分解方法,前人也做了很多研究:X.C.Cai[59,60,61]等给出了关于多种椭圆方程的基于重叠不匹配网格的重叠mortar有限元、有限差分方法的理论分析.C.N.Dawson,Q.Du和T.F.Dupont[31-34,44]等提出了多种显-隐区域分解的有限差分及有限元算法,给出了相应的误差估计,然而只是基于热传导方程提出的,且对高维问题的分析只讨论了内边界上一个方向的显式情形,张宝琳[25,27,30]等将Saul’yev的非对称差分格式应用于一对内边界点,或将具有较高稳定性的显格式置于内边界点重写了Dawson的区域分解方法,但并没有提高整体精度,李长峰[1,2,3]研究了关于热传导方程、抛物方程的基于Dawson思想的区域分解有限差分算法,得到了类似的结论。在导师芮洪兴教授的精心指导下,本文作者在前人工作的基础上,对区域分解方法做了部分研究工作,结合杜强教授的在内边界应用多步显格式的算法,我们将迎风格式、高精度格式或不匹配网格应用到非重叠显-隐有限差分区域分解算法,对变系数热传导问题或一般抛物问题给出了最大模误差分析,并通过数值实验得到的数值结果验证了算法的有效性,这种算法在内边界处,不仅采用大步长的空间步长,而且将每一个时间层分为若干子层,用较小的时间步长进行若干次显格式计算,在得到内边界点的近似值后,用隐格式在各个子区域上并行计算求出内点的值,此算法不仅扩大了原来显格式的稳定性条件,而且有较好的并行性,全文共分四章。第一章,由于关于此类算法大部分讨论的是常系数的问题,我们给出关于变系数热传导方程的显-隐有限差分区域分解算法,大体的做法是在内边界点以较小的时间步长（?）和较大的空间步长（?）进行J次显格式计算,然后,再用隐格式在各个子区域并行计算,得到的整体精度为O（△t+h2+J（?）3）,同时,这种算法较古典显格式的稳定性至少放宽了Jd2倍,计算格式也很简单,易于并行程序的实现。第一章内容安排如下:关于一、二维的算法和误差估计将分别在1.2和1.3节给出,首先,在1.2.1节给出了一维变系数热传导问题的模型,然后在1.2.2-1.2.4节讨论了一致剖分网格情形,时空不同剖分情形和多个子区域的情形,在1.3.1节给出了二维变系数热传导问题的模型之后,关于2个子区域和4个子区域的二维区域分解方法分别在1.3.2和1.3.3节讨论.最后,在1.4节我们用数值算例验证了我们的结论,本章部分结果已经在《山东大学学报》（理学版）上发表。第二章,我们给出稳定性条件宽松的高精度有限差分区域分解方法,关于一维抛物问题,我们把区域划分为一些互不相交的多个等距剖分的子区域,我们在内边界点采用高精度的显式差分格式,而且在内边界点取小的时间步长（?）和大的空间步长（?）计算,在得到内边界处的近似值后,再在内点采用高精度的紧交替方向隐式差分格式并行计算,这种有限差分区域分解方法得到了较好的收敛精度O（△t2+h4+Jq（?）5）,而且该算法的计算格式也很简单,易于编程实现,对于高维抛物问题,我们同样地在内边界点采用一族高精度的两层显式差分格式,在内点用紧交替方向隐格式进行计算,在这些格式采用的基础上,我们首先把稳定性条件的界较古典显格式扩大了Jd2倍,其次,在内边界点的格式是关于x和y方向都是显式的,然后,在内点的隐格式是可以再并行的,且其中的系数矩阵是三对角阵,可以提高并行效率,最后,也是最重要的是,这种区域分解算法的整体精度为O（△t2+（?）△t+J（?）3）,而且当选取特殊的d和网格比（?）后,精度可以达到O（△t2+h4+Jh5）。第二章内容是这样安排的:首先,在2.2节,我们不但介绍了关于一维抛物问题的一些预备知识,还在之后的各个小节分析了算法、误差估计和并行效率,然后,关于二、三维的区域分解算法和误差分析我们将分别在2.3和2.4节中给出,最后,在2.5节我们用一些数值算例验证了算法的稳定性和数值精度.本章部分结果已经在《International Journal of Computer Mathematics》上发表。第三章讨论的是不匹配网格的有限差分区域分解方法,不匹配的区域分解方法在子区域采取了不同的剖分,所以在内边界处有一些不匹配的点,在这一章,我们将修正的Saul’yev非对称格式和古典隐格式相结合,得到一种在内边界使用的简单的新显格式,然后就给出非重叠不匹配有限差分区域分解算法,这种算法在二维情形的大多数内边界点是关于x和y方向都是显格式的,而且,它的稳定性条件为r≤1,这比古典显格式的稳定性条件在一维情形下扩展了2D2倍,在二维时扩展了4D2倍,当计算出内边界点的值后,就只剩下求解两个互不相关的、可并行计算的隐式差分问题,另外,这个区域分解算法的精度为O（△t+h12+h12+H3）,计算格式也很简单,易于并行程序的实现,关于一、二维问题的区域分解算法和数值解的收敛性结果分别在3.2节和3.3节给出.最后,在3.4节我们用一些数值算例验证了算法的稳定性和数值精度。第四章,我们不但将多层显-隐差分区域分解算法由第一章的热传导方程扩展到一般抛物方程,而且介绍了三类区域分解的迎风差分算法,关于一维抛物问题,我们首先在4.2节给出一维一般抛物方程的模型和预备知识,并在4.3节给出了关于此模型的有限差分区域分解算法,其次,我们在4.4节给出了三类迎风差分算法。包括一阶迎风差分算法（UDA）、内边界二阶迎风差分算法（IMUDA）和二阶迎风差分算法（MUDA）,一阶迎风差分算法是在内边界点和内点上分别采用显、隐的一阶迎风差分格式的算法,内边界二阶迎风算法是只在内边界点处采用二阶显式迎风差分格式,而在内点处仍用古典的隐式差分格式的算法,二阶迎风差分算法是在内边界点和内点上分别采用显、隐的二阶迎风差分格式的算法,接下来,我们在4.5节和4.6节介绍了关于二维一般抛物方程的多层显-隐差分区域分解方法,最后,在4.7节给出了数值算例验证了我们的结论,其中包括一个实际问题——放射性杆中的热传导问题,本章部分结果已经在《山东大学学报》（理学版）及《工程数学学报》上发表。

论文目录

• 中文部分
• 中文摘要
• Abstract（in English）
• 第一章 变系数热传导方程的显-隐有限差分区域分解算法
• §1.1 引言
• §1.2 一维热传导问题
• §1.2.1 一维热传导问题的模型
• §1.2.2 一致剖分网格情形
• §1.2.3 不同时空步长的情形
• §1.2.4 多个相同子区域的情形
• §1.3 二维热传导问题
• §1.3.1 二维热传导问题的模型
• §1.3.2 两个子区域的情形
• §1.3.3 四个子区域的情形
• §1.4 数值算例
• 第二章 高精度显-隐有限差分区域分解方法
• §2.1 引言
• §2.2 一维抛物问题
• §2.2.1 算法描述
• §2.2.2 误差分析
• §2.2.3 并行效率分析
• §2.3 二维抛物问题
• §2.3.1 算法描述
• §2.3.2 误差分析
• §2.4 三维抛物问题
• §2.4.1 算法描述
• §2.4.2 误差分析
• §2.5 数值算例
• 第三章 不匹配网格的有限差分区域分解方法
• §3.1 引言
• §3.2 非一致剖分的一维抛物问题
• §3.2.1 算法描述
• §3.2.2 误差分析
• §3.3 不匹配网格上的二维抛物问题
• §3.3.1 算法描述
• §3.3.2 误差分析
• §3.4 数值算例
• 第四章 一般抛物方程的显-隐有限差分区域分解方法
• §4.1 引言
• §4.2 一维一般抛物方程模型和预备知识
• §4.3 一维一般抛物方程的显-隐有限差分区域分解方法
• §4.3.1 算法描述
• §4.3.2 误差分析
• §4.4 一维一般抛物方程的三类迎风差分区域分解方法
• §4.4.1 算法描述
• §4.4.2 误差分析
• §4.5 二维一般抛物方程模型和预备知识
• §4.6 二维一般抛物方程的显-隐有限差分区域分解方法
• §4.6.1 算法描述
• §4.6.2 误差分析
• §4.7 数值算例
• 插图目录
• 表格目录
• 符号
• 参考文献
• 致谢
• 攻读博士学位期间完成论文情况
• 作者简介
• 学位论文评阅及答辩情况表
• 英文部分
• Abstract（in English）
• 摘要
• Chapter 1 Explicit-Implicit Finite Difference Domain Decomposition Algorithm for Variable Coefficient Heat Equations
• §1.1 Introduction
• §1.2 One-dimensional Heat Conduction Problem
• §1.2.1 One-dimensional Heat Conduction Model
• §1.2.2 Uniform Mesh Case
• §1.2.3 Varying Time and Space Steps Case
• §1.2.4 Multiple Subdomains Case
• §1.3 Two-dimensional Heat Conduction Problem
• §1.3.1 Two-dimensional Heat Conduction Model
• §1.3.2 Two-subdomains Case
• §1.3.3 Four-subdomains Case
• §1.4 Numerical Experiments
• Chapter 2 Explicit-Implicit Finite Difference Domain Decomposition Method with High Accuracy
• §2.1 Introduction
• §2.2 One-dimensional Parabolic Problems
• §2.2.1 Algorithm Presentation
• §2.2.2 Error Analysis
• §2.2.3 Parallel Efficiency Analysis
• §2.3 Two-dimensional Parabolic Problems
• §2.3.1 Algorithm presentation
• §2.3.2 Error Analysis
• §2.4 Three-dimensional Parabolic Problems
• §2.4.1 Algorithm Presentation
• §2.4.2 Error Analysis
• §2.5 Numerical Experiments
• Chapter 3 A Finite Difference Non-matching Domain Decomposition Method
• §3.1 Introduction
• §3.2 One-dimensional Parabolic Problems with Different Discretization on Subdomains
• §3.2.1 Algorithm Presentation
• §3.2.2 Error Analysis
• §3.3 Two-dimensional Parabolic Problems on Non-Matching Grid
• §3.3.1 Algorithm Presentation
• §3.3.2 Error Analysis
• §3.4 Numerical Experiments
• Chapter 4 Explicit-Implicit Finite Difference Domain Decomposition method for The General Parabolic Problems
• §4.1 Introduction
• §4.2 One-dimensional General Parabolic Model and Preliminaries
• §4.3 Explicit-Implicit Finite Difference Domain Decomposition Method for One-dimensional General Parabolic Problems
• §4.3.1 Algorithm Presentation
• §4.3.2 Error Analysis
• §4.4 Three-kind Upwind Difference Domain Decomposition Method for One-dimensional General Parabolic Problems
• §4.4.1 Algorithms Presentation
• §4.4.2 Error Analysis
• §4.5 Two-dimensional General Parabolic Model and Preliminaries
• §4.6 Explicit-Implicit Finite Difference Domain Decomposition Method for Two-dimensional General Parabolic Problems
• §4.6.1 Algorithm Presentation
• §4.6.2 Error Analysis
• §4.7 Numerical Experiments
• List of Figures
• List of Tables
• Notation
• Bibliography
• Acknowledgement
• List of Publications & Preprints
• Curriculum Vitae
• 学位论文评阅及答辩情况表