下载掌阅APP，畅读海量书库
立即打开
多重网格方法 [1] 是求解大型线性代数方程组的一种迭代算法，是对传统迭代解法，如Gauss-Seidel方法、Jacobi方法等的一种卓有成效的加速解法。它以快捷高效的特点而受到人们的广泛关注，目前已经广泛应用到各种实际计算，如流体力学计算、石油储藏模拟、电磁模拟、图像处理、 [2-4] 经济问题仿真等问题中。它被认为是求解微分方程最快的数值方法。
根据误差理论，数值解与差分方程精确解之间的误差与傅里叶分析中不同频率分量有关。数值求解的误差可以展开成级数的形式，从级数的形式我们可以看出误差的振动分量有很多频段，只要消除了这些频段的误差，整个解也就收敛了。而网格则可以看成一种滤波器，不同尺度的网格可以过滤掉不同频段上的误差。如果网格一定，对于某些误差来说，可以很快过滤掉，对于与其频段不匹配的误差来说，这种网格可能完全失败而根本无法过滤掉。倘若采用多重网格方法，先在低分辨率（网格间隔大）上进行求解，因为此时网格间隔大、数据量小、进行松弛的时空耗费小、收敛快，而且一个很重要的优点是在低分辨率上对初值的敏感度显然要低于在高分辨率上的要求。这样，可以在不同网格层内消去不同波长的误差分量，保证所有的误差分量的收敛速度都不会降低，更快地得到精确的解。它巧妙地结合了细网格光滑和粗网格校正的思想，使得求解方程组的效率空前提高。
多重网格方法 [5] 最根本的哲学指导思想是一种多分辨率的方法。当我们用显微镜看物体的时候，首先用较小的放大倍数看，寻找微小物体所在的大致场所；然后增大放大倍数，寻找物体所在的精确场所；最后再放大，对物体进行仔细地观察。如果一开始，就用最大的放大倍数看，寻找物体的位置都会花费大量时间。这与代数多重网格方法的思路其实是一致的。在问题求解的过程中，使用方法跟求解域之间应该有一个比较切合的频段。如果频段一致，就能取得事半功倍的效果。
多重网格方法分为几何多重网格方法（GMG）和代数多重网格方法（AMG）。 [6，7] 几何多重网格方法所针对的问题是有几何背景的问题，即椭圆型偏微分方程在几何区域上的边值问题离散后所得到的大型病态线性代数方程组。几何多重网格方法要用到所求解问题的几何特性，这给实际应用带来一定的不便。代数多重网格方法从某种意义上讲是几何多重网格方法的一种数学抽象，是多重网格法思想的进一步发展。它仍采用多重网格方法的基本循环方法来求解方程组，但是它的组元的构造仅利用方程组本身的信息，即系数矩阵的元素的信息，它仍具有与几何多重网格方法差不多的效率。代数多重网格方法是仅利用方程组本身的信息来求解方程的多水平方法，这就克服了几何多重网格方法的致命缺点。几何多重网格方法的粗化光滑步骤影响比较小的误差分量，即光滑误差，可以通过求解较粗网格上的残量方程，用较小的计算量而得到比较好的近似，然后插值到细网格，以校正光滑步骤所得到的近似解，从而得到更好的近似解。一般取 h →2 h 的一致粗化，如图1.1所示。插值一般用线性插值，这对光滑算子提出了较高的要求。为了设计有效的多重网格方法，必须选择复杂的光滑算子，使得它能很快地减少不在插值算子值域内的误差分量。而代数多重网格方法是出于另外的一种考虑。它是固定光滑算子，一般是Gauss松弛或带参数的Jacobi松弛。粗网格和插值算子的建立采取一种自动的方式，以使插值算子的值域能很好地近似不能被光滑步骤所消除掉的误差分量，所以它的插值算子更具有针对性。
图1.1 h →2 h 的一致粗化图示
目前代数多重网格在图像中的应用主要是图像重构、图像二值化、图像复原、图像去噪 [8] 、图像融合和轮廓分析 [9] 等。图像领域里很多处理方法如图像分割、图像去噪、图像融合的问题都可以转化成椭圆差分方程（PDE），如各向异性扩散方程可以用来进行图像去噪，Mumford和Shah等提出的用偏微分方程处理图像分割，level set [10] 算法也是其中的典型例子。
代数多重网格方法直接针对方程组，它的组元构造仅利用方程组本身的信息，如系数矩阵元素之间的相对大小关系、强连接点的性质等，因此更多地应用于图像处理等各种领域。首先，定义最细的网格为 0 Ω ，构造一个网格序列使得式（1.1）成立。相互关系表示如图1.2所示。
图1.2 多重网格方法求解空间示意图
在代数多重网格方法求解过程中，细网格光滑步骤、粗网格校正步骤贯穿于网格迭代技术中，三者被巧妙地糅合在一起，求解效率得到提高，而且算法稳健性较高 [11] 。代数多重网格方法最根本的指导思想是采用迭代的步骤，在细网格中把影响比较小的误差分量投影到粗网格中，而且粗网格相对于下一级别粗网格亦可认为是细网格，依次迭代到能够精确求解的粗网格级别，再按照原来的序列，由粗网格到细网格，将误差依次插值到最精细的网格中，那么原问题的精确解就可以得到。
代数多重网格方法将由具体方程离散出来的系数矩阵，重投到一系列的由细到粗的网格上，在每一层网格上只做若干次Gauss-Seidel迭代，网格信息只来源于系数矩阵。在粗网格中可以求解上一层网格近似解和精确解误差的投影，套迭代技术是整体求解的技术，通过限制算子和延拓算子，将相邻的相对较细网格和相对较粗网格联系起来，将误差和粗网格的解也联系起来，为同一问题进行迭代。首先这种迭代技术必须有两个基础：①方程可以转化到不同网格上求解；②细网格负责消除高频误差，而粗网格负责消除低频误差 [12] 。