多重网格算法综述.docx

多重网格算法综述.docx

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

多重网格算法综述

邹静文6

摘要本文总结了多重网格算法的基础理论，剖析了多重网格方式的一种并行模式和总结了已取得的功效和待扩充的领域。

对多重网格方式的大体思想有一个较详细的概述，比较分析了单一网格和多重网格的计算结果，并对多重网格的并行模式进行了探讨和分析。

关键词多重网格算法，套迭代，粗网格校正，并行模式，交织多重网格，区域分解

一、引言

多重网格法（MultipleGridMethod），简称M—G方式是最近几年来求解偏微分方程边值问题的快速方式之一，本文参考前人的文献资料，并结合所学知识，总结多重网格法的基础理论，包括多重网格的应用原那么、具体实现步骤和计算结果的分析和比较。

其计算结果说明：

多重网格方式具有收敛速度快的优势，当多重网格方式所用层数越多，生效速度就越快；而且撞制粗、细网格层之间自适应转换的撞制参数在选取上有专门大的灵活性；能够看出随着剖分的加密，单一网格方式达到收敛所需的迭代次数显著增加，而多重网格方式所需迭代次数大体上不随网格的疏密和层数而转变，这说明多重网格方式具有与网格参数无关的收敛性。

二、多重网格方式的基础理论

多重网格方式的最初被提出是由于在网格方程迭代求解时，误差的各个Fourier分量的衰减程度不同。

熟悉到高频振荡误差是局部行为，来源于周围几个网格点之间的彼此藕合，与边界或距离较远的网格点信息无关；而低频滑腻误差是全局行为，要紧来源于边界信息。

传统的点或块松弛都是局部性较强的方式，因此它们能迅速抹平局部性的高频振荡误差，但对全局性的低频滑腻误差却衰减缓慢。

事实上，通过初始几回迭代后，误差将呈现滑腻性。

因此，适应上称能迅速抹平高频振荡误差，使误差趋于滑腻的松驰方式为有效滑腻方式，并用松驰因子来刻画它们的滑腻效应。

多重网格方式思想的引入

考虑在简单区域上泊松方程的第一类边值问题（狄立克雷边值问题）：

那个地址是一个单位正方形，是那个正方形的边界如以下图所示：

在以步长为h的网格上离散后，取得一个线性系统，其中是一个稀疏矩阵。

一样采纳经典的迭代法如Guass·seidel迭代、Jaccobi迭代、SOR迭代等，不难发觉如下一个事实：

开始的几回迭代近似解与真解之间的误差衰减专门快，可是后来的迭代误差去衰减很慢。

而且系数矩阵的条件数越高，达到必然精度所需要的迭代次数越多。

通过对迭代进行傅立叶分析，咱们发觉处在高频的误差分量在迭代的进程中迅速衰减，而处在低频的误差分量确衰减的很慢。

为了解决那个问题，多重网格方式应运而生。

通过局部松驰后误差呈现滑腻性，现在误差要紧来源于边界。

能够假想二维网格上的点松驰方式，将边界信息传播到所有点至少需O（N）次迭代，因此收敛速度奇慢。

不妨将网格方程的剩余部份（残差）限制到粗网格上进行。

在粗网格上精准求解后，将所得解延拓到细网格上，与原先近似解组合，形成网格方程的近似解，称这一进程为粗网格校正。

在粗网格上，由于网格点少，边界信息能较快地传播到所有网格点，收敛速度将加速。

一样地，在粗网格上也存在高、低频误差，类似于细网格，进行几回局部松弛排除高频误差后，能够将低频误差再转移到更高层网格。

如此进行下去，直到最高层网格，那里未知量个数超级少，直接精准求解的工作量可忽略不计。

然后从高层到低层依次将所得解返回、组合，在最细网格上最终形成一个近似解，这一递归性质称为套迭代技术。

多重网格算法确实是如此将问题的求解散布在不同的层上，所有层彼此和谐地求解同一问题的。

事实上，现在的粗网格校正确实是起到将边界信息迅速传播到所有网格点的作用。

细网格松弛、粗网格校正和套迭代技术是多重网格算法的三大支柱。

