多重网格算法综述

《多重网格算法综述》由会员分享，可在线阅读，更多相关《多重网格算法综述（10页珍藏版）》请在装配图网上搜索。

1、多重网格算法综述邹静文6摘要 本文总结了多重网格算法的基础理论，剖析了多重网格方式的一种并行模式和总结了 已取得的功效和待扩充的领域。对多重网格方式的大体思想有一个较详细的概述，比较分析 了单一网格和多重网格的计算结果，并对多重网格的并行模式进行了探讨和分析。关键词 多重网格算法，套迭代，粗网格校正，并行模式，交织多重网格，区域分解一、引言多重网格法(Multiple Grid Method)，简称MG方式是最近几年来求解偏微分方程边值 问题的快速方式之一，本文参考前人的文献资料，并结合所学知识，总结多重网格法的基础 理论，包括多重网格的应用原那么、具体实现步骤和计算结果的分析和比较。其计算结

2、果说 明：多重网格方式具有收敛速度快的优势，当多重网格方式所用层数越多，生效速度就越快; 而且撞制粗、细网格层之间自适应转换的撞制参数在选取上有专门大的灵活性；能够看出随 着剖分的加密，单一网格方式达到收敛所需的迭代次数显著增加，而多重网格方式所需迭代 次数大体上不随网格的疏密和层数而转变，这说明多重网格方式具有与网格参数无关的收敛 性。二、多重网格方式的基础理论多重网格方式的最初被提出是由于在网格方程迭代求解时，误差的各个Fourier分量的 衰减程度不同。熟悉到高频振荡误差是局部行为，来源于周围几个网格点之间的彼此藕合， 与边界或距离较远的网格点信息无关；而低频滑腻误差是全局行为，要紧来源

3、于边界信息。 传统的点或块松弛都是局部性较强的方式，因此它们能迅速抹平局部性的高频振荡误差，但 对全局性的低频滑腻误差却衰减缓慢。事实上，通过初始几回迭代后，误差将呈现滑腻性。 因此，适应上称能迅速抹平高频振荡误差，使误差趋于滑腻的松驰方式为有效滑腻方式，并 用松驰因子来刻画它们的滑腻效应。多重网格方式思想的引入考虑在简单区域Q上泊松方程的第一类边值问题(狄立克雷边值问题)：f-Aw3, y) = f 3, y),(x, y) eQu (x, y) = 0,( x, y) edQ那个地址Q是一个单位正方形，8Q是那个正方形的边界如以下图所示：u=0在以步长为h的网格上Qh离散后，取得一个线性系

4、统Luh =二，其中Lh是一个稀疏 矩阵。一样采纳经典的迭代法如Guass - seidel迭代、Jaccobi迭代、SOR迭代等，不难发觉 如下一个事实：开始的几回迭代近似解与真解之间的误差衰减专门快，可是后来的迭代误差 去衰减很慢。而且系数矩阵L的条件数越高，达到必然精度所需要的迭代次数越多。通过 h对迭代进行傅立叶分析，咱们发觉处在高频的误差分量在迭代的进程中迅速衰减，而处在低 频的误差分量确衰减的很慢。为了解决那个问题，多重网格方式应运而生。通过局部松驰后 误差呈现滑腻性，现在误差要紧来源于边界。能够假想二维N x N网格上的点松驰方式， 将边界信息传播到所有点至少需O(N)次迭代，因

5、此收敛速度奇慢。不妨将网格方程的剩余 部份(残差)限制到粗网格上进行。在粗网格上精准求解后，将所得解延拓到细网格上，与原 先近似解组合，形成网格方程的近似解，称这一进程为粗网格校正。在粗网格上，由于网格 点少，边界信息能较快地传播到所有网格点，收敛速度将加速。一样地，在粗网格上也存在 高、低频误差，类似于细网格，进行几回局部松弛排除高频误差后，能够将低频误差再转移 到更高层网格。如此进行下去，直到最高层网格，那里未知量个数超级少，直接精准求解的 工作量可忽略不计。然后从高层到低层依次将所得解返回、组合，在最细网格上最终形成一 个近似解，这一递归性质称为套迭代技术。多重网格算法确实是如此将问题的

