（计算数学专业论文）外推多网格法——大规模科学计算的新算法.pdf

摘要 快速求解由差分法或有限元法导出的大型线性方程组是大规模科 学和工程计算中的重要问题人们的目标是对阶方程组用o ( n ) 次 乘除运算得到所需精度的解而多网格法( m g ) 第一次实现了这个目 标，成为求解大规模问题最有效的方法经典m g 的理论方法已经比 较成熟，由于使用了3 种运算：插值，限制和迭代，求解时需要在多重 粗细网格上反复迭代，所以程序较为复杂1 9 9 6 年德国b o r n e m a n n 等人 提出瀑布式多网格法( c m g ) ，即从粗网到细网的单向计算，只采用了 插值与迭代两种运算，程序容易实现令人注目 本论文研究一类新的瀑布式多重网格法，主要工作和创新点如下 首次提出了外推瀑布式多网格法( e x c m g ) 本论文基于有限元的 渐近展开式，导出了新的外推公式新算法沿用c m g 的思想，但将粗 网上的线性插值改为新外推与二次插值，为密网提供更好的初值，本 质上减小了初始误差，对加速收敛起着关键的作用新算法对函数和 导数都收敛，且都有高精度本论文在p c 机上用e x c m g 求解了4 0 0 万未知数的问题，对函数和导数都达到8 - 1 0 位精度，仅费时l o 分钟，进 一步证实了这些优势 首次证明了共轭梯度法( c g ) 按f 2 模的有界性和收敛性对c g 法 至今只有按能量模的收敛估计，因此这是一个新结果本文还发现当 第i 层网格的迭代次数取幂指数形式( m l p 仁t ) 时，基于c g 迭代的多 重网格法，存在着个网格层数的“阀值”i o ，即当i 硒时，c g 主要起 磨光作用此特性对证明e x c m g 按离散l 2 模的收敛性起重要作用 对正则性较弱的解u h 3 ，首次证明了双线性元的渐近展开在节 点集上按离散l z 模有高精度o ( h 3 ) ，因此e x c m g 仍有效已有的渐近 展开式研究主要是对光滑解( 如牡c 。) ，并只得到了在逐点意义下的 结果上述结果拓宽了e x c m g 的应用范围数值试验表明，e x c m g 对非光滑解u h 3 甚至h 2 仍有很高精度 关键词：有限元；新外推公式；二次插值；共轭梯度法；瀑布式多 重网格法 a b s t r a c t h o wt os o l v et h el i n e a rs y s t e mo fe q u a t i o n sd e r i v e db yf i n i t ed i f f e r e n c e m e t h o do rf i n i t ee l e m e n tm e t h o dr a p i d l yi sa ni m p o r t a n ti s s u ei nl a r g e - s c a l e s c i e n t i f i ca n de n g i n e e r i n gc o m p u t i n g p e o p l e sg o a li st oo b t a i nt h es o l u t i o n w i t hr e q u i r e da c c u r a c yo fn - o r d e rs y s t e mt h r o u g ho ( n ) t i m e sm u l t i p l i c a t i o n a n dd i v i s i o no p e r a t i o n s m u l t i - g r i dm e t h o d ( m c ) a c h i e v e st h i sg o a lf o rt h ef i r s t t i m e ，a n db e c o m e st h em o s te f f e c t i v em e t h o dt os o l v el a r g e - s c a l ep r o b l e m s s i n c e1 9 7 0 s ，t h em u l t i - g r i dm e t h o dh a sb e e ni n - d e p t hs t u d y , a n das y s t e m a t i c t h e o r yo nm gh a sb e e nd e v e l o p e d h o w e v e r ，m gr e p e a t e d l yu s e st h r e ek i n d s o fo p e r a t i o n s ( i n t e r p o l a t i o n ，r e s t r i c t i o na n di t e r a t i v e ) i nc o a r s ea n df i n eg r i d s ， s oi t sc o d el o o k sc o m p l e x i n1 9 9 6 ，b o r n e m a n ne ta 1 p r o p o s e dt h es o - c a l l e d c a s c a d i cm u l t i g r i dm e t h o d ( c m c ) ，w h i c hr e q u i r e sn oc o a r s eg r i dc o r r e c t i o n sa t a l la n dm a yb ev i e w e da sa o n ew a y ”m u l t i g r i dm e t h o d o n l yt h ei n t e r p o l a t i o n a n di t e r a t i o nf r o mc o a r s eg r i d 8t or e f i n e dg r i d sa r eu s e di nc m g ，t h u si t sc o d e i se a s yt oi m p l e m e n ta n dm o r er e m a r k a b l e t h i sp a p e rp r o p o s e san e we x t r a p o l a t i o nc a s c a d i cm u l t i - g r i dm e t h o d ，t h e m a i nw o r ka n di n n o v a t i o np o i n t sa r ea sf o l l o w s a ne x t r a p o l a t i o nc a s c a d i cm u l t i - g r i dm e t h o d ( e x c m g ) i sp r o p o s e di nt h e p a p e r b a s e do n a na s y m p t o t i ce x p a n s i o no ff i n i t ee l e m e n t ，an e we x t r a p o l a t i o n f o r m u l ai sd e r i v e d f o l l o w sc m g si d e a t h en e wa l g o r i t h mu sn e we x t r a p o - l a t i o na n dq u a d r a t i ci n t e r p o l a t i o ni np l a c eo ft h el i n e a ri n t e r p o l a t i o ni nc o a r s e g r i d st op r o v i d eab e t t e ri n i t i a lv a l u eo ff i n eg r i d s i tr e d u c e st h ei n i t i a le r r o r e s s e n t i a l l y , a n dp l a y sak e yr o l ei nt h ea c c e l e r a t i o no fc o n v e r g e n c es p e e d t h e p r o p o s e da l g o r i t h m c o n v e r g e sw i t hh i g h a c c u r a c yf o rf u n c t i o n sa n dd e r i v a t i v e s t h ed i s c r e t ee l l i p t i cp r o b l e mw i t h4m i l l i o nu n k n o w n sh a sb e e ns o l v e db ye x - c m go np ci n1 0m i n u t e s e r r o r so nt h ef i n e s tg r i d sa t t a i nt h ea c c u r a c y1 0 一， w h i c hf u r t h e rc o n f i r m st h ea d v a n t a g e so fc m g t h i sp a p e rp r o v e st h e 2 - n o r mb o u n d e d n e s sa n dc o n v e r g e n c eo fc o n j u g a t e g r a d i e n tm e t h o d ( c g ) f o rt h ef i r s t t i m e s of a r ，t h ec o n v e r g e n c eo fc gh a s b e e no b t a i n e do n l yi nt h es e n s eo fe n e r g yn o r m ；h e n c ei ti san e wr e s u l t w h e n m l l 一i st a k e na st h ei t e r a t i o nn u m b e ro ng r i d 五，w ef i n dt h a tt h e r ei sa i i “t h r e s h o l d i oa b o u tg r i dl e v e lf o rc g b a s e dm u l t i g r i dm e t h o d t h a ti s ，t h e e r r o ro n 五w i l ld e c a yr a p i d l yi fl i ot h er o l eo fc gi so n l y s m o o t h i n g t h i sf e a t u r ep l a y sa ni m p o r t a n tr o l ei np r o v i n gt h ec o n v e r g e n c eo f e x c m gi nt h es e n s eo fd i s c r e t el 2n o r m f o rt h es o l u t i o nt l h 3 w eh a v ep r o v e dt h ea s y m p t o t i ce x p a n s i o no fb i l i n e a re l e m e n tw i t ho ( h s ) a c c u r a c yf o ra l ln o d e si nt h es e n s eo fd i s c r e t el 2n o r m ， t h u se x c m gi ss t i l lv a l i d e x i s t i n gw o r ko na s y m p t o t i ce x p a n s i o ni sa b o u ta s m o o t hs o l u t i o n ( s u c ha su c 3 ) i ns e n s eo fp o i n tb yp o i n t t h ea b o v er e s u l t s e x t e n dt h ea p p l i c a t i o no fe x c m g n u m e r i c a le x p e r i m e n t ss h o wt h a te x c m g i sa l s ov a l i df o rn o n - s m o o t hs o l u t i o n sf u h 3o ru g k e yw o r d s ：f i n i t ee l e m e n t ；e x t r a p o l a t i o n ；q u a d r a t i ci n t e r p o l a t i o n ；c o n j u - g a t eg r a d i e n tm e t h o d ；c a s c a d i cm u l t i g r i dm e t h o d i l l 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果除文中已经注明引用的内容外，本论文不含任何其它个人或集 体已经发表或撰写过的作品成果x , t - 4 ：论文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明本人完全意识到本声明的法律结果由本人承担 学位论支作者签名：孝强殿 勿年朋多矿日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅本人授权湖南师范大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 l 、保密e l ，在年解密后适用本授权书 2 、不保密衫 ( 请在以上相应芴框内打) 9 7 日期：劢年岁月勿日 日期溯屏乡膨矿日 外推多网格法一一大规模科学计算的新算法 1 绪论 1 1 大规模计算的困难 1 1 1 科学计算中的困难 随着现代科学技术的日益发展，许多科学与工程问题，如大型喷气 客机及核裂变等的设计计算、石油的勘探与开发、流体涡度结构的模 拟等，它们的数学模型为高维的偏微分方程，其数值计算都归结为求 解大规模方程组，未知数常常超过数百万数千万要精细地求解这些 问题很困难，这时人们面临大规模，高效率，高精度，真实估计误差等 难题困扰实质上这些都是为保证所需的精度问题提高精度有两种 经典的模式：加密网格和增高次数，但实际上都受到了一定的限制： ( 1 ) 加密网格特别是对高维问题，当网格加密时，随问题维数的 增加其计算规模按几何级数猛增，这是很本质的困难如每个方向取 1 0 0 个节点，三维是百万节点，每个节点还可能有多个变量( 如三维弹 性力学组有三个方向位移，流体力学组有5 7 个变量) ，目前大型机都 难解决，称为“三维烦恼”( 多网格法已有本质的推进) ； ( 2 ) 使用高次元对光滑缌精度将提高但多维问题解的光滑性一 般不高，情况就并非如此如裂纹附近，在均匀网格下，任意次元及其 梯度分别只有精度o ( h ) 和o ( h m ) ，令人失望( 局部加密网格已有重要 推进) 又如对光滑解，人们常用线性元逼近的精度是o ( h 2 ) ，但导数( 力学 中是应变或应力) 的精度却猛降为d ( ) ，即网格加密1 0 倍( 三维节点增 加了千倍) 才能提高1 位精度，情况很糟糕( 用超收敛可提高到o ( h 2 ) ) 例如考虑如图所示正方形( 0 ，1 ) 2 上的p o i s s o n 方程 - a u = ，i nq ，u = 0o nf ( 1 1 ) 1 湖南师范大学2 0 1 0 届博士学位论文 图1 1 ：五点中心差分格式 用直线将区域剖分为n 亿个均匀正方形网格，步长为h = i n ，记 u ( 。，) 在节点( i h ，i h ) 上的值为在每个内节点( i h ，i h ) 上可建立五 点中心差分格式 虹壁h 2 虫+ 坐型h 2 型 ( 1 2 ) i “r 一7 补充零边界条件，化为总未知数为n = 一1 ) 2 的线性方程组，可直接 求解得节点值但由于未知数的个数n = o ( h d ) ( d 是问题的维数) ， 求解规模随维数d 猛增当未知数超过数万、数十万时，用直接法 求解，计算工作量浩大，计算时间长，已不合适必须考虑迭代法由于 矩阵的条件数为o ( h 吨) ，它随h 的变小而逐渐增大，迭代法收敛很缓 慢，效率低因此遇到很大困难 1 1 2 迭代算子的磨光和压缩作用 对椭圆问题的离散方程( 1 2 ) ，可以写为某个迭代格式 u 七+ 1 = s u 七，vu o ，k = 0 ，1 ， u 膏是n 维的节点未知向量由于准确解v 也满足此方程，迭代误差 矿= u k u 满足迭代关系 e 七= s e 奄一1 = s 2 e k 一2 = = s k e o ，k = l ，2 ， 这里s 是迭代算子 一2 一 外推多网格法一一大规模科学计算的新算法 假设 办，咖墙。是算子s 的特征对，初始误差能表示成e 0 ：妻咖， j = 1 f | e o f f 2 = f 唧1 2 ，则迭代误差的z 2 模是 j = 1 e 七1 1 2 = i l 铲e 。1 1 2 = i i 砖吩咖1 1 2 = 力七l a j l 2 ( 1 4 ) j = l j = l 谱半径j d = m a x 办 1 ，则 j i e 七 , o k i j e oj js , o k j o 一1 1 ( 1 5 ) 在迭代过程中，高频部分( 乃1 ) 被几次迭代消除了，但低频部分( 乃 1 ) 仍然保持了，很难消除 对一般的迭代法，如j a u c o b i 迭代法，g a u s s - s i e d e l 迭代法等，其谱半径 p = 1 一c h 2 1 次有限元及p o i s s o n 方程的双七 2 次矩形元在节点上有超收敛以后m z l a m a l 1 5 ( 1 9 7 7 ) 和陈传淼等 ( 1 9 7 8 ) 相互独立地研究了1 - 2 次矩形有限元梯度的超收敛性，并在文 献【2 0 中证明三角形线元的平均梯度在对称点上有超收敛，这里对称 点是指均匀三角形网格的内角点和边中点以后文献 2 2 ( 1 9 8 1 ) 证明任 意次矩形有限元的超收敛具有g a u s s - l o b a t t o 结构，即七次矩形元及其 梯度分别在七+ 1 阶l o b a t t o 点和七阶g a u s s 点上有超收敛，并建立了单 元正交分析框架和两个基本估计【3 3 ，8 2 1 9 9 5 年w a h l b i n 3 1 】，b a b u s h k a 8 4 】及陈【3 4 1 ( 1 9 9 7 1 9 9 9 ) 研究了任意次三角形元超收敛的对称点结构， 即偶次元的函数及奇次元的平均梯度在对称点上有超收敛迄今为 止，g a u s s - l o b a t t o 点和对称点是有限元超收敛的两种基本结构经3 0 多年研究已形成比较完整的超收敛理论方法，在1 9 9 6 年芬兰( 见文 集 3 3 】) 和2 0 0 0 年美国两次有限元超收敛国际会议上公认国际三学派 中国，i t h a c a ，t e x a s 3 1 以上这些结果已推广到分片几乎均匀网格和朝 1 4 外推多网格法一一大规模科学计算的新算法 奇点分片局部加密的等级网格( 对不光滑解) 等【2 5 ，2 7 ，对很广的区域 和奇异解都适用 下面主要讨论三角形线元及矩形双线性元，并假定网格均匀 记三角形线性元及矩形双线元空间为s 已经证明( 双) 线性有限 元u 与乱的( 双) 线性插值矗u 的梯度之差d ( u 一矗u ) 有超收敛性估计 ， i l v 一，1 牡i i l ，n = ( l d ( v h u ) 1 2 d x d y ) 1 2 = o ( h 2 ) l i t l i l 3 ，f l ， ( 2 1 4 ) ，n 它比标准误差i l u u i i = o ( h ) i m i 。高一阶精度( 超收敛) 梯度在单元 角点精度