细网格松弛负责排除高频振荡误差，粗网格校正负责排除低频滑腻误差，套迭代技术负责通过限制和延拓算子连接所有层一起求解同一问题。

可见多重网格算法的大体思想是：

（1）一个问题能在不同规模的网格上求解；

（2）细网格仅仅只需负责排除高频误差，而粗网格负责排除低频误差。

多重网格方式的应用原那么

下面从算法对物理问题的离散格式、松弛方式、限制与延拓、网格粗化策略和套迭代技术的需求，别离论述应用多重网格算法的大体准那么。

离散格式离散格式必需是稳固的。

格式的数值稳固性是一种局部行为，将致使解的局部高频振荡，使得松弛方式在细网格上无法有效滑腻误差，从而使多重网格算法的效率将很低，乃至发散。

而离散解滑腻部份的稳固性一样仅仅依托于微分方程本身的稳固性，与离散格式关系不大。

固然，物理问题本身的稳固性是一个大体前提。

由于离散格式的稳固性是局部行为，要求离散格式能将方程本身在一个或几个网格步长上的所有振荡较好地描述出来，以便于松弛方式有效地排除。

可是，对给定的步长h，只判定格式是不是稳固是不够地，还应该给出一个尺度来刻画这种稳固性的程度。

h一椭圆性确实是一个专门好的判别方式。

具有h一椭圆性的离散格式，都必然存在一种有效的松弛方式，排除所有高频误差。

松弛方式总原那么是让残差从细网格限制到粗网格之前充分滑腻。

滑腻效应的气宇采纳滑腻因子，可通过局部模分析方式简单地获取。

假设在每层网格上松弛次，那么可用预测多重网格算法的近似最优收敛因子。

松弛时要注意以下几点：

（1）每层网格上松弛次数不宜过量（一样2一3次），只需要排除高频误差，因为松弛到必然程度，低频误差将占主导地位，与高频误差彼此祸合，无助于限制之前残差的滑腻。

（2）最好具有数值稳固性，幸免迭代进程中的高频振荡。

（3）点松弛方式仅滑腻最强藕合方向的误差，对存在次藕合方向的问题，如各向异性问题、奇异扰动问题，那么必需采取块迭代方式，如线松弛、平面松弛，使位于同一块的所有未知量被同时松弛或使强祸合方向的未知量被同时松弛。

（4）滑腻因子不宜过小，一样使得多重网格算法的收敛因子在左右为最正确。

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循环之间，视具体情形可别离采纳。

多重网格方式

最简单的椭圆型问题是Poisson方程

（）

多重网格算法迭代的大体步骤：

对式进行离散，取得的方程组

Lu=f（）

其中，L是个通过离散所取得的系数矩阵。

在网格步长为h（细网格）的网格点上，方程知足

关于方程传统的迭代方式是在确信的一种网格上采纳某种迭代解法，例如Gauss一Seidel迭代法、超松弛法（SOR）和它们改良的迭代技术，而多重网格方式采纳不同品级的网格剖分。

假定有一组网格称为网格序列，随着k的增加，网格愈来愈细，这些网格都逼近同一区域，相应的有网格步长序列，算子序列。

与传统计算方式不同，多重网格方式采纳一系列不同步长的网格层。

因为场值的误差在粗网格层上猛烈摆动，因此在粗网格层上对误差进行迭代将加速收敛速度。

误差从细网格层到粗网格层的变换进程称为限制，即将细网格层上与某一网格点相邻的假设干个点的信息通过必然的权重浓缩到粗网格层的该点。

在粗网格层上对场值的误差进行迭代后，必需将粗网格层上的误差通过插值补充出细网格层上的函数值，这一插值进程称为延拓。

能够看出，限制和延拓是互逆的。

在每一层网格迭代前对场值的误差进行限制，完成最粗一层网格迭代后对其进行延拓。

多重网格法的一个重要方面确实是通过递归挪用二重网格方式来做近似。

也确实是残差方程不是通过直接方式求解，而是用几回松弛磨光来磨掉高频误差，固然是伴随向更粗一级网格上残差限制，这确实是多重网格法的思想。