6、求解散布在不 同的层上，所有层彼此和谐地求解同一问题的。事实上，现在的粗网格校正确实是起到将边 界信息迅速传播到所有网格点的作用。细网格松弛、粗网格校正和套迭代技术是多重网格算法的三大支柱。细网格松弛负责排 除高频振荡误差，粗网格校正负责排除低频滑腻误差，套迭代技术负责通过限制和延拓算子连接所有层一起求解同一问题。可见多重网格算法的大体思想是：（1）一个问题能在不同规模的网格上求解；（2）细网格仅仅只需负责排除高频误差，而粗网格负责排除低频误差。多重网格方式的应用原那么下面从算法对物理问题的离散格式、松弛方式、限制与延拓、网格粗化策略和套迭代技 术的需求，别离论述应用多重网格算法的大体准那么。

7、离散格式离散格式必需是稳固的。格式的数值稳固性是一种局部行为，将致使解的局 部高频振荡，使得松弛方式在细网格上无法有效滑腻误差，从而使多重网格算法的效率将很 低，乃至发散。而离散解滑腻部份的稳固性一样仅仅依托于微分方程本身的稳固性，与离散 格式关系不大。固然，物理问题本身的稳固性是一个大体前提。由于离散格式的稳固性是局部行为，要求离散格式能将方程本身在一个或几个网格步长 上的所有振荡较好地描述出来，以便于松弛方式有效地排除。可是，对给定的步长h，只判 定格式是不是稳固是不够地，还应该给出一个尺度来刻画这种稳固性的程度。h 一椭圆性确 实是一个专门好的判别方式。具有h 一椭圆性的离散格式，都必然

8、存在一种有效的松弛方式， 排除所有高频误差。松弛方式总原那么是让残差从细网格限制到粗网格之前充分滑腻。滑腻效应的气宇采 纳滑腻因子R，可通过局部模分析方式简单地获取。假设在每层网格上松弛v次，那么可用PV预测多重网格算法的近似最优收敛因子。松弛时要注意以下几点：（1）每层网格上松弛次数不宜过量（一样2 一 3次），只需要排除高频误差，因为松弛到 必然程度，低频误差将占主导地位，与高频误差彼此祸合，无助于限制之前残差的滑腻。（2）最好具有数值稳固性，幸免迭代进程中的高频振荡。（3）点松弛方式仅滑腻最强藕合方向的误差，对存在次藕合方向的问题，如各向异性问 题、奇异扰动问题，那么必需采取块迭代方式，

9、如线松弛、平面松弛，使位于同一块的所有 未知量被同时松弛或使强祸合方向的未知量被同时松弛。（4）滑腻因子不宜过小，一样使得多重网格算法的收敛因子在左右为最正确Guass 一 Seidel迭代是一个较好的选择。（5）滑腻方式尽可能追求Robust性，使多重网格算法适应多种类型的问题。限制与延拓要紧考虑算子的阶，它们依托于原始方程中导数的阶。设含有q个未知函 数的q个微分方程。%表示第j个未知函数在第i个方程中的最高导数的阶。设这j个未知 函数在限制和延拓进程中彼此独立。令mj表示第j个未知函数的延拓阶，mi表示第i个方程残差限制阶。那么应有以下关系式成立:（1）低频调和空间中高频通过粗网格校正振

10、幅被放大1 + O（Z伽+mm）倍。故为了 ，j幸免由于粗网格校正引发高频振荡，应有m + mj m_，同时也能够看出 m + mj m +1是没必要要的。（2）细网格限制时，每一个高频对低频振幅的奉献为0（，气盘），故应有m 2 m，对 那些高、低频彼此祸合的松弛方式，如Gauss 一 Seidel迭代，还应有m Z （m七）, 其中O（rj为高频误差在第j个方程由于松弛所产生的对低频的奉献。（3）对完全多重网格算法（FMG），第j个未知函数从粗网格到细网格第一次延拓的阶 m，必需知足m p+匕，以保证细网格上第一次显现的高频误差的阶不小于微分方程的 离散阶p，其中匕为第j个方程微分算子的阶

