（计算数学专业论文）抛物型方程的多层迭代快速算法.pdf

擞物型方程的多层迭代快速算法 学位申请人： 导师及职称： 专业t 浚袭： 何崇南 陈仲英教授 计算数学 数学与壹专彝辩学学藏 摘要 本文所讨论的是梅造一类抛物型方程的多朦迭代快速算法本文选取 础( o ，1 ) 申的多尺度破交小波基函数对抛物型方程的空间变撼离散，由于基 函数的紧支性和多尺发性质使得离散后的方程缝的系数矩障具有稀疏性秘 凄凌毪，农琵基疆上稳逢警踅麓鍪方程静多罄逡代算法。对方程懿时阁变量 则采用熬分法离散给出了半离散格式和全离散格式的误差估计，给出了抛 物型方稷的多层迭代算法的三种计算格式，最腐给出了数值算例 关键调：多层，小波，迭代，抛物型方程 m u l t i l e v e li t e r a t i o nf a s ta l g o r i t h m sf o r t h ep a r a b o l i ce q u a t i o n s n a m e ： c h o n g n a nh e s u p e r v i s o r ：z h o n g y i n gc h e n m a j o r ：c o m p u t i n gm a t h m a t i c s a b s t r a c t i nt h i sp a p e r ，w ed e v e l o pm u l t i l e v e li t e r a t i o nf a s ta l g o r i t h m sf o rs o l v i n gp a r a b o l i c e q u a t i o n s ，w ec h o o s em u l t i s c a l eo r t h o g o n a lw a v e l e tb a s e si n 础( o ，1 ) s p a c e sa n dl l s e t h e s eb a s e st od i s c r e t i z et h ep a r a b o l i ce q u a t i o n s t h es p e c i a lp r o p e r t i e so ft h eb a s e s s u c ha sv a n i s h i n gm o m e n t ，o r t h o g o n a t i t y , c o m p a c ts u p p o r ta n dn m l t , i s c a l ep r o p e r t i e s l e a dt ot h es p e c i a lp r o p e r t i e so ft h ec o e f f i c i e n tm a t r i xo ft h ed i s c r e t es y s t e m m u l t i l e v e l i t e r a t i o nf a s ta l g o r i t h m sa r eb a s e do ns u c hp r o p e r t i e s t h ee s t i m a t i o no ft h es e m i d i s c t e t i z e ds c h e m ea n dd i s c t e t i z e ds c h e m ea r ep r o v i d e d i nt h ee n d ，w ep r e s e n to u r n u m e r i c a le x a m p l 霉 k e y w o r d ：m u l t i l e v e l ，w a v e l e t i t e r a t i o n ，p a r a b o f i ce q u a t i o n s ， i i 第一节：引论 在数值分析和科学计算中，开发稳定和有效的快速算法来解算子方程一 直是研究的热点，这里的算子方程包括积分方程和微分方程这样的算法对 于大规模的科学计算尤为重要一般地说，要解一个算子方程，通常有三个 步骤：首先，要选取合适的子空间来作逼近以及选取相应的基函数，这属于 数值逼近的范畴逼近的方法通常有整体逼近，分片逼近和多尺度逼近等 其次，用某种方法离散化算子方程，这属于方程数值解的范畴通常的离散 方法有g a l e r k i n 方法，有限元方法，配置法，有限差分法，有限体积法，谱 方法等最后是用代数的方法来解线性方程组，这属于线性代数的范畴通 常可根据所得的代数方程组的特点采取各种消元法或迭代法如波前法、追赶 法和共轭斜量法等来求解事实上，离散方程组的有效解法应同时考虑到子 空间和基函数的选取以及方程离散化的方法，在这方面，多重网格法就是一 个成功的范例 多尺度与小波快速算法是上世纪九十年代初发展起来的一种解算子方程 的新方法，其主要的思想是构造具有紧支集和消失矩性质的多尺度基底来离 散算子方程，使得离散后的代数方程组的系数矩阵具有某种特殊的性质，如 稀疏性和层次性等，在此基础上构造各种矩阵压缩算法，从而达到快速求解 的目的该方法的开创性工作可追朔到g b e y l k i n ，r c o i f m a n 和v r o k h l i n 9 1 年发表的文章1 5 】，该文章构造了解积分方程的具有紧支集正交小波基，指 出以小波为坐标架的某些积分算子的坐标几乎是稀疏的，得到的刚度矩阵几 乎是稀疏矩阵，大部分元素很小，从而在不影响收敛性的情况下，可以将其 忽略以达到提高速度的效果，这种思想后来得到了广泛的应用z c h e n ，y x u ，c a m i c c h e l l i 在文献 1 1 】中，提出了有弱奇核的第二类积分方程的快速算 法，他们采用多尺度插值小波和点值泛函作为基底，由于基底的消失矩性质 使得离散后的线性方程组的系数矩阵绝大多数元素非常小，通过合理的截断 后得到一个稀疏矩阵，从而构造出相应的矩阵压缩算法，节省了存储空间， 加快了求解的速度 多尺度与小波g a l e r k i n 方法和传统的有限元方法不同之处，在于其逼近 的方法上它采用的是多尺度逼近，即它构造的小波基函数是多尺度的，利用 小波基函数特有的性质使离散方程组的系数矩阵具有某种性质在文献 8 中，z c h e n ，y x u ，c a m i c c h e l l i 提出了第二类积分方程的p e t r o v - g a l e r k i n 方 法，他们用区间【0 , 1j 上的非连续正交小波离散方程后得到的系数矩阵是稀疏 的，且条件数是有界的，并提出了相应的截断策略，得出了此类方程的快速 算法，并证明了此方法具有最优的收敛阶对于微分方程来说，有限元法由 于采用的是单尺度的基底，得到离散方程组的系数矩阵往往是病态的，从而 无法用迭代法求解实际上，如果我们选取适当的多尺度小波基底，那么得 到的离散方程组的系数矩阵将是良态的，即离散方程组的系数矩阵的条件数 是有界的基函数的层次性还会导致离散方程组系数矩阵的层次性，这一特 征成为我们构造多层迭代快速算法的基础另外，小波基函数可由初始小波 基函数通过伸缩和平移来生成，易于编程和计算 抛物型方程是一类有很强物理背景的偏微分方程，它的数值解法主要有 有限差分法和有限元法等有限差分法的求解步骤是：首先将求解区域划分 为网格，然后在网格的结点上用差分方程近似微分方程有限差分法对于几 何形状复杂的问题，它的精度较低有限元法的出现是数值分析和计算领域 的重大突破，得到了广泛的应用但在某些问题中，由于有限元法采用是单 尺度的基底，其离散后得到的系数矩阵是病态的，给数值求解带来困难而 且在剖分加细的过程中，所有基底都要变动，刚度矩阵需要重新生成，计算 量较大本文提出的多尺度小波方法是针对抛物型方程的特点，采用分片线 性多尺度小波基底对方程的空间变量离散，使得离散后的刚度矩阵是非病态 的，即条件数是有界的，且此方法有良好的自适应性，即在剖分加细的过程 中，只需加入更细尺度的基底，丽无需变动所有的基底，生成刚度矩阵的计 算量较小由于小波基底的正交性和紧支性也导致了离散后的剐度矩阵数值 的稀疏性，节省了存储空间由于多尺度小波的层次性，还导致了离散方程 组的系数矩阵的层次性在此基础上，我们构造出抛物型方程多层迭代快速 算法的三种计算格式由于采取的小波是分片线性多项式，在实际数值计算 中更为简单，加快了计算速度 全文总共分为八节，第一节简单介绍国内外关于抛物型方程数值解法及 多尺度与小波方法的研究工作第二节主要描述多层迭代法解算子方程的具 体步骤第三节介绍抛物型方程数值求解的半离散格式第四节给出抛物型 2 方程半离散格式的误差估计第五节绘出抛物型方橼多层迭代法的计算格式 及全离散格式的误差估计，第六节介缨本文选取的璃( o ，1 ) 中的多尺度正交 小渡基函数豹擒造方法。第七节梅逢熬物螯方程多鼷迭代质量察审法第八 节给出数值算例 3 第二节：基于g a l e r k i n 格式的多层迭代算法 本节描述多层迭代法解算子方程步骤 在这篇文章中，我们将使用指标集z 。：= o ，1 n o ：= o ，1 ，2 ，) 设x 是h i l b e r t 空间，尼：x x 是一线性算子 考虑下列形式的第二类算子方程 n 一1 ) ，n ：= 1 ，2 ，) 和 且z 一疋是x 上的双射 口一疋) u = ， ( 2 1 ) 其中，x ，“是待求的解 为了求解方程( 2 1 ) ，我们首先选取x 的有限维嵌套子空间序列稀， 繇稀+ 1 ) n = 0 ，1 ， ( 2 2 ) 使得 1 万一 u x 。一x n = 1 为了离散原方程，引入正交投影算子r ：x 一，则有i i p i i ：1 ，：r x ，并 且r 在x 中是点态收敛于z 的用g a l e r k i n 方法解( 2 1 ) 就是求“。x 。使得 口一p j c ) u n = r ， ( 2 3 ) 这里，要求对于任意充分大的竹，工一r 咒是可逆的，其逆是一致有界的，即 存在不依赖于礼的常数c ，使得 仁一r ) - 1 i i c 当尼是x 上的紧算子时，这个条件是满足的在这种情况下， x 中是点态收敛于z 及算予的紧性可得 臬0 k r i i = 桌恐一尼r l i = 0 因此方程( 2 3 ) 有唯一解u 。岛满足以下估计 4 ( 2 4 ) 由于r 在 怯怯c ，| | “一u n 忙c 。i n ；f 。l l u 一。n 扎 这里“x 是方程( 2 1 ) 的精确解 由于子空间的嵌套属性，我们可以对逼近子空间x t l 作直和分解，对于 v n n 0 ，可定义子空间w 。+ lc x 。+ l i 使得 x 。+ 1 = x 。o 上w n + 1 ，礼n o ，( 2 5 ) 其中五0 1 死表示乃和马的正交直和，即对于任意o 乃，b 死，有( o ，b ) = 0 反复利用( 2 5 ) ，对于n = 女+ z ，k o ，l 0 ，我们可以得到空间x 。的如下分解： x = x k “= x 自。上w k + l o 上o 上w k “( 2 6 ) 易见吼是一个到w n 上的投影，且 w n = q n x n + l 我们还注意到，算子p n 和q 。有下列正交关系： r = 。( 。，。) 及 蚴咄r = 乏羹黧 为了方便起见，我们用算子的矩阵形式来表述多层迭代格式为此，将 x k w k w 中的向量f i o ，g o ，引7 与& o 上w + 10 1 0 1w k + 2 中的向 量，0 - b g o + + g l 等同起来，其中，0 取，m + 】k 0 ，0 i z 相应地， u 州x 川可以表示为： + f = u ，o + v k ，1 + + 饥，f 其中“蛐磁，”w 州( os i z ) 并且下式成立 r + l = 7 气+ q k + 一- + q k + l 5 r 一 “r | | 锄 令 令 瓦。= r 疋7 毛，。m = q 。k q m ， 玩，m = 7 咒q m ，厶，m = q n k i k 那么算子妊“可以用矩阵的形式表示为： a k f = 鼠1 尼k + 1 + l 段 + l 厄k + i k “ 靠+ l ，c k + z ，k + l + f ，k 州 这时我们可将算子方程( 2 , 3 ) 写成 ( 2 7 ) u k 1 一a k ，l u k ，j = f k ，2( 2 8 ) 其中u f = m m 魄1 j 一，u k ，f 7 ，f k 1 _ 陬 q k ，q 州， 对于方程( 2 3 ) ，我们要在子空间x 川中求解如果我们选定子空间x 。和 w k + i 的基，则算子圮州可以表示成( 2 7 ) 中的a “ 将a “分解成两个算子矩阵：严格上三角矩阵 和下三角矩阵 此外，定义 u k z = l k i = d 鼠 + l o o 仇+ 1 ，k尼k + l ， + 1 取 + l 咒+ l 。k “ 芄k + 1 - 1 , k + f o g k + l ， l g k + 1 k + 1 咒k + l 。k + l d k ，i ：= z a k ，j + u 1 + l k z 6 则d “有以下形式 d k f = z 一庀k 工 其中对角线上的五可以理解为在相应的子空间x m ，w ，吼+ 2 一，上的单 位算子这时方程( 2 8 ) 可以写为： ( d k f u k ，1 一l k ，z ) u k ，1 = f k ，1 这个矩阵形式可导出以下两种多层迭代格式来解方程( 2 8 ) j a c o b i 型迭代 d u 器+ 1 = ( u + l ”) u 黯+ f k 山m = 0 ，1 ，2 ， g a u s s s e i d e l 型迭代 ( d 一u 1 ) u 忠+ 1 = k j u 孵+ 如f ，m = 0 ，1 ，2 ， ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) 在以上两种迭代格式中，要求k + l 层的解，我们只需求解一个计算量 相当于k 层的线性方程组，因为在( 2 1 0 ) 式左边项d “中除了左上角第一 项外，其余的对角块都是单位算子，在( 2 儿) 中，d 一u 划则是上三角块 矩阵因此一旦选定初始层数( 一般不太大) ，并求出初始层的近似解，把 u 鼎= 【1 1 k ，0 ，o ? 带入( 2 1 0 ) 或( 2 1 1 ) 中通过若干次迭代后就能得到k + l 层 上更为精确的解关于这两种格式迭代法的收敛性有以下定理，详细证明可 以参看文献f 3 4 3 0 定理2 1 设x 是h i l b e r t 空间，圮是x 上的紧算子，工一j c 是x 上的双射，正 交投影算子豫：x 一稀在x 中点态收敛于z x 。) 黯。是x 的逼近子空间序列 且满足( 2 2 ) 式，即鞴x 。+ 1 in = 0 ，1 ，并且每个稀有形如( 2 6 ) 式的正交 投影分解，则对任意的z 1 及充分大的k ，解方程( 2 8 ) 的迭代格式( 2 1 0 ) 和 ( 2 1 1 ) 是收敛的 7 对于算子- 2 的矩阵形式a 川，也可以分解为低频矩阵 和高频矩阵 魄，k + l 玩k + 2 鼠， + l o0d o o0o p 0oo o c k + 1 ，尼k + l ，k + 1 c k + 1 k + 2j 矗+ 1 + i 靠+ z ，k坛k + l ，k + l尼k + i ， + 2 k 女+ 1 + l 定义 g l ：= z a 毛，h k ，l ：= 一a 州h 则方程( 2 8 ) 可写为： ( g k ，f + h k ，t ) u k ，l = 最，f 也就是 g k ，l u k ，i _ 最 j h k ，i u k 1 于是我们可以导出另一种迭代格式解方程( 2 8 ) 高低频分裂迭代 g k ，j u 黯+ 1 = 最，l h u 船，m = 0 ，1 ，2 ，( 2 1 2 ) 与前面j a c o b i 型和g a u s s - s e i d e l 型迭代相似，我们要求方程( 2 8 ) 在k + l 层 的解，同样也只需解一个计算量与初始层相当的线性方程组，因为我们注意 到矩阵g 有以下形式， g k j = z 一k 一玩， + 1 一鼠 + l 0 ： o 工 d 8 d ： z g 州中除了左上角第一块外，对角块都是单位算子以u 黜= 【u t ，0 ，o ，代 入( 2 1 2 ) 迭代若干次后可得到+ f 层上较为精确的解，因而用上述格式求解 加快了求解的速度下面我们来考察迭代格式( 2 1 2 ) 的收敛性 定理2 2 设x 是h i l b e r t 空间，尼是x 上的紧算子，z 一咒是x 上的双射，正 交投影算子r ：x 一在x 中点态收敛于z 鞴) 箍。是x 的逼近子空间序列 且满足( 2 2 ) 式，即x 。x 。+ 1 ) n = 0 ，1 ，并且每个x t i 有形如( 2 6 ) 式的正交 投影分解，则对任意的f21 及充分大的，解方程( 2 8 ) 的迭代格式( 2 1 2 ) 是 收敛的 证明：由于是x 上的紧算子，z 一庀是x 上的双射，r 点态收敛于z ，所 以在方程( 2 8 ) 中，对于任意l 0 及任意充分大的k ，z a 是可逆的，其逆 是一致有界的，即存在常数a 0 ，使得 口一a k ，1 ) _ 1 i i o “ 而对于u k i x 有 0 g t l u k ，i i l = | | 口一a k ，f h ，1 ) u ，l i i ( a i l h t ，, 1 1 ) l l u t l ， 所以 峨- 圳1 南 因为r 点态收敛于2 ，所以 i h “0 = i i ( r + l 致) 芄0 0 ，当七一o 。 由( 2 1 3 ) 和( 2 1 4 ) 我们有 0 g 矗h 0 0 ，当一o 。 因而，当充分大时，有i g 矗h 训 1 ，所以迭代格式( 2 1 2 ) 是收敛的 9 第三节：抛物型方程数值求解的半离散格式 现在，我们开始考虑以下抛物型微分方程的混合问题 fu 。+ 血= i ( x ，t ) “= o ， i 札：咖( 。) ， 茁q ，0 o ， lu ( z ，0 ) = t 幻( z ) ， 。n ， 其中( ，) 表示l 2 ( f 1 ) 的内积， 小，”，= 二喀瓯，蹇器+ r _ 3 盟o x j ”+ ) 衄 为解问题( 3 2 ) ，在空间域上用g a l e r k i n 方法离散，取x ：= h o ( n ) 的子空间 鞴，则相应的半离散格式为：求“。= “。( ，t ) 岛，0 t z 使得 ( 出”) + 。( “n ，”) 。( ， ”) ，x l ，。 o( 3 2 1 ) lu 。( z ，0 ) = u o r 。( 茹) ， o n ， 现考虑一种特殊情形：n = 0 ，1 】， a u = 一u ”+ p ( 。) u + q ( x ) u ， 其中p ( z ) ，q ( x ) l o o ( o ，1 ) 此时与( 3 1 ) 相应的变分问题为：求u = u ( ，t ) 刚( o ，1 ) ，0 t t 使得 ( u t , v ) u , v ) 4 - 。( “，”) = ( ，”) ， 4 v 础( o ，1 ) ，。 o ， i “( z ，0 ) = “o ( z ) ，z ( 0 ，1 ) ， 、。 其中( - ，) 表示l 2 ( o ，1 ) 的内积，b ( u ，口) = ( “7 ，u ，) ) c ( u ，”) = ( 叫7 + q u ， ) 为了解方程( 3 3 ) ，我们在空间域上用g a l e r k i n 方法离散现取x ：= 础( o ，1 ) 的分片线性多项式子空间x 。，那么求解( 3 3 ) 的半离散g a l e r k i n 格式为：求 。= ? a n ( ，t ) x 。，0 t t ，使得 慨u n , t l 舻v ) - 。0 麓r 叫 警0 x 刈 慨s ， i “。( z ，) = u o 。( z ) ，。( ，1 ) 、。 设子空间稀满足( 2 2 ) 式，即稀c 稀+ 1 i 则x 。有正交直和分解 x 。= x o o 上w 1o 上- - o 上w 。 令：= w o ，设 w 日( 。) ：( i ，j ) u 。) 为稀的多尺度基底，使得 w i = s p a n w 玎：j z ( 1 ) ) ，i n 其中w ( i ) = d i m w i ，则问题( 3 3 。) 可以表述为求形如 u 。= p 玎( 枷b ( z ) 的解，其中：= ( i ，j ) ：j ( ) ， z n + 。) ，使系数肠( t ) ，满足方程： 。磊。 塑铲( 吲+ 舭) ( 6 ( w i j , w i j l ( w l j , w i ，j t ) ) 刈嗍，) ( i i , j ) u n p u ( o ) = o 玎，( ，j ) u 。 式中的o 。为u = o u ”蚶的系数 ( i z ) e c n ( 3 4 ) 引进矩阵和向量记号 尬产【( w i j ，w i ，j ，) 】，u 。= # i j ( t ) ：( i ，j ) 7 ， 晶= b ( w i j ，w i 印) ，凰= c ( ，毗o ，) 】，( 3 5 ) f j = f ( ，毗，) 】7 ，o t ：= 【o 玎：( ，j ) u 。】7 ， 则问题( 3 4 ) 可写成向量和矩阵形式为 f 可d u n + ( r + ) u n 吒( 3 6 ) i ( o ) = o 易见为正定矩阵，由常微分方程理论可知上述半离散g a l e r k i n 格式对于 任意，l 2 ( o ，1 ) 有唯一解 第四节：半离散格式的误差估计 注意到在多尺度方法中，我们仍然使用分片多项式子空间，而只是改变 了子空间的基函数，即将有限元法中的单尺度基底，改为多尺度基底由于 子空间不变，因此单尺度方法得到的误差估计仍然成立参照 3 7 和 3 8 】，我 们将误差的工2 与日1 估计整理叙述如下 首先引进伴随椭圆投影算子r ：h 。( n ) n 铫( n ) 一x 。，这里稀是础( q ) 的 分片线性函数逼近予空间，其中n = ( 0 ，1 ) ，它由以下广义差分格式确定： o ( r 札，v n ) = o ( 札，v n ) ，v u 。x 。( 4 1 ) 由文献 3 7 3 8 可知，对于任意“h 2 ( q ) n 日3 ( n ) ，只由上式唯一确定 引理4 1 设r “是( 4 1 ) 确定的“的椭圆投影算子，则有 l u 一只u l l l c h l u l 2( 4 2 ) 一p 。u l l o c h 2 i l u l l 2( 4 3 ) 先考虑误差的三2 估计 定理4 1 设“和“。分别是问题( 3 2 ) 和半离散g a l e r k i n 格式( 3 2 1 ) 的解，则 o u u 。0 g o “。一u 帆i i 。+ 2 川u 。o 。+ z i l “，l l ：d 7 1 ) ( 4 4 ) 证明：令 p = 一只u ，e = r “一u n ， ( 4 5 ) 其中p n 为椭圆投影算子，则 u u n = p + e( 4 6 ) 由( 4 3 ) 得， i 。c h 2 i z = c h 2 i + ru ，d r o z c h 2 i i z + r l l “，i l ：d r l ( 4 。7 ) 】3 再估计e 由于u ，u 。分别满足( 3 2 ) 和( 3 2 t ) ，故 再由( 4 1 ) 可得 取v n = e ，可推得 即 对t 积分得 ( 毗一u 。南珥。) 4 - o ( “一u 。，v n ) = 0 ，v v 。x 。( 4 8 ) ( 龟， 。) 4 - a ( e ，v n ) = 一( 胁，) ，v v 。x 。( 4 9 ) 抽刮：i i p , i i 川i i 瓤i i 。i i p , i i 。 e i i ot 0 ，f 0 ，( 5 3 1 ) 可写为： i k ，z u 。i ，f a k 1 u i ，l = g ；，f ，( 5 4 ) 按照第二节的步骤，我们把( 5 4 ) 式中的a 分解为两个矩阵，严格上三 角矩阵 u k f = 0 b + 1 o b k b 2 k k + 1 + 2 1 7 b k + f k k + 1 k + l k k + 一1 k + i o 和下三角矩阵 此外，定义 l k f = 则d k z 有以下形式 此时方程( 5 4 ) 可写为 c + l ，kk k 州，k + l一k k + z ，k 州 d k ，f ：= i a k ，f + u k ，f + l k ， d k ，i = i k k ( d k ，j u k ll ，j ) u ：1 = g ：z 这样我们就可以构造出抛物型方程多层迭代法的两种计算格式 j a c o b i 型迭代 ( 5 5 ) d ”u ：护“= ( u ”+ l ”) u ：p + 醯一m = 0 ，1 ，2 ， ( 5 6 ) g a u s s - s e i d e l 型迭代 ( d k j u ) u ：p + 1 = l 1 i , ( 。m + 醯加m = 0 ，l ，2 ， ( 5 7 ) 在( 5 6 ) 和( 5 7 ) 中u l ( 0 ) 的值可由初始层的解获得，即u ：p 一( u ：，0 ，0 ，o ) 7 ， 其中，u 是在时刻赴初始层的解我们可以看到在( 5 6 ) 中d k ，2 除左上角外 是对角线矩阵，在( 5 7 ) 中除左上角外是上三角矩阵因此求解之每次迭代只 需解一个规模和初始层相当的线性方程组，迭代若干次后即可得到k + z 层 上较为精确的解，因而极大地提高了求解的速度利用( 5 4 ) 式，我们可以算 出每个时刻岛的初始层( 第k 层) 近似解，然后用( 5 6 ) 或( 5 7 ) 计算出在时刻 t ；第+ l 层上较为精确的解 如果把( 5 4 ) 式中的，z 分解为低频矩阵 和高频矩阵 a 。lc = a 。h j = k k b k + lb k ，k + 2 b k 。k + l ooo o ooo o oo c k + 1 ，kk k + i k + 1 o k k + 1 + l c k + 1 女k k + l ，k + lk k + l ，k + 2 k k + ，k + f 定义 g k 一z a l ，h k i = 一a 磊 则方程( 5 4 ) 可写为： ( g k ，i + h ，1 ) 碱1 = g t i 也就是 g l u ；1 2 = g ! 一h 1 u ；f 那么我们可以导出抛物型方程多层迭代法的另一种计算格式 高低频分裂迭代 g k ，l 吣妒“= 酿，。一h k ，r u 2 扩，m = 0 ，1 ，2 ，( 5 8 ) 在( 5 8 ) 中越p 的值可由初始层的解获得，即- t ! f = ( u 毛0 ，0 ，o ) ，其 中，u 是在时刻如初始层的解因为在( 5 8 ) 式中，g 有以下形式： g k l = i k k o b k + 1 i oo 1 9 氏o ；。 一 g 。中除了左上角第一块外，对角块都是单位算子，因而要求方程在k + 2 层 的解，只需解一个计算量和初始层相当的线性方程组，因雨可以加快求解的 速度利用( 5 4 ) 式，我们可以算出每个时刻屯的初始层( 第k 层) 近似解， 然后用( 5 8 ) 计算出在时刻t ；第k + f 层上较为精确的解 与半离散格式的误差估计一样，参照【37 和 3 8 】，我们将全离散格式误差 估计整理叙述如下先考虑误差的口估计 定理5 1 设u 和碡分别是问题( 3 2 ) 和向后差分格式( 5 1 ) 的解，则 证明：令 矿= u ( h ) 一r u ( 屯) ，e t = p u ( h ) 一u 2 n ， 则 u ( h ) 一噱= 矿+ e 。 由( 4 3 ) 得， i l d l l o 0 其中所有的基函数都是正交的，则 ：i z 。+ t o ，啡，曲) 是子空间x m ，k ，“ 的一组正交基 下面我们介绍构造子空间碍r m ，的基函数的方法为此，需要用到以下 两个命题，详细证明可参阅【3 5 命题6 1 函数u f 一当且仅当下列条件成立 ( i ) 是次数不超过k 的分片多项式，节点为 j z ：j 一1 z z , 一1 ) ( i i ) ( “，1 在节点 j 肛：j 一1 一1 ) 上是连续的 ( i i i ) 口( ( o ) = ( ) ( 1 ) = 0 ，1 z 。 ( i v ) f 口( m ) ( t ) t j d t = o ，jez k - m z 。 由此命题，可以构造出子空间w ， m 的基，由条件( i ) 任何函数u w p ，“ 可以表示为以下形式： 呻) 2 薹a i j t j ， 1 的基，引入一族仿射变换垂。：= 札：e z 。) ，其中 俐：= 半 e z 一 相应地，定义一族算子7 ，一：卵( o ，1 ) 一爿铲( o ，1 ) ，e ， ( ? ? p 口) ( t ) ：= p 5 1 一” ( 酊1 ( t ) ) x 。( ) ( t ) 注意到每个? “是可逆的，且保内积，即 ( 了一，：7 口) m = ( ， ) m ， 学( o ，1 ) 对于e ：= ( e 0 ，e l ，e n 一- ) 冠，定义合成映射 机：= 屯。一l 。机。一lo o e o ， 以及合成算子 ? “：一瓦= o 咒骂o o 譬” 因此， ( ? ，) ( t ) = 旷 - m ) ( 虻1 ( t ) ) x 籼( 【0 ，l 】) ( t ) 对于任意的j z 。( 帅 ，) ，存在唯一的分解 j = p ( e ) r + j ，e z 。i - - 1 ，l z ， 其中r ：一w ( 1 ，m ，k ，) 且 卢( e ) ：= # - 2 e o + + p e 一3 + e l 一2 对于i l ，设 叫嚣也“= ? ? 埘加嚣 水 ( 6 3 ) 命题6 2如果 w 1 j ：j z r ) 是w ? ”的一组正交基，则对于任意i 1 ，由 ( 6 。3 ) 定义的 “：j ( 溉k ， 是w ? k “的一组正交基 下来，我们来看空间础( o ，1 ) 中具体的小波基函数，这里我们用到的是分 片线性的基函数为此，令m = 1 ，k = 2 ，p = 2 ，则有d i n 璃1 2 ，2 = o ，d i m ( w j 2 ，2 ) = 2 t _ - ，i 0 。为了求出w ；，印的基，设 吣，2aoo+aolt,，嚣0箬1alo a l l1 t1 l + 【一纵i i ，j 由条件( i i i ) 可得a m = a l o = 0 ，这时条件( i v ) 自然满足由条件( i i ) 可得吣= a 。 因而 2 r 1 - t , 嚣 f i g u r e1 ：础中的线性多尺度正交小波基 静2 根据命题6 2 ，我们用小波基函数w l o ( ) 来生成子空间哦，2 ，2 的基函数其 嚣挲 慨a ， f i g u r e2 ：分片线性多尺度小波基，层数n = 6 的情形 第七节：抛物型方程的质量集中多层迭代法 现仍考虑前面提到的抛物型方程中的一种特殊情形，即： a u = 一u ”+ p ( z ) + g ( z ) “，其中p ( z ) ，q ( x ) p ( o ，1 ) ，q 一 0 ，1 】，此时问题( 3 1 ) 变为 i 三三二：l z ) + 口( z ) u = ，( x n ，0 0 ， 【u n ( $ ，0 ) = “o n ( 。) ，。( 0 ，1 ) ( 7 3 ) 或者写成 l ( “：，) + 6 ( u ：，”。) + c ( ：，) = ( “ 1 + ，( 屯) ，) ，v x 。， h 胁。一1 1 2 ， ( 7 4 ) 若记d ( u ， ) = ( 础7 + ( g + ) “，口) ，g ( t ；) = “ 1 + ，( 蛾那么( 7 4 ) 可以写为 i6 ( t ：，d n ) + d ( u ：， 。) = ( a ( t ) ， 。) ，7 。x 。， 1 i = 1 ，2 ， ( 7 5 ) iu n ( o ) = “o n 其中b ( u ，v ) = ( u ，”，) 令：= l 2 ( o ，1 ) ，x ：= 硪( o ，1 ) ，设 b ( u ，v ) ：= ( ，b u ) ，d ( “， ) ：= ( u ，d u ) 由文献 3 5 问题( 4 1 ) 可知，上式双线性形式定义的算子b ，d 可以唯一地扩 张为定义在x 上的连续线性算子工和紧线性算子咒，因而( 7 5 ) 式所确定的是 一个形式上为t口+ 尼) u = g 的第二类的算子方程，其中尼为紧线性算子 设x n 是砩( o ，1 ) 分片线性逼近子空间，x t i 是嵌套的，即稀c 稀+ h 我们 可以得到x 。的一个直和分解： x n = w 0 0 w 2 0 一o 砜 用第六节介绍的w ，o 为初始小波，通过压缩和平移后得到空间繇的一列小 波基函数，使得 砜= s p a n w i j ：j ( 。) ) ，忙1 ，2 ，n ， 其中 w ( i ) = d i m ( w ) ， 若用记号( 扎) 表示x 。的维数，则有( n ) = d i m x 。= 她。、 ( ) 设“。是方程( 7 1 ) 在空间鞴的解，则 “。= 卢玎( t ) 畅， 其中u n ：_ ( ，j ) ：i z w ( ) ，j z 竹+ 1 ) 与方程( 7 1 ) 相应的g a l e r k i 逼近问题可 半离散为以下矩阵形式； f _ 百d u n + ( 玩+ ) u n 吒( 7 6 ) iu 。( o ) = a 4 其中 朋k = ( t 地j ，z o i , j ，) 】( n ) x ( n ) ，l k = # q 0 ) ：( 巧) u 。l 斋( 。) ， 晶= 【b ( w o ，w l , j ，) 】v ( n ) x ( n ) ，= 【c ( 2 ，t 地o ，) 】_ v ( 。) 。( 。) ， ( 77 ) f n = ( ，叫盯) 】爵( 。) ，q ：= 陋1 ，一，a n ( 。) 】7 ， 为了更快速而有效地求解，我们将质量矩阵 厶= 【m 蟮 的每一行元素相 加后集中到对角线上，此时得到的矩阵记为砜= 吼 ，则有 f0 ，j i ， 确2 妻，j ： 汀8 显然，五k 是对角矩阵，求逆极为简单，因而可以简化求解格式在( 7 6 ) 式中，用( u ：一u 1 ) 一代替百d u n ，得到全离散的质量集中法的格式： 呼竹低) ) 峨= _ n u ”i - - 1 十碾，待1 , 2 , - - ( 7 9 ) lu ：= q 、。 其中 赴= 打，岵= i i n ( 如) ，最= 厶( 山) 质量集中法有与前面相同的误差估计 在( 7 9 ) 式中，令 i 一矾+ t e n ，瓦= 一r ，己= 矾蝣1 + r 最， 对于n ：= + f ，k 0 ，z 0 ，( 7 9 ) 可写为t h ，z u ；，l a k ，t u k 1 = f k 。，l( 7 1 0 ) 按照第二节的步骤，我们把瓦，z 分解为两个矩阵，严格上三角矩阵 和下三角矩阵 u k z = k f = o b 女1 o o c k + l ， k k + l ，+ 1 b k k “ k k + 1 + l k + 2 1 + l o c 女+ l ，kk k + ，k + l - k k + 1 女+ 1 3 1 仲 m 弘 扎 b 磁 此外，定义 则硫z 有以下形式 此时方程( 7 1 0 ) 可写为 瓯，j ：= 一i 一一a 4 1 + 取1 + l k ，l d 4 1 = i k k ( 百k f 一砜，2 一l ，i ) u ：，l = k _ - ， 这样我们构造出抛物型方程质量集中多层迭代法的两种计算格式 j a c o b i 型迭代 瓯，z u i , ( m + 1 = ( 矾1 + 【”) u 2 护+ 砭山r n = 0 ，1 ，2 ，( 7 1 1 ) g a u s s - s e i d e l 型迭代 ( 玩，f u 4 ，1 ) 峨p ”= 瓦，l u 妒+ 砭mm = 0 ，1 ，2 ，( 7 1 2 ) 在( 7 ，1 1 ) 和( 7 1 2 ) 中u 拶的值可由初始层的解获得，即u 拶= ( u 毛0 ，0 ，o ) 7 其中，u 2 是在时刻t i 初始层的解我们可以看到在( 7 1 1 ) 中百除左上角 外是对角线矩阵，在( 7 1 2 ) 中除左上角外是上三角矩阵因此求解之每次迭 代只需解一个规模和初始层相当的线性方程组，迭代若干次后即可得到k + l 层上较为精确的解利用( 7 9 ) 式，我们可以算出每个时刻t ；的初始层( 第k 层) 近似解，然后用( 7 1 1 ) 或( 7 1 2 ) 计算出在时刻“第+ ；层上较为精确的 解 如果把( 7 1 0 ) 式中的瓦。z 分解为低频矩阵 甏：= k k b k 4 + 1b 4 ，4 + 2 b 。+ i ooo o ooo o 3 2 和高频矩阵 oo c k + l ，k k + 1 k + l o k k + 1 k + f c + ，kk + l ， + 1k k + t ， + 2 k k + l ，k + z 定义 百州：= i 一鹫i 风= 一- - a “h 则方程( 7 1 0 ) 可写为： 佩，r + 凰，z ) 吨。= 瓦。 也就是 强，u ：，f = 瓦厂h k ，j 啦，j 那么我们可以导出抛物型方程质量集中多层迭代法的另一种计算格式 高低频分裂迭代 硪j 填妒“= 砭，f h k ，l u ：p ，m = 0 ，1 ，2 ，( 7 1 3 ) 因为在( 7 1 3 ) 式中，瓦，z 有以下形式 g 1 = i k 女 。 一b k ，k + l i oo 百矧中除了左上角第一块外，对角块都是单位算子，因而要求方程在k + f 层 的解，只需解一个计算量和初始层相当的线性方程组，因而可以加快求解的 速度我们可以算出每个时刻t 。的初始层( 第k 层) 近似解，然后用( 7 1 3 ) 计 算出在时刻如第k + l 层上较为精确的解 k o ； 一 第八节：数值算例 作为数值算例，我们考虑下列初边值问题 瓦o u u ”= ( 1 + t 7 r 2 ) s i n (