（计算数学专业论文）基于小波与多重网格法求解偏微分方程.pdf

摘要 小波分析作为一门新型的应用数学分支，系统地研究开始于2 0 世纪8 0 年代 初期。从数学的角度看，小波分析是在f o u r i e r 分析的基础上发展起来的数学分 支，是f o u r i e r 分析、泛函分析、数值分析的完美结晶。从信息科学的角度看，小 波分析是时频分析、多尺度分析的进一步发展，已经成为信号分析和信号处理 的新的强有力的工具。同时，在微分方程的数值解问题中，小波同样受到了相 当大的关注。 而多重网格法已被广泛应用于各门学科和各种工程技术问题中，并且已从 理论上证明多重网格法对于椭圆型问题是一种理想的数值方法，其计算工作量 仅仅与网格节点数的一次方成正比，并且收敛速度与网格的尺度无关，从而特 别适合于应用在超大型工程数值计算中。多重网格法中粗细网格之间的延拓和 限制算子起了非常重要的作用，而常用的算子是线性插值算子与加权限制算 子。 b r i g g s 和h e n s o n 首先提出了多重网格法与小波的多分辨分析形式上的相似 之处，他们认为多分辨分析中的尺度空间序y u v j b z 与多重网格法中的粗细网 格剖分q i 对应。 本论文根据这个特点，利用离散小波变换构造多重网格法中的限制算子和 延拓算子，来代替传统的插值和加权算子，并应用于多重网格法中求解椭圆型 偏微分方程。发现与传统多重网格法相比，小波多重网格法的数值结果能够达 到更小的误差。并且从数值例子中发现在传统的多重网格法中循环7 - 8 次得到的 的结果与小波多重网格法循环1 次得到结果相近，因此，小波多重网格法必然会 加快收敛速度并减少计算时间。 关键词：多重网格法，多分辨分析，离散小波变换 a b s t r a c t w a v e l e ta n a l y s i sa s s u m e ds i g n i f i c a n c ea san e wb r a n c hi na p p l i c a t i o nm a t h e m a t i c sd u r i n gt h e1 9 8 0 s i t sr e c o g n i z e da sap o w e r f u ln e wm a t h e m a t i c a lt o o l i ns i g n a la n di m a g ep r o c e s s i n g ，t i m e s e r i e sa n a l y s i s ，g e o p h y s i c sa n da p p r o x i m a t i o n t h e o r y , e t c t h el a s tf e wy e a r sh a v ew i t n e s s e da ni n t e n s ea c t i v i t ya n di n t e r e s ti nt h e a p p l i c a t i o no fw a v e l e tt h e o r ya n di t sa s s o c i a t e dm u l t i r e s o l u t i o na n a l y s i s a n o t h e r a r e ai nw h i c hw a v e l e t sa r eg a i n i n gi m p o r t a n c ei st h en u m e r i c a la n a l y s i so fo r d p n a r ya n dp 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 m u l t i g r i dm e t h o dh a sb e e nw i d e l yu s e di nm a n yk i n d so fp r o b l e m so fe n - g i n e e r i n g i t sw e l lk n o w nt h a tm u l t i g r i dm e t h o di sa m o n gt h ef a s t e s ts o l u t i o n m e t h o d s ，e s p e c i a l l yf o re l l i p t i ce q u a t i o n s t h e yh a v eb e e np r o v e dt ob eh i g h l ye f - f i c i e n t ，i t sw o r k l o a do fc o m p u t i n gi sd i r e c tr a t i ot ot h en u m b e ro fn e tn o d e sa n d t h es p e e dc o n v e r g e n c ei si n d e p e n d e n to ft h es i z ei nt h en e t t h ei n t e r g r i do p e r - a t o r so fi n t e r p o l a t i o na n dr e s t r i c t i o np l a ya ni m p o r t a n tr o l ei nt h en u m e r i c a l s o l u t i o no 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 su s i n gt h em u l t i g r i dm e t h o d 。t h ec o r n - m o n l yu s e di n t e r g r i do p e r a t o r sa r et h el i n e a ri n t e r p o l a t i o na n dt h ef u l lw e i g h i n g r e s t r i c t i o n t h es i m i l a r i t i e sb e t w e e nt h em u l t i g r i dm e t h o da n dw a v e l e t sa r i s i n gf r o m m u l t i r e s o l u t i o na n a l y s i sw e r ef i r s tb r o u g h to u tb yb r i g g sa n dh e n s o n t h e yo b - s e r v e dt h a tt h es p a c eo fh i g h e s tr e s o l u t i o ni nm u l t i r e s o l u t i o nc a nb ec o r r e l a t e d t ot h es p a c eo ff i n eg r i dv e c t o r si nt h em u l t i g r i ds c h e m e i nt h i sp a p e rw ee m p l o y e dw a v e l e tb a s e di n t e r p o l a t i o na n dr e s t r i c t i o no p - e r a t o r si np l a c eo ft r a d i t i o n a li n t e r g r i do p e r a t o r so fi n t e r p o l a t i o na n dr e s t r i c t i o n t os o l v ee l l i p t i cb o u n d a r yv a l u ep r o b l e m s c o m p a r e dt ot h ec l a s s i c a lm u l t i g r i d m e t h o d ，t h i sa p p r o a c hm i n i m i z e se r r o r ，r e q u i r e ss h o r t e rc o m p u t a t i o nt i m e i ti s f o u n dt h a tj u s to n ec y c l ei se n o u g hf o rt h ec o n v e r g e n c eo fw a v e l e t m u l t i g r i d s c h e m ew h e r e a sn o r m a l l y7 - 8 c y c l e sa r er e q u i r e di nc l a s s i c a lm u l t i g r i ds c h e m e st o m e e tt h es a m ea c c u r a c y n u m e r i c a le x a m p l e ss h o wt h a t ，t h es c h e m eo f f e r saf a s t a n dr o b u s tt e c h n i q u ef o re l l i p t i cp d e s a b s t r a c t 1 1 1 k e y w o r d s ：m u l t i g r i dm e t h o d ，m u l t i r e s o l u t i o na n a l y s i s ，d i s c r e t ew a v e l e tt r a n s f o r m 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝垄态堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位敝作者签名：列锄 签字嗍 p8 年易月彩日 学位论文版权使用授权书 本学位论文作者完全了解逝江盘堂有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝望盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：主似 签字日期：训肛6 月旷日 翩虢心弋 签字日期：2 肌坶年。月沥 致谢 这次毕业论文能够得以顺利完成，是指导我的导师，帮助过我的 同学，一直支持着我的家人对我的教诲、帮助和鼓励的结果。我要在 这里对他们表示深深的谢意! 首先要特别感谢我的导师韩丹夫教授。韩老师在我毕业论文 的撰写过程中，给我提供了极大的帮助和指导。从开始选题到中期修 正，再到最终定稿，韩老师给我提供了许多宝贵建议。韩老师一丝不 苟的作风，严谨求实的态度，踏踏实实的精神，不仅授我以文，而且 教我做人，虽历时二载，却给以终生受益无穷之道。对韩老师的感激 之情是无法用言语表达的。 我还要感谢和我一起学习的同学张宋宋和陈纪文，感谢他们对我 的帮助和提供的资料。尤其要感谢我的同学张宋宋，没有她无私的帮 助，我无法如此顺利地完成我的毕业论文。同时我也感谢我的师兄师 姐们对我的指导。 最后我要感谢一直支持我的父母和亲友。 第一章引言 多重网格法是流体问题中一种快速收敛到稳定状态的计算方法，而且已能 成功的解决椭圆方程的数值问题。该方法是前苏联计算数学家f e d o r e n k o 1 在 1 9 6 1 年首先提出的，他在方形区域用标准五点有限差分离散化p o i s s o n 方程时提 出了多重网格法。而且多重网格法最早的实际运用结果也出现在b r a n d t 早期的 文章中。h a c h b u s h 2 也独立的发现多重网格法，并且建立了坚固的数学基础和 提供了可靠的多重网格法的运算方案。此后，根据不同的延拓和限制算子衍生 出多种解偏微分方程的多重网格算法。 多重网格法的优势在于它能够同时减少高频与低频误差。经典迭代算法本 质上仅起到光滑作用，能很快地消去残量中的高频部分，但对低频的部分的效果 不是很好，而高频与低频是相对的，细网格上的低频误差可以看做是粗网格上 的高频误差。多重网格法能够在一套粗、细网格中同时消去残量中的高频和低 频部分。 小波分析在2 0 世纪8 0 年代被成功的运用到信号和图像处理中，是目前国际 上公认的时频分析工具。从一个函数平移和伸缩得到光滑的标准正交基，对信 号和图像的压缩非常有用。在h a r t 提出的小波标准正交基后，小波理论才有了 现如今的发展。d a u b e c h i e s 的小波正交组是从m a l l a t 4 】和m e y e r 5 1 的多尺度分 析发展起来的，d a u b e c h i e s d 、波 7 1 构造了l 2 ( r ) 的标准正交基，l 2 ( 冗) 是实数域 上的平方可积函数空间。l 2 ( r ) 的标准正交基可以构造所有n = 2 的多项式，这 里n 是尺度函数的滤波系数。 当前，利用小波的这些特征，在时间序列分析，图像处理，近似理论，密集 矩阵预处理这些领域的研究都有了新的突破，在这些领域的研究中，小波被认 为是一种强有力的工具。此外，在微分方程的数值解问题中，小波同样受到了 相当大的关注 8 1 。b r i g g s 9 1 和h e n s o n 1 0 首先提出了多重网格法与小波的多尺 度分析相似之处，他们认为多尺度分析中的最高分解能与网格划分中的最细网 格空间互相联系起来【1 1 1 ，由此可以利用小波变换构造粗细网格间的延拓与限 制算子。 本文在后面的第二章中介绍了小波分析及多分辨分析的基础知识；在第三 章中介绍了多重网格法的基本原理与算法，在第四章中给出了把小波应用于多 第一章引言 2 重网格法的具体算法，及用小波多重网格法求解椭圆型偏微分方程的具体实例 与计算结果。 第二章小波分析理论基础 2 1 从傅立叶分析到小波分析 傅立叶变换是众多科学领域( 特别是信号处理，图像处理，量子物理等) 里 的重要应用工具之一，使用傅立叶分析时，通常指傅立叶变换和傅立叶级数。函 数，( t ) l 1 ( r ) 的连续傅立叶变换定义为： f ( u ) = e - 如。f ( t ) d t f ) 的傅立叶逆变换定义为： m ) = 去e 删甜 在实际计算机应用中，由于时域和频域应该是离散的，所以使用离散的傅 立叶变换，简称( d f t ) 。给定实的或复的离散时间序列如， ，a 一1 ，设该序 列绝对可积，即满足 州 o o ， n = o 称 x ( 七) = f ( 厶) = a e j 丁2 1 r k ”, ， k = o 为序列厶的离散傅立叶变换，称 厶= 丙1 x = ( 七) 警， k = o 为序列x ( 后) 的离散傅立叶逆变换。 虽然傅立叶变换能够将信号的时域特征和频域特征联系起来，能够分别从 信号的时域和频域观察，但不能把二者有机的结合起来。这是因为信号的时域 波形中不包括任何频域信息，而其傅立叶谱是信号的统计特性，从其表达式中 也可以看出，它是整个时间域内的积分，没有局部化分析信号的功能。这样在 第二章小波分析理论基础 4 信号分析中就面临一对最基本的矛盾一一时域和频域的局部化的矛盾，因而这 就促使人们去寻找一种新的方法，能将时域和频域结合起来描述观察信号的时 频联合特征，构成信号的时频谱，这就是所谓的时频分析法，亦称时频局部化方 法。 小波分析方法是一种窗口大小( 即窗口面积) 固定但其形状可以改变，时 间窗和频率窗都可以改变的时频局部化分析方法 1 0 】，即在低频部分具有较高 的频率分辨率和较低的时间分辨率，在高频部分具有较高的时间分辨率和较低 的频率分辨率。正是由于这种特性，使小波变换具有对信号的自适应性。原则 上讲，传统使用傅立叶分析的地方，都可以用小波分析取代。小波分析优于傅 立叶变换的地方是，它在时域和频域同时具有良好的局部化性质。 设妒( z ) l 2 ( 兄) ，其傅立叶变换为移 ) 。当移0 ) 满足允许条件：q = 厶警掣幽 0 0 时，我们称矽( ) 是一个基本小波或母小波，将母函数矽( ) 经过伸 缩和平移后，就可以得到一个小波序列。对于连续的情况，小波序列为 1 十一，l 妒。，b ( t ) = 寺彳妒( 二_ - ) ，n ，b 兄；口0 、i a i u 其中a 为伸缩因子，6 为平移因子。 对于离散的情况，小波序列为： 奶，七( ) = 2 - j 2 砂( 2 一j t 一七) ，j ，k z 对于任意函数，( t ) l 2 ( 兄) 的连续小波变换为： 晰( n ，6 ) ： ：h 叫2 ! 弛) 矽( _ t - b ) 疵 这里砂+ ( t ) 表示矽( ) 的复共轭。 其逆变换为： 弛) = 击上z 去噼 6 ) 砂( 字胁如 小波分析是傅立叶分析思想方法的发展和延拓，它自产生以来，就一直与 傅立叶分析密切相关，它的存在性证明，小波基的构造以及结果分析都依赖于 傅立叶分析，二者是相辅相成的。 第二章小波分析理论基础5 两者相比主要有以下不同点： ( 1 ) 傅立叶变换的实质是把能量的有限信号厂( ) 分解到以1 【“) 为正交 基的空间上去；而小波变换的实质是把能量的有限信号厂( ) 分解到肌f ( 歹= 1 ，2 ，l ，) 和v _ 3 ( 歹= 1 ，2 ，t ，) 所构成的空间上去。 ( 2 ) 傅立叶变换用到的基本函数只有s i n ( w t ) ，c o s ) ，e x p ( j w t ) ，具有唯一性； 小波分析用到的函数( 即小波函数) 则不具有唯一性，小波函数的选用是小波 分析应用到实际中的一个难点问题( 也是小波分析研究的一个热点问题) ，目前 往往是通过经验或不断的试验来选择小波函数。 ( 3 ) 傅立叶变换在频域内有较好的局部化能力，但在时域内，傅立叶变换 则没有局部化的能力。 ( 4 ) 在小波分析中，尺度a 的值越大相当于傅立叶变换中的u 的值越小。 2 2离散小波变换 实际应用中，连续的小波变换必须离散化，需要强调的是，这一离散化过程 是针对连续的尺度参数a 和连续平移参数b 的，而不是针对时间变量t 的 1 1 】。为 了方便起见，在离散化的过程中，总限制。取正值，相应的相容条件就变为： q = o 。铧幽 通常，把连续小波变换中尺度参数a 和平移参数b 的离散化公式分别取作a = 晶，b = k a j o b o 这里j z ，扩展步长a o 1 是固定值。所以对应的离散小波函 数奶，鬼( t ) 即可以记作： 2 j , k ( t ) ：。矽( 掣) ：。o i l 2 砂( n 孔一k b 。) 而离散化的小波变换系数则可以表示为： 0 ，蠡= 邢) 螃七( ) 班= 其重构公式为： 雕) = q ，膏略，七( t ) j = - o ok = - o o 是与信号无关的常数。 第二章小波分析理论基础 6 2 3多分辨分析和s m a l l a t 算法 m e y e r 于1 9 8 6 年创造性的构造出了具有一定衰减性的光滑函数，二进制伸缩 与平移构成口( 兄) 的规范正交基，使小波分析得到了真正发展。1 9 8 8 年s m a l l a t 在 构造正交小波基时提出了多分辨分析的概念，从空间的概念上形象地说明了小 波的多分辨特性，将此之前的所有的正交小波基的构造法统一起来，给出了正 交小波的构造方法以及正交小波变换的快速算法，i l p m a l l a t 算法。m a l l a t 算法在 小波分析中的地位相当于快速傅立叶变换算法在经典傅立叶分析中的地位。 空间l 2 ( r ) 中的多分辨分析是指l 2 ( r ) 中满足如下条件的一个空间序 列 k ) j z ； ( 1 ) 单调性：巧c 屿+ 1 对于任意的) i z ( 2 ) 逼近性：n zk = o ) ，u j zy j = l 2 ( 冗f ( 3 ) 伸缩性：( t ) y j 兮f ( 2 t ) 巧+ l 伸缩性体现了尺度的变化，逼近正交 小波函数的变化和空间的变化具有一致性。 ( 4 ) 平移不变性：对于任意的k z ，s ( t ) v o 兮( t k ) v o ( 5 ) r i e s z 基存在性：存在妒( t ) y o ，使得_ 妒( t k ) l k z ) 构成的r i e s z 基。 对于条件( 5 ) ，可以证明，存在函数妒( ) v o 使它的整数平移系 妒( 亡一k ) l k z ) 构成巧的正交基，我们称妒( t ) 为尺度函数。并称妒( ) 生 成l 2 ( 兄) 的一个多分辨分析 y j b z 。 定义函数： 仍，知( t ) = 2 2 妒( 2 t k ) j ，k z 则函数系 k ( t ) l j ，k z ) 是规范正交的。 设以巧表示信号分解中的低频部分，表示分解中的高频部分，则w j 是b 在 k + l 中的正交补，即 kow j = y j + l ，j z 显然 ow je + lo o + 优= y j + m 则多分辨分析中的子空间可以用有限个子空间来逼近，即有 v o = 肼= e o = = v no 一1o ow 2ow 1 ( 宰) 第二章小波分析理论基础 7 空间列 j ，k z 是l 2 ( r ) ( r ) 中的标准正交 基，u p , j , 波正交基。 综合以上分析，我们可以归纳出为了使，七( ) = 2 - j 2 妒( 2 一j t 一后) 构成k 子 空间的正交基，生成元妒( ) ( 尺度函数) 应该具有以下基本性质： ( 1 ) 尺度函数的容许条件：巴妒( ) 出= 1 ( 2 ) 能量归一化条件：i i 垆( t ) l l ；= 1 ( 3 ) 尺度函数妒( t ) 具有正交性 ( 4 ) 尺度函数妒( t ) 与小波函数矽( t ) 正交，即 ( 妒( ) ，妒( ) ) = 0 ( 5 ) 跨尺度的尺度函数妒( 亡) 与垆( 2 ) 相关，满足尺度函数双尺度方程。 ( 6 ) 基小波函数砂( ) 与矽( 2 ) 相关，满足小波函数双尺度方程。 除此以外，还要求尺度函数妒( t ) 是冗上的实值函数，并且是r 次可微的，其导 数连续，具有足够的下降速度，i l p 妒( t ) 满足： i 妒( 七) ( ) i c 缸( 1 + i t l ) pk = 0 ，1 ，2 ，r ；p z ；t r 1 3 】 第三章多重网格法 在用简单的迭代方法如j a c o b i 迭代方法等求解由微分方程定解问题导出的 代数方程组时，一般需要多次的迭代才可能获得理想的近似值，而且迭代步数 将随着网格步长的减小而增大。而多重网格法( m u l t i g r i dm e t h o d ) 简称m g 方 法是收敛速度基本不随着离散的精细化而改变的迭代法 1 4 。近年来，多重网格 法已成为求解大规模科学工程计算问题最有效的方法之一，该法是由前苏联计 算数学家f e d o r e n k 在1 9 6 1 年基于差分法提出的，当时并没有引起很大的注意。 直n 2 0 世纪7 0 年代中期，多重网格法才受到普遍的重视，被认为是一种行之有 效的数值分析方法，这很大程度上要归功于欧美计算数学家的努力，他们在实 际计算中首先发现了多重网格法完全优于其它的迭代法。2 0 世纪8 0 年代以后， 世界各国的计算数学家在这方面投入了大量的人力、物力，使得这一方法在理 论研究中取得了很多重要成果，并在实际应用中也显示了强大的生命力。 3 1 多重网格法的思想 考虑一维d e r i c h l e t 边值问题 l u ：= 一u ，( z ) = ，( z ) ，x q = z i z l z z 冗) ， u ( x l ) = x ( u n ) = 0 ( 3 1 ) ( 3 2 ) 如果将q 剖分成m + 1 等分，内网格节点记为z ，= x l + j h ，j = 1 ，2 ，m ，h = 1 ( m + 1 ) 是网格步长，则离散方程( 3 1 ) 的最简单的差分格式是 h ：= 一兰生三二弓学= 厶，j c f = ，( 巧) ( 3 3 ) 将边界条件( 3 2 ) 和格式( 3 3 ) 联立，可以得到相应的离散边值问题 l ，l 吻：= 一兰生! 二学= 办， ( 3 4 ) u 02u m + 1 = 0( 3 5 ) 或者 a u = b ( 3 6 ) 第三章多重网格法 1 0 其中 1 a = 磊 凡 21 121 1 21 12 牡= u l ，u 2 ，u m 】t ，b = 盼，尼，知】丁 类似地，我们司以用简单迭代法求解上述线性方程组。为了方便起见，这 里以阻尼j a c o b i 迭代方法为例，迭代公式可以写为 妒1 j ：等力+ 1 ) u v 。+ 掣1 ) ， 钆尹+ 1 】= u 面r + 1 】+ ( 1 一u ) u i v 】， ( 3 7 ) 其中乱= 仳盟+ 。= o ，u 是松弛因子，当u = 1 时，上式就是通常的j a c o b i 迭 代方法。如果用u 表示线性方程组( 3 6 ) 的精确解，则迭代误差e l 】= u - u p + 1 满 足齐次线性方程组 e 1 1 = g ，洲， 其中g ，是阻尼j a c o b i 迭代方法( 3 6 ) 的迭代矩阵 和 g j ，= 1 一u 等 等 1 一u 詈 w 2 1 一u 詈 学 1 一u 易知，迭代矩阵g ，的m 个特征值以及相应的m 个特征向量是 a 七( g j ，) = 1 - - 2 ws i n 2 ( t k h l r ) ，1 七m ( 3 8 ) = s i n ( k h a ) ，s i n ( 2 k h 7 i - ) ，s i n ( m k h r c ) r ，1 k m ( 3 9 ) 第三章多重网格法 显然，波数k 影响着特征向量的频率k 越大，特征向量的频率越高。由于m 个 线性无关的特征向量 v k 形成了m 维线性空间的一组基，所以初始误差e 【o 】可以 写成他们的线性组合，即 m e 【o 】= fq 七v k - _ _ 一 七= l 由迭代方程3 8 得 m e 忡】= fo l 七+ 1 ( g j 咖奄 七= 1 这说明迭代矩阵g j ，的特征向量可以用来表示误差分量，而对应的特 征值则表示误差分量的增长系数。从特征值扎( g j ，) 的表达式可以知道，仅 当0 u 1 时，才能保证p g l ， 1 ，即只有当0 u 1 时，阻尼j a c o b i 迭代方 法3 6 才收敛。 通常将误差分量讥，j = s i n ( 也m ) 分成两组：低频误差分量( 如果0 k h j 或1 k 虿m ) 和高频误差分量( 如果； h 。，来消除误差分量，即一旦迭代方法 在细网格q h 。上的收敛速度减慢( 表明误差已经光滑) ，则将问题转移( 投影或 限制) 到较粗的网格q 。一，上消除掉在其上属于高频的那些误差分量，这样一层 层地做下去直到将各种误差分量消去，以便达到迅速衰减细网格上的低频误差 分量的目的，最后还需要将求解问题一层层的返回( 插值或延拓) 直到最初的 细网格q 。上。这就是多重网格法的基本思想。 3 2 双重网格方法 针对模型问题3 1 和3 2 介绍最简单的多重网格算法一双重网格方法 1 5 】。假 设，对区域q 引进两套网格：细网格q 。= 巧i 巧= j h l ，j = 1 ，2 ，舰) 和 笙三童垒重塑堑鲨1 2 一一 粗网格q 。= x j x j = j h 2 ，j = 1 ，2 ，舰) ，其中蝇是奇数，m 2 ：( 舰一 1 ) 2 即h 2 = 2 h l 。这样，解问题的双重网格方法可以描述为： ( i ) 在细网格q 。上用迭代方法求解离散问题 毖一_ i ：= j - - - - f h l , j ，坯径巩( 3 1 0 ) 【u h l ，02u h l ，m i + i20 7 设迭代了均步，对应的近似解记为，j ：= 让如，并计算相应的残量 r h l ，歹= 1 j l h l v h l j ，1 j m 1 则吮步迭代的近似解逼近差分解的误差e 。，加j = 乱h 。，j u h 。，j 满足 jl ，1 1 e 器0 = 。j l h 。v h l ，j 三r 。，j ，1sj 舰， i 锄1 i o = l ，+ l = 0 这表明，细网格q ，l 。上的迭代误差由相应的残向量，唯一确定。 ( i i ) 将细网格上的误差转移到粗网格q _ i l 。，即将残向量，j 限制到q h 。上，通 常的限制方法是对残向量o 进行加权，例如 j e h 2 j2 五1 、e l ，2 j 一1 + 2 e h l ，巧+ e h l ，2 j + 1 ) ，1 j 尬， le _ h 2 ，o = e h 2 , + 1 ：0 ( i i i ) 在粗网格q 地上解离散问题 求解方法可以是直接方法，也可以是迭代方法。此外，算子l 。不一定要和三 相 同。 ( i v ) 将粗网格q b 上的误差插值或延拓回细网格，例如 je h l ，巧一1 = ；( e 2 ，j l + e 2 j ) ， 【乱1 ，2 j = e h 2 ，j ，j = 1 ，2 ， ( v ) 对近似解作修正 1 j 卜嘲1 ，j + 磊。，j ，j = 1 ，2 ，u l ， 一 v 1 0 1 = l i k = e 0 伽咖 ，1l 第三章多重网格法 1 3 并以一最为初始猜测，在细网格上迭代求解问题3 1 0 耽步，从而得到新的近似 解，然后回到第( i ) 步，并开始下一个循环。这一循环过程通常记为y 循环。 上述两重网格算法可以自然的延拓到高维微分方程的边值问题的数值 求解，只是从细网格到粗网格的限制算子老和从粗网格到细网格的延拓算 子礤的定义形式需要需作适当的变化，现以二维区域q = ( z ，u ) l o h n 。此时，多重网格算法可以描述为( 为方便起见， 设h t + 1 = 2 h ) ： 第三章 多重网格法 1 4 v 循环算法： ( i ) 在细网格，上用迭代方法解边值问题 jl l 让 l j ，七= 1 j ，七，( j ，k ) q 1 ， 【u h 。囊七= 7 h 1 ，j ，k ，( j ，k ) a q 。 记经过1 次迭代后的近似解是，相应的误差e _ h 。j ，七满足 jl l e h l ，j ，七2 1 囊南一l h l v h l ，互七：= r h l ，歹，南， 【e h 。，m = 0 ，d ，k ) a q ( i i ) 对i = 2 ，3 ，将残量从细网格q k 一。限制到粗网格q 屯上，即计 算7 k ：_ i 嘶h l 一。并用迭代方法计算 k e h , j , k - - - - - r ，h 。0 ，嶝) ( 3 1 1 ) ie h 。j ，七= 0 ，( j ，k ) a q k 、7 可以取迭代次数等于。 ( i i i ) 对i = n 一1 ，n 一2 ，1 ，将粗网格q + ，上的误差e 屯+ 。j ，k 插值回细网 格q 虬，e p i t - 算e h ；= _ i m h , + 。e h m ，并对误差e k 进行光滑，即用迭代方法近似求解 问题3 1 2 v ：次。 w 循环算法： ( i ) 在细网格q ，l ，上用迭代方法解边值问题 jl 1 u h l 囊七= l ，j 。奄，k ) q l ， 【u h l ，j ，知= 7 九1 ，j ，k ，0 ，k ) a q ，1 1 记经过均次迭代后的近似解是v h 。，相应的误差e 。，互七满足 jl h l e h l ，j ，七。 1 ，j ，七一l h l v h l ，j ，南：= r h l j ，詹， ie h i ，是= 0 ，k ) 砸2 五1 ( i i ) 对i = 2 ，3 ，将残量从细网格q k 一。限制到粗网格q k 上，即计 算他：= 班，并用迭代方法计算 k t t , j , k = r ? hj 0 “婺) t ， ( 3 - 1 2 ) le ，歹，七= 0 ，d ，k ) a q k 、 第三章多重网格法1 5 可以取迭代次数等于约。 ( i i i ) 对i = n 一1 ，一2 ，将粗网格q h 州上的误差e k 扎j ，k 插值回细网格q h ， ，并对误差e h 。进行光滑；然后对i = n 一1 ，将残量从细网格q k 一，限制到粗网 格q k 上，并用迭代方法光滑误差。 ( i v ) 对i = n 一1 ，一2 ，1 ，将粗网格q k + 。上的误差e ，l i + l , j , k 插值回细网 格q ，即计算e h ；：= 瑰。c h 川，并对误差e 玩进行光滑，即用迭代方法近似求解 问题3 1 2 v 2 次。 第四章小波应用于多重网格法 在多重网格法中，限制与插值算子的选取是一个重要而关键的内容，它直 接决定了多重网格方法的收敛性。根据小波多分辨分析与多重网格方法之间的 切合点，结合小波的优点，将小波理论应用于限制和延拓算子的构造，进一步提 高多重网格法的效率 1 7 1 。 ( i ) 尺度空间，与多重网格法中网格剖分的粗网格到细网格对 应。 ( i i ) 小波多分辨分解过程对应于多重网格法中细网格到粗网格的限制。 ( i i i ) 小波多分辨重构过程对应于多重网格法中粗网格到细网格的延拓。 ( v ) w w t = m 厂是小波变换矩阵对应于多重网格法，秒吃= i 。 4 1 小波延拓算子 首先考虑在k 上，假设0 ，0 5 ，l 三点上的函数值已知，定义函数为 ( x ) = a l o ( x ) + 0 2 西( z + 1 ) + a 3 多( z + 2 ) ( z ) 是d a u b e c h i e s - 4 ) 畏度函数，并满足 ( z ) = h o ( 2 x ) + h l ( 2 x 1 ) + h 2 ( 2 x 一2 ) + h a 矽( 2 x 一3 ) 这里= 刁1 + , r 5 ，h = 鼍乎，h 2 = 糟，h 3 = 杀乎是d a u b e c h i e s - 4 滤波系数。 用给定的函数值和条件矽( o ) = 矽( 3 ) = 0 ，可以从方程 f = a 球a 求出a 。 其中，= ( ，( o ) ，f ( o 。5 ) ，( 1 ) ) 丁，a = ( 8 z ，眈，a 3 ) t ，以及 a = 0 妒( 0 5 ) ( 1 ) ( 1 ) ( 1 5 ) ( 2 ) 妒( 2 ) ( 2 5 ) 0 第四章小波应用于多重网格法 1 7 当计算出插值常数后，利用上面已定义的插值函数可以求出 ，i 处的函数 值。这样，可以把较粗网格k 上的函数值延拓到较细网格：0 ，i 1 ，互1 ，i ，1 上。 在中，首先考虑区间 o ，；】上的插值函数 f ( x ) = b x 矽( 2 x ) + 6 2 矽( 2 z + 1 ) + ( 2 z4 - 2 ) 由于已知，( z ) 在o ，i 1 ，；三点的函数值，可以唯一确定常数6 l ，6 2 ，b 3 。 同样的在区间【 ，1 】上可令插值函数为 f ( x ) = c l 妒( 2 z 一1 ) - 4 - c 2 ( 2 x ) + c a ( 2 x - 4 - 1 ) 已知函数，( z ) 在；，；，1 = - 点的函数值，三个系数c 1 ，c 2 ，c 3 也可以确定。 从而可求得更细网格圪上节点的函数值o ，；，i 1 ，i ，互1 ，i ，互3 ，i ，1 上的函数值。这 样，就把上的函数值延拓到圪：0 ， ，石i ，i ，；，i ，i ，i ，1 上。 值得指出的是每个的矩阵a 是完全相同的。 这里a 可以用h o ，h l ，h 2 ，h 3 求得： 4 ：j l 一 ( 1 一v f 2 ) h 2 - 4 - 、2 3 点。 0 ( 以一2 h 2 ) ( 、，互一2 h 2 ) 危1 + 2 3 ( 以一2 h 2 ) l - 4 - 2 h 3 h o ( 以一2 h 2 ) 2 - 4 - 2 h 3 h l ( 以一2 h 2 ) 3 - 4 - 2 h 3 h 2 ( 以一2 2 ) 九3 + 2 h 3 h 2 2 镌 0 而这个一维插值算子自然地可以拓展到二维插值算子： f ( x ，y ) = 妒( 秒) 【a 1 ( z ) - 4 - a 2 砂( x - 4 - 1 ) + a a ( x + 2 ) 】 + ( 4 - 1 ) 【6 1 ( z ) - 4 - 妒( z + 1 ) - 4 - b a 矽( x + 2 ) 】 + ( 矽4 - 2 ) 【c 1 ( z ) + c 2 ( z - 4 - 1 ) + c 3 砂( z 4 - 2 ) 】 利用这个插值算子，可以把一组3x3 的网格节点扩展到一组5 5 的网格节 第四章小波应用于多重网格法 1 8 4 2 小波限制算子 令，( z ) 为定义征【0 ，1 】_ _ v _ f l q 函数，上已知函数在o ，孑1 ，i 1 ，i ，1 五点的函数值。 限制到上，边界o ，1 上的函数值相同，；处的函数值为 丘( 三) = 鲁胂) + 疗( 三) 帆疗( 丢) 地疗( 丢) + 鲁加) 其中，兀和厂，分别是粗、细网格上节点的函数值。 同理，更细网格：0 ，百1 ，i 1 ，面3 ，i 1 ，百5 ，互3 ， ，1 上的函数值限制到：0 ，互1 ，i i ，i 3 ，1 上 的节点 ，虿1 ，i 的函数值定义为 ，c ( 丢) = 鲁厂，( o ) + ，( 言) + - 疗( 三) + 2 厂，( 詈) + 虿h 3 ，八互1 ) 砖) = 鲁疗( 三) + 疗( 扣晰( 三) 讹疗( 砂h 3i 3 五( 兰) = - h i 3 ，r ，。7 互1 ，、+ 无。疗( 詈) + 壳。疗( 三) + 秃：疗( 吾) + 鲁办( 1 ) 4 3 利用小波多重网格法对微分方程求解 考虑方程 x u = 一2 丌( s t n ( 7 r z ) + s i n ( n y ) ) q = ( z ，v ) l o z ，y l d i r i c h l e t 边界条件：u ( o ，y ) = u ( 1 ，y ) = u ( z ，0 ) = u ( x ，1 ) = 0 并将其剖分成规则的正方形网格，其中网格线是两组分别平行于坐标轴的 直线 1 巧2j h , y k 。k h , 0g j 坯m “，h 2 志 其标准五点差分格式为 1 索( 一4 乱u + 珏件1 j + u i 一1 j + j + l + t t j 1 ) = 五，j 这里 五j = 一2 r r ( s i n ( r r x i ) + s i n o r y j ) ) 由小波多重网格法与传统多重网格法结果比较如下表： 第四章小波应用于多重网格法 1 9 x y 小波多重网格法误差传统多重网格法误差精确解 0 5 8 8 0 5 8 8 0 5 8 8 3 5 2 9 1 1 7 61 7 6 5 1 1 7 69 4 1 2 1 7 6 56 4 7 1 2 3 5 30 5 8 8 2 3 5 34 7 0 6 2 9 4 11 1 7 6 2 9 4 15 8 8 2 3 5 2 92 9 4 1 3 5 2 94 1 1 8 4 1 1 82 3 5 3 4 1 1 88 2 3 5 4 7 0 61 1 7 6 4 7 0 66 4 7 1 5 2 9 40 5 8 8 5 2 9 4 2 9 4 1 5 8 8 2 1 1 7 6 5 8 8 28 2 3 5 6 4 7 1 2 3 5 3 6 4 7 16 4 7 1 7 0 5 99 4 1 2 7 6 4 73 5 2 9 7 6 4 77 0 5 9 8 2 3 54 7 0 6 8 8 2 42 3 5 3 8 8 2 44 1 1 8 9 4 1 22 9 4 1 9 4 1 27 6 4 7 8 8 2 45 2 9 4 9 4 1 21 7 6 5 9 4 1 22 9 4 1 0 3 3 7 9 1 6 4 8 0 1 9 0 5 2 6 6 4 6 3 4 7 0 2 5 1 2 3 8 6 6 7 2 3 5 2 8 7 5 8 7 6 3 0 4 7 0 9 6