基于小波的多重网格多重网格数值解

基于小波的多重网格多重网格数值解

多重网格方法是20世纪60年代以来被广泛使用的有效算法偏微分方程数值解（pde）的有效方法。该方法的研究已取得许多成熟的成果，小波变换是20世纪80年代由摩尔、热狗、daum、bart等人开发的一种具有多分辨率分析特征的新算法。近年来，deleon等人将微波变换与多重网格方法相结合，获得了求解pde的有效方法。魏立之等人还将微波变换与多重网格方法相结合，以求解toeplitz方程。在文献中，pde模型的解算方法是先对pde模型进行小波变换的。通过对矩阵特征的矩阵研究，在多重网格法的帮助下求解变换后的方程。多重网格法的经典本质是一种特殊的低通或高周分算子，也是最简单的滤波器。因此，在这项工作中，我们提出了使用小波矩阵来构造延伸和限制算子的新方法，并对算法进行了改进。数值实验验证了算法的效率。1=k-2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.对于一类微分方程,利用三点中心差分逼近得到下列三对角形式的数值解模型,即Τu=h2f式中Τ=1hdiag{-1,2,-1}为三对角矩阵;h为空间步长;f为离散点函数值构成的向量.如果上述方程组迭代求解使用的迭代过程采用为阻尼Jacobi方法,即设xn+1=(I-σ-1T)xn+σ-1f,其中σ为阻尼系数.因此若设x为原方程组的精确解,则有x-xn=(Ι-σ-1Τ)(x-xn-1)=⋯=(Ι-σ-1Τ)n(x-x0).由于系数矩阵T的N个特征值λk以及相应的特征向量yk满足λk=4hsin2kπ2(Ν+1)‚yki=sinkiπΝ+1‚1≤i≤Ν.其中yk=(yki).因此计算得到xn-x0=Ν∑k=1(1-λkσ)nαkyk=Ν∑k=1αnkyk‚其中αnk=(1-σ-14hsin2kπ2(Ν+1))nαk‚若选取σ=h4,则又有αnk=αkcos2nkπ2(Ν+1)=αksin2n(Ν-k+1)π2(Ν+1)≈αk(Ν-k+12(Ν+1))2n.显然,当k→N时,αnk→0.这表明对于按照σ=h4的阻尼Jacobi迭代,其高频分量会很快变为0,但对于低频分量,由于1-sin2kπ2(Ν+1)=1-(kπ2(Ν+1))2+0((kπ2(Ν+1))2)≈1-(kπ2(Ν+1))2→1,k≪Ν.即当K≪N时,上式趋近于1.因此,只要αk≠0,便有αkn在理论上收敛非常慢,实际计算中可能根本不收敛的情形.改善收敛性的根本方法就在于去掉低频信息.如果取通常的Jacobi迭代,得到的系数满足αkn=(1-2sin2kπ2(Ν+1))nαk‚对于低频分量,有αkn→αk,N→∞,而对于高频分量,有αkn→-αk,N→∞,只要αk≠0,高、低频组成的向量同样会出现不收敛的情况,因此改善收敛性的关键是去掉高、低频分量的信息.为去掉这些信息,多重网格方法实质上是对N×N矩阵分别实施延拓与限制处理,而这一过程从信号处理的角度来看本质上是做滤波器运算(高通、低通或者高、低通混合).在经典多重网格算法中,限制与延拓算子通常取为Ιkk+1=[121121⋱⋱⋱121⋱]‚Ιk+1k=(Ιkk+1)*.(1)其中*表示共轭转置.下面将看到式(1)的取法事实上基于一种特殊的小波(5～3小波)得到的矩阵,而Ikk+1的作用实质上为一种简单的5～3小波变换过程.由于5～3小波是一种最简单的小波,因此寻求更一般的小波变换矩阵代替它成为自然的选择.为了得到更好的小波限制算子,有必要对小波的滤波器性质作简单的描述.考虑由一系列嵌套闭子空间{Vj}组成的小波多分辨分析(MRA),空间序列满足下关系⋯V-1⊂V0⊂V1⊂⋯Vj-1⊂Vj⊂⋯⋯‚其中Vj+1=Vj⊕Wj,Vj⊥Wj.设H和G分别为尺度空间(低通滤波)和小波空间(高通滤波)的滤波算子.而低通滤波器系数{hk}与高通滤波器系数{gk}由双尺度方程φ(x)=∑k∈Ζhkφ(2x-k)‚gk=(-1)kh¯1-k确定,此时小波变换矩阵分别为Η=[hk-2n]n,k=-∞+∞‚G=[gk-2n]n,k=-∞+∞.注意到5～3小波重构低通滤波器系数满足{h0,h1,h2}=c{1,2,1},因此式(1)中得到的限制算子实质上为5～3小波系统取重构端低通滤波器得到的小波矩阵H.基于上述思想,本文根据迭代过程中的收敛情况,提出分别取基于小波的低通或高通滤波器变换矩阵作为多重网格算法中的限制与延拓算子,以加快算法的收敛速度,提高计算效率.2求解空间的滑动迭代考虑由偏微分方程得到的线性方程组:Tu=b,则系数矩阵T具有对称正定的性质.假设其在选定的网格ΩK上的离散方程为Τkuk=bk.(2)利用多重网格方法求解此问题的V型算法MVk(uk,bk)可以总结如下.1)给定初值uok,在网格Ωk上光滑迭代为uk=φα1(u0k,bk).2)若网格Ωk为最粗网格,转第4步,否则bk+1=Ιkk+1(fk-Τkuk)；uk+1=0；uk+1=ΜVk+1(uk+1,bk+1).3)细网格校正uk=uk+Ιk+1kuk+1.4)网格Ωh上光滑迭代uk=φα2(uk,bk).多重网格算法中解空间一般定义为Ωk=Range{Ik+1k}⊕Nullspace{Ikk+1},因此如果设Ωk为{Vj}中的某一个Vk,利用小波分解Vk+1=Vk⊕Wk将解分别分解到尺度空间和小波空间.而经过光滑迭代后,根据系数矩阵的性质,有可能出现下列情形:①高频空间的误差分量基本衰减殆尽,而低频空间的衰减缓慢;②低频空间的误差分量衰减殆尽,而高频空间的衰减缓慢;③高、低频空间均有部分分量衰减缓慢.因此此时进行小波分解,误差分量可能落在尺度空间、小波空间或者在尺度空间与小波空间均有分量.因此需要根据光滑迭代后误差向量的性质选择下一级粗网格,在其上进行粗网格校正迭代.因此基于小波的多重网格算法,其算法步骤可以描述如下.选定小波变换,按照下面过程进行递推计算.1)尺度空间(或小波空间)作为粗网格层Vk(Wk)⊂Vk+1.2)粗网格层上用选定的迭代法对方程:Tkuk=bk进行光滑迭代.3)利用小波变换矩阵得到粗转换(限制)算子,并对残(亏)量限制bk+1=Η(bk-Τkuk)或bk+1=G(bk-Τkuk).4)实施小波变换建立粗网格:Tk+1=HHTk或Tk+1=GGTk.5)逐层求解方程Tk+1uk+1=bk+1.6)以小波变换的逆作为粗到细转换算子,将粗网格上得到的误差插值到细网格层,同时实施粗网格校正.图1为算法的流程图.,其中矩形框是V型多重网格算法的一般流程,设小波变换W确定,那么在图1的矩形框中有:Ikk+1=W,Ik+1k=W-1,Ak+1=WWAk,第j层的粗网格Ωk+1=Vk+1.3快速小波变换算法验证考虑经典的二维椭圆偏微分方程边界问题-∇(a(x,y)∇u(x,y))=f(x,y),(x,y)∈Ωu(x,y)=g(x,y),(x,y)∈∂Ω.(3)为简单计算,求解区域取为Ω=(0,1)⨂(0,1).a(x,y)=1+0.8xy,f(x,y)=0,g(x,y)=0.由于不同的小波对应的滤波器性质存在着较大的区别,同时为了利用快速小波变换算法,本文选取二进制系数9～7双正交小波作为多重网格算法中的限制与延拓算子,此时小波滤波器系数满足{h0=2332‚h1=h-1=14,h2=h-2=-18,h3=h-3=0,h4=