《多重网格算法综述》由会员分享，可在线阅读，更多相关《多重网格算法综述（10页珍藏版）》请在金锄头文库上搜索。
1、多重网格算法综述邹静文 102071406摘要 本文总结了多重网格算法的基础理论，剖析了多重网格方法的一种并行模式以及总结了已取得的成果和待扩充的领域。对多重网格方法的基本思想有一个较详细的概述，比较分析了单一网格和多重网格的计算结果，并对多重网格的并行模式进行了探索和分析。关键词 多重网格算法，套迭代，粗网格校正，并行模式，交错多重网格，区域分解一、引言多重网格法(Multiple Grid Method)，简称 MG 方法是近年来求解偏微分方程边值问题的快速方法之一，本文参考前人的文献资料，并结合所学知识，总结多重网格法的基础理论，包括多重网格的应用原则、具体实现步骤以及计算结果的分析和比
2、较。其计算结果表明：多重网格方法具有收敛速度快的优点，当多重网格方法所用层数越多，收效速度就越快；而且撞制粗、细网格层之间自适应转换的撞制参数在选取上有很大的灵活性；可以看出随着剖分的加密，单一网格方法达到收敛所需的迭代次数显著增加，而多重网格方法所需迭代次数基本上不随网格的疏密和层数而变化，这表明多重网格方法具有与网格参数无关的收敛性。二、多重网格方法的基础理论多重网格方法的最初被提出是由于在网格方程迭代求解时，误差的各个 Fourier 分量的衰减程度不同。认识到高频振荡误差是局部行为，来源于附近几个网格点之间的相互藕合，与边界或距离较远的网格点信息无关；而低频光滑误差是全局行为，主要来源
3、于边界信息。传统的点或块松弛都是局部性较强的方法，因此它们能迅速抹平局部性的高频振荡误差，但对全局性的低频光滑误差却衰减缓慢。实际上，经过初始几次迭代后，误差将呈现光滑性。所以，习惯上称能迅速抹平高频振荡误差，使误差趋于光滑的松驰方法为有效光滑方法，并用松驰因子来刻画它们的光滑效应。2.1 多重网格方法思想的引入考虑在简单区域 上泊松方程的第一类边值问题(狄立克雷边值问题) ：(,)(,)0uxyfxy这里 是一个单位正方形， 是这个正方形的边界如下图所示：在以步长为 h 的网格上 离散后，得到一个线性系统 ，其中 是一个稀疏hhLufhL矩阵。一般采用经典的迭代法如 Guassseidel
4、迭代、Jaccobi 迭代、SOR 迭代等，不难发现如下一个事实：开始的几次迭代近似解与真解之间的误差衰减很快，但是后来的迭代误差去衰减很慢。而且系数矩阵 的条件数越高，达到一定精度所需要的迭代次数越多。经hL过对迭代进行傅立叶分析，我们发现处在高频的误差分量在迭代的过程中迅速衰减，而处在低频的误差分量确衰减的很慢。为了解决这个问题，多重网格方法应运而生。通过局部松驰后误差呈现光滑性，此时误差主要来源于边界。可以设想二维 网格上的点松驰N方法，将边界信息传播到所有点至少需 O(N)次迭代，因此收敛速度奇慢。不妨将网格方程的剩余部分(残差)限制到粗网格上进行。在粗网格上精确求解后，将所得解延拓到
5、细网格上，与原来近似解组合，形成网格方程的近似解，称这一过程为粗网格校正。在粗网格上，由于网格点少，边界信息能较快地传播到所有网格点，收敛速度将加快。同样地，在粗网格上也存在高、低频误差，类似于细网格，进行几次局部松弛消除高频误差后，可以将低频误差再转移到更高层网格。如此进行下去，直到最高层网格，那里未知量个数非常少，直接精确求解的工作量可忽略不计。然后从高层到低层依次将所得解返回、组合，在最细网格上最终形成一个近似解，这一递归性质称为套迭代技术。多重网格算法就是这样将问题的求解分布在不同的层上，所有层相互协调地求解同一问题的。实际上，此时的粗网格校正就是起到将边界信息迅速传播到所有网格点的作
6、用。细网格松弛、粗网格校正和套迭代技术是多重网格算法的三大支柱。细网格松弛负责消除高频振荡误差，粗网格校正负责消除低频光滑误差，套迭代技术负责通过限制和延拓算子连接所有层共同求解同一问题。可见多重网格算法的基本思想是：（1）一个问题能在不同规模的网格上求解；（2）细网格仅仅只需负责消除高频误差，而粗网格负责消除低频误差。2.2 多重网格方法的应用原则下面从算法对物理问题的离散格式、松弛方法、限制与延拓、网格粗化策略以及套迭代技术的需求，分别阐述应用多重网格算法的基本准则。离散格式 离散格式必须是稳定的。格式的数值稳定性是一种局部行为，将导致解的局部高频振荡，使得松弛方法在细网格上无法有效光滑误
7、差，从而使多重网格算法的效率将很低，甚至发散。而离散解光滑部分的稳定性一般仅仅依赖于微分方程本身的稳定性，与离散格式关系不大。当然，物理问题本身的稳定性是一个基本前提。由于离散格式的稳定性是局部行为，要求离散格式能将方程本身在一个或者几个网格步长上的所有振荡较好地描述出来，以便于松弛方法有效地消除。但是，对给定的步长 h，只判断格式是否稳定是不够地，还应该给出一个尺度来刻画这种稳定性的程度。h 一椭圆性就是一个很好的判别方法。具有 h 一椭圆性的离散格式，都必定存在一种有效的松弛方法，消除所有高频误差。松弛方法 总原则是让残差从细网格限制到粗网格之前充分光滑。光滑效应的度量采用光滑因子 ，可通
8、过局部模分析方法简单地获取。若在每层网格上松弛 次，则可用 预测多重网格算法的近似最优收敛因子。松弛时要注意以下几点：（1）每层网格上松弛次数不宜过多(一般 2 一 3 次) ，只需要消除高频误差，因为松弛到一定程度，低频误差将占主导地位，与高频误差相互祸合，无助于限制之前残差的光滑。（2）最好具有数值稳定性，避免迭代过程中的高频振荡。（3）点松弛方法仅光滑最强藕合方向的误差，对存在次藕合方向的问题，如各向异性问题、奇异扰动问题，则必须采取块迭代方法，如线松弛、平面松弛，使位于同一块的所有未知量被同时松弛或者使强祸合方向的未知量被同时松弛。（4）光滑因子不宜过小，一般使得多重网格算法的收敛因子
9、在 0.1 左右为最佳。Guass一 Seidel 迭代是一个较好的选择。（5）光滑方法尽量追求 Robust 性，使多重网格算法适应多种类型的问题。限制与延拓 主要考虑算子的阶，它们依赖于原始方程中导数的阶。设含有 q 个未知函数的 q 个微分方程。 表示第 j 个未知函数在第 i 个方程中的最高导数的阶。设这 j 个未ijm知函数在限制和延拓过程中相互独立。令 表示第 j 个未知函数的延拓阶， 表示第 i 个jmim方程残差限制阶。则应有以下关系式成立：（1）低频调和空间中高频通过粗网格校正振幅被放大 倍。故为了,1()jiiijOh避免由于粗网格校正引起高频振荡，应有 ， ，同时也可以看
10、出,jiij是不必要的。,1jiijm（2）细网格限制时，每个高频对低频振幅的贡献为 ，故应有 ，对,()ijmOhiijm那些高、低频相互祸合的松弛方法，如 Gauss 一 Seidel 迭代，还应有 ，()iijkr其中 为高频误差在第 j 个方程由于松弛所产生的对低频的贡献。()kjOr（3） 对完全多重网格算法(FMG)，第 j 个未知函数从粗网格到细网格第一次延拓的阶，必须满足 ，以保证细网格上第一次出现的高频误差的阶不小于微分方程jmjjpl的离散阶 p，其中 为第 j 个方程微分算子的阶。j网格粗化策略 从程序设计的模块化、易移植性出发，一般采用标准网格粗化策略( 步长在所有方向
11、扩大一倍)。但为了保持点松弛，对特殊问题可以采用半粗化策略，即仅粗化藕合方向网格，使之也变为强藕合方向。粗网格上方程离散格式和迭代方法都可以与细网格上的不同，对对称正定算子，典型代表为 Galerski 近似。套迭代技术 一般采用 V 或 W 循环，W 循环能保持收敛因子不随网格的变化而变化，具有 Robust 性，但代价相对昂贵；当网格层不多时，V 循环具有同样的性质，但计算量小，因此更受欢迎。除此之外，还存在 S 循环、F 循环，它们的性能介于 V 循环与 W 循环之间，视具体情况可分别采用。2.3 多重网格方法最简单的椭圆型问题是 Poisson 方程（2.2）,dufQR多重网格算法迭
12、代的基本步骤：对式 (2.2)进行离散，得到的方程组Lu=f （2.3）其中，L 是个经过离散所得到的系数矩阵。在网格步长为 h(细网格) 的网格点上，方程满足 (2.4)hLuf对于方程 (2.4)传统的迭代方法是在确定的一种网格 上采用某种迭代解法，例如 Gaussh一 Seidel 迭代法、超松弛法 (SOR)以及它们改进的迭代技术，而多重网格方法采用不同等级的网格剖分。假定有一组网格 称为网格序列 ，随着 k01,.,l (0,1.)kl的增加，网格越来越细，这些网格都逼近同一区域 ，相应的有网格步长序列 ，算子序kh列 。kL与传统计算方法不同，多重网格方法采用一系列不同步长的网格层
13、。因为场值的误差在粗网格层上剧烈摆动，因此在粗网格层上对误差进行迭代将加快收敛速度。误差从细网格层到粗网格层的变换过程称为限制，即将细网格层上与某一网格点相邻的若干个点的信息通过一定的权重浓缩到粗网格层的该点。在粗网格层上对场值的误差进行迭代后，必须将粗网格层上的误差通过插值补充出细网格层上的函数值，这一插值过程称为延拓。可以看出，限制和延拓是互逆的。在每一层网格迭代前对场值的误差进行限制，完成最粗一层网格迭代后对其进行延拓。多重网格法的一个重要方面就是通过递归调用二重网格方法来做近似。也就是残差方程不是通过直接方法求解，而是用几次松弛磨光来磨掉高频误差，当然是伴随向更粗一级网格上残差限制，这
14、就是多重网格法的思想。这样多重网格方法的一系列问题将在不同网格大小的嵌套网格上得到解决。多重网格算法根据在每层上作校正循环的次数又可以分为多重网格 V 一循环和多重网格 W 一循环算法。多重网格 V 一循环算法是从最细网格一直到最粗网格，然后又返回到最细网格上的一种计算过程。如果一个V 一循环算法是在每层上作二次校正循环，然后返回到下一级细网上，这就是多重网格 W一循环算法。2.4 计算结果和分析单一网格和多重网格的比较考虑以下的二维线性对流扩散方程的定解问题（1）2(),()0,1()uubxyxyep(0,),(1),exp,()2(,0).bbuux选择这一定解问题主要是可求得其精确解，
15、以检验所给出的混合有限分析多重网格法计算的有效性，求得此定解问题的精确解是（2）exp()1exp()1(,)bbyuy取 x 向和 y 向步长为 h 和 k，将计算区域 进行均匀剖分，在离散网格(0,)上建立方程（1）的混合有限分析格式（3）111, ,1,nnnnijijijijijijijijijCuuCu 将计算区域均匀剖分为 33 33 个结点，单一网格和多重网格中最细网格的步长0.03125。多重网格取 4 层，最粗网格步长为 0.25。计算中取方程(l)中hk 8hkb=12。在单一网格上求代数方程组(3)的收敛解。对于多重网格，因方程(l)是线性的，故在每层网格上的混合有限分析
16、系数仅与该层步长有关。具体计算是在最细网格上完成一次迭代后，嵌入多重网格循环，我们采用 V 循环。收敛判据取 ，对于多重网格收敛要求最细网格上残差范数 ，510 cR，21/2(,)/ccijRjNXY其中 和 是最细网格上 x 和 y 方向的最大结点数；maxax()(),NXYIJmaxIaJ是最细网格结点(i，j)上的残差。(,)cRij图 l 是计算区域对角线上的计算结果与精确解的比较 .可见无论是单一网格还是多重网格用混合有限分析法计算结果都是同精确解吻合的很好。图 2 是迭代的收敛过程，也是残差的衰减过程。图中的工作单位(W.U)等价于在最细网格上进行一次单独的光滑迭代所需的计算量。对于标准粗化系列，较粗网格上 4 次迭代相当于相邻细网上一次迭代。由图可以看出多重网格法的收敛速度比单一网
