（计算数学专业论文）基于小波的多重网格方法(1).pdf

嗣防科学技术大学研究生院学位论文 摘要 本文提出了一种基于双正交小波多分辨分析的多重网格方法。该方 _ 基具有粗网格 生成拳i 粗细网格间转换的自动化性质；插值算予和限制算予具有高精度邋近性。这两 意捷褥该方法在实舔瘟矮中篱程嵩效。篓法中考虑了塞逶黩技术。鼗繁试验验证了该 算法的优效性。 关键稍：多重网梅方法双歪交小波分耩秘适应 第1 页 璺堕翌兰矍查奎兰里鏊兰堕翌壁笙兰 a b s t r a c t an e w 鲫l t 群da 王g 蕊t h m ( b w m g ) b a s 礤雌氆eb i o 魅o g o n 越w a v e l e tm r ai s p m p o s e d i nm i sp a p e r c o m p a r i n gw i t hn l ec l a s s i c a lm u l t i 班d ，t h eb w m g a l g o r i t h mh a st w oa d v a n t a g e s ：o n ei st h ec o a r s e n i n go f 鲥ds p a c ei sa u t o m a t i c ，也eo t b e r 趣搬ei n 融p 磋蕊锄强d f e s 糖罐。n 霹凇o f s a f eh l 黪l ye 爨c i e 懿t 诵e 珏融e r e s i 畦u a li s e n o u g hs m o o t h 聃心s ea d v a i l t a g e sm a k et h 0b w m ga l g o r i m mm o r c c o n v e n i e n c ea n dp r a c t i c a l _i t a d o p t ss c l f _ a d a p t i v et e c h l l i q u ei n t l l e a l g o r i m m s o m e n u 豹1 0 纛c 采e x p e 薮l n e 藏t sa l 弓g 量v e 臻 k e y w o r d s ：m u i l i g r j db i o r t h o g o n a l w a v e l e t $ e i 卜a d a p t i v e 第疆 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：基士4 1 遂鲍垒重圈整左洼 学位论文作者签名：窒! l 塾日期：山口r 年月f ，日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：基王尘这鲍垒重圈整虚洼 学位论文作者签名：盔l 塑日期：知岁年月j 厂日 作者指导教师签名：j 萄年日期：如$ 年f f 月吵日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 小波分析与多重网格方法 多重网格方法【1 】【2 】闸自上个世纪六七_ 卜年代诞生以来，在各个计算领域应用十 分广泛，已经作为解各种偏微分方程尤其是线性椭圆型方程的一种加速收敛的迭 代方法，在流体力学，工程力学，天体物理，电磁学，光学，天气预报，信号图 像处理等方面有着十分，。泛的应用。 与此同时，上个世纪八十年代，种新的调和分析理论小波理论诞生了。 这种新兴的分析工具在信号处理，图像处理，数值逼近方面有着广泛的应用。尤 其是其多分辨分析的思想，成为多尺度研究方面经典智慧的结晶。 这两种理论之间有着天然的相似性】，基于这种观察，数值计算专家们提出 了结合小波分析的多重网格方法以期获得更高的性能。2 0 世纪末，国内外从事小 波分析应用于多重网格方法方面的研究还比较少，只有一些探讨性的研究2 4 】俐。 近年来，出现了一些具体算法方面的研究，这些研究主要有三类，第一类把小波 分析应用于多重网格方法解决奇异性较强的问题，如美国加州大学的d d l e o n l 2 副 的博士学位论文就是把小波多分辨分析的思想应用于多重网格，对微分算子进行 小波变换，提出一类新型的插值、限制算子和粗网格算子，构建了解决一类系数 振荡剧烈甚至间断的微分方程的高效算法，微分方程的类型局限于线性椭圆型。 第二类是把小波变换算子中的尺度空问投影算子及其逆算子分别作为限制算子和 插值算子，这种算法比使用一般的限制、插值算子的算法而言，有一个很大的优 越性，就是粗网格空问的选择是自动的，就是下一层的尺度空间。这样，使得算 法更为简便实用，具有黑匣子性。而黑匣子算法在实际应用中很有优势。这方面 的研究见于国内何军删和宋玉明博士【2 ”，文中利用小波滤波的思想将亏量分解在 尺度空间和小波空间，而将尺度空间上的分量作为粗网格上的亏量。这实际上是 指把小波变换算子中的尺度空间投影算子作为限制算子，其逆算予作为插值算子， 第l 页 潮跨科学技术大学磷究生浣学饿论文 下一级尺度空间作为较粗网格层，从而构造了多重网格的各个分量。作者把这种 方法应用于解一个无限氏金属条的t e 模，t m 模入射波电波的幅度分布问题。用 数傻实验检验了其方法静正确瞧，毽没有谖弱算法狡敛糕。并置疆窭在一些猿嚣 下，结合小波的多匿网格方法比般经典的方法具有更好的效率。第三类，由于 双正交小波逼近的简精度性，赢接将双正交小波系数作为插值限制算子。这类研 究冤予闰肉王红霞簿圭p ”。俸蠢褥双歪交小波滤波算子作为插值限澍舞子，结合 多重网格算法可以求解阶数为小波消失矩数两倍的病态t o e p l i t z 系统，充分显示 了双正交小波的赢逼近能力。文中证明了采用该类算子佟为插值和限制算子，算 法楚瘁殳敛静。搴文挺密了结合双芷交，l 、波多分辨分孝斤的多麓网格方法。在这释方 法中，既使算法县有插值限制辣子的高精度道近性，又鼠有粗网格生成自动化的 特点，通过数值实验，验证这两方面的确使褥算法简便离效。文中验诞了对大多 数润溪，双正交夺波多重网穰方法和经爽的多重丽穆算法稳院较更为有效。文中 还讨论了双正交小波系统如何选榉才能实现辣法最优的问题：以及算法的并行化， 以期娆求解更大型的复杂问题。 1 2 论文主要创新和内容结构 本文逶过对翦人工馋戆总绥，遮双正交多分瓣分辑与多耋瓣捂方法稳螽台， 提出了一种基于双正交小波多熏网格算法，发现这种算法不但延续了正交多分辨 分析与多重网格结合的一些优点，比如黑匣子性质( 粗细网格之间转换基本上是 垂动戆) ，还因为双歪交枣波系数共有对称缓秘寒数据压缫瞧这嚣丈耱患，菠褥撬 值和限制算子更为有效，从而使得这种多重网格算法更为高效和方便。并对该算 法作了并行化的分析考虑。创新点有如下两个方面： l 。 秘臻小渡多分瓣分孝厅褒谂对多重霹掇遴牙了分掇，健缮多重瓣秘瓣翟缨霹 格之间的转授自动化，为创立双正交小波多重网格算法创立了基础。 2 利用重构滤波器理论对擒值和限制作了详尽的分析。以及对具体问题如何 选择双玉交小波系统，绘懑了算法的麓本滚程錾。 文章内容结构如下： 第2 受 里堕型芏茎查查兰堕塑生堕兰垡笙茎 2 2 多重网格方法的发展历史 第一个二重网格迭代法是前苏联数学家f e d o r e i l k o 在1 9 6 1 年提出的。他在 1 9 6 4 年又构造了第一个多重网格算法【1 】，并证明典型问题( 如正方形区域上的 p o i s s o n 方程) 的收敛状态。随后，b r a n d t 在1 9 7 2 年发现了多重网格方法的有效性。 在1 9 7 6 年h a c k b u s c h 也独立发现了多重网格算法，并给出了收敛性分析和软件。此 后，多重网格一直受到广大计算数学工作者的关注，出现许多对特定问题，例如对 流扩散问题，n a v i e r s t o k e s 方程的具体技术细节的多重网格算法 2 】川。这个时期在 这个领域活跃的学者有b r a n d t ，h a c k b u c s h ，w s s e l i n g ，d u p o n t ，n i c o l a i d e s ，s n l b e n 等。 八十年代后，多重网格的研究更是如火如荼。几何多重网格方法应用各个领 域。同时，在这个时期代数多重网格法的思想诞生。这种方法克服了几何多重网 格的强几何依赖性。首先是由a b r a n d t ，s m c c o i l i c k 和j r u g e 于1 9 8 2 年在文【j j 和 1 5 1 中提出。s t i l b e n 于1 9 8 3 年在文献嗍中给出了一个较为系统的描述1 9 8 5 年j r u g e 和s t u b e n 发表了文”。1 9 8 6 年在文献中a b r a l l d t 给出了代数多重网格法的理论 背景和一般代数多重网格法的代数理论，同年r u g e 在文口o l 中给出一个模型平面弹 性问题的代数多重网格法计算结果r u g e 和s t u b e n 于1 9 8 7 年在文献【1 2 】中对代数多 重网格法作了一系列的改进，给出了代数多重网格法的基本算法和经典理论。我 国的c h a l l g 首先于1 9 9 2 年在文献【1 4 】中提出在代数多重网格法中引入几何假设，即 矩阵元素的相对大小反映了网格点之间的距离，并且考虑了正的非对角元素的处 理方法利用这样的一种指导思想，c h a n g 改进了代数多重网格法的插值公式，提 高了插值公式的精度。而且还对所得的算法进行了严格的收敛性证明。在文献【1 4 和【1 6 的基础上c h a n g 等人1 9 9 6 年在文献【1 7 】【1 8 】中给出了进一步完善的代数多重 网格算法及其收敛性证明，提高了代数多重网格法的效率，推广了代数多重网格 法的应用范围。该文已成为代数多重网格法的基本文献，其中的算法成为代数多重 网格法的基本算法。 1 9 9 6 年，d e u n h a r d 等 19 提出了一类瀑布型多重网格法。文献【1 9 【2 0 中的数 值试验表明该方法非常有效。瀑布型多重网格法是和有限元结合的一类方法，其 第5 页 潮貉季萼学技零大学研宠生院学位论文 主要特点在于不耍求粗网格校正，故又称单步多重网格法。但也正因为如此，在 细网格上进行迭代时，与粗网格相关的误差变成低频，很难用传统的摩光子减小。 这群，秘溺瀑毒黧多重网疆方法在每层土求释必须达虱鬣缓翊格主豹耪爱，这藏 要在粗网格上进行大量迭代，另方面，瀑布型多重网格法的误差估讨“在能量范 数下保持最优。瀑稚型多重网格法又一个主婴特点是它的简浩性。每层上的迭代 次数霹黻预先确定。般灵蔹簸予，- j 表示簸绥瓣穆瑟数，j 表示当兹隧褡层鼗) ， 而不依赖于空间维数2 3 1 ，所以应用于高维问题更有效。 我国学者石钟熬院士、许学军、谢正辉以及p e n n s y l v a n i a 娴立大学的许进超 先生在多重隧格方法方蟊 亟傲了 鼗多优秀豹王彳乍，参考文激f 3 5 6 0 】【6 6 】。 2 3 几何多骥网格方法 1 多黧黼格方法的基本框架嘲1 2 6 】 先介绍两重网格，考虑在网格q 上离散微分方程得到的线性系统： 。掌狂= ， ( 2 。2 ) 设插假算子眨，限制算子，f ，亏量，= ，一“。 那么两重网格算法粥m + ，q ，锡) 如下： 1 ) 绘定任意的一个初值“，在网格q 上光滑迭代次；h = 伊t ：，) ； 2 ) 计算亏量r 2 = ，a 2 h 2 ； 3 ) 在q “陡裁该亏爨：r “1 = j ；。r 。； 4 ) 在q “上解方程a “+ p “= r “1 得到解8 “； 5 ) 校委纲阙格上的勰：首先把g “1 插值到q 2 上：8 = j 墨1 8 “1 ，然后“。一“+ e 。； 6 ) 再在闲格q 上光滑迭代搿：次：“2 = 妒。，6 ) 。 下面的多重网格算法以递归的形式给出。为了简单起抛，这里主要介绍v 型 多重瓣疆算法掰矿。嵇。，垂。) ： 1 ) 给定任意的一个初值m ：，在网格n 上光滑迭代次：“= 妒4 ( h ：，) ； 第6 页 国防科学技术大学研究生院学位论文 2 ) 如果网格q 是最粗的网格，转到第4 ) 步，否则： ，“1 = 咋1 ( ，。一a 2 “) ； = o ： “= m y “似“，“) ； 3 ) 细网格上解的校正扩= 扩+ 毫； 4 ) 再在网格q 上光滑迭代d 2 次：m 2 = p “z ( “2 ，扩) 。 在上述算法实现过程中，有如下几个方面值得研究的： 1 ) 在细网格上的光滑迭代算子有多种选择方案，有g u a s s s e i d d 迭代，j a c c o b i 迭代，松弛迭代s o r 、s s o r ，共轭梯度法等等。可根据实际情况选择不同 的光滑迭代算子。选择标准关键是看能否把误差的高频分量尽量阻尼在细网 格上，这样误差限制在粗网格上可以高逼近于原问题的解。否则的话，误差 的高频分量在粗网格上不可分辨，进而使得逼近效果很差，算法的收敛性难 以保证。 2 ) 插值算子，皇h 和限制算子j 尹的选择，也是根据实际问题确定的，但是一般插 值算子和限制算子满足一定的关系：，= ( ，盖) + 。二维经典的多重网格方案 中有九点、七点插值算子，相应的也有九点限制算子和七点限制算子吲。插 值限制算子具有越高阶的逼近精度，误差的限制和插值效果就越好，但是增 加了计算量，有时会影响算法收敛的速度。因而尽量选择恰当精度逼近阶的 插值算子和限制算法是比较合适的。 3 ) 粗网格矩阵算子4 2 6 的选择，在经典的二重和多重网格中，有两种选择方法 6 ：一是原问题直接在该粗网格上按细网格上同样的方式( 如二维p o i s s o n 方程离散为五点格式) 离散得到的。二是g a l e r k i n 方法a “= ，墨。本 文是利用尺度空间下逼近原空间的矩阵算子。 2 两种典型的几何多重网格算法6 】【2 6 】 完全多重网格方法( f u l lm u l 衄耐m e t l l o d ) ，简记为f m g 方法。它是m g 方 法与套迭代相结合性能较好的方法。套迭代通过在粗网格上的迭代计算结果为细 第7 页 国防科学技术大学研究生院学位论文 网格上原问题的求解提供较好的初始值。具体算法如下 f b r k = 1s t e p u n t i l md o b e g i n “k = j 乞l “ f b r j 2 1s t 印1u n t i lf t d om g m ( k ，“ ， ) e n d 说明：f 。指在q 2 上的套迭代的次数一般取f 。= 1 ，2 即可达到套迭代所需到达 近似的精度。其一般流程图如下图所示： 初始： 网格层数女= f 套迭代次数 仞始猜测“? 终止： 计算出结果“ ，、 是 、垦 7 。、”“r t f 、7 。j 、 、t o ，一一7 “o 一。o 。 一、鼍i - t 7 7 、7 、 否 否 p 、 校正： e ：= t + l 前光滑 “：= “一p m 1 “= 妒嘞( “：，) l ：= f i 一1 女：= 一1 m ：= 0 后光滑 i ：= ， “2 = 妒“z m ，) ，：= r ( l “1 一，“1 ) 是i ，芝i 、芝：一一7 i 否 图( 2 ，1 ) 完全多重网格算法流程图 第8 页 国防科学技术人学研究生院学位论文 非线性多重网格的f a s 方法( f u ua p p m x i m a t i o ns c h e m e ) 【6 l 【2 叼是针对微分方 程或其边界条件是非线性方程的情形下提出的。假设我们对这些微分方程及其边 界条件进行离散，得到下面一个非线性方程， 4 ) = 厂 ( 2 - 3 ) 其在网格q 上离散得到的非线性系统为： 4 h 。= ，。( 2 4 ) 解这个方程的多重网格算法流程如下： 1 ) 给定任意的一个初值“：，在网格q 。上光滑迭代口，次得到一个近似解“，即 “= 妒( m ：，2 ) ； 2 ) 如果网格q 是最粗的网格，转到第4 ) 步，否则： ，“1 = a “1 ，：+ 1 “+ ，：+ 1 ( ，一a h ) ； “制= 0 ： “2 + 1 = m y 2 “( h 。“，6 + 1 ) ； 3 ) 细网格上解的校正扩= 矿+ ； 4 ) 再在网格q 上光滑迭代次：= 妒。：( “，) 。 上面过程中，最关键的是粗网格上怎么求解亏量方程的问题，般是解下面的亏 量方程 a “1 ( j ：“+ p “1 ) = a “1 j ：+ 1 “+ j ：“( ，一a “) ( 2 5 ) 2 4 代数多重网格方法 求解给定问题( 2 2 ) 的代数多重网格法1 0 j 【1 1 】 12 】分为两大步即配置步( s e t u p p h a s e ) 和求解步( s 0 1 u t i o n p h a s e ) 。配置步的任务是对给定的问题自动构造多重网格 算法的各个分量组元，以便下一步求解使用。求解步的任务就是利用已有的构造 好的多重网格组元选择多重网格循环流程来对给定问题进行求解。 下面详细介绍代数多重网格法配置步的选择的五个组元： 1 多水平粗网格点集q “1 的选取 第9 页 国防科学技术大学研究生院学位论文 3 限制公式j ：“的确定 一般取插值算予的共轭，这样可以保持原问题的正定性。但有时会根据粗网 格选择的特殊性而略作些改变。 4 粗网格算子a “1 的确定 一共有三种方案：一般取g a l e r k i n 算子a “1 = j a 2 砭，这种方案的优点是 可以保持细网格算子原有的一些特性如非奇异性，对称正定性等。缺点在计算该 算子时需耗费多余的计算时间。另外两种方案是我国学者c h a i i g 提出的，见于文献 【1 6 】【1 7 】。 5 光滑算子妒的确定 代数多重网格的光滑算子一般是固定不变的，根据实际情况选定。一般选择 阻尼j a c o b i ，g u a s s s e i d e l 迭代，s o r ，c g 等。 有了上面的几个分量，代数多重网格的算法就可以执行和几何多重网格大体 一样的算法流程了。如：v 一循环，w 一循环，f m g 等。 2 5 瀑布型多重网格方法 下面给出瀑布型多重网格法19 【捌【翻 蛔一般框架。 首先定义能量模| | v | | 2 蚶= 6 。( v ，v ) ，v v k ( = o ，l ，l 1 ) ，再定义网格转移算 子j 厶：s 。，斗屹要求满足下列条件： ( 1 ) l j 厶v l c i v k 。，v v 。 ( 2 ) kl 。“4 。 新的瀑布型多重网格法定义如下： 1 ) 端= = 五。，i ? = j 品。蛀。； 2 ) 在k = 1 ，l l 层上，进行迭代i = 乒? ； 3 ) ：= i ； 在最后一层网格l上， 4 ) “：= j 乙旺，： 5)进行迭代“： 墼堕翌兰篓查奎兰篓鏊兰壁兰燕篷兰 6 ) “：# m ：。 2 。6 多重溺格并行葵法 多重网格方法的主要计算步骤包括光滑迭代( 松弛邀代) 、亏量计算、插值 翻羧铡等，这些步骤嚣篷组织并行诗算。其中，实瑷光澄逡钱、捶擅_ 秘限制运算 都会产生通信要求。如果宜接把最细层网格q 。指派给的二维处理器阵列 上，那么在较粗网格q 1 ，q 2 n 】o g “1 上需蒙通信的处理器是不相邻的，随着网格 戆毯纯，薤毫越袋越太，郡么在著学诗募中，逶信涛袋为激蘩，严重损害了多重 网格算法的快速求解的优良性能。 实际上，一般是把网格q o ，q 1 ，q ”s “1 等映射到超立方处理器网络上，这样 虽然魄较复杂，惫随着霹捂夔交邃，逶信薰瓣热缀缓馒。邋信不霉戒为菠颈，簌 而获得较好的性能。具体操作，一般而言，不能使用g r a y 码把二维网孔q o 直接 嵌入到超立方上。而是将处理器编号为两部分，一部分相应于行，另一部分相应 予烈；然后使臻融y 玛将裙邻戆行帮弼元素获袈羁超立方俸裙邻靛繇点主1 1 5 】澄l 。 如下图所示： 图( 2 2 ) = 维多重网格映射到超立方体上 第1 2 贾 国防科学技术大学研究生院学位论文 ( 4 ) ：。 t e z 1 ， ：。= 1 定理3 3 3 3 1 ( s i | a t ) 设( 匕；m z j ；妒( r ) ) 是一个正交m r a ，则存在 。 f 2 使得下面的双尺度方程 伊( 班= 吼妒( 2 石一七) ( 3 4 ) t 成立，并且，利用( 3 1 ) 得到的尺度函数p ( x ) 构造函数 y ( 石) = g 女伊( 2 x 一) ( 3 5 ) i 的伸缩、平移构成r ( r ) 的正交基，其中g 。= ( 一1 ) 瓦一。进一步地，当 ! = 删n 2 2 ( 2 7 z k ) ；z 时，上一，j o = + 定理3 3 主要包含f 回三方向的内答： ( 1 ) 集合k = 渺0 一女) ；七z l 构成的标准正交基，因此 ， 妒，( x ) = 22 i f ，( 2 7 艽一t ) ；女z l 构成的标准正交基； ( 2 ) k2 。可以保证：r ( r ) 2 曼，因而保证的基向量的并可以表 示r ( 矗) 中的任意函数； ( 3 ) ，上。j ，可以保证在彼此正交的前提下当且仅当地表示信息。 3 3 信号或数据的小波分解与合成( m a l l a t 算法) 设( e i 伊) 为r ( r ) 的一个多尺度分析，y ( f ) 为对应的小波。 1 信号或数据的小波分解 【删吲 给定信号，( f ) r ( r ) ，由于实际中离散采样的原因，总可假定，( f ) 是频限信 号，即存在n 使得 ，= o 彬 ( 3 6 ) 不妨假定，( f ) k ，则有 第1 5 页 鞠防辩学技术大学磷究生院学位论文 下面我们定义：一斗_ 。，从而有= ( 苫 ，而且是正交变换： 形。舻= 孵7 = f ( 3 。1 4 ) 3 5 二维小波变换 t 面讨论的主要是维小波变换内容，对于二维情澎有两种方法。一种是直 接对维多分辨分析做张量积【1 3 3 3 l ；其二是利用投影法【6 7 l 【6 8 1 ，先把小波扩展到高 维，群投影回到二维，这秘方法比较麻颓，实嚣上一般袋蕊嚣一秘方法。下蘑分 绍张攘积方法。 定义2 = 融l ，那么孵 是r 哪2 ) 空间中的一个多分辨分析( m r a ) 。同 释兹，定义孵在吆；中窝曙熏n 囊歪交。嚣梵，有， 吆，= k ，鞫吆。 = 锣；蝤v ；) 毪 ；固v ；、白婶；固w p 臼辑；国w ；) 令w ；= 姆；圆v ；氆姆；w ；鬯 ；w ；) 则有 喉；= 鬈 孵 ( 3 。1 5 ) 漫 h i h ：v 氛屿v ；固v ； g 珏：y k w ；毽v ； h l g y k 崎v ；固w ； g 。g 7 ；吆；峙掣。彤 从而，我们定义2 = 嚣日， 啦黔l i g g 。j 第1 8 茨 国防科学技术人学研究生院学位论文 以及二维变换睇2 = 倍：) ，那么阱2 ：呼_ 曙，。聘，同样地它也是正交变换。 3 6 双正交多分辨分析 前面我们介绍了正交多分辨分析【1 3 】【删 3 3 】下的正交小波变换理论及其构造方 法。正如已经指出过的，除开h a a r 小波外，正交小波下所对应的低通滤波器系数 不满足对称性，或者说不存在线性相位。为了克服这一弊端，借用完全重构滤波 器的思想，用于信号分解和重构的滤波器可以不要求相同，从而得到一种双正交 结构以及双正交小波变换系统。为此，我们先介绍双正交多分辨分析概念与性质。 与正交多分辨分析不同的是，在双正交多分辨分析的框架下，尺度函数驴( f ) 与 小波函数( f ) 关于时间平移参数都不是正交的。当函数妒( f ) 与y ( f ) 作时问平移与 频率伸缩得到妒舭( f ) 与p 肚( f ) 时，双正交要求它们与其对应的对偶函数妒 ( f ) 与 。( f ) 满足下面的正交条件： = j j ，f 坑月， = 占j ，。瓯，。， ( 3 1 6 ) 式( 3 1 6 ) 也称之为双正交条件。 按照双正交条件得到的多分辨分析子空间嵌套序列分为两种： t 2 h lc c c 屹，c t 2c p lc c kc k ， ( 3 1 7 ) 其中，= 印，l 吩，女：七z ) ，= 印口，l ( 妒肚：七z 】此时，设 = 印h ，女：女z l 与= 印口n 址：女z ) ， 则要求下列正交补关系成立： 一j _ ，j _ ， ( 3 1 8 ) 在双正交多分辨分析框架下，尺度函数与小波函数对应的双尺度方程变为 p ( 工) = 。妒( 2 工一女) 矿( x ) = 。p ( 2 工一七) ， 吣) ：受卿m 卅痧( 工) 芝；酬2 “) ， 。1 由于( 3 1 6 ) 表明函数妒( j ) 与y ( z ) ，以及妒( z ) 与( z ) 彼此正交。因此，由完 第1 9 页 一一 潮糖季季学技术犬学研究生瘫学经论文 第四章结合小波的多重网格方法 4 1 小波多分辨分析与多重网格的天然相似性 曾先，考虑一个一般的彝予方程 h = ，( 4 1 ) 熬中l 是个囊伴随静算予，譬如一个线性糖国型静逋赛逮阀题的舆子。令 妒站一妒( 2 x 一) 和卅= y ( 2 x 一) ，那么在最细层的网格矿一上和第个较粗 网格”，“) ，解将分别表示成如下形式： 鞋o ) 一。妒( 2 “1 x 一女) “( z ) = c ，妒( 2 ”蔗一七) + d f ( 2 ”工一七) 女t ( 4 。2 ) ( 4 3 ) 藏数，在最缨瑟翡疆格y “主零篱一个较粮露穆f y * ，* ) 主将分蘩表示残 对应的“，和g ? 。那么绷网格上的问题通过g a l e r l c i n 内积化方法3 4 1 有如下 的形式： e p 鲈+ l 女 = “，w ( 4 4 ) 同样在较粗网格( 矿”，”) 上有 妒跚，瓢聿矗夕 - 彤，磁 ( 4 5 ) 和 至：c + d f = g ? ，影 ( 4 。6 ) 式( 4 - 5 ) 给出的怒粗网格上低颇分量的解的问题，而式( 4 6 ) 给出的怒粗网格上 高频分量的解的问题。由上面两个方程得知：尺度函数硝张成的空间就是插值 算予j 鬈“弱篷空阙，嚣，l 、渡函数矿粥张或限潮算子f 是，静零空闻。在多分辨形式 下，细网格矿“写成： 第2 1 硬 鞠茨科学鼓术大学弱窕生院学纯论文 p ”= 置p 杆h 妒， o 点p d n 0 l = y o w 7 ( 4 7 ) 丽在多重网格形式下，有【2 翱 矿“1 一妒酬 e 妒娃托 矿l - 熘捧g e f o 触f 琏烨扰 唆1 在经媳的多重网格方法中一般只求解代表解的低频部分( 4 5 ) 式的第一项，因为 ( 4 ，5 ) 式的第二磺通常接近予潜嚣被忽略撩。由 产生的系数矩阵 即是多重网格中糨潮格矩阵算子。 4 。2 正交多分辨分析与多重网格的结合 由上面的分析，我们很自然地就得到了下面简单的基于小波的多重网格算法， 其算法步骤2 ”如下： 选定一今小演系绫，对m = n + l ，n 0 递捺遴行： 1 ) 尺度空间作为粗网格层一。； 2 ) 上用选定的遮代法对方稷瓦“。= 厶逃彳亍光滑迭代，前后光滑次数分别为 苁，2 ； 3 ) 以一维小波低通滤波算子h 作为从细网格到粗网格转换得限制算予，对亏量 进行限割：五。= 嚣( 东一互。扭。) ； 4 ) 通过二维小波低通滤波算予祷到粗网格葬子：+ 。= h _ 抒； 5 ) 以维小波低通滤波算子的共轭算子作为粮网格到细网格转换的插慎算予，将 疑嗣捂上褥爨熬误差播镶蘩缨礴掺攫，著曼送行褪霹格较歪，帮： “= m + 日m i 。 由于小波理论自身完整的体系，一旦小波系统选定，糊网格层和转换算子的 生残帮莛蠡动懿，掰骧这耱方法又可戮称之为黑枣子整蒺繁法箨“。秘下闺潺示 第2 2 炎 黼转辩学技术大学错究生陵学绽论文 豳( 4 1 ) 黑匣子小波多重网格框图 4 。3 小波交换与多重瓣格的结合 在式子( 4 5 ) 中，如果第二项d 的德较大时，不能忽略。那 么上筒的算法可能失效。下面考虑小波变换写多重网格方法的结合口孵。 1 一维情况 考虑尺度j 上熬线牲方程： t u = f( 4 9 ) 其中，五，表示一维微分方程在对应的网格上离散得到的矩阵。对方程两边应用小 波交援，有魏下等式： ( 雌t ) 坼u = f ( 4 1 0 ) 定义己= 嚣t 啄8 一( ，黠荬送行v 封l 分鳃，有： 己= ( ：丑罗一 ( i 一曰f 嚣； 。i 乞j 那么， 哥= ( 坼工，雌+ ) ：巧- 睇+ 由( 4 + 9 ) 式我织褥翘秽= 写f ，麸嚣 u ：雌掣坼7 町f ：t ，睇， 刁 ( 4 1 1 ) ( 4 1 2 ) ( 4 1 3 ) 第2 3 受 结合( 6 ) 、( 7 ) 和( 8 ) 式，我们得到 呻h 掣譬鹫r 粤。背一随m 从而自然地，定义插值算子 i = 叫2 嶝：一q 掣b ：、 和限制算子 j ，= 击( ，厶) 那么( 4 9 ) 式可写为： 玎= f 二；( 弓一或廖j 1 蟛) 。z ；。，+ d ；1 嘭芦 ( 4 1 5 ) 在多熏网格中，我们解的一般鼹亏量方程，则有： # = ! 三；( 弓一露j p i l 琴) - 1 j ；。r + 霹d ，q r ( 4 。1 6 ) 其中，r 是亏量，假设嘭巧1 q rj 常小，换茅中说法说r 纂本上在空间最口n 秽( 日j ) 中，那么方程( 1 1 ) 近似变成如下的： e 。f 主；弓一鬈p 譬。j ；。， ( 4 1 7 因而，就有 ( i 一嚣，d 一曰；) f ，一，= j ；_ 1 0 ( 4 1 8 ) 叁然鸯孽，褪两稽上瓣矩阵算予为： 川= t 一口，巧1 霹 ( 4 1 9 ) 2 。黧继情况 相似建，二维构造同样地可以得舞j 刍、f j 。帮，髓稍有不同的楚由于： t = 雌。，晖= 芑3 ，从而 j 知= 压( 珂；一巧1 c ，) ， 妒1 = 等哆霹q ) l ；“= t i b i d ? c 。 ( 4 2 0 ) ( 4 1 2 1 ) ( 4 2 2 ) 第2 4 贾 国防科学技术大学研究生院学位论文 ( 4 2 0 ) 、( 4 2 1 ) 、( 4 2 2 ) 式中的三个算子即可分别作为多重网格的插值算子、 限制算子和粗网格矩阵算予。有了上面三个算子，套用经典多重网格算法流程即 可得到如下v 型一小波多重网格算法： 1 ) 给定任意的一个初值“：，在网格q 7 上光滑迭代口。次：“= 妒1 ( “；，) ， 2 ) 计算亏量r ，= - 厂，一f “， 3 ) 在q 。限制该亏量：r = j r ， 4 ) 在q 一上嵌套用m g m 解方程 工j 。14p 川= r 得到解e 川， 5 ) 校正细网格上的解：首先把p 插值到q ，上：e7 = j l e 1 ，然后“7 = “7 + p ， 6 ) 再在网格q 上光滑迭代口2 次：h7 = 妒。2 ( “7 ，7 ) 。 在上面的算法中牵系到小块矩阵求逆的问题即d ，。1 的求解，这是一个很困难的问 题，需要用到最近发展较快的多水平方法( i l u ) 【2 9 】，而且还要进行合理的截断。 本文在于介绍这种方法，就不再展开讨论。详细讨论请参考文献【2 8 。 4 4 双正交小波与多重网格的结合 1 插值限制的双正交小波多重网格方法 在文献3 1 1 中，作者指出滤波器乙= ， ：， 。) 生成的多重网格方法求解病 态t o e p t z 系统的插值算子为 限制算子为 p = 矗l 2 3 _ i l f 1 2 3 l 2 。 ：如k l 2也 m 文献还指出高阶的消失矩的双正交小波对于高阶病态的t o e p | i t z 系统能有效 第2 5 页 国防科学技术大学研究生院学位论文 工r 矿+ o 1 2 0 o l 2 矿+ 9 2 l 。 0 l a 2 矿+ q 3 o 0 o 1 2 12 一矿矿+ 9 2 ) 对于下面的两点边值问题： l “= 一芸c p 罢，+ r 罢+ 叫= ， 1 。 此外，对于二维的问题，三。随着未知解“。的网格节点的排列顺序不同而有 不同的表达形式。网格节点的排列顺序一般有下面五种方式嗍 3 4 】 j j 1r 1， ， 1r 1 3 1 41 51 6 一 一一 j 哥 r1r1 rr 1 01 11 2 j j r ，1r 5 67 8 一jj 1 ， 2 ，3 ， 于 r ( i ) x 方向，即“。= ( “引。，“。，“。，“引：，“。，。：，“。) 4 r 8 rr ， 1 2 1 6 jjjj 3 ， 一1r ， 1 手 ， 1 1 一 2 ，1， 1 净 ， r 6 1 4 j l r 5 1 r， l ， r 1 9 ( i i ) y 方向，即“。= 0 引。，h 引：叫引m 础，卅即叫h 跏。) 第3 1 页 国防科学技术大学研究生院学位论文 ( i i i ) ( i v ) ( v ) j一 l5 1 ，7， 1 6 一 ， 8 r jj 一 一 ， 1 3 ，6 ，1 4 r j一一j l l ，3 ， 1 2 ， 4 r 一一j一 1 ， 9 1， 2 ， 1 一 ， 红黑顺序，“。= - 引。，“引，“蜘。，“引：，“刖旷，“脚。一。) 一 1 ， 1 2 ， 8 7 l 一 ， jj一 3 1r ， l 一 ， 1 17 jj ，r， 21 0 6 1 4 jj 1 ， 9 ， 5 1 ， 1 一 ， 斑马顺序“。= 0 朋。，“蛐。，“跏“引，“帅，“跏。) j j 一 l ， 一1， 1 6 ， 8 ， 一一 1， 1， 4 ， 1 2 ， 3 1 1 l jj一、 1， 5 ， 1 4 一 ， 6 ， 1 3 一一j 1 ， 一 ， r， 2l o 四色顺序“。= 0 列，“引，“刖。，“耶，“肌。一。) 第3 2 页 国防科学技术大学研究生院学位论文 其中第一类、第二类又分别称为字典顺序和旋转字典顺序。下面给出第一种 情形y 方向网格排列进行讨论硐： 对方程 j 一“硝一“ i “( x ，) ，) h + 硎= ，( x ，y ) ，o j 1 ，o ) t 1 = o ， x = o ，x = 1 ，y = 0 ，y = 1 其中口( x ，) ，) o ，在单位区域q 上采用五点格式差分则得如下的线性方程 其中 和 则 a = 工x 。 m 。= ( “1 1 ，m 。2 ，“f f ) 1 ， 1 矗l 2 ( 5 2 0 ) 为一块三对角矩阵。 一般而言，网格节点不同的排列次序适合不同类型的差分格式以及迭代方式。 第3 3 页 厶厶；k 叱； k ， 、 一 0 一 如 盯十 上砰三碍 一 + ：一砰 盯+ 上砰三酵土印 一 + 一 ：一砰 盯 土砰：矿上砰 一 + 一 2 一砰 盯+ 三磅上砰 + 一 2 一砰 r o 山 4 o m0 国防科学技术人学研究生院学位论文 例如：字典顺序和旋转字典顺序适合逐点的g a u s s s e i d e l 迭代，红黑顺序适合五 点差分格式及其g a u s s s e i d c l 迭代，四色顺序适合九点差分格式及其g a u s s s e i d e l 迭代。 3 有限元离散法 有限元方法嘲【3 铂是从等价的区域上的变分形式出发，近似地求解微分方程边 值问题的计算方法，实质上是经典r i t z g a l e 蹦n 法的推广，即提供了一种选取“局 部基函数”或“分片多项式”的新技巧，克服了经典r 池一g a l e r k i n 法选取基函数 的固有困难。有限元法在结构力学、固体力学、流体力学等工程科学方面得到成 功的应用，它和差分法一样，成为求解偏微分方程，特别是线性椭圆型偏微分方 程的有效方法。有限元离散的基本步骤如下： 1 ) 把问题转化为变分形式； 2 ) 选定单元的形状，对求解区域作剖分( 一维情形的单元是小区间。二维情形的重 要单元有两种：三角形和凸四边形。三维单元就更加复杂多样了) ； 3 ) 构造基函数或单位圆形状函数，形成有限元空间； 4 ) 形成有限元方程l 。h = ，。 结合有限元离散法的多重网格算法具有更简便的方法生成限制和插值算子。 例如：有限元空间的投影算子直接可以作为限制算子，插值算子直接取为单位矩 阵就可以获得很好的效果。不需要构造复杂的插值与限制算子。有限元空间选择 的灵活性，使得与多重网格法的结合更为具有活力。第二章介绍的一类新型的无 需粗网格校正的瀑布型多重网格算法就是与有限元离散法结合的优效算法。 5 2 光滑迭代 理论上，经典的迭代方法均可以用来做前后光滑迭代旧【翊，但实际上要根据 具体问题选择适当的迭代方法。下面介绍几种基本的迭代方法。 1 几种常用的经典迭代 ( 1 ) g a u s s s i d e l 迭代 g a u s s s i d e l 迭代