（计算数学专业论文）改进的semilagrangian算法及其应用.pdf

摘要 本文主要是研究如何设计有效的自适应算法和并行算法，用以复兴传统的 s e m i l a g r a n g i a i l 算法。首先我们重新分析了算法的收敛性，给出了相对简化的 e 一致的先验误差估计。然后针对对流问题和s e m i - l a g r a n g i 。a n 算法的特点，我 们给出了新型的时间误差指示子，及其后验误差估计。基于这个新型的时间误 差指示子，我们还给出了在收敛阶和正则性要求上都是最优的时间上的先验误 差估计。在用有限元方法进行空间离散后，我们给出了完全离散格式的后验误 差估计，并设计了相应的自适应算法。再然后，我们对传统的时间并行算法进 行了改进，将其与时间自适应算法相结合，设计了自适应的时间并行算法。最 后，我们运用s e m i - l a g r a n g i a n 算法进行非牛顿流体的数值模拟，给出了数值算 法，算法相关实现的细节以及数值模拟结果。 s e m i l a g r a n g i a l l 算法是在2 0 世纪8 0 年代初提出的( 【3 6 ，8 0 】) 。该算法将 时间导数项和对流项同时处理，并沿着特征线方向进行时间离散。由于算法是 基于l a g r a n g i a n 观点，所以可以将方程对称化，线性化。数值解在使用精确积 分时是无条件稳定的，因此允许使用较大的时间步长。算法提出后，就被研究人 员应用到了不同的实际问题上去，例如对流扩散问题【9 6 ，1 3 ，9 7 1 ，不可压缩流 体仿真模拟【8 0 ，1 7 ，1 ，7 8 ，9 9 】，甚至更为复杂的粘弹性流体仿真 7 7 ，7 8 ，6 2 ，4 l 】 等等。对于s e m i - l a g r a n g i a n 算法在l 。( o ，明；l 2 ( q ) ) 范数意义下的先验误差估 计，数学家们首先得到形式如下的最优收敛阶的结果【3 6 ，8 9 ，3 5 】( 空间使用线性 有限元离散) ： i i 札( n ) 一叼i l l ：( r d ) c ( k + z ) ， 但是这里常数e 和成反比。当_ 0 时，这个误差估计就没有意义了。因此， 数学家们又给出了一致的误差估计【1 1 】： h 2 i l u ( t 。) 一w ij l z ( o ) c ( k + m i n h ，) ) 但是上述误差估计的证明比较冗长，而且对解的正则性有额外的要求。因此，我 们在第二章给出了一个简化的证明，得到了类似的结果，并且对解的正则性并 没有额外的要求。这个一致但是收敛阶次优的先验误差结果和数值实验的结 果更为符合。 i i改进的s e m i - l a g r a n g i a n 算法及其应用 在应用中，研究人员也发现了s e m i l a g r a n g i a n 算法的缺点f 2 2 ，6 ，1 0 ，5 1 。 这限制了s e m i l a g r a n g i a n 算法的推广和使用。由于有数值积分和插值的引入， 算法会产生数值耗散，且在某些情况下，会变得不稳定。而均匀网格的使用，并 不适合对流占优问题的解往往具有激波，运动界面的特点。研究人员为了解决 这些问题，设计了人工粘性法，高精度格式，移动有限元，s t r e a m l i n e 算法等 方法。而自适应算法也被数学家们很自然的引入到了s e m i l a g r a n g i a n 算法中 【3 3 ，2 6 ，4 9 ，2 4 ，2 5 】。由于自适应算法根据当前数值解提供误差信息，自适应地 改进网格，所以显示了其一定的有效性。但是，这些自适应算法并没有注意对流 占优问题的特点，所使用的时间误差指示子仍然直接借鉴了抛物型方程的结果， 从而影响了自适应算法的效率。我们注意到引入随体导数后，对流扩散问题沿 着特征线满足能量等式。根据这点，我们在第三章中给出了一个新型的时间误 差指示子，以及其后验误差估计。然后将其和传统的残量型空间误差指示子结 合，给出了完全离散格式的后验误差估计和自适应算法。另外，基于这个新型 的时间误差指示子，我们给出了一个在收敛阶和正则性要求上都是最优的时间 的先验误差估计，克服了传统的分析技巧在时间上对正则性要求较高的不足。 s e m i l a g r a n g i a n 算法的另一个比较大的忧虑是计算量的问题。由于和传 统方法相比，s e m i - l a g r a n g i a n 算法在每一时间步要多进行一次特征线的回溯 和定位，会导致计算量的增加。另外，由于时间这个串行的物理量存在，也使 得在数值计算时，花在时间步进上的时间相当可观。对一些较为复杂的物理现 象，甚至会出现在时间上根本算不动的情况。因此，我们引入了时间并行算法 一一p a r a r e a l 算法。该算法由l i o n s ，m a d a y 和t u r i n i c if 6 5 1 于2 0 0 1 首先提出。 并在许多时间相关问题上有了应用f 9 ，7 ，6 7 ，4 4 ，3 1 】。该算法是一种基于两层 时间网格的迭代算法，每一次迭代在时间粗网格上进行预估，再在时间细网格 上进行并行的校正。从而达到时间并行的效果。在第四章中，我们从线性方程 组迭代算法的角度，重新分析了p a r a r e a l 算法，给出了新的收敛性估计。由于 s e m i l a g r a n g i a n 算法每一步求解的是一个抛物型方程，所以p a r a r e a l 算法可以 较为直接的应用到s e m i l a g r a n g i a n 算法上来。但是考虑到对流占优问题解的 特点，我们在p a r a r e a l 算法中引入了时间自适应，针对两层网格在算法中的不 同作用，分别设计了具有针对性的自适应算法。自适应p a r a r e a i 算法充分考虑 了各个中央处理器上的负载平衡，优化了并行的效果。而自适应的引入，也使 p a r a r e a l 算法更适合实际问题的求解，推广了其应用范围。 我们将s e m i - l a g r a n g i a n 算法应用于非牛顿流体的数值模拟。非牛顿流体 摘要 的数值模拟的困难是如何保持协调张量的正定性和w e i s s e n b e r g 数比较大时 ( w i 0 7 ) 算法的收敛性。协调张量的正定性是非牛顿流体模型稳定的重要条 件，如果一个数值算法不能保持这一性质，就会导致数值算法不收敛，特别是 w e i s s e n b e r g 数比较大时。而s e m i 1 a g r a n g i a n 算法可以比较自然的保持正定性 【6 3 ，6 2 1 。第五章中，我们详细介绍了算法流程以及在进行数值实验时的一些细 节问题。数值结果说明了我们的算法的有效性，在w e i s s e n b e r g 数小于0 7 时， 我们得到了符合公认值的结果。而在w e i s s e n b e r g 数较大时，数值结果说明我们 的算法仍然稳定且有效。 本文中的大部分研究成果是作者赴美国宾州州立大学留学时，在许进超教 授的指导下完成的。本文是对研究结果的阶段性总结。对于s e m i 1 a g r a n g i a n 算 法的改进和实际应用，作者仍然在许教授的指导下继续研究中。 关键词：s e m i l a g r a n g i a n 算法，有限元方法，自适应算法，并行算法，对流扩 散方程，n a v i e r s t o k e s 方程，本构方程，非牛顿流体，o l d r o y d - b 模型 a b s t r a c t t h i sd i s s e r t a t i o nm a i n l ys t u d yh o wt ou s ea d a p t i v i t ya n d p a r a l l e l i z a t i o ni n ai n t e g r a t e da n ds y s t e m a t i cf a s h i o nt or e v i t a l i z es e m i - l a g r a n g i a nm e t h o d b y t h c s en c wt e c h n i q u e s ，w eh o p et h ec o s t e f f e c t i v e n e s s ，a c c u r a c ya n d a p p l i c a b i l i t yo f t h es e m i - l a g r a n g i a nm e t h o dw i l lb ei n t r i n s i c a l l yi m p r o v e d w es i m p l i f yt h e p r o o f o ft h e - u n i f o r mc o n v e r g e n c er e s u l t sa n d p r e s e n tae u n i f o r mp r i o r ie r r o re s t i m a t e w i t h o u te x t r ar e q u i r e m e n to ft h er e g u l a r i t yo ft h ee x a c ts o l u t i o n a c c o r d i n g t ot h en a t u r eo ft h ec o n v e c t i o n - d o m i n a t e dp r o b l e ma n dt h es e m i l a g r a n g i a n m e t h o d ，w ed e v e l o pan e wt i m ee r r o ri n d i c a t o ra n di t sap o s t e r i o r ie r r o re s t i m a t e s b a s e do nt h i sn e wt i m ee r r o ri n d i c a t o r ，w eg i v ea p r i o r ie r r o re s t i m a t ew i t h o p t i m a lc o n v e r g e n c er a t ea n dm i n i m a lr e q u i r e m e n to ft h er e g u l a r i t y w eu s ef i n i t e e l e m e n tm e t h o df o rs p a c i a ld i s c r e t i z a t i o na n dg i v eap o s t e r i o r ie r r o re s t i m a t ef o r t h ef u l l yd i s c r e t i z e ds c h e m e m e a n w h i l e ，w ei m p r o v et h ec l a s s i c a lt i m ep a r a l l e l a l g o r i t h mb yi n t r o d u c i n gt i m ea d a p t i v i t y w ea p p l ys e m i l a g r a n g i a nm e t h o dt o t h cn o n - n e w t o n i a nf l u i d ss i m u l a t i o n w ep r o p o s e dt h ea l g o r i t h m s ，i m p l e m e n t d e t a i l sa n dn u m e r i c a lr e s u l t s s e m i l a g r a n g i a nm e t h o di sf i r s t l yp r o p o s e di nt h ee a r l y8 0 s 3 6 ，s o i td i s - c r e t i z e st h ec o n v e c t i o na n dt h et i m ed e r i v a t i v es i m u l t a n e o u s l y ，a n dt h et e m p o r a l d i s c r e t i z a t i o ni sd o n ea l o n gt h ec h a r a c t e r i s t i c s s i n c et h i sm e t h o di sb a s e do nt h e l a g r a n g i a np o i n to fv i e w ，i tc a nl i n e a r i z ea n ds y m m e t r i z et h eo r i g i n a lp r o b l e m i fe x a c ti n t e g r a t i o ni su s e d ，t h i ss c h e m ei su n c o n d i t i o n a l l ys t a b l ea n d r e l a t i v e l y l a r g et i m es t e ps i z ei sa l l o w e d s e m i l a g r a n g i a nm e t h o dh a sb e e na p p l i e dt o m a n yd i f f e r e n tp r o b l e m s ，s u c ha st h ec o n v e c t i o nd i f f u s i o np r o b l e n l s 【9 6 ，1 3 ，9 7 ， i n c o m p r e s s i b l ef l u i d ss i m u l a t i o n 8 0 ，1 7 ，l ，7 8 ，9 9 1a n dv i s c o e l a s t i cf l u i d ss i r e - u l a t i o n s 【7 7 ，7 8 ，6 2 ，4 1 f o rt h ep r i o r ie r r o re s t i m a t e sf o rl 。( 【o ，卅；l 2 ( q ) ) n o r m ，m a t h e m a t i c i a n sh a v et h ef o l l o w i n gr e s u l t sw i t ho p t i m a lc o n v e r g e n c er a t e 【3 6 ，8 9 ，3 5 ， i l u ( t n ) 一簖jj l 。( r a ) c ( k + h 2 ) ， w h e r el i n e a rf i n i t ee l e m e n ts p a c ei su s e d h e r e ，u n f o r t u n a t e l y t h ec o n s t a n tc 改进的s e m i l a g r a n g i a n 算法及其应用 d e p e n d so n i n v e r s e l y , w h i c hm e a n st h i se r r o re s t i m a t e si sm e a n i n g l e s sw h e n _ 0 t h e r e f o r e ，e - u n i f o r me r r o re s t i m a t e si sp r o p o s e db y 【11 ， h 2 i i u ( 如) 一叼i i 工：i n ) c ( k + m i n h ，詈) ) b u tt h i sr e s u l tr e q u i r e se x t r ar e g u l a r i t yo ft h ee x a c ts o l u t i o n i nc h a p t e r2 ， w es i m p l i f yt h ep r o o f , o b t a i nt h es i m i l a rr e s u l t sw i t h o u ta n ye x t r ar e g u l a r i t y r e q u i r e m e n t s a l t h o u g ht h i sr e s u l ti ss u b o p t i m a li nt h ec o n v e r g e n c er a t e ，i ti s m o r er e a s o n a b l ea c c o r d i n gt ot h en u m e r i c a lr e s u l t s r e s e a r c h e r sa l s of i n ds o m ed r a w b a c k so ft h es e m i l a g r a n g i a nm e t h o df 2 2 ，6 ， 1 0 ，5 】w h i c hw o u l dl i m i tt h ea p p l i c a t i o n so ft h em e t h o d s i n c ew eh a v et ou s e n u - m e r i c a li n t e g r a t i o no ri n t e r p o l a t i o n n u m e r i c a ld i f f u s i o nw i l lb ei n t r o d u c e d t h e s c h e m ea l s om a yb e c o m ec o n d i t i o n a l l yu n s t a b l e f u r t h e r m o r e ，u n i f o r mg r i dd o e s n o ts u i tt h es h o c kl a y e r so rm o v i n gf r o n t sw h i c hu s u a l l yo c c u ri nt h ec o n v e c t i o n d o m i n a t e dc a s e i no r d e rt oo v e r c o m et h e s ed r a w b a c k s ，r e s e a r c h e r si n t r o d u c e d s o m en e wm e t h o d ss u c ha sa r t i f i c i a ld i f f u s i o nm e t h o d ，h i g hr e s o l u t i o ns c h e m e ， m o v i n gf i n i t ee l e m e n tm e t h o da n ds t r e a m l i n em e t h o d a n da d a p t i v i t ya l s oh a s b e e ni n t r o d u c e di n t ot h es e m i - l a g r a n g i a nm e t h o d 3 3 ，2 6 ，4 9 ，2 4 ，2 5 a d a p t i v e a l g o r i t h mm o d i f i e st h es p a c i a lm e s ha n dt i m es t e ps i z ea c c o r d i n gt ot h ee r r o ri n - f o r m a t i o nw h i c hi sp r o v i d e db yt h ec u r r e n tn u m e r i c a ls o l u t i o n ，t h e r e f o r ei ts h o w s i t sp o t e n t i a la n dv a l i d i t y h o w e v e r ，f o rt i m e ，t h e s er e s u l t su s et h ec l a s s i c a lt i m e e r r o ri n d i c a t o rw h i c hi so r i g i n a l l yp r o p o s e df o rt h ep a r a b o l i cp r o b l e m t h i sk i n d o ft i m eap o s t e r i o r ie r r o re s t i m a t o r sd o e sn o tt a k et h ec h a r a c t e r so ft h ec o n v e c - t i o nd o m i n a t e dp r o b l e m si n t oa c c o u n ta n dm a yn o te f f i c i e n t n o t i c et h a tt h e c o n v e c t i o nd i f f u s i o np r o b l e ms a t i s f i e st h ee n e r g yi d e n t i t ya l o n gt h ec h a x a c t e r i s - t i c s ，i nc h a p t e r3 ，w ep r o p o s e dan e wt i m ee r r o ri n d i c a t o ra n di t sap o s t e r i o r i e r r o re s t i m a t e s c o m b i n i n gi tw i t hr e s i d u a lt y p es p a c ee r r o ri n d i c a t o r ，w eg i v ea p o s t e r i o r ie r r o re s t i m a t e sf o rt h ef u l l yd i s c r e t i z e ds c h e m ea n dt h ec o r r e s p o n d i n g a d a p t i v ea l g o r i t h m a d d i t i o n a l l y , b a s e do nt h i sn e wt i m ee r r o ri n d i c a t o r ，w e p r e s e n tap r i o r ie r r o re s t i m a t ei nt i m ew i t ho p t i m a lo r d e ro fc o n v e r g e n c er a t e a n dm i n i m a lr e q u i r e m e n to ft h er e g u l a r i t y t h i so v e r c o m e st h ed r a w b a c kt h a t c l a s s i c a la n a l y s i sr e q u i r e se x t r ar e g u l a r i t y a n o t h e rb i gc o n c e r na b o u tt h es e m i l a g r a n g i a nm e t h o di st h ec o m p u t a - t i o n a lo v e r h c a d c o m p a r ew i t hs t a n d a r dt i m e d i s c r e t i z es c h e m e ，t h es e m i l a g r a n g i a nm e t h o dh a v et ob a c k t r a c k i n gt h ec h a r a c t e r i s t i c sa te a c ht i m es t e p w h i c hi n c r e a s e st h eo v e r a l lc o m p u t a t i o n a lt i m e m o r e o v e r ，w h e nw ed e a lw i t h c o m p l e xp r o b l e m s ，t i m em a r c h i n gd ot a k ea l o n gt i m ew h e nw eu s es m a l lt i m e s t e ps i z ed u et ot h es t a b i l i t yi s s u e s o m e t i m e sw ec a n n o tg e tar e a s o n a b l er e s u l t s i nar e a lt i m e t h e r e f o r e ，w ei n t r o d u c ep a r a l l e la l g o r i t h mi nt i m et ot h es e m i l a g r a n g i a nm e t h o d p a r a r e a li sf i r t l yp r o p o s e di n 【6 5 】a n dh a sb e e na p p l i e dt o m a n yd i f f e r e n tp r o b l e m s 【9 ，7 ，6 7 ，4 4 ，3 1 t h i sa l g o r i t h mi sai t e r a t i o nm e t h o d b a s e do nt w ot i m eg r i d a te a c hi t e r a t i o n ，w ef i r s tp r e d i c to nt h ec o a r s eg r i dw i t h l a r g et i m es t e ps i z ea n dt h e nc o r r e c to nt h ef i n eg r i dw i t hs m a l lt i m es t e ps i z e c o n c u r r e n t l y i nc h a p t e r4 f r o mt h el i n e a ri t e r a t i o nm e t h o dp o i n to fv i e w ，w e a n a l y s i st h ep a r a r e a la l g o r i t h ma n dg i v ea n e wp r o o fo ft h ec o n v e r g e n c er e s u l t s s i n c et h es e m i - l a g r a n g i a nm e t h o ds o l v e sap a r a b o h cp r o b l e ma te a c ht i m es t e p ， w ec a na p p l yp a r a l l e la l g o r i t h md i r e c t l y b e c a u s eo ft h eh y p e r b o l i cn a t u r eo ft h e s o l u t i o no ft h ec o n v e c t i o nd i f f u s i o ne q u a t i o n ，w ei n t r o d u c et h et i m ea d a p t i v i t y t ot h ep a r a r e a la l g o r i t h m a c c o r d i n gt ot h ed i f f e r e n tp u r p o s eo ft h et w og r i d ， w ed e s i g nd i f f e r e n tt i m ea d a p t i v ea l g o r i t h m sf o rt h e mr e s p e c t i v e l y t i m ea d a p - t i v ep a r a r e a la l g o r i t h mb a l a n c e st h ec o m p u t a t i o n a ll o a do ne a c hp r o c e s s o r sa n d o p t i m i z et h ee f f i c i e n c yo ft h ep a r a l l e la l g o r i t h m m o r e o v e r ，a d a p t i v i t yi m p r o v e s t h ea p p l i c a b i l i t yo ft h ep a r a r e a la l g o r i t h m w ea p p l yt h es e m i - l a g r a n g i a nm e t h o dt ot h en o n n e w t o n i a nf l u i d ss i m u l a - t i o n t 1 1 ed i f f i c u l t i e so ft h i ss i m u l 【a t i o na r et h a tw es h o u l dp r e s e r v et h ep o s i t i v i t y o ft h ec o n f o r m a ls t r e s sv aa n dt h es t a b i l i t yi s s u ew h e nt h ew e i s s e n b e r gn u m b e r i sr e l a t i v e l yb i g ( w i 0 7 ) i fan u m e r i c a la l g o r i t h mc a nn o tp r e s e r v et h ep o s i t i v - i t y , t h i sa l g o r i t h mm a y n o tc o n v e r g e ，e s p e c i a l l yw h e nt h ew e i s s e n b e r gn u m b e ri s l a r g e t h es e m i - l a g r a n g i a nm e t h o d c a np r e s e r v et h ep o s i t i v i t yn a t u r a l l y ( 6 3 ，6 2 】 i nc h a p t e r5 ，w ed i s c u s st h ep r o c e d u r e so ft h ea l g o r i t h ma n ds o m ei m p l e m e n t d e t a i l s t h en u m e r i c a lr e s u l t ss h o wt h a to u rs c h e m ei se f f e c t i v e w h e nw e i s - s e n b e r gn u m b e r i ss m a l l e rt h e n0 7 ，w eg e tt h es a m er e s u l t sw i t ho t h e r sa n d w h e n w e i s s e n b e r gn u m b e ri sl a r g e ，o u rm e t h o di ss t a b l ea n d e f f e c t i v e t h i st h e s i si sap h a s e ds u m m a r yo ft h ea u t h o r sr e s e a r c hd u r i n gh i sv i s i ti n t h ep e n n s y l v a n i as t a t eu n i v e r s i t y t h ea u t h o r sr e s e a r c hi su n d e rp r o f j i n c h a o 改进的s e m i - l a g r a n g i a n 算法及其应用 x u ss u p e r v i s i o na n di ss t i l lu n d e r w a y k e y w o r d s ：s e m i - l a g r a n g i a nm e t h o d ，f i n i t ee l e m e n tm e t h o d ，a d a p t i v em e t h o d ， p a r a l l e lm e t h o d ，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 ，n a v i e r - s t o k e se q u a t i o n ，c o n s t i t u t i v ee q u a t i o n ，n o n n e w t o n i a nf l u i d s ，o l d r o y d - bm o d e l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得浙江大学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：互a 函趁签字日期 学位论文版权使用授权书 本学位论文作者完全了解塑婆盔堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权堑婆盔堂可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：塑逸l 拯 签字日期：丕立! 曼：! 导师签名：畜琶畈队 笤宝e l 蝴0 旧了6 笋签字期：堂：厶! ：! 致谢 本文是在我的博士生导师程晓良教授和我在美国访问时的导师许进超教授 的共同指导下完成的。两位老师渊博的知识，耐心的指导，严谨的态度和勤奋 的作风都使我受益匪浅。程老师对我的学术工作非常支持。在他的帮助下，我 才能有机会去美国访问留学。在留学期间，许老师对我的生活和学习都提供了 很大帮助，本文的大部分工作都是我在留学期间完成的。他们为我提供了良好 的学习条件，创造了良好的学术氛围。在他们的帮助下，我才能够顺利的完成 学业。值此毕业之际，谨以此文向他们表示我最崇高的敬意和最诚挚的感谢。 借此机会我还要感谢王兴华，韩丹夫，张振跃，叶兴德，黄正达，梁克维， 胡俊，l u d m i lz i k a t a n o v ，y o u n g - j ul e e 等老师在我求学过程中给我的悉心指导 和帮助。感谢孙洁，凌晓峰，戴晓霞，龚荣芳，刘箐，王飞，刘玉苓，张郑芳，朱 升峰，沈芳仙等同门师兄弟姐妹的对年来的支持和帮助。感谢张晨松，朱云荣， 薛光日，郑斌，贾继伟等合作者，感谢他们在学术上和我的交流和指导，也感谢 他们平日生活中对我的关心和帮助，特别是我在美国留学期间对我的帮助。同 时感谢浙江大学数学系的秘书韩东老师和资料室的各位老师所提供的各种便利 和帮助。 特别的，我要感谢我的家人和女友，他们总是在我身后默默的支持我，鼓励 我，帮助我。教会了我要坚强，勇敢而且乐观。感谢他们时时刻刻面带微笑的告 诉我他们爱我，我也爱你们。我能全身心的投入到研究工作中去，靠得就是他 们的理解和支持。 谨以此文献给帮助过我的人，谢谢你们，我会继续努力的1 2 0 0 9 年3 月于浙大 第一章绪论 1 1 引言 计算，这个动词在数学中有着非常重要的地位。从我们第一天接触数学开 始，老师和父母教给我们的，定是如何计算一加一。从此，计算就和我们结下 了不解之缘。从简单的加减乘除，到复杂点的方程求解，这都离不开计算。计算 在现代社会的各个领域普遍存在。金融行业有大量的数据要处理，这离不开算。 医疗上，一些高新技术，比如伽马刀，是靠计算定位的。工业上，比如船只，飞 机的制造，离不开计算。而现代科学技术的发展，更离不开计算。比如最近我国 神舟七号上天，宇航员太空行走，整个过程就涉及了大量的计算问题。而且还 需要相当精确的计算，一个小小的计算失误，会引起难以想象的后果。鉴于计 算的重要性，计算数学这门学科，就是专门研究这些计算问题的解决方法和有 关数学理论问题的一门学科。 计算数学属于应用数学的范畴。主要包括了函数逼近问题，线性和非线性 代数方程组求解问题以及微分方程数值求解问题。微分方程数值解是个重要的 计算数学的分支。因为生活中，生产中，自然界中，有大量的现象和问题可以用 微分方程来表示。很多物理，化学现象，都可以直接用微分方程加以刻画和描 述。而这些方程。往往是没有办法求得精确解的。这时候，数值求解就非常的重 要。这对更好的解决实际生产闯题和了解现象后面的本质，有着很大的帮助。而 本文要讨论的内容，就是对一些流体方程的数值求解。计算流体力学是在2 0 世 纪6 0 年代兴起的。计算流体的实践，大大地推动了计算科学的深化和发展，计 算科学的研究和创新也为计算流体不断提供这新方法和理论。计算流体力学中， 介质面，激波等等运动界面的问题，或者间断解的数值模拟，是极为迫切也是最 困难的。这方面的计算科学新方法，新思想和新理论也就应运而生了。但是，还 是有很多困难的。比如大r e y n o l d s 数的遄流模拟，非牛顿流体的模拟等等。本 文就是针对计算流体中的一些困难，从流体本身性质出发，运用了l a g r a n g i a n 的观点，与一些先进，新颖，有效的方法相结合，提出了新的算法，提供了解决 困难的可行性。 对微分方程的数值求解的方法种类繁多，例如有限差分法，有限元方法，有 2 改进的s e m i l a g r a n g i a n 算法及其应用 限体积法，无网格法，谱方法等等。其中有限元方法首先于2 0 世纪5 0 年代初有 工程师们提出。其系统的数学基础的奠定，则是在6 0 年代中期，以冯康先生为 代表的中国学者和西方学者独立并行地完成的。有限元方法已为工程力学界广 泛地应用于各类数值问题的求解上。同时，在数学上也建立了一套完整的理论。 基于有限元的新算法和新理论的研究，仍然不断的涌现。移动有限元，间断有 限元，时空有限元，自适应有限元等等新方法，都给有限元增加了活力。使其能 更好的解决实际问题中的困难。 总之，计算数学，涉及了我们生活生产，科技发展的各个方面。而微分方程 的数值求解，特别是有限元方法，随着计算机的发展，广泛的应用于船舶，机 械，巨型建筑和水利设施的设计。近年来，又被广泛的应用于流体力学，电磁场 等非应力分析问题中。本文就是用有限元算法结合s e m i l a g r a n g i a n 算法，并用 自适应，并行等新算法进行改进，使其能解决计算流体力学中的难点问题一一 非牛顿流体的数值模拟和仿真。 1 2研究背景 对流扩散方程是一类非常常见的方程。它描述了粒子或者能量( 或者别的 物理量) 在一个物理系统中进行传递，而且这种传递包含两个过程，一是对流， 二是扩散。其最基本的形式如下 五o u ：e a u b v 仳 ( 1 1 ) 方程右端的两项，就分别表示了对流和扩散这两个物理过程。其中第一项表示 了物理量乱的扩散，且扩散系数是e 。第二项表示了物理量扎的以速度b 对流。 对流扩散方程出现在许多数学物理模型中，而由于其对流扩散的特点，所以最 主要的是出现在各种流体的数学模型中。比如空气动力学，遄流模拟，流体体 积函数追踪模型，激波问题，浅水波问题，交通动力学，非牛顿流体模拟等等。 其形式除了上面给出的基本形式( 1 1 ) 外。还有在不可压和可压流体模拟中非常 常见的n a v i e r s t o k e s 方程 筹+ ( 钍v ) u = 一跏+ 瓦1 让 ( 1 2 ) 这里r 就是r a y n o l d s 数。还有其简化模型b u r g e r s 方程 鬻+ ( u v ) u = a 乱 ( 1 3 ) 第章绪论 3 这是一类非线性的对流扩散方程，可以代表浅水波问题，也可以代表交通流动 力学问题。另外还有线性化后的模型问题 象+ 6 v 让一山+ c u = ， ( 1 4 ) 这个问题仍然是很多流体问题的模型。比如河流水质问题，地下油贮问题，大 p & l e t 数的热传导问题等。当然，对流扩散问题也不仅仅出现在流体问题中， 它在半导体模拟，电器学等等前沿学科都有应用。 由于对流扩散问题在许多领域都有实际应用，所以对它的数值求解方法的 研究也就吸引了很多工程师，数学家等研究人员的兴趣。人们用一些传统的微 分方程数值解的方法去求解它。比如有限差分法，有限元方法，有限体积法等 等。但是正如前面提到的，对流扩散问题的求解有许多困难。首先最显著的一 个问题就是对流扩散问题的解往往有运动界面，常常会发展和生成激波，这就 给传统算法带来很大问题。数值解会很不稳定，有巨大的数值耗散或者非物理 的震荡。其次我们可以看到对流扩散问题和参数有关，比如r a y n o l d s 数，粘性 系数，p & l e t 数等等，这些参数对数值求解方法有很大影响。随着参数的不同