多网格法

在数值分析中，多网格法（MG法）是一种使用离散化层次解决微分方程的算法。它们是一类被称为多解方法的技术的例子，对表现出多尺度行为的问题非常有用。例如，许多基本的松弛方法对于短波长和长波长的成分表现出不同的收敛率，这表明这些不同的尺度应该被不同地处理，就像在多网格的傅里叶分析方法中。MG方法可以作为求解器，也可以作为预处理器使用。多网格的主要思想是通过对细网格解近似的全局修正来加速基本迭代方法的收敛（称为松弛，通常可以减少短波长的误差），这是由解决一个粗问题来完成的。粗放问题，虽然解决起来比较便宜，但与细网格问题类似，它也有短波长和长波长误差。它也可以通过放松和上诉到更粗的网格的组合来解决。这个递归过程不断重复，直到达到一个网格，在那里直接求解的成本与细网格上的一次松弛扫描的成本相比可以忽略不计。这个多网格循环通常将所有的误差分量减少到一个固定的数量，远远低于1，与细网格的大小无关。多网格的典型应用是在二维或多维的椭圆偏微分方程的数值解。多网格方法可以与任何常见的离散化技术结合使用。例如，有限元方法可以被重塑为多网格方法。在这些情况下，多网格方法是目前已知的最快的解决技术之一。与其他方法相比，多网格方法是通用的，因为它们可以处理任意的区域和边界条件。它们不依赖于方程的可分离性或方程的其他特殊属性。它们也被广泛用于更复杂的非对称和非线性方程组，如弹性的拉梅方程或纳维尔-斯托克斯方程。

多网格算法有很多变化，但共同的特点是考虑离散化（网格）的层次性。重要的步骤是。平滑化--减少高频误差，例如使用高斯-赛德尔方法的几次迭代。剩余计算--计算平滑化操作后的剩余误差。限制--将剩余误差下采样到更粗的网格。内插或延长--将在较粗的网格上计算的修正值内插到较细的网格上。修正--将延长的较粗的网格解决方案添加到较细的网格上。多网格方法有很多选择，在单个迭代的求解速度和所述迭代的收敛率之间有不同的权衡。3种主要类型是V-循环、F-循环和W-循环。对于一个离散的二维问题，F-循环的计算时间比V-循环的计算时间多83%，而W-循环的计算时间多125%。如果问题被设置在三维领域，那么F-Cycle迭代和W-Cycle迭代分别比V-Cycle迭代多花64%和75%的时间，忽略开销。

通常情况下，W-循环产生的收敛效果与F-循环相似。然而，在具有高贝克莱特数的对流扩散问题中，W-Cycle在每次迭代的收敛率上会比F-Cycle更有优势。平滑化算子的选择是非常多样化的，因为它们包括Krylov子空间方法，并且可以进行预处理。任何几何多网格循环迭代都是在网格的层次结构上进行的，因此可以用递归进行编码。由于函数以较小尺寸（较粗）的参数调用自己，最粗的网格是递归停止的地方。在系统具有高条件数的情况下，修正程序被修改为只将延长后的粗网格解决方案的一部分添加到细网格中。

这种方法比其他方法的优点是它通常与所使用的离散节点的数量呈线性扩展。换句话说，它可以用与未知数数量成正比的操作数来解决这些问题，达到一定的精度。假设有一个微分方程，可以在网格上近似地（以一定的精度）求解i{displaystylei}上近似求解。的网格上近似求解（具有给定的精度），网格点密度为{displaystylerho=N_{i+1}/N_{i}<1}是相邻网格上各点的比值，假定为常数。