11、。网格粗化策略从程序设计的模块化、易移植性动身，一样采纳标准网格粗化策略（步长 在所有方向扩大一倍）。但为了维持点松弛，对特殊问题能够采纳半粗化策略，即仅粗化藕 合方向网格，使之也变成强藕合方向。粗网格上方程离散格式和迭代方式都能够与细网格上 的不同，对对称正定算子，典型代表为Galerski近似。套迭代技术一样采纳V或W循环，W循环能维持收敛因子不随网格的转变而转变， 具有Robust性，但代价相对昂贵；当网格层不多时，V循环具有一样的性质，但计算量小， 因此更受欢迎。除此之外，还存在S循环、F循环，它们的性能介于V循环与W循环之间， 视具体情形可别离采纳。多重网格方式最简单的椭圆型问题是P

12、oisson方程-Aw = f,Q u Rd（）多重网格算法迭代的大体步骤：对式进行离散，取得的方程组Lu=f（）其中，L是个通过离散所取得的系数矩阵。在网格步长为h（细网格）的网格点上，方程知足LhUh = fh关于方程传统的迭代方式是在确信的一种网格%上采纳某种迭代解法，例如Gauss 一 Seidel迭代法、超松弛法(SOR)和它们改良的迭代技术，而多重网格方式采纳不同品级的网 格剖分。假定有一组网格。，町,称为网格序列*(k = 0,1,.,l)，随着k的增加， 网格愈来愈细，这些网格都逼近同一区域，相应的有网格步长序列q，算子序列匕。与传统计算方式不同，多重网格方式采纳一系列不同步长

13、的网格层。因为场值的误差在 粗网格层上猛烈摆动，因此在粗网格层上对误差进行迭代将加速收敛速度。误差从细网格层 到粗网格层的变换进程称为限制，即将细网格层上与某一网格点相邻的假设干个点的信息通 过必然的权重浓缩到粗网格层的该点。在粗网格层上对场值的误差进行迭代后，必需将粗网 格层上的误差通过插值补充出细网格层上的函数值，这一插值进程称为延拓。能够看出，限 制和延拓是互逆的。在每一层网格迭代前对场值的误差进行限制，完成最粗一层网格迭代后 对其进行延拓。多重网格法的一个重要方面确实是通过递归挪用二重网格方式来做近似。也 确实是残差方程不是通过直接方式求解，而是用几回松弛磨光来磨掉高频误差，固然是伴随

14、 向更粗一级网格上残差限制，这确实是多重网格法的思想。如此多重网格方式的一系列问题 将在不同网格大小的嵌套网格上取得解决。多重网格算法依照在每层上作校正循环的次数又 能够分为多重网格V 循环和多重网格W 一循环算法。多重网格V 一循环算法是从最细网 格一直到最粗网格，然后又返回到最细网格上的一种计算进程。若是一个V 一循环算法是 在每层上作二次校正循环，然后返回到下一级细网上，这确实是多重网格W 一循环算法。计算结果和分析一一单一网格和多重网格的比较考虑以下的二维线性对流扩散方程的定解问题du 8、 d2 d2 ,b( + ) = + ,(x,y) e (0,1)x (0,1)(1)exp(b

15、y) -1u (0, y) = 0, u (1, y) = 1 +,exp b -1 exp(bx) -1u (x,0) =, u (x,1) = 2u (x,0).exp b -1选择这必然解问题主若是可求得其精准解，以查验所给出的混合有限分析多重网格法计算的有效性，求得此定解问题的精准解是u (x, y)=(2)exp(bx) -1 1 * exp(by) -1exp b -1 exp b -1取X向和y向步长为h和k,将计算区域Q（0,1）X （0,1）进行均匀剖分，在离散网格上 成立方程（1）的混合有限分析格式Cun+1+ un+1- Cun+1= CUn+1+ CUn（3）i, j-

