（计算数学专业论文）求解helmholtz方程的组合紧致差分格式及其快速预处理算子.pdf

求解h e l m h o l t z 方程的组合紧致 差分格式及其快速预处理算子 !ii ifiii l f l lli i jill i l lilliir i l l y 17 6 8 3 3 5 摘要：本文第一次成功地将组合紧致差分( c c d ) 格式应用于离散一维和二维 h e l m h o l t z 方程，并显式给出了对应的用矩阵表示的非对称c c d 线性系统和借 助合适的边界条件实现了理论上的高阶收敛精度特别地，对于带有n e u m a n n 边界条件的h e l m h o l t z 方程，还提出了一组新的高阶c c d 边界格式用于提高边 界的逼近精度总体而言，本文所给出的c c d 格式对于一般边界情况至少达到 了六阶精度 对于一维h e l m h o l t z 方程，先从理论上讨论了c c d 离散线性系统满足非奇 异性的充分必要条件，然后提出并分析了一个新的块下三角预处理算子用于迭 代求解所考虑的c c d 线性系统同时，注意到c c d 线性系统所带有的鞍点结 构，本文还考虑了一类基于s c h i l d e r s 分解的约束预处理算子作为比较数值结 果表明本文提出的块下三角预处理算子要明显快于现有的约束预处理算子更 加重要的是，基于块下三角预处理算子的g m r e s 迭代算法在数值上实现了与 网格规模无关的收敛速度，对块下三角预处理算子的特征值分析也部分地证实 了这一数值现象对于规模为犯的c c d 线性系统，块下三角预处理算子的预处 理方程求解仅需p m ) 的计算量 对于二维h e l m h o l t z 方程，借助k r o n e c k e r 积和一维c c d 线性系统简洁地 给出了二维c c d 线性系统的矩阵表示，同时，为了保证离散系统的非奇异性， 四个c c d 边界公式用于替换四个角点的原边界方程为了构造针对二维c c d 线性系统的块下三角类型预处理算子，一种创新的矩阵拉伸技巧用于重组原系 数矩阵同样，本文还构造了基于s c h i l d e r s 分解的约束预处理算子用于比较 数值结果显示本文提出的块下三角类型预处理算子比现有的约束预处理算子要 更加有效，这与理论上的特征值分析是吻合的数值上也观察到了与网格规模无 关的收敛速度，这一特点对于求解超大规模问题特别重要 最后，本文得到了一些结论并给出了部分后续研究的建议 关键词：h e l m h o l t z 方程；有限差分方法；组合紧致差分；鞍点问题；k r y l o v 子 空间法；约束预处理算子；s c h i l d e r s 分解；矩阵拉伸；g m r e s s o u t hc h i n an o r m a lu n i v e r s i t y e f f i c i e n tp r e c o n d i t i o n e r sf o rt h e h e l m h o l t z e q u a t i o nd i s c r e t i z e db y c o m b i n e d c o m p a c td i f f e r e n c em e t h o d b y j u nl i u at h e s i ss u b m i t t e di np a r t i a lf u l f i l l m e n tf o r t h e d e g r e eo fm a s t e ro fs c i e n c e i nt h e s c h o o lo fm a t h e m a t i c a ls c i e n c e s m a y 2 0 10 a b s t r a c t t h ec o m b i n e dc o m p a c td i f f e r e n c e ( c c d ) s c h e m e sa r e ，f o rt h ef i r s tt i m e ，s u c c e s s f u l l ya p p l i e dt od i s c r e t i z et h ew e l l - k n o w nh e l m h o l t ze q u a t i o n s ，i n c l u d i n go n e d i m e n s i o n a l ( 1d ) a n dt w o d i m e n s i o n a l ( 2 d ) c a s e s ，w h e r et h ed i s c r e t i z e dc c dl i n e a rs y r s t e m sa r ee x p l i c i t l yf o r m u l a t e di n m a t r i xf o r ma n dt h et h e o r e t i co r d e ro fa c c u r a c yi sf u l l ya c h i e y e db yi n c o r p o r a t i n gs u i t a b l eb o u n d a r yc o n d i t i o n s e s p e c i a l l y ，an e wg r o u po fs i x t h o r d e ra c c u r a t ec c db o u n d a r ys c h e m ei sg i v e nt o i m p r o v et h ew h o l ea c c u r a c yw h e nf a c i n gn e u m a n nb o u n d a r yc o n d i t i o n s i nb o t hc a s e s ，t h ec c d s c h e m e sa t t a i na tl e a s ts i x t h o r d e ra c c u r a c yf o rg e n e r a lb o u n d a r yc o n d i t i o n s h l1d c a s e an e c e s s a r ya n ds u f ! f i c i e n tc o n d i t i o no nt h en o n s i n g u l a r i t yo ft h ec c dl i n e a rs y s t e mi sg i v e na n dan e wb l o c kl o w e rt r i a n g u l a r ( b l t ) p r e c o n d i t i o n e ri sc o n s t r u c t e da n da n a l y z e d f o rt h ed i s c r e t i z e dc c dl i n e a rs y s t e m n o t i n gt h eb l o c ks a d d l e p o i n ts t r u c t u r eo ft h ec c dl i n e a rs y s t e m ，t h es c h i l d e r s f a c t o r i z a t i o nb a s e dc o n s t r a i n tp r e c o n d i t i o n e r sa r ea l s od i s c u s s e df o r c o m p a r i s o n t h en u m e r i c a lr e s u l t ss h o wt h a tt h eb l tp r e c o n d i t i o n e ri sf a s t e rt h a nt h ec o n s t r m n t p r e c o n d i t i o n e r s m o r ei m p o r t a n t l y , t h ec o n v e r g e n c er a t eo fg m r e sw i t hb 【tp r e c o n d i t i o n e ri s o b s e r v e dt ob eh - i n d e p e n d e n ta n dt h ee i g e n v a l u ea n a l y s i sp a r t i a l l ys u p p o r t st h i sn u m e r i c a lp h e n o m e n a n ec o m p u t a t i o n a lc o s to ft h ep r e c o n d i t i o n i n gs t e pi so fo ( n 、c o m p l e x i t y i l l2 dc a s e t h eo r i g i n a lb o u n d a r yc o n d i t i o n sa tt h e f o u rc o m e r sa r er e p l a c e db yf o u rc c dc o r - n e rf o r m u l a st oa s s u r et h en o n - s i n g u l a r i t yo ft h ed i s c r e t i z e dc c dl i n e a rs y s t e m , w h i c hi ss t r a i g h t - f o r w a r d l yc o n s t r u c t e df r o mt h e1 dc a s eb yu t i l i z i n gk r o n e c k e rp r o d u c t s a ni n n o v a t i v em a t r i x s t r e t c h i n gt e c h n i q u ei sp r o p o s e df o rb u i l d i n gab l t 哆p ep r e c o n d i t i o n e rf o rt h ec c dl i n e a rs y s - t e m n u m e r i c a le x p e r i m e n t sa lep e r f o r m e dt ov e r i f yt h ee f f i c i e n c yo ft h ec a r e f u l l yd e s i g n e db l t t y p ep r e c o n d i t i o n e r , w h i c ha r ew e l lc o n s i s t e n tw i t ht h ee i g e n v a l u ea n a l y s i s t h er e s u l t sa l s os h o w t h a tt h eb l tt y p ep r e c o n d i t i o n e ro u t p e r f o r m st h ec o n v e n t i o n a lc o n s t r a i n tp r e c o n d i t i o n e r t h ee x p e c t e dh - i n d e p e n d e n tc o n v e r g e n c er a t eo ft h eb l tp r e c o n d i t i o n e dg m r e si sa l s ov a l i d a t e di n n u m e r i c a l ，a n dt h i sm e r i ti sp a r t i c u l a r l yi m p o r t a n tf o rs o l v i n gl a r g es c a l el i n e a rs y s t e m s f i n a l l y , s o m ec o n c l u d i n gr e m a r k sa n da f e wv a l u a b l es u g g e s t i o n so nf u t u r er e s e a r c ha r eg i v e n k e y w o r d s ：f i n i t ed i f f e r e n c em e t h o d ，c o m b i n e dc o m p a c td i f f e r e n c e ，h e l m _ h o l t ze q u a t i o n ，s a d d l e p o i n ts y s t e m ，k r y l o vs u b s p a c em e t h o d ，c o n s t r a i n tp r e c o n d i t i o n e r , s c h i l d e r s f a c t o r i z a t i o n ，m a t r i x s t r e t c h i n g ，g m r e s c o n t e n t s a b s t r a c t 1 b a c k g r o u n d s 1 1h e l m h o l t ze q u a t i o n 。 1 1 1 b o u n d a r yc o n d i t i o n s 1 1 2r e l a t e dl i t e r a t u r e s 1 2 f i n i t ed i f f e r e n c em e t h o d s 1 2 1s e c o n d o r d e rs c h e m e 1 2 2 h i g h o r d e rc o m p a c t ( h o c ) s c h e m e 1 2 3 c o m b i n e dc o m p a c t d i f f e r e n c e ( c c d ls c h e m e 1 3i t e r a t i v em e t h o d sf o rs p a r s el i n e a rs y s t e m 2c c ds c h e m ef o r1 dh e l m h o l t ze q u a t i o n 2 1c c dl i n e a rs y s t e ma n di t sn o n s i n g u l a r i t y 2 2 p r e c o n d i t i o n e r sf o rt h ec c dl i n e a rs y s t e m 2 2 1 s a d d l e - p o i n tt y p ep r e c o n d i t i o n e r s 2 2 2b l o c kl o w e r t r i a n g u l a r ( b l t ) p r e c o n d i t i o n e r 2 3n u m e r i c a lr e s u l t s 2 3 1 1 dc a s ew i t hd i r i c h l e tb o u n d a r yc o n d i t i o n 2 3 21dc a s ew i t ha b s o r b i n gb o u n d a r yc o n d i t i o n 3c c ds c h e m ef o r2 1 ) h e l m h o l t ze q u a t i o n 3 1c c dl i n e a rs y s t e m 3 2p r e c o n d i t i o n e r sf o rt h ec c dl i n e a rs y s t e m 。 3 2 1 s a d d l e p o i n tt y p ep r e c o n d i t i o n e r 。 3 2 2m a t r i xs t r e t c h i n ga n db l t t y p ep r e c o n d i t i o n e r 3 3n u m e r i c a lr e s u l t s 3 3 12 dc a s ew i t hd i r i c h l e tb o u n d a r yc o n d i t i o n 3 3 2 2 dc a s ew i t ha b s o r b i n gb o u n d a r yc o n d i t i o n 4c o n c l u s i o n l i s to ff i g u r e s l i s to ft a b l e s a c k n o w l e d g e m e n t s v n 1 l 2 2 3 3 4 6 7 l l 7 7 9 6 6 9 3 3 6 7 8 5 5 9 1 3 5 7 副 1 l 1 1 1 2 2 2 3 3 3 3 3 4 4 4 5 5 5 5 b i b l i o g r a p h y 5 9 c h a p t e r1 b a c k g r o u n d s 1 1h e l m h o l t ze q u a t i o n t h eh e l m h o l t ze q u a t i o ni sd e r i v e dw h e nt h ea s s u m p t i o no ft i m e h a r m o n i cw a v e si si m p o s e do n t h ef o l l o w i n gw a v ee q u a t i o n 【1 ，2 】 叼托( z ，t ) 一c 2 a w ( x ，亡) = 0 ，z r a , d = 1 ，2 ，3 ( 1 。1 ) a r i s ei nm a n yp h y s i c a la p p l i c a t i o n s ，e g ，e l e c t r o m a g n e t i cw a v ep r o p a g a t i o na n da c o u s t i c s ，w h e r e cd e n o t e st h es p e e do fs o u n di nt h et r a v e l i n gm e d i a l e tz = 厂ja n dp 0d e n o t e st h ea n g u l a r f r e q u e n c y , t h e nt h et i m e d e p e n d e n tp r e s s u r ew ( x ，t ) i sa s s u m e d t ob eo ft h ef o r m 伽( z ，t ) = ，( z ) e 一彬 o ns u b s t i t u t i n gt h i sp a r t i c u l a rw ( x ，t ) i n t oe q u a t i o n ( 1 1 ) l e a d st ot h eh e l m h o l t ze q u a t i o n a f ( z ) + 后2 ，( z ) = o ，七= 等 d e p e n d i n go nt h en a t u r eo fo r i g i n a lw a v ee q u a t i o no rp r o b l e m ，w ec o u l da l s oa s s u m ea n o n z e r ot i m e h a r m o n i cf o r c i n gt e r mi nt h er i g h t - h a n d s i d eo f ( 1 1 ) ，a n dt h u so b t a i nt h em o r eg e n e r a l h e l m h o l t ze q u a t i o n a f ( m ) + k 2 f ( x ) = 夕( z ) ( 1 2 ) f o rt h ec o n v e n i e n c eo fn u m e r i c a lt r e a t m e n tw es u p p o s et h eo r i g i n a lp r o b l e md o m a i nqh a sa l r e a d y b e e ns c a l e dt ot h eu n i ts q u a r eq = 0 ，1 】ds u c ht h a tt h ew a v e n u m b e rki sd i m e n s i o n l e s s 。i nt h i s t h e s i s w eo n l yc o n s i d e rt h en u m e r i c a ls o l u t i o nf o rt h eh e l m h o l t ze q u a t i o nw i t hd = 1a n dd = 2 t h eg e n e r a l i z a t i o no fo u rr e s u l t st ot h et h r e e - d i m e n s i o n a lc a s e si sb e y o n dt h es c o p eo ft h i st h e s i s ， 1 1 1 b o u n d a r yc o n d i t i o n s i no r d e rt os o l v et h eh e l m h o l t ze q u a t i o n ( 1 2 ) c e r t a i nb o u n d a r yc o n d i t i o n sh a v et ob ei m p o s e d o n t h eb o u n d a r yf = o f t h o m o g e n e o u sd i r i c h l e tb o u n d a r yc o n d i t i o n 厂( z ) = 0 o nf = 0 f z ( 1 3 ) i so f t e nn o ts u i t a b l ei nap h y s i c a lm e a n i n gb u ti r r e p l a c e a b l ei ni n v e s t i g a t i n gan e w d i s c r e t i z a t i o n s c h e m ef o rt h ee q u a t i o no re v a l u a t i n gan e wp r e c o n d i t i o n e rf o rt h er e s u l t a n tl i n e a rs y s t e m 。i n p r a c t i c a l t h ea b s o r b i n g o rs o m m e r f e l dr a d i a t i o nb o u n d a r yc o n d i t i o n 【3 】o ff i r s to r d e r 百o f ( x ) 一。k f ( z ) = o 。n r = a q( 1 4 ) s h o u l db eu s e dw h e nai n f i n i t ed i s t a n c ei sc o n c e r n e d h e r e 佗d e n o t e st h ed i r e c t i o nn o r m a lt ot h e b o u n d a r y ，p o i n t i n go u t w a r d l y s i n c e t h et h e o r e t i ca n a l y s i so ft h ec a s ew i t ht h ea b s o r b i n gb o u n d a r y i sm o r ed i f f i c u l t ，w em a i n l yf o c u so na n a l y z i n gt h ec a s e sw i t hd i r i c h l e tb o u n d a r i e sb u tv e r i f y i n g o u ra n a l y s i so nt h ec a s e sw i t ha b s o r b i n gb o u n d a r i e st h r o u g hn u m e r i c a le x p e r i m e n t s 1 1 2r e l a t e dl i t e r a t u r e s h o wt oa c c u r a t e l ya n de f f i c i e n t l ys o l v et h eh e l m h o l t ze q u a t i o n ( 1 2 ) w i t hag i v e nb o u n d a r yc o n 。 d i t i o n ( 1 3 ) o r ( 1 4 ) b yn u m e r i c a lm e t h o d s i st h em a i nt h e m eo ft h i st h e s i s t h em o s tl i t e r a t u r e so n t h en u m e r i c a ls o l u t i o n so fh e l m h o l t ze q u a t i o n sc a nb ec l a s s i f i e di n t ot h r e ea s p e c t s c o n s t r u c t i n ge f f i c i e n tp r e c o n d i t i o n e r s 【4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1l 】 d e v e l o p i n gh i g h o r d e rd i s c r e t i z a t i o ns c h e m e s 1 2 ，1 3 ，1 4 ，1 5 ，1 6 ，1 7 i n t r o d u c i n gs p e c i a lm e t h o d s f o rt r e a t i n gh i g hw a v en u m b e rk 18 ，19 ，2 0 ，21 ，2 2 i ti si n t e r e s t i n gt on o t i c et h a ta l lt h e s ee n d e a v o u r sa r ea c t u a l l yf o ras a m ep u r p o s e - - - e f f i c i e n t l y s o l v i n gh e l m h o l t ze q u a t i o n sw i t hh i g hw a v en u m b e rk t h ec a s e sw i t hl a r g ew a v en u m b e ra r e o fg r e a t e rp h y s i c a li n t e r e s ta n da l s om o r ec h a l l e n g i n gd u et ot h e i rh i g h l yo s c i l l a t i n gs o l u t i o n s e f f i c i e n tp r e c o n d i t i o n e r sm a k ei tp o s s i b l et os o l v el a r g e rh e l m h o l t z l i n e a rs y s t e m sw h e nn e c e s s a r y , w h i l eh i g h o r d e rd i s c r e t i z a t i o ns c h e m e se n a b l eu st oo b t a i ne q u i v a l e n ta c c u r a t ea p p r o x i m a t i o n s b ys o l v i n gs m a l l e rh e l m h o l t z l i n e a rs y s t e m s ，w h i c hm e a n sh i g h e rw a v en u m b e r 尼c o u l db em o r e e a s i l yh a n d l e d a m o n g t h e s en u m e r i c a lm e t h o d s ，t h ef i n i t ed i f f e r e n c em e t h o di st h em o s tp o p u l a rc h o i c ef o r i t ss i m p l i c i t yi nf o r m u l a t i o na n dm a t u r i t yi np r a c t i c a la p p l i c a t i o n t h u si nt h en e x ts e c t i o n sw e c h a p t e r1 b a c k g r o u n d s3 w i l lb r i e f l yi n t r o d u c et h es t a n d a r df i n i t ed i f f e r e n c em e t h o d a sw e l la si t sr e c e n t l yv a r i a n t si n c l u d i n g h i g h o r d e rc o m p a c ts c h e m ea n dc o m b i n e dc o m p a c ts c h e m e 1 2f i n i t ed i f f e r e n c em e t h o d s w h e nam o d e l i n gd i f f e r e n t i a le q u a t i o nw i t hg i v e nb o u n d a r i e si st o oc o m p l i c a t e dt od e r i v ei t s a n a l y t i cs o l u t i o ne a s i l y , e n g i n e e r sw i l lt u r nt on u m e r i c a lm e t h o d sf o ri t sa p p r o x i m a t e ds o l u t i o ni n d i s c r e t ef o r m t h ea c c u r a c yo ft h ea p p r o x i m a t e ds o l u t i o nd e p e n d so nt h ee m p l o y e dd i s c r e t i z a t i o n s c h e m ea n da l s ot h en u m b e ro fu s e dc o m p u t a t i o n a lg r i d s l e tf ( x ) r e p r e s e n t sas m o o t hf u n c t i o no fo n ev a r i a b l ed e f i n e do nt h ei n t e r v a l a ，6 1 t h ef i n i t e d i f f e r e n c em e t h o d 2 3 】e m e r g e si ft h ed e r i v a t i v et e r m si nt h ed i f f e r e n t i a le q u a t i o na r ea p p r o x i m a t e db yt h ea s s u m e dd i s c r e t es o l u t i o n g i v e nai n t e r i o rp o i n t ( a ，6 ) ，t h ef i r s td e r i v a t i v eo f ，7 ( z ) a tz = c a nb ea p p r o x i m a t e db y 确盟等巡， w h e r eh 0i sa p r e s c r i b e ds m a l ls t e ps i z es a t i s f y i n g + h b t h i sa p p r o x i m a t i o ni sm o t i v a t e d b yt h ed e f i n i t i o no fd e r i v a t i v e 删= l i m 。盟掣 n o t et h a ti na b o v ef i n i t ed i f f e r e n c ef o r m u l aw ei nf a c to n l ya p p r o x i m a t et h e r i g h td e r i v a t i v e t h e l e f td e r i v a t i v ec a nb ea p p r o x i m a t e di nt h es a m e w a y 1 2 1s e c o n d o r d e rs c h e m e t h es t a n d a r da p p r o a c hf o ra n a l y z i n gt h ee r r o ro faf i n i t ed i f f e r e n c es c h e m ei st h r o u g he x p a n d i n g t h et a y l o rs e r i e so ft h ef u n c t i o na tt h e c o n c e r n i n gp o i n t 毒( a ，6 ) ，e g ， ， + 九) = 厂( ) + 允，代) + 虿h 2 厂( ) + 百h 3 ，( ) + 夏h 4 厂( 4 ( ) + d ( 5 ) ， ( 1 5 ) 厂( f 一 ) = 厂( ) 一九，代) + 虿h 2 厂( ) 一百h 3 尸( f ) + 夏h 4 厂( a ( ) + p ( 九5 ) ( 1 6 ) s u b t r a c t i n g ( 1 6 ) f r o m ( 1 5 ) g i v e sac e n t r a la p p r o x i m a t i o nf o rt h ef i r s td e r i v a t i v e 堑型型=，-代)-4i-笙，代)-4i-2h6 p ( a )= l ，1 一r i 卜ll ，l 门l ，、，。j 、。， w i t hs e c o n d - o r d e ra c c u r a c y t h ea d d i t i o no f ( 1 6 ) a n d ( 1 5 ) a l s op r e s e n t sac e n t r a la p p r o x i m a t i o n f o rt h es e c o n dd e r i v a t i v e ，( + h ) 一2 厂( ) + ，( 一九) 2= ，( f ) + 西h 2 产悃+ o ( h 4 ) w i t hs e c o n d o r d e ra c c u r a c y u n d e rt h ea s s u m p t i o nt h a t ，( 4 ) ( z ) i su n i f o r mb o u n d e di na ，6 】，w i t h as u f f i c i e n ts m a l lhw ec o u l dn e g l e c tt h ee r r o rt e r m sw i t hh 2a n dh 4t od e r i v et h es e c o n d - o r d e r c e n 廿a lf i n i t ed i f f e r e n c es c h e m ef o rt h ef i r s td e r i v a t i v e a n dt h es e c o n dd e r i v a t i v e r e s p e c t i v e l y 八淞盟掣 ，( f ) ，( + h ) 一2 ，( ) + ，( 专一h ) 6 1 ，( ) h 2 6 2 t 厂( f ) ， ( 1 7 ) ( 1 8 ) i ft h ep o i n t l i e so nt h eb o u n d a r y = ao r = b ，w es h o u l du s eo n e - s i d e df o r m u l at o a p p r o x i m a t et h ed e r i v a t i v e f o ri n s t a n c e ，a g a i nb yt h et a y l o rs e r i e sw e c o u l dd e r i v et h ef o l l o w i n g s e c o n d o r d e ra p p r o x i m a t i o n 心= 巡坚笔岩丛型 f o rt h ef i r s td e r i v a t i v eo nt h er i g h tb o u n d a r yf = b 1 2 2 h i g h o r d e rc o m p a c t ( h o c ) s c h e m e t h e r ea r em a n yd i f f e r e n tw a y st oi m p r o v et h eo r d e ro fa c c u r a c yo ft h ef i n i t ed i f f e r e n c ea p p r o x i m a - t i o n sg i v e ni nt h ep r e v i o u ss e c t i o n m a k i n gu s eo fm o r eg r i dp o i n t sa r o u n dt h ec o n c e r n i n gp o i n t i san a t u r a li d e a f o re x a m p l e ，af o u r t h o r d e ra c c u r a t ea p p r o x i m a t i o nf o rt h es e c o n dd e r i v a t i v ei s g i v eb y ，( ) = 一厂( 一2 ) + 1 6 f ( f h ) 一3 0 f ( ) + 1 6 f ( + h ) 一，( 一2 h ) 1 2 h 2 w h e r ef i v ep o i n t si n c l u d i n g a r eu s e d h o w e v e r , t h i st r e a t m e n tw i l lr e s u l ti nad i s c r e t ec o e f f i c i e n t m a t r i xw i t hl a r g e rb a n d w i d t ha n dt h t l si n c r e a s et h ec o m p u t a t i o n a lc o s tal o te s p e c i a l l yf o rt w o - d i m e n s i o n a lp r o b l e m s r e c e n t l y ，t h eh i g h o r d e rc o m p a c t ( h o c ) d i f f e r e n c es c h e m ew a sp r o p o s e d t oa l l e v i a t et h e