多重网格方法

出处：按学科分类—自然科学总论 北京出版社《现代科技综述大辞典上》第111页（4002字）

简称MG方法。

它最初是做为求解椭圆型边值问题的一种加速收敛技术而被提出的。最早出现在20世纪60年代初期，但当时并未引起重视。直到70年代，经A．Brandt等的研究，此方法的本质及其重要性才逐步为人们认识，并得到迅速地应用发展，成为80年代计算方法研究中的热门课题之一。对一般椭圆型边值问题，采用多重网格技术可以获得与网格步长无关的收敛因子，大大加快了迭代法的收敛速度，采用全多重网络法更可进一步减少迭代次数，从而达到最佳的计算效率。

从80年代以来，多重网格技术及多层次计算思想(Multi-level computation)的应用范围也在不断扩大，被用于计算不定常问题、非椭圆型问题、积分方程、特征值问题等等，甚至许多并非由连续问题离散而导出的问题。多重网格法的计算过程适合做向量化、并行化的处理，适应当前计算机硬件的发展趋势，同时也促进了它与区域分裂法、并行算法等现代计算技术的相互结合、渗透。

经典的求解椭圆型边值问题的迭代算法如Jacobi方法、Gauss-Seidel方法等对于不同频率的误差分量具有不同的收敛因子。通常波长接近于网格步长的高频误差的衰减速度最快，而相应于低频误差的收敛因子则随频率的下降而趋向于1，即影响收敛速度的主要因素来源于误差中的低频部分。

换一角度说，经典的迭代算法对误差函数通常具有较强的光滑作用，只需少数几次迭代便可有效地消除误差函数中的高频振荡部分而使其成为一个光滑函数。多重网格法正是利用许多迭代算法的这一特点构造出来的。

它的基本原理是利用一组越来越粗的网格来对细网格上的近似解进行修正，从而加快迭代过程的收敛速度。具体做法是首先在细网格上进行几次迭代(采用通常的迭代法，如Gauss-Seidel迭代)，以使误差函数变得光滑，然后将误差函数所满足的方程(称为余量方程)插值到粗网格上去求解，再利用粗网格上求出的(误差函数的)解对细网格上的解进行修正，从而消除细网格上的近似解的误差中的低频部分，加速迭代过程的收敛速度。

上述过程中细网格上的迭代称为光滑迭代过程，而利用误差函数在粗网格上的解对细网格上的近似解进行修正的过程称为粗网格修正过程，所使用的迭代算法称为基本迭代方法或光滑算子。双网格方法就是利用两组不同粗细的网格重复进行光滑迭代和粗网格修正直到细网格上的近似解收敛到给定精度。在许多重网格上递归地使用双网格方法，即在粗网格上求解误差函数时采用同样的基本迭代方法而借助于更粗的网格加速收敛，便是多重网格方法。

在多重网格法中将经过光滑后的误差函数插值到粗网格上求解主要基于以下几条理由：(1)误差函数已足够光滑可在粗网格上得到很好的近似。

(2)误差函数中主要包含低频分量，在粗网格上可更有效地消除这些分量。(3)粗网格上求解的计算量大大小于在细网格上求解。在多重网格法中误差中的不同频率的分量分别在不同粗细的网格上得到有效地消除，既减少了细网格上的迭代次数，又加快了整个过程的收敛速度。

多重网格法中除了在最粗的网格上用迭代或直接算法求出精确解(指满足一定误差要求的解)外，在中间的各层网格上只进行一至数次“光滑迭代－粗网格修正－光滑迭代”的迭代过程，然后便用所得的近似解对更细一层上的解进行修正，而不必在每层网格上都求出方程的精确解。

通常将粗网格修正前的光滑迭代称为预松驰，而将粗网格修正后的光滑迭代称为后松驰。若在中间的每层网格上均进行相同次数的粗网格修正，则将粗网格修正的次数称作循环指数，通常以γ表示。γ=1时称为V循环γ=2时称为W循环，这是最常见的两种循环流程。还有一种循环流程是根据每层网格上误差的下降情况动态地控制网格间的切换，现在已不常用。

为了说明在多重网格法中怎样将余量方程插值到粗网格上求解，假设所求解的方程为LU=F，其中L是求解区域Ω上的椭圆型微分算子(可以是非线性的)，U为未知函数。考虑双网格的情形，设G_h为细网格，G_H为粗网格，L_h和L_H分别是L在G_h和G_H上的离散近似(通常是有限元或差分逼近)。我们希望计算U在G_h上的满足L_hU_h=F_h的近似解，其中F_h是F在G_h上的一个近似。