16、1 i,j-1ji, j+1 i,j+1i-1,j i-1,ji+1, j i+1, j将计算区域均匀剖分为33 x 33个结点，单一网格和多重网格中最细网格的步长h = k =。多重网格取4层，最粗网格步长为8h = 8k =。计算中取方程（l）中b=12。在单一网格上求代数方程组（3）的收敛解。关于多重网格，因方程（l）是线性的，故在 每层网格上的混合有限分析系数仅与该层步长有关。具体计算是在最细网格上完成一次迭代 后，嵌入多重网格循环，咱们采纳V循环。收敛判据取8=10-5，关于多重网格收敛要求最细网格上残差范数R 8，R = Z R2（i,j）/ NXY 1/2， ccij其中NXY

17、= （Imax 1）x（JmaxT）max和Jmax是最细网格上x和y方向的最大结点数；R （i, j）是最细网格结点（i，j）上的残差。 c图l是计算区域对角线上的计算结果与精准解的比较.可见不管是单一网格仍是多重网 格用混合有限分析法计算结果都是同精准解吻合的专门好。住】1 E瑁线上i十算值图2是迭代的收敛进程，也是残差的衰减进程。图中的工作单位等价于在最细网格上进 行一次单独的滑腻迭代所需的计算量。关于标准粗化系列，较粗网格上4次迭代相当于相邻 细网上一次迭代。由图能够看出多重网格法的收敛速度比单一网格法快很多，所需工作单位 少得多，计算证明了多重网格法的优越性图中A、B、C表示第一、二

18、、三个多重网格循环 步。一1. 50以亳 10 测 3D 40506。图2 收鼓曲线最细网格剖分 17X1733X33 65X65 129X129网格层数 3456最细网格步长最粗网格步长图4给出了 4种不同疏密剖分时，应用单一网格方式和多重网格方式计算达到收敛解所 需的工作单位。能够看出随着剖分的加密，单一网格方式达到收敛所需的迭代次数显著增加， 而多重网格方式所需迭代次数大体上不随网格的疏密和层数而转变。这说明多重网格方式具 有与网格参数无关的收敛性。图5是4套多重网格的收敛曲线。能够看出这些曲线的斜率，即收敛率是大体上相同的。 也确实是说，多重网格方式的收敛率不受网格疏密的阻碍。-2.

19、01)-2. 50-3. QQ-3. 50J 0C4. 53-5. 005. 501W图! 达到枚魏衅所需作单位三、多重网格方式的一种并行模式作为求解离散微分方程的一种迭代法，多重网格方式有效地利用了迭代进程的误差校正 特性和对高频误差分量的滑腻特性，改变了传统的作法，作了变革性的构造。其敛速与步长 h无关，计算工作量为O（N）（N为离散格点数）。总之，多重网格法是一种高效率迭代法。在求解边值问题的近似解方面，为了高效求解大型方程组的需要，人们尝试并行处置。 而区域分解法是并行计算最活跃的研究和应用领域之一。其大体方式是把一个复杂区域（或 系统），依照必然原那么（如物理特性、几何形状、离散方式

20、、算法特点与处置器个麴分解成 假设干子系统，要紧采纳高效快速迭代法求解原始问题。基于以上缘故，提出了一种并行的多重网格方式一一交织多重网格法。其对边值问题的 并行处置有别于通常的区域分解方式。通常的区域分解是将复杂区域分解成较小的子区域 （重叠或不重叠）的和集。而交织多重网格法的思路是先将大区域离散划分成网格，然后于网 格中交织取点，分成假设干较粗的子网格，将这些子网格置于不同的处置器上，用通常的多 重网格法计算其上边值问题。最后，将这些不同处置器粗网格上的解组合成大区域的网格上 的近似解。从数学上看，交织多重网格方式思路如下：设有边值问题一u = f,在。上h)设式的解析解为u*,方程组、的

