论文部分内容阅读
本文主要是研究如何设计有效的自适应算法和并行算法,用以复兴传统的Semi—Lagrangian算法。首先我们重新分析了算法的收敛性,给出了相对简化的ε一致的先验误差估计。然后针对对流问题和Semi—Lagrangian算法的特点,我们给出了新型的时间误差指示子,及其后验误差估计。基于这个新型的时间误差指示子,我们还给出了在收敛阶和正则性要求上都是最优的时间上的先验误差估计。在用有限元方法进行空间离散后,我们给出了完全离散格式的后验误差估计,并设计了相应的自适应算法。再然后,我们对传统的时间并行算法进行了改进,将其与时间自适应算法相结合,设计了自适应的时间并行算法。最后,我们运用Semi—Lagrangian算法进行非牛顿流体的数值模拟,给出了数值算法,算法相关实现的细节以及数值模拟结果。
Semi—Lagrangian算法是在20世纪80年代初提出的([36,80])。该算法将时间导数项和对流项同时处理,并沿着特征线方向进行时间离散。由于算法是基于Lagrangian观点,所以可以将方程对称化,线性化。数值解在使用精确积分时是无条件稳定的,因此允许使用较大的时间步长。算法提出后,就被研究人员应用到了不同的实际问题上去,例如对流扩散问题[96,13,97],不可压缩流体仿真模拟[80,17,1,78,99],甚至更为复杂的粘弹性流体仿真[77,78,62,41]等等。对于Semi—Lagrangian算法在L∞([0,T];L2(Ω))范数意义下的先验误差估计,数学家们首先得到形式如下的最优收敛阶的结果[36,89,35](空间使用线性有限元离散):
‖u(tn)—Unh‖L2(Rd)≤c(k+h2),但是这里常数c和ε成反比。当ε→0时,这个误差估计就没有意义了。因此,数学家们又给出了ε一致的误差估计[11]:
‖u(tn)—Unk‖L2(Ω)≤c(k+min{h,h2/k}).但是上述误差估计的证明比较冗长,而且对解的正则性有额外的要求。因此,我们在第二章给出了一个简化的证明,得到了类似的结果,并且对解的正则性并没有额外的要求。这个ε一致但是收敛阶次优的先验误差结果和数值实验的结果更为符合。
在应用中,研究人员也发现了Semi—Lagrangian算法的缺点[22,6,10,5]。这限制了Semi—Lagrangian算法的推广和使用。由于有数值积分和插值的引入,算法会产生数值耗散,且在某些情况下,会变得不稳定。而均匀网格的使用,并不适合对流占优问题的解往往具有激波,运动界面的特点。研究人员为了解决这些问题,设计了人工粘性法,高精度格式,移动有限元,Streamline算法等方法。而自适应算法也被数学家们很自然的引入到了Semi—Lagrangian算法中[33,26,49,24,25]。由于自适应算法根据当前数值解提供误差信息,自适应地改进网格,所以显示了其一定的有效性。但是,这些自适应算法并没有注意对流占优问题的特点,所使用的时间误差指示子仍然直接借鉴了抛物型方程的结果,从而影响了自适应算法的效率。我们注意到引入随体导数后,对流扩散问题沿着特征线满足能量等式。根据这点,我们在第三章中给出了一个新型的时间误差指示子,以及其后验误差估计。然后将其和传统的残量型空间误差指示子结合,给出了完全离散格式的后验误差估计和自适应算法。另外,基于这个新型的时间误差指示子,我们给出了一个在收敛阶和正则性要求上都是最优的时间的先验误差估计,克服了传统的分析技巧在时间上对正则性要求较高的不足。
Semi—Lagrangian算法的另一个比较大的忧虑是计算量的问题。由于和传统方法相比,Semi—Lagrangian算法在每一时间步要多进行一次特征线的回溯和定位,会导致计算量的增加。另外,由于时间这个串行的物理量存在,也使得在数值计算时,花在时间步进上的时间相当可观。对一些较为复杂的物理现象,甚至会出现在时间上根本算不动的情况。因此,我们引入了时间并行算法——Parareal算法。该算法由Lions,Maday和Turinici[65]于2001首先提出。并在许多时间相关问题上有了应用[9,7,67,44,31]。该算法是一种基于两层时间网格的迭代算法,每一次迭代在时间粗网格上进行预估,再在时间细网格上进行并行的校正。从而达到时间并行的效果。在第四章中,我们从线性方程组迭代算法的角度,重新分析了Parareal算法,给出了新的收敛性估计。由于Semi—Lagrangian算法每一步求解的是一个抛物型方程,所以Parareal.算法可以较为直接的应用到Semi—Lagrangian算法上来。但是考虑到对流占优问题解的特点,我们在Parareal算法中引入了时间自适应,针对两层网格在算法中的不同作用,分别设计了具有针对性的自适应算法。自适应Parareal算法充分考虑了各个中央处理器上的负载平衡,优化了并行的效果。而自适应的引入,也使Parareal算法更适合实际问题的求解,推广了其应用范围。
我们将Semi—Lagrangian算法应用于非牛顿流体的数值模拟。非牛顿流体的数值模拟的困难是如何保持协调张量τA的正定性和Weissenberg数比较大时(Wi>0.7)算法的收敛性。协调张量的正定性是非牛顿流体模型稳定的重要条件,如果一个数值算法不能保持这一性质,就会导致数值算法不收敛,特别是Weissenberg数比较大时。而Semi—lagrangian算法可以比较自然的保持正定性[63,62]。第五章中,我们详细介绍了算法流程以及在进行数值实验时的一些细节问题。数值结果说明了我们的算法的有效性,在Weissenberg数小于0.7时,我们得到了符合公认值的结果。而在Weissenberg数较大时,数值结果说明我们的算法仍然稳定且有效。
本文中的大部分研究成果是作者赴美国宾州州立大学留学时,在许进超教授的指导下完成的。本文是对研究结果的阶段性总结。对于Semi—lagrangian算法的改进和实际应用,作者仍然在许教授的指导下继续研究中。