进一步假设我们有一个粗网格G_H到细网格G_h上的插值算子p(称为扩展算子)和一个细网格G_h到粗网格G_H上的插值算子r(称为限制算子)。

设u_h为U_h(经光滑迭代后产生)的近似解，v_h=U_h－u_h为误差函数。当L_h为线性算子时，v_h满足方程L_hv_h=F_h－Lhu_h，我们只需将此方程右端的余量项插值到G_h上即可导出粗网格方程：L_HV_H=F_H，其中F_H=r(F_h－L_hu_h)。

可取0做为v_H的初始近似，求出V_H后再将其插回G_h对u_h进行修正：u_h：=u_h+Pv_H．这样导出的算法称为CS算法(Correction Storage)，因为在粗网格上计算、存储的是细网格近似解的修正量(Correction)，它仅适合解线性问题。当L_h为非线性算子时，我们可将v_h满足的方程写成：

L_h(u_h+v_h)=(F_h－L_hu_h)+L_hu_h

将上述方程中的余量项F_h－L_hu_h及u_h插值到粗网格即可导出v_H在粗网格G_H上所满足的方程：

LH(ru_h+v_H)=r(F_h－L_hu_h)+L_H(ru_h)

令，，可得u_H所满足的方程为：

L_Hu_H=F_H

其中F_H=r(F_h－L_hu_h)+L_H(ru_h)．通常取做为u_H的初值。

求出u_H的近似解后即可得出，然后插值到G_h上用于修正．此算法称为FAS算法(FulluApproximation Scheme)，因为粗网格上计算的是u_h的一个全近似u_H。对于线性问题FAS与CS算法等效，而对于非线性问题，FAS格式可获得与线性问题一样的收敛速度。

将多重网格的基本算法(CS或FAS)与套网络方法(Nesteduiteration)结合则导出全多重网络法(Full MultiGrid，简称FMG)。在全多重网格法中，首先从最粗的网格开始，每次求得一层网格上的解后，用高阶插值算子(通常阶数高于粗网格修正中使用的插值算子p)，将其插到更细一层网格上做为迭代求解的初始近似，直到所得的近似解达到一定的逼近精度。

每层网格上的求解则借助于CS或FAS算法来进行。对于许多椭圆型问题，每层网格上只需做一次V循环迭代便可使近似解的代数误差低于离散带来的误差。FMG方法还可与自适应局部网格加密、Richardson外推法等技术结合，进一步提高计算效率。

多重网格法的另一发展趋势是代数多重网格法(Algebraic MultiGrid method，简称AMG)。

代数多重网格法从代数的角度出发，运用多重网格法的思想构造求解线性方程组的快速算法。与之相对应，传统的多重网格法也叫做几何多重网格法。代数多重网格法中根据所求解的方程组的系数构造虚拟的粗网格及粗网格方程，而不管所解问题的具体物理及几何来源，同一个程序可用于计算一大类问题，甚至某些并非由连续问题离散而产生的线性方程组。假设所求解的线性方程组为LU=B，其中L为N×N矩阵，B为已知向量。我们可将下标集合G=｛1，…，N｝看作细网格，而选取G的一个子集做为粗网格。通常采用GaussSeidel方法做为基本迭代法，而取粗网格方程为rLpv=r(BLu)(即粗网格上的算子为rLp)，其中r为限制算子，p为扩展算子，u在细网格法上的修正量。

由于限制算子可取为扩展算子的转置：r=p^T，因此代数多重网格法中实际需确定的只有粗网格的选取和扩展算子p的定义。它们的构造尚属研究中的问题。

。【参考文献】：

1 Brandt A, Dinar N. Numerical Methods in PDEs Academic Press,1984

2 Hackbusch W. Multigrid methods and applications , Springer-Verlag, 1985

3 McCormiek S. Math Comp, 1986,19 : 1～372

4 McCormick S. Multigrid methods:theory, applications and supercomputing, Proc 3rd Coper Moutain conference on multigrid methods ,Marcel Dekker,1988

5 McCormiek S. Proceedings, 4th Copper Mountain Confer-ence on Multigrid Methods, 1989

6 Brandt A. Rigorous quantitative analysis of multigrid,Weizmann Institute of Sciences Report,The Weizmann Inst, of Sciences,Rehovot,Israel. 1990

(中国科学院计算中心科学与工程计算国家重点实验室张林波副研究员、博士撰)