21、精准解为u；,u；。随着h趋近于零，%是趋近于u*。设 用迭代法近似求解方程组及所得近似解为uh及uh。能够看出，想用uh组合成逼近%的近 似解是没有理论依据的。可是，可考虑用uH的组合作为较好的初始值，用适合的迭代法(包 括多重网格方式)来求出知足精度要求的逼近u的近似解。因此，利用交织多重网格法加速 边界值的信息传递以取得较好的初值，并结适合当的迭代法求得中意精度的近似解。四、已取得的功效和待扩充的领域多重网格算法通过近30年的研究，在经典应用领域一线性和非线性、标量和非标量椭 圆型间题取得了丰硕的功效，每一个未知量只需十多次算术运算便能在误差许诺范围内正确 求解，具有内在并行性，而且能适

22、应这些情形：自由边界问题，狭小区域问题，各类类型的奇 异与非持续性，局部网格细化，严峻非线性问题，区域中含有粗网格上不可见的小洞问题， 高振荡边界问题等等。在弹性力学，网格生成技术方面也取得了一样的效率。类似于椭圆型问题，从80年代开始，多重网格算法已深切到计算流体力学(CFD)，时 刻相关间题、波动方程、积分方程等领域。对流体力学Euler方程、Stokes方程、Navier-Stokes 方程、位势方程中的大量定常与非定常问题，加入人工粘性，采纳适当的离散格式(如迎风 格式，矢通量割裂格式，半离散格式)后，能以一样的效率求解。在捐躯一至几个数量级效 率条件下，能够成功求解含单族或多族特点线

23、的高雷诺数不可紧缩流问题。多重网格算法在求解来自波动方程的高不适定问题时，成效超级不睬想，但如果是转化 为积分问题，那么成效要好得多。一样，这种转换也适合求解特点值或特点函数问题。对时刻相关抛物型问题，不但在求解隐式离散格式时与椭圆型算子具有一样的效率，而 且只要问题本身在时刻方向上滑腻，那么求解进程在时刻方向访问细网格的次数很少，能迅 速达到稳固状态。多重网格算法被推行到别的领域，取得了大量功效，如统计物理中的快速Monte 一 Carlo 方式，积分变换，人工智能中N个体的彼此关系识别，全局优化问题，图象处置，量子色 动力学(QCD)图等等。同时，多重网格技术与别的领域中高效方式结合，产生

24、了许多新方式， 如高精度谱多重网格算法，处置非规那么间题的代数多重网格方式，与有限元结合的和谐、 非和谐元多重网格算法，非结构网格上多重网格算法等等。参考文献I 王歇成，邵敏编.有限元大体原理和数值方式.北京:清华大学出版社.1997.I2谢德馨.三维涡流场的有限元分析技术.北京:机械工业出版社.2007.3 W.哈克布思.多重网格方式.北京:科学出版社.1998.4 李晓梅，莫那么尧.多重网格算法综述.中国科学基金.1996，1:4 一 11.5 王烈衡，许学军编著.有限元方式的数学基础.北京.科学出版社。6 吴东阳.多重网格方式在工程电磁场数值计算中的应用.研究沈阳工业大学.2020.7

25、郭庆平，王伟沧，高曙，卫加宁，高洁多重网格方式的一种并行模式.国家自然科学基8 徐长发.有效偏微分方程数值解法.武汉:华中理工大学出版社，9 郭庆平,陈先桥,卫加宁.交织多重网格方式及其并行化技术.武汉交通科技大学学 报,1997,21(2):13814010 关治，陆金甫编.数值分析基础.高等教育出版社,1998.II 李炜，彭文启.线性对流扩散方程混合有限分析多重网格法.武汉水利电力大学学 报.1995.12 Li Wei, YangYisong. Numerical analysis of turbulent separated flow passed a wall-mounted obstacle. Hydraulie Engineering， 1992， l(1):1320.