如此多重网格方式的一系列问题将在不同网格大小的嵌套网格上取得解决。

多重网格算法依照在每层上作校正循环的次数又能够分为多重网格V一循环和多重网格W一循环算法。

多重网格V一循环算法是从最细网格一直到最粗网格，然后又返回到最细网格上的一种计算进程。

若是一个V一循环算法是在每层上作二次校正循环，然后返回到下一级细网上，这确实是多重网格W一循环算法。

计算结果和分析——单一网格和多重网格的比较

考虑以下的二维线性对流扩散方程的定解问题

（1）

选择这必然解问题主若是可求得其精准解，以查验所给出的混合有限分析多重网格法计算的有效性，求得此定解问题的精准解是

（2）

取x向和y向步长为h和k，将计算区域进行均匀剖分，在离散网格上成立方程

（1）的混合有限分析格式

（3）

将计算区域均匀剖分为3333个结点，单一网格和多重网格中最细网格的步长。

多重网格取4层，最粗网格步长为。

计算中取方程（l）中b=12。

在单一网格上求代数方程组（3）的收敛解。

关于多重网格，因方程（l）是线性的，故在每层网格上的混合有限分析系数仅与该层步长有关。

具体计算是在最细网格上完成一次迭代后，嵌入多重网格循环，咱们采纳V循环。

收敛判据取，关于多重网格收敛要求最细网格上残差范数，

，

其中和是最细网格上x和y方向的最大结点数；是最细网格结点（i，j）上的残差。

图l是计算区域对角线上的计算结果与精准解的比较.可见不管是单一网格仍是多重网格用混合有限分析法计算结果都是同精准解吻合的专门好。

图2是迭代的收敛进程，也是残差的衰减进程。

图中的工作单位等价于在最细网格上进行一次单独的滑腻迭代所需的计算量。

关于标准粗化系列，较粗网格上4次迭代相当于相邻细网上一次迭代。

由图能够看出多重网格法的收敛速度比单一网格法快很多，所需工作单位少得多，计算证明了多重网格法的优越性.图中A、B、C表示第一、二、三个多重网格循环步。

最细网格剖分17X1733X3365X65129X129

网格层数3456

最细网格步长

最粗网格步长

图4给出了4种不同疏密剖分时，应用单一网格方式和多重网格方式计算达到收敛解所需的工作单位。

能够看出随着剖分的加密，单一网格方式达到收敛所需的迭代次数显著增加，而多重网格方式所需迭代次数大体上不随网格的疏密和层数而转变。

这说明多重网格方式具

有与网格参数无关的收敛性。

图5是4套多重网格的收敛曲线。

能够看出这些曲线的斜率，即收敛率是大体上相同的。

也确实是说，多重网格方式的收敛率不受网格疏密的阻碍。

三、多重网格方式的一种并行模式

作为求解离散微分方程的一种迭代法，多重网格方式有效地利用了迭代进程的误差校正特性和对高频误差分量的滑腻特性，改变了传统的作法，作了变革性的构造。

其敛速与步长h无关，计算工作量为O（N）（N为离散格点数）。

总之，多重网格法是一种高效率迭代法。

在求解边值问题的近似解方面，为了高效求解大型方程组的需要，人们尝试并行处置。

而区域分解法是并行计算最活跃的研究和应用领域之一。

其大体方式是把一个复杂区域（或系统），依照必然原那么（如物理特性、几何形状、离散方式、算法特点与处置器个数）分解成假设干子系统，要紧采纳高效快速迭代法求解原始问题。

基于以上缘故，提出了一种并行的多重网格方式——交织多重网格法。

其对边值问题的并行处置有别于通常的区域分解方式。

通常的区域分解是将复杂区域分解成较小的子区域（重叠或不重叠）的和集。

而交织多重网格法的思路是先将大区域离散划分成网格，然后于网格中交织取点，分成假设干较粗的子网格，将这些子网格置于不同的处置器上，用通常的多重网格法计算其上边值问题。

最后，将这些不同处置器粗网格上的解组合成大区域的网格上的近似解。

