（计算数学专业论文）几类发展型方程的并行计算与数值分析.pdf

摘要 本论文对几类发展型偏微分方程的数值求解问题进行了研究和分析，这些方 程包括对流扩散方程、b u r g e r s 方程以及神经传导方程等。本文分别运用并行计 算方法、差分方法及特征有限元方法，对一些具体的问题给出了相应的算法格式 及其误差估计，并用数值试验证实了理论分析的正确性和计算格式的有效性。 本文取得的主要结果概括如下： 1 第二章研究了几类发展方程的并行数值算法。 首先，利用s a u l y e v 型非对称格式分别对一类对流扩散方程和b u r g e r s 方程 建立了两种不同的交替分组并行计算格式，证明了这些格式的并行性以及无条件 稳定性，最后用数值试验说明格式的精度和有效性。其次，对于一类非线性发展 方程巧妙地使用了一种变换，实现了对其进行a g e 的并行数值计算，得到了方 法的无条件稳定性及并行性兼顾的结论。由于“，在实际问题中也是重要的物理 量，这一格式使我们同时得到了“，的数值解，避免了先计算“，然后再计算珥而 造成二次误差的积累和产生。最后用数值例子说明了理论分析的正确性和格式的 有效性。 2 第三章对二类神经传播方程进行了差分方法分析和研究，本问题分别运用分 片二次插值和双线性插值对两类神经传播方程构造出不同的特征差分格式，并且 进行了数值分析。由于在沿特征线方向构造离散差分格式的过程中，可能会出现 差分离散点落在区域之外和在解的陡峭前沿附近产生振荡的棘手问题，本文分别 采用了新的可变时间步长和发展的u n o 格式进行处理。数值实验表明了理论分 析的正确性和格式的有效性。由于以也是十分重要的物理量，这一格式同时得到 了“，的误差估计。该计算格式易于实现，实际计算效率大大提高，而且计算稳定， 较好保持了问题的物理性质，适用于大规模科学工程与计算。 3 第四章研究了一类非线性发展方程的交替方向差分格式。 对这类非线性发展方程，应用交替方向差分格式【5 】作进一步的研究。使用 一种变换，通过增加人工扰动项，得到了算子乘积型的有限差分格式。利用算子 分裂技巧得n - ；新型d o u g l a s 1 0 】形式的交替方向差分格式，实现了交替方向求 解，把高维问题化成若干个独立的一维问题用简便易行的追赶法求解，计算效率 大大提高。本章还给出了差分解关于时间和空间二阶精度的误差估计。数值试验 证明了所给格式的稳定性和有效性，以及理论分析的正确性。 4 第五章对几类非线性发展方程运用交替方向( 特征) 有限元法进行了分析。 本章考虑了以下问题： ( 1 ) 对一类非线性发展方程应用一种恒等变换技巧，建立了交替方向有限 元格式，这种格式避免了普通的交替方向有限元方法先逼近u ，再逼近“，而造成 的两次误差积累的产生。使用张量积计算、日1 模估计及先验估计理论和技巧， 得到了最佳的三2 模误差估计。 ( 2 ) 对一个血吸虫病数学模型( 类反应扩散方程) 构造了交替方向有限 元格式，给出了模型( p ) 的交替方向g a l e r k i n 逼近法和收敛性分析。 ( 3 ) 对一类半线性反应对流扩散方程组提出了交替方向特征有限元方法。 对第一，第二方程采用交替方向特征有限元格式，对第三方程利用交替方向有限 元格式进行计算，将三维问题化为一系列的一维问题逐次求解，大大降低了计算 量，提高了计算效率，而且具备有限元的高精度的特点。应用变时间步长处理边 界条件，采用张量积计算，区域变换以及先验估计理论和技巧，得到了最佳的 模误差估计。 关键词： 非线性发展方程，数值逼近，并行数值方法，特征差分方法，交替方 向有限元方法 i l a b s t r a c t t h i sd i s s e r t a t i o nf o c u s e so nt h en u m e r i c a ls o l u t i o n st os e v e r a le v o l u t i o n a r y p a r t i a l d i f f e r e n t i a l e q u a t i o n s ( p d e s ) ，i n c l u d i n g c o n v e c t i o nd i f f u s i o ne q u a t i o n s ， b u r g e r se q u a t i o n s a n dn e u r a lc o n d u c t i o n e q u a t i o n s ，e t c b yu s i n gp a r a l l e lp r o c e s s i n g ， d l f f e r e n c em e t h o d sa n df i n i t ee l e m e n tm e t h o d s ，s o m en u m e r i c a ls c h e m e s a r e p r o p o s e da n dt h e i re r r o re s t i m a t e sa r ea n a l y z e df o rs o l v i n gs o m e c o n c r e t ep r o b l e m s m e a n w h i l e ，s o m en u m e r i c a lt e s t sa r ep r e s e n t e dt oi l l u s t r a t e t h ea c c u r a c ya n dt h e e f f i c i e n c yo f t h e s es c h e m e s 1 1 1 em a i nr e s u l t so f t h e p a p e r a r eo u t l i n e da sf o l l o w s ： 1 i nc h a p t e r2 ，w es t u d ys o m ep a r a l l e ln u m e r i c a la l g o r i t h m sf o rs e v e r a lk i n d so f e v o l u t i o n a r ye q u a t i o n s f i r s t l y , w e c o n s t r u c tt w od i f f e r e n tk i n d so fa l t e m a t i v e s c h e m e sf o rac l a s sc o n v e c t i o nd i f f u s i o ne q u a t i o na n db u r g e r se q u a t i o nb yu s i n g s a u l y e vu n s y m m e t r i c a ls c h e m e t h e n ，t h ep a r a l l e l i s ma n du n c o n d i t i o n a ls t a b i l i t yo f t h e s es c h e m e sw e r ep r o v e d ，a n dt h ea c c u r a c ya n de f f i c i e n c yo ft h es c h e m ew e r e a p p r o v e db yn u m e r i c a le x p e r i m e n t s e c o n d l y , ap r o p e rt r a n s f o r m a t i o ni s u s e dt oa c l a s so fp d e s ，s ot h a tt h e ( a g e ) p a r a l l e ln u m e r i c a ls c h e m ee a r lb ee x e c u t e di nt h e s e p d e s 硒er e s u l t sw eo b t a i n e dh o l db o t ht h eu n c o n d i t i o n a ls t a b i l i t yf e a t u r ea n dt h e p a r a l l e l i s mo n e b e c a u s e “，i sa ni m p o r t a n tp h y s i c a lp a r a m e t e r i np r a c t i c a lp r o b l e m s ， t h i ss c h e m ec a no b t a i ns i m u l t a n e o u s l yt h en u m e r i c a ls o l u t i o no f “t ，w h i c ha v o i d st h e g r o w t h o ft h e a c c u m u l a t i n g e r r o r g e n e r a t e db y f i r s t c a l c u l a t i n g “t h e n t h e c a l c u l a t i o no f “，n u m e r i c a le x a m p l e sd e m o n s t r a t et h a tt h et h e o r e t i c a la n a l y s i si s c o r r e c ta n dt h es c h e m ei se f f i c i e n t 2 i nc h a p t e r3 ，w ea n a l y z et w oc l a s s e so fn e u r a lc o n d u c t i o ne q u a t i o n sb yf i n i t e d i f f e r e n c em e t h o d w ec o n s t r u c tt w od i f f e r e n tc h a r a c t e r i s t i cd i f f e r e n c es c h e m e sf o r t w oc l a s s e so fn e u r a lc o n d u c t i o n e q u a t i o n sb yu s i n gp i e c eq u a d r a t i ci n t e r p o l a t i o na n d b i l i n e a ri n t e r p o l a t i o n d u r i n gt h ec o n s t r u c t i o no fd i s c r e t ed i f f e r e n c es c h e m e si nt h e d i r e c t i o no fc h a r a c t e r i s t i cl i n e ，t h ed i s c r e t ed i f f e r e n c ep o i n t sm a ye x c e e dt h ed o m a i n a n do s c i l l a t i o n sa tt h es t e e pf r o n to ft h es o l u t i o nm a yo c c u r w et a c k l et h e s ed i f f i c u l t p r o b l e m sb yu s i n gn e wv a r i a b l et i m es t e pa n de v o l u t i o n a r yu n 0 t h et h e o r e t i c a l a n a l y s i s a n de f f i c i e n c yo ft h es c h e m ew e r ev e r i f i e db yt h en u m e r i c a le x p e r i m e n t s b e c a u s e “，i sa l s oa r t _ i m p o r t a n tp h y s i c a lp a r a m e t e r , i t se r r o re s t i m a t ei so b t a i n e d s i m u l t a n e o u s l yb yu s i n gt h es c h e m e t h ei m p l e m e n to f t h ec o m p u t a t i o n a ls c h e m ei s e a s y , s t a b l ea n dk e e p st h ep h ) 7 s i c a lf e a t u r e sa sw e l l 。s oi ti ss u i t a b l ef o rl a r g e s c a l e s c i e n t i f i ca n d e n g i n e e r i n gc a l c u l a t i o n 3 i nc h a p t e r4 ，w es t u d ya l t e r n a t i n gd i r e c t i o nd i f f e r e n c es c h e m eo fac l a s so fp d e s f o rt h en o n l i n e a re v o l u t i o n a r ye q u a t i o n ，t h ea l t e r n a t i n gd i r e c t i o nd i f f e r e n c es c h e m e 5 i sf u r t h e rc o n s i d e r e d b yu s i n gat r a n s f o r m a t i o na n da d d i n gap e r t u r b a t i o nt e r m ，w e i l l o b t a i nad i f f e r e n c es c h e m ew i t ho p e r a t o rp r o d u c tt y p e b yd e c o m p o s i n g t h eo p e r a t o r , w eo b t a i nan e wd o u g l a s 10 】t y p eo fa l t e r n a t i n gd i r e c t i o nd i f f e r e n c es c h e m e ，s o m u l t i d i m e n s i o n a ld i f f e r e n c es y s t e m s a r e d e c o m p o s e dt o as e r i e so fi n d e p e n d e n t o n e d i m e n s i o n a lp r o b l e m s ，w h i c hc a d b es o l v e de a s i l y h e n c e ，t h ec o m p u t a t i o n a l e f f i c i e n c yi si m p r o v e d a ta g r e a te x t e n t t h es e c o n d o r d e re r r o re s t i m a t eo fd i f f e r e n c e s o l u t i o na b o u tt h et i m ea n d s p a c ei sg i v e n n u m e r i c a lr e s u l t ss h o w t h a tt h et h e o r e t i c a l a n a l y s i si sc o r r e c ta n d t h es c h e m ei se f f i c i e n ta n ds t a b l e 4 i nc h a p t e r5 ，w ea n a l y z et h ea l t e r n a t i n gd i r e c t i o nf i n i t ee l e m e n tm e t h o df o raf e w c l a s s e so f n o n l i n e a rd i f f u s i o ne q u a t i o n w ec o n s i d e r e dt h ef o l l o w i n gt h r e ep r o b l e m s ： ( 1 ) w ec r e a t ea l t e r n a t i n g d i r e c t i o nf i n i t ee l e m e n tm e t h o df o rac l a s sn o n l i n e a r e v o l u t i o ne q u a t i o nb yu s i n ge q u i v a l e n tt r a n s f o r m a t i o n t h es c h e m ep r e v e n t st w i c e c u m u l a t i n ge r r o r sb yu s i n gt h ec o m n l o na l t e r n a t i n g d i r e c t i o nf i n i t ee l e m e n t m e t h o dt o a p p r o x i m a t e 甜a tf i r s t ，t h e nt oa p p r o x i m a t e 材，b yu s i n gt h ec a l c u l a t i o no f t e n s o r p r o d u c t ，何1 n o r me r r o re s t i m a t e ，t h et h e o r ya n d t e c h n i q u eo f p r i o re s t i m a t e ，o p t i m a l o r d e r 三2n o r me r r o re s t i m a t ei so b t a i n e df o rt h em e t h o d ( 2 ) t h ef i n i t ee l e m e n ta n a l y s i sf o rt h es c h i s t o s o m i a s i sm a t h e m a t i c a lm o d e li s p r e s e n t e d t h i s a r t i c l e g i v e s t h e a l t e r n a t i n g d i r e c t i o ng a t e r k i n a p p r o x i m a t i o n m e t h o da n di t sc o n v e r g e n c ea n a l y s i s ( 3 ) a l t e r n a t i n gd i r e c t i o nc h a r a c t e r i s t i cf i n i t ee l e m e n t m e t h o df o rs o l v i n gac l a s so f s e m i l i n e a rr e a c t i v ec o n v e c t i o nd i f f u s i o n e q u a t i o n s i s i n t r o d u c e d a l t e r n a t i n g d i r e c t i o nc h a r a c t e r i s t i cf i n i t ee l e m e n ts c h e m ei su s e df o rs o l v i n gt h ef i r s ta n ds e c o n d e q u a t i o n s ，a n da l t e r n a t i n gd i r e c t i o ns c h e m ei su s e df o rs o l v i n gi nt h et h i r de q u a t i o n b e c a u s et h em e t h o dr e d u c e s3 - d i m e n s i o n a lp r o b l e m st o1 - d i m e n s i o n a lo n e s ，t h e c a l c u l a t i o nc o s ti sr e d u c e ds i g n i f i c a n t l ya n dt h ee f f i c i e n c yi s i m p r o v e dg r e a t l y , m e a n w h i l et h ef e a t u r eo f1 1 i 曲a c c u r a c yo ff i n i t ee l e m e n tm e t h o di s k e ：p t c h a r a c t e r i s t i cm e t h o di sas i m p l ec a l c u l a t i n gs c h e m ew i t hs m a l lt n m c a t i o ne r r o ra n d p e r m i t su s i n gl a r g et i m es t e p ，t h u st h en u m e r i c a lm e t h o dh a sh i g ha c c u r a c ya n d e f f i c i e n c y b yu s i n gv a r i a n tt i m es t e p t ot r e a tw i t ht h eb o u n d a r yc o n d i t i o n sa n d a d o p t i n gt h et h e o r i e sa n dt e c h n i q u e so f t e n s o rp r o d u c t c o m p u t a t i o na n dp r i o re s t i m a t e ， w eo b t a i no p t i m a lo r d e rl 2n o r me r r o re s t i m a t e sf o rt h es c h e m e k e y w o r d s ：n o n l i n e a re v o l u t i o n e q u a t i o n ；n u m e r i c a la p p r o x i m a t i o n ；p a r a l l e l n u m e r i c a lp r o c e s s i n g ；c h a r a c t e r i s t i cd i f f e r e n c es c h e m e ；a l t e r n a t i n gd i r e c t i o nf i n i t e e l e m e n tm e t h o d 1 1 并行计算方法的简介 第一章绪论 现代科学技术的发展在很大程度上依赖于物理学、化学和生物学的成就和 进展，而这些学科自身的精确化又是它们取得进展的重要保证。学科的精确化往 往是通过建立数学模型来实现的，而大量的数学模型可以归结为所谓的非线性发 展方程。 非线性发展方程的研究日益受到广大数学工作者和工程技术人员的普遍关 注和重视，这是因为非线性发展方程涉及的大量问题来自于力学、物理学、化学 和生物学等许多数学物理领域的数学模型，例如生态方程、神经传播方程、对流 扩散方程、热传导方程等，由于其应用的广泛性和深刻的物理背景，有必要在理 论方预及数值分析与应用方面进行全面深入的研究。 现代科学技术对大规模科学与工程计算的需求日益突出，在科学与工程计算 领域内提出了许多大规模和超大规模的科学计算问题。然而，这些问题的解决需 要在高性能并行计算机上进行。并行计算机系统的研制与应用推动了微分方程的 数值解与并行算法的研究和发展，进而推动和发展了大规模科学计算。同时随着 高性能并行计算机系统的问世与发展，研究适合于并行计算机系统上运行的高效 率的计算方法已经为当务之急。 并行数值方法是一种重要的计算方法。所谓的并行计算方法，就是适合在并 行计算机和向量计算机上求解问题的数值方法。由于在使用向量和并行计算机 时，设计算法和安排计算要求充分利用具体的计算机特征。原有的串行算法变成 了不能令人满意的算法，需要重新改造甚至抛弃；而在串行机上许多不是最优的 “老”算法，由于其并行性而焕发了“青春”，传统的数值方法正在经历并行性 改造并在机器上得到检验，发展新的并行算法的研究工作正在向纵深发展。由此 可见并行算法不只是一种新技术，而且也是一种新思维、新概念。j r i c e 曾指出： 由于客观物理世界是并行的，这是人们开展并行算法研究的基础。正因为世界上 很多事物都是并行发生的，彼此间又有一定联系，从而给并行算法研究方法奠定 了基础。把一个问题分解成为互相独立，但彼此又有一定联系的若干个子问题( 或 若干个进展) 是并行算法研究的主要方法和手段。所以利用并行计算系统求解数 值计算问题或非数值计算问题时，需根据系统的类型设计并行算法。虽然并行算 法涉及的主要是求解问题所涉及的学科领域中的原理和方法，或直接揭示某些已 有方法中潜在的并行性，或推广了某些理论上显含着并行性的新方法，但是需要 建立可行和有效的并行算法，就必须把握并体现各类并行算法的基本特征。我们 大连理工大学博士学位论文 可以大致规定数值并行算法的研究内容，它应该包括： 1 在传统数值计算方法基础上进行的并行性改造和创新； 2 已经具有明显并行性的传统数值方法和新方法在并行计算机上的算法设计 程序实现。 关于并行算法的精确描述，下面引用 ：“怄给出的定义： 定义：并行算法是多个并发进程的集合，这些进程同时并相互协作地运行， 从而达到对给定问题的求解。 按照传统计算数学的一般概念，数值计算方法和程序设计是两门密切相关的 不同学科。算法是解题方法的精确描述，它是由一组有穷的规则就可以确定在计 算机上求解某一给定问题的系列运算。从而根据算法可以直接地进行程序设 计。下文指出，在人们利用计算机解算一个问题时，对于串行机而言，数值方法 ( 可简称为解法) 与算法的关系比较简单，解法一旦确定，有效的串行算法和计 算程序也随之产生，它们可以在任何一种串行机上得到实现。但是，在并行计算 系统出现以后，区别解法和算法这两个概念的重要性增加了。同样一个解法针对 不同类型的并行机可以有着差异甚大的算法和程序设计。值得注意的是，上述定 义使用了计算机科学的术语“进程”，并行算法这个概念与并行程序设计的含义 很贴近，并行算法一经给出，并行程序即可直接由该算法设计产生。但是，不难 知道，算法是受到数值方法影响和制约的。解法对算法有决定的意义。有效的并 行算法一般必须建立在容易得到并行实现的数值方法基础之上。顾名思义并行数 值方法就是具有良好并行性质的数值方法。并行数值方法与并行算法在概念上属 于两个不同层次，前者更接近数学问题，在使用上有普遍性，并不局限于某一特 定的并行计算机；而后者更接近计算机和程序设计，需要与计算机的具体特征相 结合。将传统数值方法的并行化在并行计算过程的运用以图表示如下： 第一章绪论 1 2 偏微分方程的并行差分方法的研究现状 研究偏微分方程的并行数值方法，首先必须研究和了解偏微分方程的差分格 式，根据差分格式来构造和设计并行计算的方法。下面将差分格式的并行计算的 历史背景做简单的回顾。 在上个世纪7 0 年代初，m i r a n k e r 曾指出，用有限差分方法逼近微分方程时， 主要是组织传统差分方法的并行实现，至于设计新算法，推动力是很小的，而且 在整个7 0 年代确实没有出现过新算法但是自8 0 年代以来，上述情况由于e v a n s 和a b d u l l a h 的工作而得到了改善，他们设计的交替分组显示方法( a g e ) ( 文献 【2 1 】， 2 2 1 ) 不但保证了数值计算的稳定性，而且由于显式求解而使该方法有很好 的并行性质。这项工作说明了建立满足上述要求的新的差分格式是可能的。 分组显式( g r o u pe x p l i c i t ) 的思想是e v a n s 和a b d u l l a h 在8 0 年代初提出， 分组显示格式是不同类型的s a u l y e v 非对称格式的恰当组合。截断误差分析表 明，在同一时间层或不同时间层上连续交替使用不同的非对称格式，可带来截断 误差的明显改善，从而提高方法的计算精度。这些s a u l y e v 非对称格式都是半隐 式的，但由于它们之间的巧妙结合，可以显式求解，这就是e v a n s - a b d u h a h 组显 式格式。 在文献 9 6 1 中，该文作者研究如下面问题： o ua 2 ” 面3 一o x 2 u ( o ，t ) = g l ( r ) ，u ( 1 ，f ) = 9 2 0 ) u ( x ，0 ) = ，( x ) ( z ，f ) n 【0 ，t 】 ( x ，r ) 铀 0 7 t 】 x q 其中q = o ，l 】，a q 表示q 的边界。作者建立了一种差分格式，这是一种无条件 稳定性的交替分段隐式格式( a s e i ) 。a s e i 格式在研究问题的有限差分逼近方 法中，由两类格式联合起来：一类是古典显式格式，这类方法适合于并行计算， 但不是绝对稳定：而另一类格式如古典隐式格式和c r a n k - - n i c o b o n 格式，这类 格式方法是绝对稳定的，但要求解线性代数方程组，实现并行计算有定的困难。 后来，a r a b d u l l a h 和d j e v a n s 文献【1 ， 2 3 】， 2 5 】中巧妙地利用踟u l y e r 非对 称格式构造了交替分组显示格式( a g e ) 方法。近年来，e v a n s 等进一步将a g e 方 法的应用拓广到许多方面( 见文献 2 8 】， 2 9 】， 3 0 ，【7 8 】) 。 在文献【1 0 3 】中，作者提出y - - 维对流扩散方程的块a d i 方法。该文中构造 的块交替方向隐式( a d i ) 方法，不仅格式是绝对稳定的，而且具有计算和通讯局 部化特点，甚至适合在分布存储的大规模并行计算系统上应用。传统的交替方向 隐式( a l t e r n a t i n gd i r e c t i o ni m p l i c i t ) 方法( 见文献 1 0 ，【6 9 】) 在数值数学研究 与应用领域占有十分重要的地位，它把多维问题化为一系列的一维问题处理，而 且一维问题所要求解的三对角方程组很容易使用熟知的追赶法在计算机上实现。 大连理工大学博士学位论文 然而，在分布式存储多处理机系统上应用时，一般以三对角方程组的计算作为子 任务分配给各个处理机，这样在每改变一个方向的计算中，系统中每一台处理机 都必须和其余所有处理机通讯，这种过多的通讯消耗显然是很不经济的。为了能 够在分布存储的大规模并行计算系统上实现计算和通讯的局部化策略，既保证计 算可以并行又可把通讯消耗减少到最小程度，文献 9 9 1 ，【m o ，【1 0 3 发展了求解 二维扩散方程的块a d i 方法，且在大型计算机上实现了数值实验，并和传统的 a d i 方法比较，块a d i 方法不但适合在传统的串行计算机上应用，而且由于在 沿着一个方向的计算中诸三对角方程组的求解可以同时进行，因此也适合在共享 存储的并行计算机上应用。 在文献 9 6 】。【1 0 7 】中i 作者提出了交替分段g r a n k - n i c o l s o n ( a s c - ) 格式， 应用了分而治的原则，具有十分明显的并行性质。而在文献1 1 0 5 中，将文献 9 6 】， f 1 0 7 建立的隐式格式，改进为一种求解隐式差分方程的并行算法。基本思想是 把差分方程组化为若干个差分方程组，得到联系着这些子方程组的串联方程组， 在求解该关联方程组的基础上实现各自方程组的并行求解。这是一种直接法，但 当子方程组的阶数较大时，确定关联方程组的有关常数涉及到复杂的行列式计 算，此时直接法不便于应用，为了便于在实际计算中应用，作者设计了主子方程 组的并行迭代求解方法，并且证明了迭代过程的收敛性。 在文献【6 2 】中，g r g a n e 与a r g o u r l a y 建立一种求解二维扩散方程的分块 隐式格式 3 9 ，【4 0 ，简记为b h a l o c kh o p s c o t c ha l g o r i t h m ) 。在文献 1 0 6 1 中， 张宝琳等建立了分块显隐交替方法，简记a b e i ( a l t e r n a t i n gb l o c k e x p l i c i 卜b 阳l i c i tm e t h o d ) 。虽然所有这些方法都是具有很好的稳定性与并行性， 但是它们的截断误差含有时间方向的一阶项，还是不能令人满意。另外， p e a c e m a n 与r a c h f o r d 在文献 6 9 】中提出的交替方向的隐式方法 ( a l t e r n a t 嘲卜d i r e c t i o ni m p l i c f f ) 具有一些相当好的性质，但是对于多指令流多 数据( m i m d ) 并行机来说，由于每个并行处理器在奇数时间层计算一列或者若 干列的数值，而在偶数时间层计算一行或者若干行的数值( 或者是相反) ，因而 在每个时间层，大部分数据需要从一个处理器传送到另一个处理器，但是效果不 佳。 对于变系数的微分方程的差分并行计算，近来也有人做了一些工作。如张宝 琳，袁国兴，刘兴平等人在 1 0 4 1 中，对在变系数的情况下扩散方程，用a g e ， a s e i ，a s c - n 等并行计算方法进行了研究。他们运用能量方法处理非对称差分 格式的技巧，证明了a g e 方法在离散上，范数意义下是绝对稳定的，而且与传统 的能量法技巧相结合，论证了a s e 和a s c - n 方法的绝对稳定性。 李德元等在文献【5 3 】中研究了间断系数问题的显隐交替方法( a s e i ) 。关于 间断系数问题在现实中有很多例子，例如热传导方程中当热传导过程发生在多介 4 第一苹绪论 质的体系中，由于不同的物质热传导系数不同，描述该传热过程的抛物线方程的 系数就是间断的。 周毓麟，袁光伟等在文献 1 1 0 “1 1 1 中提出了一般的抛物型方程的显一隐混 合格式，即具有并行本性的差分格式，并对其理论问题，如差分解的存在性、唯 一性、收敛性以及稳定性进行了研究，得到了一系列理论结果。 例如著名的b u r g e r s 方程 一o u + “竺：占罂， ( e f ) q o ，t 1 0 t孤8 t 。 u ( o ，f ) = g i o ) ，u 0 ，f ) = 9 2 ( f ) ， ( z ，r ) a q o ，t 】 u ( x ，0 ) = ( x ) ， x e q 其中q = 【0 , 1 】，m 表示q 的边界。由于它具有n a v i e r - s t o c k e s 方程的一些特性， 通常可以将它看成是n a v i e r - s t o c k e s 方程的简化形式，在数值方法上也是如此， 所以讨论求解b u r g e r s 方程的方法具有现实意义。在文献 6 4 ， 8 4 中王子丁，陆 金甫等在扩散方程的一些并行计算方法的基础上也构造了一些并行计算方法的 格式。 对于高维问题这方面也有很多的工作，例如上面已经讲过的一维抛物线方程 的有限差分并行计算方法，即a g e 、a s e i 和a s c - n 方法都已经推广到求解二 维甚至三维问题，见文献1 6 3 1 。其中a s e i 方法发展为a b e i 方法、a s c - n 发 展为a b c - n 方法( 其中b 表示占，o 以即块的意思) 。这些方法都是绝对稳定的， 适合各种类型的并行计算系统，特别是当空间分点数足够大时，这些方法在计算 和通信方面都具有明显的局部化特征，很适合在分布存储的大规模并行计算系统 上应用。兹举例说明如下：在文献【3 7 】中，f l e t c h e r 研究了二维b u r g e r s 方程的初 边值问题a g e 方法的并行计算；文献【4 1 中g o e d e 和b o o n k k a m p 采用交替方向 隐式格式( a d d 方法和奇偶跳点方法在向量机上对b u r g e r s 方程进行了数值计 算。虽然a d i 方法是无条件稳定的，但需要在每个时间层上交替求解x 和y 方 向的诸三对角方程组，从而问题归结为求解线性方程组。另外，适合于并行的解 法还有w a n gh s 的分裂法，见文献【8 1 】。 张宝琳等人在文献 9 7 】中通过对求解二维扩散方程有限差分新解法a g e 方 法、a b e i 方法、块a d i 方法的研究，发现了构造这类方法的一个基本的和一 般的途径，这就是使得相邻网格点处所使用的基本差分格式之间保持一种对称差 分关系，并在此基础上给出求解二维扩散方程的一类交替差分块方法及其差分图 的统一数学描述。这类方法也具有绝对稳定的性质，并且根据差分图，并行算法 和并行程序的设计将变得非常灵活和容易。这类方法的特例有传统的显隐交替 法、a d i 方法、a g e 方法、a b e i 方法、块a d i 方法等。 大连理工大学博士学位论文 1 3 特征差分和特征有限元方法的研究现状 在处理对流项占优的抛物方程的初边值问题时，常用特征差分方法和特征有 限元方法进行先验误差估计分析。对流扩散抛物型方程是流体力学、渗流力学等 领域中一类重要的数学模型，可以用来描述一系列科学与工程计算中的实际问题 ( 见文献 1 1 】， 3 3 ，【3 4 ， 7 3 ，【7 5 ， 9 2 】) 。而文献 1 8 】， 9 1 中介绍了对流项 的存在使这类方程具有较强的双曲性质。考虑到这种物理特性，d o u g l a s 和 r u s s e l l 在文献 1 6 1 中最先提出了特征差分法的思想。特征差分法能避免数值弥散 和非物理的数值振荡现象( 见文献 3 5 ， 7 2 ) 。所给出的模型关于时间的截断误 差比用传统的差分方法所给出的相应模型关于时间的截断误差常常小得多。因 而，在不损失精度的条件下，可采用时间大步长计算见文献 1 1 】， 1 6 】。有限元 方法网格剖分灵活，适用区域广泛，系数矩阵稀疏，对有限维空间函数光滑性要 求低，逼近精确度高，是现代数值求解各种偏微分方程的重要方法之一。 近年来特征差分和特征有限元( 交替方向特征差分和交替方向的特征有限 元) 方法这一方面的研究已经有了许多好的工作。例如，袁益让的工作 8 8 】，【8 9 ， 9 1 】，【9 2 】等，孙澈等 6 ， 7 】， 5 7 】，【5 8 】， 9 3 】，【9 4 的工作。 最典型的例子，热传导型半导体问题的模型中，d o u g l a s ，袁益让等对该问 题的模型提出了便于使用的差分方法和特征有限元方法，并得到了理论分析见文 献【1 8 】，【9 2 】。袁益让于1 9 9 6 年从生产实际出发，研究现代三维热传导半导体问 题的差分方法，考虑热传导对半导体瞬态问题的影响，以避免模拟失真( 见文献 9 1 ) 。h a y e s 于八十年代初提出了利用等参元和等参变换j a c o b i a n 行列式的逼近 来研究非矩形等区域上的非线性抛物问题( 见文献 4 6 1 ) 。 另外，例如，在地下水运移中，常常发生的各种化学反应，文献【4 】，【4 2 】，7 0 ， 【1 0 8 的作者建立和描述了这类反应的数学模型，并且用特征差分和有限元等数 值分析得到的一些结果( 见文献【5 ，【1 7 ，【3 8 】，【5 1 ， 1 0 2 ， 1 0 8 ) 。 特别是文献 4 9 ，【5 1 的作者首先对上述模型进行了理论上的定性分析，利 用上，下解方法，算子半群理论和s o b o l e v 空间的嵌入定理等论证了模型的整体 古典解的存在唯一性和渐进性质，也论证了整体解的极限性态和收敛性估计。此 外，文献 6 5 】的作者等也对该模型的一类特殊情形的多孔介质二相驱动问题的数 学模型进行了研究。其它相关的工作也可参见 1 5 】， 5 4 】，【7 5 】，【8 8 1 。 交替方向有限元方法的主要思想是可以将多维问题化为一系列的一维问题 迭代求解，降低了计算量和存储量，且有不损失精度，计算效率高等优点。 在上述文献中作者还证明了交替方向有限元和特征有限元格式具有最优三2 一 模和日一模误差估计。 值得一提的是，袁益让教授等在油藏数值模拟以及热传导型半导体的数值模 6 第一章绪论 拟以及应用软件的开发方面做了很多有特色的工作，见文献 8 9 ，【9 0 ，【9 2 a 我们在研究对流扩散方程时，如果用中心差分格式，标准有限元方法和及标 准有限体积元方法来进行先验估计，尽管关于空间步长具有二阶精确度，但由于 以对流为主的扩散方程具有很强的双曲特性，仍会产生数值弥散和非物理性力学 特性的数值振荡，使数值模拟失真。但是如果我们将特征差分方法和标准的有