（计算数学专业论文）求解拟线性对流扩散方程的牛顿多重网格方法.pdf

c a n d i d a t e ： g r a d e ： s p e c i a l i t y ： q i n g q i n gl i a o 2 0 0 4 c o m p u t i n gm a t h e m a t i c s r e s e a r c hf i e l d ：n u m e r i c a lm e t h o d sa n da p p l i c a t i o nf o r p a r t i a ld i f f e r e n t i a le q u a t i o n s t h e s i st o p i c ：an e w t o n m u l t i g r i d m e t h o 。d f o r s o 1 v i n g q u a s i l i n e a rc o n v e c t i o nd i f f u s i o ne q u a t i o n f i n i s h e dt i m e ：m a y1 8 ，2 0 0 7 s u p e r v i s o r ： p r o f e s s o rj i a n w e ih u d e p a r t m e n to fc o m p u t i n gm a t h e m a t i c s s c h 0 0 1o fm a t h e m a t i c a ls c i e n c e s n a n k a iu n i v e r s i t y , t i a n ji n3 0 0 0 7 1 ，p r c h i n a m a y1 8 ，2 0 0 7 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：廖昔畸 幼7 年，月彩e t 经指导教师同意，本学位论文属于保密，在了年解密后适用 本授权书。 指导教师签名： 砌拗 学位论文作者签名： 廖：清青 一 7 旷 解密时间： 如l o 年 ，月 多2 日 各密级的最长保密年限及书写格式规定如下： ；内部5 年( 最长5 年，可少于5 年) ；秘密- k l o 年( 最长1 0 年，可少于1 0 年) ：机密2 0 年( 最长2 0 年，可少丁2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 廖清嗜 细7 年- 月彩日 摘要 摘要 本文提出一种求解拟线性对流扩散问题的牛顿多重网格算法对原问题采用 部分迎风有限元格式进行离散应用牛顿迭代方法处理非线性的右端项，得到线 性问题最后应用多重网格方法求解线性的离散问题 众所周知，多重网格方法是求解离散问题最有效的方法之一，并且有可能达 到最优的计算复杂度通常，求解非线性方程的牛顿迭代法要求迭代初值近似真 解，并且每一步迭代都需要直接求解线性代数方程组在多重网格背景下，本文提 出的方法，以粗网格解的插值作为细网格的迭代初值，并且使用快速的多重网格 迭代避免了直接求解线性代数方程组本文表明，牛顿迭代方法与多重网格方法 的结合是近似求解拟线性对流扩散问题的一种有效方法本文给出该算法在一些 假设条件下的收敛性分析，并且验证了该算法在每个时间步的计算开销与肌同阶， 胍为第k 层有限元空间的维数 关键词：多重网格方法，对流扩散问题，部分迎风有限元格式，牛顿迭代方法， 收敛性分析 a b s t r a c t i nt h i sp a p e r , w ep r o p o s ean e w t o nm u l t i g r i da l g o r i t h mf o rs o l v i n gq u a s i l i n e a r c o n v e c t i o n d i f f u s i o np r o b l e m sw i t hn o n l i n e a rr i g h t - h a n dt e r m t oo b t a i nt h ed i s c r e t e p r o b l e m , t h ep a r t i a lu p w i n df i n i t ee l e m e n ts c h e m ei sa p p l i e d t h e nw e u t i l i z et h en e w t o ni t e r a t i v em e t h o dt od e a lw i t ht h en o n l i n e a rr i g h t - h a n dt e r m , a sar e s u l t ，t h ep r o b l e m i sl i n e a r i z e d a tl a s t , m u l t i g r i dm e t h o di su s e dt os o l v et h el i n e a rd i s c r e t ee q u a t i o n s m u l t i g r i dm e t h o d i sk n o w nt ob ea m o n gt h em o s te f f i c i e n tm e t h o d s ，a n do f f e r st h e p o s s i b i l i t yo fs o l v i n gt h ed i s c r e t ep r o b l e m w i t ho p t i m a lc o m p u t a t i o nc o m p l e x i t y u s u - a l l y , n e w t o ni t e r a t i v em e t h o df o rs o l v i n gn o n l i n e a re q u a t i o nr e q u i r e st h a tt h ei n i t i a l v a l u ea p p r o x i m a t e st h ee x a c tv a l u ev e r yw e l la n dt h el i n e a ra l g e b r a i cs y s t e mi ss o l v e d e x a c t l ya te a c hi t e r a t i o n i nt h ec o n t e x to fm u l t i g r i d ，o u rn e w t o nm u l t i g r i da l g o r i t h m t a k e st h ei n t e r p o l a t i o no ft h ea p p r o x i m a t es o l u t i o no nt h ec o a r s e rg r i da st h ei n i t i a li t e r - a t i v ev a l u eo nt h ef i n e r 妒d b e s i d e s ，t h ef a s tm u l t i g r i di t e r a t i o na v o i d se x a c t l ys o l v i n g as y s t e mo fl i n e a ra l g e b r ae q u a t i o n sa te a c hn e w t o ni t e r a t i o n t h ec o m b i n a t i o no ft h e c l a s s i c a ln e w t o nm e t h o da n dt h em u l t i g r i dm e t h o di ss h o w e dt ob ea l le f f i c i e n ta p p r o a c ht oa p p r o x i m a t et h es o l u t i o no ft h eq u a s i l i n e a rc o n v e c t i o n d i f f u s i o ne q u a t i o n s w e p r e s e n tt h ec o n v e r g e n c ea n a l y s i su n d e rs o m ea s s u m p t i o n sa n ds h o wt h a tt h ec o m p u t a f i o n a lc o s to ft h ea l g o r i t h mi sp r o p o r t i o n a lt od ( 眠) a t e a c ht i m es t e p ，w h e r e 帆 i st h ed i m e n s i o no ft h ef i n i t ee l e m e n ts p a c eo nt h ek t hl e v e l k e yw o r d s ：m u l t i g r i dm e t h o d ，c o n v e c t i o n d i f f u s i o np r o b l e m s ，u p w i n df i n i t ee l e m e n ts c h e m e ，n e w t o nm e t h o d ，c o n v e r g e n c ea n a l y s i s 一一一 t 出l eo fc o n t e n t s t a b l eo fc o n t e n t s 摘要i a b s t r a c t i i c h a p t e r1i n t r o d u c t i o n 1 5 1 1 m o d e lp r o b l e m l 1 2 n u m e r i c a lm e t h o d s l 1 3d e v e l o p m e n t o f m u l t i g r i d m e t h o d 2 1 - 4 o u t l i n eo f t h i sp a p e r 3 c h a p t e r2t h ep a r t i a lu p w i n df i n i t ee l e m e n ts c h e m ef o rc o n v e c t i o n d i f f u s i o np r o b l e m 5 2 1 d o m a i nt r i a n g u l a t i o n 5 2 2 t h ep a r t i a lu p w i n df i n i t ee l e m e n ts c h e m e 7 5 2 3 t h ee r r o ra n a l y s i s 9 c h a p t e r 3m u l t i g r i dm e t h o d 1 3 5 3 1m u l t i g r i d m e t h o d f o r p o i s s o n p r o b l e m 1 3 3 2m u l t i g r i dm e t h o df o rn o n s y m m e t r i ca n di n d e f i n i t ee l l i p t i cp r o b l e m18 3 3 n u m e r i c a le x p e r i m e n t 2 2 c h a p t e r4a n e w t o nm u l t i g r i dm e t h o df o rq u a s i l i n e a rc o n v e c t i o n d i f f u s i o n p r o b l e m 2 5 5 4 1 n e w t o nm u l t i g r i da l g o r i t h m 2 5 5 4 2c o n v e r g e n c ea n a l y s i s 2 7 弘3 c o n c l u s i o na n df u t u r ew o r k 3 3 a c k n o w l e d g e m e n t 3 4 b i b l i o g r a p h y 3 5 r e s u m e 3 8 w h e r eqcr 2i sac o n v e xp o l y g o n a l ；va n dv d e n o t er e s p e c t i v e l yt h eg r a d i e n to p e r - a t o ra n dt h ed i v e r g e n c eo p e r a t o ri nt h es p a t i a lc o o r d i n a t e s ；t h ec o e f f i c i e n t sa n di n i t i a l v a l u es a t i s f ys o m ec o n d i t i o n sw h i c hw i l lb ed e t a i l e do u ti nt h en e x tc h a p t e r e q u a t i o n so ft h i st y p e ( c a l l e dc o n v e c t i o n d i f f u s i o ne q u a t i o n s ) r e p r e s e n ta m a t h e m a t i c a lm o d e lf o rac l a s so fd i f f u s i o np h e n o m e n ai nw h i c hu n d e r l y i n gf l o wi sp r e s e n t v ( o ( z ，t ) v u ) a n dh ( x ，t ) v uc o r r e s p o n dt ot h et r a n s p o r to fut h r o u g ht h ed i f f u s i o np r o c e s sa n dt h ec o n v e c t i o ne f f e c t ，r e s p e c t i v e l y t h em o d e lr e p r e s e n t e db y ( 1 1 ) c l o s e l ya p p r o x i m a t es u c hp h y s i c a lp h e n o m e n ai nt h er e a lw o r l da sh e a to rp o l l u t a n t t r a n s p o r t a t i o n s1 2n u m e r i c a lm e t h o d s t os o l v e ( 1 1 ) n u m e r i c a l l yt h e 丘i l i t ed i 虢r e n c em e t h o da n d 丘i l i t ee l e m e n tm e t h o d h a v eb e e na p p l i e de x t e n s i v e l y t h ef i r s tk i n do fm e t h o d si n c l u d ec h a r a c t e r i s t i cf i n i t e d i f f e r e n c em e t h o d ，u p w i n df i n i t ee l e m e n tm e t h o d ，g e n e r a l i z e dd i f f e r e n c em e t h o d ( o r c a l l e df i n i t ev o l u m em e t h o d ) 【1 】a n ds oo n i ti sw e l lk n o w nt h a tt h ec l a s s i c a lg a l e r k i n m e t h o dw i t hc o n t i n u o u sp i e c e w i s el i n e a rf i n i t ee l e m e n tl c a d st os p u r i o u so s c i l l a t i o n s w h e nt h el o c a lp e c l d tn u m b e ri sl a r g e t h u s ，m a n yn o n - s t a n d a r df i n i t ee l e m e n tm e t h o d s a r ep r o p o s e dt os o l v e ( 1 1 ) ，s u c ha sp e t r o v g a l e r k i nf i n i t ee l e m e n tm e t h o d 2 1 ，u p w i n d f i n i t ee l e m e n tm e t h o d 【3 】，c h a r a c t e r i s t i cf i n i t ef i n i t em e t h o d 4 】，s t r e a m l i n ed i f f u s i o n m e t h o d 【5 】，d i s c o n t i n u o u sg a l e r k i nm e t h o d 6 】a n ds oo n c h a p t e r1 i n t r o d u c t i o n2 i nt h i sp a p e rw ea p p l yt h ep a r t i a lu p 、) i ，i n df i n i t ee l e m e n ts c h e m ew h i c ha p p r o x - i m a t e st h ec o n v e c t i o nt e r mb ( x ，t ) v ub a s e do nam e s hd u a lt ot h et r i a n g u l a rg r i d ， m a i n l yr e f e rt o 【7 】 1 3d e v e l o p m e n t o fm u l t i g r i dm e t h o d i nr e c e n ty e a r s ，m u l t i g r i dm e t h o d sh a v eb e e nu s e de x t e n s i v e l ya st o o l sf o ro b - t a i n i n ga p p r o x i m a t i o n st os o l u t i o n so fp a r t i a ld i f f e r e n t i a le q u a t i o n s t h ec h a r a c t e r i s t i c f e a t u r eo ft h em u l t i g r i di t e r a t i o ni si t sf a s tc o n v e r g e n c e t h ec o n v e r g e n c es p e e dd o e s n o td e t e r i o r a t ew h e nt h ed i s c r e t i z a t i o ni sr e f i n e d , w h e r e a sc l a s s i c a li t e r a t i v em e t h o d s s l o wd o w nf o rd e c r e a s i n gg r i ds i z e f u r t h e r m o r em u l t i g r i dm e t h o d so f f e rt h ep o s s i b i l i t yo fs o l v i n gt h ed i s c r e t ep r o b l e mw i t ho ( n ) c o m p u t a t i o n a lw o r k a n ds t o r a g e ，n a st h en u m b e ro fu n k n o w n s ，w h i c hm e a n st h ec o m p l e x i t yi so p t i m a l h o w e v e r , t h e r e i sn of i x e dm u l t i g r i da l g o r i t h ma p p l i c a b l et oa l lp r o b l e m s ，i n s t e a d , o n es h o u l da d j u s t t h em u l t i g r i dc o m p o n e n t st ot h ep r o b l e mi nq u e s t i o nb a s e do nt h ef r a m e w o r ko ft h e m u l t i g r i dm e t h o d s i nw h a tp r o b a b l yw a st h ef i r s t t r u e m u l t i g r i dp u b l i c a t i o n 8 】，f e d o r e n k o ，am a t h e - m a t i c i a no f s o v i e tr u s s i a n ，f o r m u l a t e dam u l t i g r i da l g o r i t h mf o rt h es t a n d a r df i v e - p o i n t f i n i t ed i f f e r e n c ed i s c r e t i z a t i o no ft h ep o i s s o ne q u a t i o no nas q u a r e ，i n19 6 4 t h i sw o r k w a sg e n e r a l i z e dt ot h ec e n t r a ld i f f e r e n c ed i s c r e t i z a t i o no ft h eg e n e r a ll i n e a re l l i p t i cp a r - t i a ld i f f e r e n t i a le q u a t i o nw i t hv a r i a b l es m o o t hc o e f f i c i e n t sb yb a c h v a l o vi n1 9 6 6 【9 】 t h et h e o r e t i c a lw o r ke s t i m a t e sw e r ep e s s i m i s t i c ，a n dt h em e t h o dw a sn o tp u ti n t op r a c t i c ea tt h a tt i m e i n1 9 7 3t h ef i r s tp r a c t i c a lr e s u l t s ( s e e 1 0 ) w e r ep r o p o s e db yb r a n & ，w h op u b l i s h e da n o t h e rp a p e ri n1 9 7 7 1l 】，c l e a r l yo u t l i n i n gt h em a i np r i n c i p l e sa n d t h ep r a c t i c a lu t i l i t yo ft h em u l t i g r i dm e t h o d s t h ew o r ko fb r a n d td r e ww i d ea t t e n t i o n a n dm a r k e dt h eb e g i n n i n go ft h er a p i dd e v e l o p m e n t m e a n w h i l e ，h a c k b u s c hd i s c o v e r e dm u l t i g r i dm e t h o d si n d e p e n d e n t l yi n1 9 7 6 1 2 ，a n dp r o v i d e df i r mm a t h e m a t i c a l f o u n d a t i o n sa n dr e l i a b l em e t h o d s 【1 3 ，1 4 1 a tf i r s tt h e r ew a sm u c hd e b a t ea n ds c e p t i c i s ma b o u tt h et r u em e r i t so fm u l t i g r i d m e t h o d s t h i sl e dan u m b e ro fr e s e a r c h e r st ot h ed e v e l o p m e n to f b o t ht h e o r e t i c a la n a l y s i sa n dc o m p u t a t i o n a li m p l e m e n t a t i o no fm u l t i g r i dm e t h o d s t h et h e o r yo ft h ea n a l y s i sa p p l i e dt os y m m e t r i cp o s i t i v ed e f i n i t ep r o b l e m sw a s c h a p t e r1 i n l x o d u c t i o n3 a l m o s tc o m p l e t e db yb a n k 1 5 ，b r a m b l e 1 6 ，b r a e s sa n dh a c k b u s c h 1 7 g e n e r a l l y , t h e s er e s u l t sa s s u m e da r e g u l a r i t ya n da p p r o x i m a t i o n h y p o t h e s i sw h i c hi n v o l v e da p a r a m e t e r0 o t 1 t h e r e s u l t si nt h e s ep a p e r sg u a r a n t e e dc o n v e r g e n c er a t ef o r m u l t i g r i dv - c y c l ea n dw - c y c l ea l g o r i t h m sf o rv a r i o u so i nc o n t r a s t ，t h et h e o r yf o rn o n - s y m m e t r i ca n di n d e f i n i t ee l l i p t i cp r o b l e m sa r en o t d e v e l o p e ds oc o m p l e t e l y , a n ds o m er e s u l t so n l yh o l du n d e rr a t h e rr e s t r i c t i v ea s s u m p - t i o n si n v o l v i n gt h er e l a t i o nb e t w e e nt h en u m b e ro fs m o o t h i n gs t e p sa n dt h es i z eo ft h e c o a r s e s tg r i d ( s e e 【18 ，19 】) i n19 8 8 ，b r a m b l e 2 0 】p r e s e n t e dr e s u l t sf o rt h es o c a l l e d s y m m e t r i cs c h e m e a p p f i e dt on o n - s y m m e t r i ca n di n d e f i n i t ee l l i p t i cb o u n d a r yv a l u e p r o b l e m s ，a n ds h o w e dt h a tm u l t i g r i da l g o r i t h m sw i t ha n ya m o u n to fs m o o t h i n gs t e p s o nt h ef i n e s tg r i dc o n v e r g ea tar a t et h a ti si n d e p e n d e n to ft h en u m b e ro fl e v e l so ru n - k n o w n s ，p r o v i d e dt h ei n i t i a lg r i di ss u f f i c i e n t l yf i n e w i t h o u tr e g u l a r i t ya s s u m p t i o n s ， an e wt e c h n i q u ef o rp r o v i n gc o n v e r g e n c er a t ew a sp r o p o s e db yb r a m b l e 2 1 f u r - t h e r m o r e ，w a n g 2 2 】e s t a b l i s h e dac o n v e r g e n c ee s t i m a t ef o r n o n s y m m e t f i c m u l t i g r i d a l g o r i t h m ss o l v i n gn o n s y m m e t r i ca n di n d e f i n i t ep r o b l e m s ，w i t h o u tf u l t h e rr e g u l a r i t y a s s u m p t i o nb e y o n d h 1 f o r p a r t i a ld i f f e r e n t i a lp r o b l e m sd i s c r e t i z e db yb o t hc o n f o r m i n ga n d n o n c o n f o r m - i n gf i n i t ee l e m e n tm e t h o d s ，t h em u l t i g r i dm e t h o d sa l ee x t e n s i v e l ya p p l i e d t h ec i t e d l i t e r a t u r e sa b o v em a i n l yd i s c u s s e dt h ec a s eo fc o n f o r m i n gf i n i t ee l e m e n t s t h es i g n i f i - c a n td i f f e r e n c ei nt h en o n c o n f o r m i n gc a s ei st h a tm k 一1 垡m k ，w h e r em ki st h ef i n i t e e l e m e n ts p a c eo nm e s hl e v e l 七h e n c e o n ec a nn o tu s et h en a t u r a li n j e c t i o nf o rt h e i n t e r g r i dt r a n s f e ro fg r i df u n c t i o n s t h eo r i g i n a lw o r k sc a nr e f e rt o 【2 3 ，2 4 ，2 5 】e t c 51 4 o u t l i n eo ft h i sp a p e r t h er e s to ft h ep a p e ri so r g a n i z e da sf o l l o w s i nc h a p t e r2 ，t h ep a r t i a lu p w i n df i n i t ee l e m e n ts c h e m ei sb r i e f l yi n t r o d u c e dt og e t t h ed i s c r e t ep r o b l e mc o r r e s p o n d i n gt o ( 1 1 ) t h ef i n i t ee l e m e n ts p a c e s ，as e c o n d a r y 鲥d b a s e do nt h ec i r c u m c e n t r i cd u a ld o m a i n ，a n ds o m ep r o p e r t i e so ft h ed i s c r e t ep r o b l e m a r ea l s og i v e n i nc h a p t e r3 ，m u l t i g r i dm e t h o di sc o n s i d e r e dt os o l v et h ep o i s s o nm o d e lp r o b l e m a sw e l la sn o n s y m m e t r i ca n di n d e f i n i t ee l l i p t i cp r o b l e m ，a n dw e p r e s e n t t h ec o r r e s p o n d c h a p t e r1 i n t r o d u c t i o n 4 e n c er e s u l t sw h i c hw i l lb ea p p l i e di nc h a p t e r4 t os h o w t h ee f f i c i e n c yo fm u l t i g r i dm e t h o d ，w el i s tt h er e s u l t so fm u l f i g r i dm e t h o dc o m p a r e dt o t m d i t i o n a ii t e r a t i o nm e t h o dt os o l v et h ep o i s s o np r o b l e m b e s i d e s ，w ec o m p a r et h e r e s u l t so fv - c y c l ea n dw - c y c l ea sw e l la sd i f f e r e n tl e v e l so fm e s h e s i nc h a p t e r4 ，n e w t o nm u l t i g r i da l g o r i t h m ( t h ec o m b i n a t i o no ft h ec l a s s i c a ln e w t o nm e t h o da n dt h em u l t i g r i dm e t h o d ) i sp r o p o s e dt oa p p r o x i m a t et h es o l u t i o no ft h e q u a s i l i n e a rc o n v e c t i o n d i f f u s i o ne q u a t i o n s w ep r o v i d et h ec o n v e r g e n c ee r r o re s t i m a t e a n ds h o wt h a tt h ec o m p u t a t i o n a lc o s to ft h ea l g o r i t h mi sp r o p o r t i o n a lt o0 ( 肌眠) ， w h e r en ki st h ed i m e n s i o no ft h ef i n i t ee l e m e n ts p a c eo nt h ek t hl e v e la n dn ti st h e t o t a ln u m b e ro ft i m es t e p s a n dt h i sc h a p t e ri st h em a i nw o r ko ft h i sp a p e r t h r o u g h o u tt h i st h e s i s ，ca n dc ，w i t ho rw i t h o u ts u b s c r i p tw i l ld e n o t eag e n e r i c p o s i t i v ec o n s t a n t sw h i c hm a y t a k eo nd i f f e r e n tv a l u e si nd i f f e r e n tp l a c e s t h e s ec o n s t a n t sw i l la l w a y sb ei n d e p e n d e n to ft h em e s hp a r a m e t e r t h ef o l l o w i n gm e s hp a r a m e t e r s ： h = m a x h 。) ， e 1 h k = m 蹲 仡。) e 6 7 k 。 。 w ea s s u m et h a tt h et r i a n g u l a t i o nt hi sr e g u l a ra n dw e a k l ya c u t e ，i e t h e r ee x i s t s q o ( 0 ，i 7 1 ) i n d e p e n d e n to fh ，s u c h t h a ta l li n t e r i o ra n g l e sao f t h et r i a n g l e sa r eb o u n d e d a sf o l l o w s ： 口尹7 r w ec o n s t r u c tas e c o n d a r yg r i do fq w h i c hi sa n o t h e rp a r t i t i o nd e r i v e df r o mt h e o r i g i n a lt r i a n g u l a t i o n t h e r ea r em a i n l yt w o f o r m so fs e c o n d a r yg r i d s ，n a m e l yb a r y c e n - t r i ct y p ea n dc i r c u m c e n t r i ct y p e i nt h i sp a p e r , w ep r e f e rt oa s s o c i a t i n ga d u a ld o m a i n q to ft h es e c o n d a r yg r i do