从数学上看，交织多重网格方式思路如下：

设有边值问题

（）

将Ω划分为步长h的细网格后,问题离散为求解方程组

（）

然后,于Ω

（H>h）

设式的解析解为u*,方程组、的精准解为,。

随着h趋近于零，是趋近于u*。

设用迭代法近似求解方程组及所得近似解为及。

能够看出，想用组合成逼近的近似解是没有理论依据的。

可是，可考虑用的组合作为较好的初始值，用适合的迭代法（包括多重网格方式）来求出知足精度要求的逼近的近似解。

因此，利用交织多重网格法加速边界值的信息传递以取得较好的初值，并结适合当的迭代法求得中意精度的近似解。

四、已取得的功效和待扩充的领域

多重网格算法通过近30年的研究，在经典应用领域—线性和非线性、标量和非标量椭圆型间题取得了丰硕的功效，每一个未知量只需十多次算术运算便能在误差许诺范围内正确求

解，具有内在并行性，而且能适应这些情形：

自由边界问题，狭小区域问题，各类类型的奇

异与非持续性，局部网格细化，严峻非线性问题，区域中含有粗网格上不可见的小洞问题，高振荡边界问题等等。

在弹性力学，网格生成技术方面也取得了一样的效率。

类似于椭圆型问题，从80年代开始，多重网格算法已深切到计算流体力学（CFD），时刻相关间题、波动方程、积分方程等领域。

对流体力学Euler方程、Stokes方程、Navier-Stokes方程、位势方程中的大量定常与非定常问题，加入人工粘性，采纳适当的离散格式（如迎风格式，矢通量割裂格式，半离散格式）后，能以一样的效率求解。

在捐躯一至几个数量级效率条件下，能够成功求解含单族或多族特点线的高雷诺数不可紧缩流问题。

多重网格算法在求解来自波动方程的高不适定问题时，成效超级不睬想，但如果是转化为积分问题，那么成效要好得多。

一样，这种转换也适合求解特点值或特点函数问题。

对时刻相关抛物型问题，不但在求解隐式离散格式时与椭圆型算子具有一样的效率，而

且只要问题本身在时刻方向上滑腻，那么求解进程在时刻方向访问细网格的次数很少，能迅速达到稳固状态。

多重网格算法被推行到别的领域，取得了大量功效，如统计物理中的快速Monte一Carlo方式，积分变换，人工智能中N个体的彼此关系识别，全局优化问题，图象处置，量子色动力学（QCD）图等等。

同时，多重网格技术与别的领域中高效方式结合，产生了许多新方式，如高精度谱多重网格算法，处置非规那么间题的代数多重网格方式，与有限元结合的和谐、非和谐元多重网格算法，非结构网格上多重网格算法等等。

参考文献

[1]王歇成，邵敏编.有限元大体原理和数值方式.北京:

清华大学出版社.1997.

I2]谢德馨.三维涡流场的有限元分析技术.北京:

机械工业出版社.2007.

[3]W.哈克布思.多重网格方式.北京:

科学出版社.1998.

[4]李晓梅，莫那么尧.多重网格算法综述.中国科学基金.1996，1:

4一11.

[5]王烈衡，许学军编著.有限元方式的数学基础.北京.科学出版社。

[6]吴东阳.多重网格方式在工程电磁场数值计算中的应用.研究沈阳工业大学.2020.

[7]郭庆平，王伟沧，高曙，卫加宁，高洁.多重网格方式的一种并行模式.国家自然科学基

[8]徐长发.有效偏微分方程数值解法.武汉:

华中理工大学出版社,

[9]郭庆平,陈先桥,卫加宁.交织多重网格方式及其并行化技术.武汉交通科技大学学报,1997,21

（2）:

138～140

[10]关治，陆金甫编.数值分析基础.高等教育出版社,1998.

[11]李炜，彭文启.线性对流扩散方程混合有限分析多重网格法.武汉水利电力大学学报.1995.

[12]LiWei,YangYisong.Numericalanalysisofturbulentseparatedflowpassedawall-mountedobstaele.HydraulieEngineering，1992，l

（1）:

13~20.