多重网格算法综述.doc

多重网格算法综述邹静文 102071406摘要 本文总结了多重网格算法的基础理论，剖析了多重网格方法的一种并行模式以及总结了已取得的成果和待扩充的领域。对多重网格方法的基本思想有一个较详细的概述，比较分析了单一网格和多重网格的计算结果，并对多重网格的并行模式进行了探索和分析。关键词 多重网格算法，套迭代，粗网格校正，并行模式，交错多重网格，区域分解一、引言多重网格法(Multiple Grid Method)，简称MG方法是近年来求解偏微分方程边值问题的快速方法之一，本文参考前人的文献资料，并结合所学知识，总结多重网格法的基础理论，包括多重网格的应用原则、具体实现步骤以及计算结果的分析和比较。其计算结果表明：多重网格方法具有收敛速度快的优点，当多重网格方法所用层数越多，收效速度就越快；而且撞制粗、细网格层之间自适应转换的撞制参数在选取上有很大的灵活性；可以看出随着剖分的加密，单一网格方法达到收敛所需的迭代次数显著增加，而多重网格方法所需迭代次数基本上不随网格的疏密和层数而变化，这表明多重网格方法具有与网格参数无关的收敛性。二、多重网格方法的基础理论多重网格方法的最初被提出是由于在网格方程迭代求解时，误差的各个Fourier分量的衰减程度不同。认识到高频振荡误差是局部行为，来源于附近几个网格点之间的相互藕合，与边界或距离较远的网格点信息无关；而低频光滑误差是全局行为，主要来源于边界信息。传统的点或块松弛都是局部性较强的方法，因此它们能迅速抹平局部性的高频振荡误差，但对全局性的低频光滑误差却衰减缓慢。实际上，经过初始几次迭代后，误差将呈现光滑性。所以，习惯上称能迅速抹平高频振荡误差，使误差趋于光滑的松驰方法为有效光滑方法，并用松驰因子来刻画它们的光滑效应。2.1多重网格方法思想的引入考虑在简单区域上泊松方程的第一类边值问题(狄立克雷边值问题)：这里是一个单位正方形，是这个正方形的边界如下图所示：在以步长为h的网格上离散后，得到一个线性系统，其中是一个稀疏矩阵。一般采用经典的迭代法如Guassseidel迭代、Jaccobi迭代、SOR迭代等，不难发现如下一个事实：开始的几次迭代近似解与真解之间的误差衰减很快，但是后来的迭代误差去衰减很慢。而且系数矩阵的条件数越高，达到一定精度所需要的迭代次数越多。经过对迭代进行傅立叶分析，我们发现处在高频的误差分量在迭代的过程中迅速衰减，而处在低频的误差分量确衰减的很慢。为了解决这个问题，多重网格方法应运而生。通过局部松驰后误差呈现光滑性，此时误差主要来源于边界。可以设想二维网格上的点松驰方法，将边界信息传播到所有点至少需O(N)次迭代，因此收敛速度奇慢。不妨将网格方程的剩余部分(残差)限制到粗网格上进行。在粗网格上精确求解后，将所得解延拓到细网格上，与原来近似解组合，形成网格方程的近似解，称这一过程为粗网格校正。在粗网格上，由于网格点少，边界信息能较快地传播到所有网格点，收敛速度将加快。同样地，在粗网格上也存在高、低频误差，类似于细网格，进行几次局部松弛消除高频误差后，可以将低频误差再转移到更高层网格。如此进行下去，直到最高层网格，那里未知量个数非常少，直接精确求解的工作量可忽略不计。然后从高层到低层依次将所得解返回、组合，在最细网格上最终形成一个近似解，这一递归性质称为套迭代技术。多重网格算法就是这样将问题的求解分布在不同的层上，所有层相互协调地求解同一问题的。实际上，此时的粗网格校正就是起到将边界信息迅速传播到所有网格点的作用。细网格松弛、粗网格校正和套迭代技术是多重网格算法的三大支柱。细网格松弛负责消除高频振荡误差，粗网格校正负责消除低频光滑误差，套迭代技术负责通过限制和延拓算子连接所有层共同求解同一问题。可见多重网格算法的基本思想是：（1）一个问题能在不同规模的网格上求解；（2）细网格仅仅只需负责消除高频误差，而粗网格负责消除低频误差。2.2多重网格方法的应用原则下面从算法对物理问题的离散格式、松弛方法、限制与延拓、网格粗化策略以及套迭代技术的需求，分别阐述应用多重网格算法的基本准则。离散格式 离散格式必须是稳定的。格式的数值稳定性是一种局部行为，将导致解的局部高频振荡，使得松弛方法在细网格上无法有效光滑误差，从而使多重网格算法的效率将很低，甚至发散。而离散解光滑部分的稳定性一般仅仅依赖于微分方程本身的稳定性，与离散格式关系不大。当然，物理问题本身的稳定性是一个基本前提。由于离散格式的稳定性是局部行为，要求离散格式能将方程本身在一个或者几个网格步长上的所有振荡较好地描述出来，以便于松弛方法有效地消除。但是，对给定的步长h，只判断格式是否稳定是不够地，还应该给出一个尺度来刻画这种稳定性的程度。h一椭圆性就是一个很好的判别方法。具有h一椭圆性的离散格式，都必定存在一种有效的松弛方法，消除所有高频误差。松弛方法 总原则是让残差从细网格限制到粗网格之前充分光滑。光滑效应的度量采用光滑因子，可通过局部模分析方法简单地获取。若在每层网格上松弛次，则可用预测多重网格算法的近似最优收敛因子。松弛时要注意以下几点：（1）每层网格上松弛次数不宜过多(一般2一3次)，只需要消除高频误差，因为松弛到一定程度，低频误差将占主导地位，与高频误差相互祸合，无助于限制之前残差的光滑。（2）最好具有数值稳定性，避免迭代过程中的高频振荡。（3）点松弛方法仅光滑最强藕合方向的误差，对存在次藕合方向的问题，如各向异性问题、奇异扰动问题，则必须采取块迭代方法，如线松弛、平面松弛，使位于同一块的所有未知量被同时松弛或者使强祸合方向的未知量被同时松弛。（4）光滑因子不宜过小，一般使得多重网格算法的收敛因子在0.1左右为最佳。Guass一Seidel迭代是一个较好的选择。（5）光滑方法尽量追求Robust性，使多重网格算法适应多种类型的问题。限制与延拓 主要考虑算子的阶，它们依赖于原始方程中导数的阶。设含有q个未知函数的q个微分方程。表示第j个未知函数在第i个方程中的最高导数的阶。设这j个未知函数在限制和延拓过程中相互独立。令表示第j个未知函数的延拓阶，表示第i个方程残差限制阶。则应有以下关系式成立：（1）低频调和空间中高频通过粗网格校正振幅被放大倍。故为了避免由于粗网格校正引起高频振荡，应有，同时也可以看出是不必要的。（2）细网格限制时，每个高频对低频振幅的贡献为，故应有，对那些高、低频相互祸合的松弛方法，如Gauss一Seidel迭代，还应有，其中为高频误差在第j个方程由于松弛所产生的对低频的贡献。（3） 对完全多重网格算法(FMG)，第j个未知函数从粗网格到细网格第一次延拓的阶，必须满足，以保证细网格上第一次出现的高频误差的阶不小于微分方程的离散阶p，其中为第j个方程微分算子的阶。网格粗化策略 从程序设计的模块化、易移植性出发，一般采用标准网格粗化策略(步长在所有方向扩大一倍)。但为了保持点松弛，对特殊问题可以采用半粗化策略，即仅粗化藕合方向网格，使之也变为强藕合方向。粗网格上方程离散格式和迭代方法都可以与细网格上的不同，对对称正定算子，典型代表为Galerski近似。套迭代技术 一般采用V或W循环，W循环能保持收敛因子不随网格的变化而变化，具有Robust性，但代价相对昂贵；当网格层不多时，V循环具有同样的性质，但计算量小，因此更受欢迎。除此之外，还存在S循环、F循环，它们的性能介于V循环与W循环之间，视具体情况可分别采用。2.3多重网格方法最简单的椭圆型问题是Poisson方程 （2.2）多重网格算法迭代的基本步骤：对式 (2.2)进行离散，得到的方程组Lu=f （2.3）其中，L是个经过离散所得到的系数矩阵。在网格步长为h(细网格)的网格点上，方程满足 (2.4)对于方程 (2.4)传统的迭代方法是在确定的一种网格上采用某种迭代解法，例如Gauss一Seidel迭代法、超松弛法(SOR)以及它们改进的迭代技术，而多重网格方法采用不同等级的网格剖分。假定有一组网格称为网格序列，随着k的增加，网格越来越细，这些网格都逼近同一区域，相应的有网格步长序列，算子序列。与传统计算方法不同，多重网格方法采用一系列不同步长的网格层。因为场值的误差在粗网格层上剧烈摆动，因此在粗网格层上对误差进行迭代将加快收敛速度。误差从细网格层到粗网格层的变换过程称为限制，即将细网格层上与某一网格点相邻的若干个点的信息通过一定的权重浓缩到粗网格层的该点。在粗网格层上对场值的误差进行迭代后，必须将粗网格层上的误差通过插值补充出细网格层上的函数值，这一插值过程称为延拓。可以看出，限制和延拓是互逆的。在每一层网格迭代前对场值的误差进行限制，完成最粗一层网格迭代后对其进行延拓。多重网格法的一个重要方面就是通过递归调用二重网格方法来做近似。也就是残差方程不是通过直接方法求解，而是用几次松弛磨光来磨掉高频误差，当然是伴随向更粗一级网格上残差限制，这就是多重网格法的思想。这样多重网格方法的一系列问题将在不同网格大小的嵌套网格上得到解决。多重网格算法根据在每层上作校正循环的次数又可以分为多重网格V一循环和多重网格W一循环算法。多重网格V一循环算法是从最细网格一直到最粗网格，然后又返回到最细网格上的一种计算过程。如果一个V一循环算法是在每层上作二次校正循环，然后返回到下一级细网上，这就是多重网格W一循环算法。2.4 计算结果和分析单一网格和多重网格的比较考虑以下的二维线性对流扩散方程的定解问题 （1）选择这一定解问题主要是可求得其精确解，以检验所给出的混合有限分析多重网格法计算的有效性，求得此定解问题的精确解是 （2）取x向和y向步长为h和k，将计算区域进行均匀剖分，在离散网格上建立方程（1）的混合有限分析格式 （3）将计算区域均匀剖分为3333个结点，单一网格和多重网格中最细网格的步长0.03125。多重网格取4层，最粗网格步长为0.25。计算中取方程(l)中b=12。在单一网格上求代数方程组(3)的收敛解。对于多重网格，因方程(l)是线性的，故在每层网格上的混合有限分析系数仅与该层步长有关。具体计算是在最细网格上完成一次迭代后，嵌入多重网格循环，我们采用V循环。收敛判据取，对于多重网格收敛要求最细网格上残差范数，其中和是最细网格上x和y方向的最大结点数；是最细网格结点(i，j)上的残差。图l是计算区域对角线上的计算结果与精确解的比较.可见无论是单一网格还是多重网格用混合有限分析法计算结果都是同精确解吻合的很好。图2是迭代的收敛过程，也是残差的衰减过程。图中的工作单位(W.U)等价于在最细网格上进行一次单独的光滑迭代所需的计算量。对于标准粗化系列，较粗网格上4次迭代相当于相邻细网上一次迭代。由图可以看出多重网格法的收敛速度比单一网格法快很多，所需工作单位少得多，计算证实了多重网格法的优越性.图中A、B、C表示第一、二、三个多重网格循环步。最细网格剖分17X17 33X33 65X65 129X129网格层数 3 4 5 6最细网格步长0.0625 0.03125 0.015625 0.0078125最粗网格步长0.25 0.25 0.25 0.25图4给出了4种不同疏密剖分时，应用单一网格方法和多重网格方法计算达到收敛解所需的工作单位。可以看出随着剖分的加密，单一网格方法达到收敛所需的迭代次数显著增加，而多重网格方法所需迭代次数基本上不随网格的疏密和层数而变化。这表明多重网格方法具有与网格参数无关的收敛性。图5是4套多重网格的收敛曲线。可以看出这些曲线的斜率，即收敛率是基本上相同的。也就是说，多重网格方法的收敛率不受网格疏密的影响。三、多重网格方法的一种并行模式作为求解离散微分方程的一种迭代法，多重网格方法有效地利用了迭代过程的误差校正特性和对高频误差分量的光滑特性，改变了传统的作法，作了变革性的构造。其敛速与步长h无关，计算工作量为O(N)(N为离散格点数)。总之，多重网格法是一种高效率迭代法。在求解边值问题的近似解方面，为了高效求解大型方程组的需要，人们尝试并行处理。而区域分解法是并行计算最活跃的研究和应用领域之一。其基本方法是把一个复杂区域(或系统)，按照一定原则(如物理特性、几何形状、离散方式、算法特点与处理器个数)分解成若干子系统，主要采用高效快速迭代法求解原始问题。基于以上原因，提出了一种并行的多重网格方法交错多重网格法。其对边值问题的并行处理有别于通常的区域分解方法。通常的区域分解是将复杂区域分解成较小的子区域(重叠或不重叠)的和集。而交错多重网格法的思路是先将大区域离散划分成网格，然后于网格中交错取点，分成若干较粗的子网格，将这些子网格置于不同的处理器上，用通常的多重网格法计算其上边值问题。最后，将这些不同处理器粗网格上的解组合成大区域的网格上的近似解。从数学上看，交错多重网格方法思路如下：设有边值问题 （3.1）将划分为步长h的细网格后,问题(3.1)离散为求解方程组 （3.2）然后,于上细网格中交错取点,划分成步长H的较粗子网格.每个子网格上边值问题离散后的离散方程组为 (Hh) (2.3)设式(3.1)的解析解为u*,方程组(3.2)、(3.3)的精确解为,。随着h趋近于零，是趋近于u*。设用迭代法近似求解方程组(3.2)及(3.3)所得近似解为及。可以看出，想用组合成逼近的近似解是没有理论依据的。但是，可考虑用的组合作为较好的初始值，用合适的迭代法(包括多重网格方法)来求出满足精度要求的逼近的近似解。因此，利用交错多重网格法加快边界值的信息传递以得到较好的初值，并结合适当的迭代法求得满意精度的近似解。四、已取得的成果和待扩充的领域多重网格算法经过近30年的研究，在经典应用领域线性和非线性、标量和非标量椭圆型间题取得了丰硕的成果，每个未知量只需十多次算术运算便能在误差允许范围内正确求解，具有内在并行性，并且能适应这些情况：自由边界问题，狭小区域问题，各种类型的奇异与非连续性，局部网格细化，严重非线性问题，区域中含有粗网格上不可见的小洞问题，高振荡边界问题等等。在弹性力学，网格生成技术方面也取得了同样的效率。类似于椭圆型问题，从80年代开始，多重网格算法已深入到计算流体力学(CFD)，时间相关间题、波动方程、积分方程等领域。对流体力学Euler方程、Stokes方程、Navier-Stokes方程、位势方程中的大量定常与非定常问题，加入人工粘性，采用适当的离散格式(如迎风格式，矢通量分裂格式，半离散格式)后，能以同样的效率求解。在牺牲一至几个数量级效率条件下，可以成功求解含单族或多族特征线的高雷诺数不可压缩流问题。多重网格算法在求解来自波动方程的高不适定问题时，效果非常不理想，但如果转化为积分问题，则效果要好得多。同样，这种转换也适合求解特征值或特征函数问题。对时间相关抛物型问题，不但在求解隐式离散格式时与椭圆型算子具有同样的效率，而且只要问题本身在时间方向上光滑，则求解过程在时间方向访问细网格的次数很少，能迅速达到稳定状态。多重网格算法被推广到别的领域，取得了大量成果，如统计物理中的快速Monte一Carlo方法，积分变换，人工智能中N个体的相互关系识别，全局优化问题，图象处理，量子色动力