下载掌阅APP，畅读海量书库
立即打开
代数多重网格方法分为两步：平滑过程和粗网格修正过程。平滑过程可以迅速将那些高频分量去掉，而粗网格修正过程则可以帮助修正那些光滑了的低频分量，通过不断地迭代，从而快速精确地处理问题。代数多重网格过程的具体思路是：先在细网格上做松弛迭代，然后将误差投影到粗一层网格上去，在粗网格上又做松弛迭代，继续平滑相应的高频部分。依此类推，直到最粗的一层。在最粗一层用直接法求解，然后用插值算子将所求得的误差返回到细网格上去，用以修正原有结果，直到最细的一层。
代数多重网格方法（AMG）的目标是求解离散域上的问题
其中， A 是一个 n × n 的矩阵， U 是未知量， f 是给定的 n 维的已知向量。 A 矩阵符合 M 矩阵的定义。
代数多重网格方法的较粗网格 Ω m +1 = C m 是它的较细网格 Ω m 的一个真子集，记作 F m = Ω m -C m ，其中 F m 为 C m 层次对应的细网格。
一般情况下， C m 和 F m 的选取规则 [13] 为：
（1）对任意
i
∈
F
m
，
j
∈
（
表示网格
Ω
m
中点
i
强连接的点），那么
j
∈
C
m
或者
j
与
C
m
的一个点强连接。
（2） C m 是强连接点构成的最大点集合。
实际上，对于许多方程组来说，同时严格满足这两个规则是不可能的，在构造粗网格过程中要求严格遵守规则（1），而规则（2）作为一种构造粗网格的指导，利用这两个规则就可以构造网格序列。
强连接点的定义 [14] ：
定义1-1： 一定条件下的矩阵，如果一个点 i 强连接到点 j ，满足
这个定义实际上是针对 M 矩阵的，即矩阵对称正定，且非对角元素非正，通常取 θ 0 =0.25。
M 矩阵的定义如下。
定义1-2： 对于一个矩阵 A 被称作 M 矩阵，需要满足下列条件：
（1） a i , i ＞0∀ i ;
（2） a i , j ＜0∀ i ≠ j ;
（3） A -1 ≥0.
如：
为一个
M
矩阵。
M 矩阵也可以表示为 A = SI-B ， S ＞0， B ≥0。若 S ≥ ρ （ B ），则称 A 为 M 矩阵，若 S ＞ ρ （ B ）则称 A 为非奇异 M 矩阵。其中 ρ （ B ）为矩阵 B 的谱半径。
通过理论分析，粗网格的提取可以等效于做一个矩阵变换，从一个高维矩阵变换到一个低维矩阵。令细网格层图为 G f ，粗网格层图为 G c ，则
将细网格变到粗网格类似于投影变换，而反变换对应插值变换。
一个代数多重网格方法主要包含两个步骤：预备部分和迭代循环部分。预备部分是从描述问题的方程组的系数矩阵构造出代数多重网格方法的五个分量：粗网格序列
h
Ω
、插值算子
、限制算子
、粗网格算子
A
h
、光滑算子
G
h
。
（1）粗网格序列
h
Ω
，它能看作是未知数
（1≤
j
≤
n
h
）的集合，是为已知矩阵有关的有向图节点的虚构网格；定义最细的网格为
Ω
0
，构造一个网格序列使得
Ω
n
⊂
Ω
n
-1
…⊂
Ω
k
…⊂
0
Ω
；
（2）光滑算子 G h ， G （ Ω h ）在 h Ω 上的光滑算子；
（3）限制算子
，
G
（
Ω
h
）→
G
（
Ω
2
h
）；
（4）插值算子
，
G
（
Ω
2
h
）→
G
（
Ω
h
）；
（5）粗网格算子 A h ， h Ω 层上的系数矩阵序列。
其中插值算子和限制算子的关系为：
这里， T 表示矩阵或者向量的转置。
上面的算子构成方法可以保证粗网格算子具有许多好的性质，比如对称正定等，而在代数多重网格方法中松弛过程是固定的，通常取Gauss-Seidel松弛法或者Jacobi松弛法，如果需要形成一个代数多重网格循环过程，就必须给出插值算子和粗网格的递推公式，这在代数多重网格中十分重要。
下面描述代数多重网格方法的主要部分 [15] 。
首先考虑线性方程组
其中， A =（ a ij ） n * n ； U =（ u 1 ，…， u n ） T ； F =（ f 1 ，…， f n ） T 。
根据多重网格方法可以得到越来越小的代数方程组
其中，
；
h
=1，…，
H
；
n
=
n
1
＞…＞
n
H
；
A
1
=
A
；
U
1
=
U
；
F
1
=
F
。
代数多重网格方法的整个流程离不开五个分量，这五个算子是构成代数多重网格方法的主体，而且在代数多重网格方法中组元分量的构造也有很多值得借鉴的地方，如粗网格选取的方法。本节中将对代数多重网格方法五个分量做一下简单介绍。
1.粗网格选取
代数多重网格方法的求解过程能够在一系列的粗网格中做若干次迭代，并将其残差投影到下一级粗网格中，然后依次迭代到在最粗的网格中，再按照原来的序列将残差插值到上一层细网格中，直至到达最细的网格，这样就可以获得问题的精确解，所以代数多重网格方法需要定义一系列的网格序列 [16] 。
传统多重网格方法的粗网格序列是很规则的，如图1.3（a）所示，而代数多重网格方法却是根据所求解问题的系数矩阵构造出粗网格序列，网格大小是不规则的，如图1.3（b）。粗网格构造仅利用方程组系数矩阵的信息，如元素之间的大小以及强连接联系等。
首先需要定义最细的网格为 0 Ω ，通常由原始系数矩阵得到。
图1.3 网格序列示意
2.插值算子的构造
当粗网格给定后就可以定义插值算子，设误差
e
h
=
-u
h
，其中
为离散方程的精确解，每个
C
h
中的变量也同时在粗网格中，这样这些点的值直接由
Ω
2
h
中相应的量以权重 1给出，所以插值公式的关键实际上是如何用
Ω
2
h
=
C
h
中的变量来计算
F
h
中的变量，即每个点
i
∈
F
h
的值是由一个较小的插值变量之集
的形式给出的。可以用式（1.7）表示。
一维空间的插值算子如式（1.8）所示。
插值的基本原则：
（1）插值时，在粗网格中的点在细网格中不发生变化。
（2）如果点不在粗网格中，那么细网格中该点的值是其周围点的平均值。插值过程如图1.4所示。
图1.4 插值计算示意图
一维插值计算代码如下：
二维空间的插值矩阵如式（1.9）所示。
根据式（1.9）可得
3.限制算子的构造
限制算子
与插值算子
联系紧密，限制算子和插值算子一般互为转置关系。但是有时候会根据粗网格算子的不同，算子会选取其他的类型。一般插值算子产生后，限制算子可以根据插值算子获得。
一维空间的限制算子如式（1.10）所示。
一维限制算子的构造过程如图1.5所示。
一维限制计算代码如下：
图1.5 一维限制算子的构造过程
二维空间的限制算子如式（1.11）所示。
图1.6 限制矩阵的效果（7 u -3 v ）
限制矩阵的效果如图 1.6 所示。细网格上的
u
j
=sin（2
j
π/8） 和粗网格上的
都是sin（）函数，但是频率增加了一倍。细网格上的平滑振荡到了粗网格上振荡只有一半了，这也是限制带来的效果。
怎样使通过限制算子求出的粗网格近似值 V 2 h 接近精确值 U ，我们从图1.7和图1.8来进行分析。如图1.7和1.8表示 V 2 h 和 U 的变化曲线图。
图1.7 U 平滑变化的情况
图1.8 U 摆动变化的情况
从图1.7和图1.8中可以看出，如果 U 是平滑变化的，那么多重网格的插值 V 2 h 会很接近精确值 U 。如果 U 是摆动的，那么多重网格的插值 V 2 h 效果不是很好。
4.粗网格算子的构造
在很多文献中，粗网格算子最常见的形成方法是取Galerkin算子
，这样能够保持细网格算子的许多优良特性，如非奇异性、对称正定性等。
5.光滑算子的构造
光滑算子在代数多重网格方法中是固定不变的，一般取Gauss-Seidel松弛或带参数的Jacobi松弛。
代数多重网格方法具有其他算法不具有的优良特性，如收敛速度快、稳健等性能。代数多重网格方法组元的构造仅仅是根据方程组本身的信息——所求问题的系数矩阵 [17] 。代数多重网格方法是固定光滑算子，粗网格和插值算子的构造根据系数矩阵自动构造。
图1.9为代数多重网格的大致流程，初始为 Ω 0 ， AU = F ，在此网格上做若干次迭代，将误差投影到 Ω 1 ，得到 A 1 U 1 = F 1 ，再做若干次迭代，将误差投影到下一级网格中，继续迭代求解，最后在网格 Ω m ，得到 A m U m = F m ，由于阶数较低，所以就可以直接求出精确解。那么下一步迭代回去，误差一步一步地返回到原来的网格中，就可以得到问题的精确解，这是算法的大致思路。
图1.9 代数多重网格的大致流程
代数多重网格方法另一部分就是标准的多重网格循环过程。图1.10中的代数多重网格方法采用的是V循环，此外还有W循环和FMG循环，这些循环的主要思想是一致的。这些循环方法收敛性很好，而且效率也会提高。
图1.10 代数多重网格的循环方式
通用的二重网格方法步骤如算法1.1所示。
算法1.1 通用的二重网格方法
在 f 层（精细层，粗糙层定义为 c 层）执行如下。
1.前光滑：在 f 层进行 n 1 次松弛 A fuf = f f ；
2.粗网格校正：
（1）在细网格层计算残差，得到残差为 r f = f f-Afuf ；
（2）将残差通过限制矩阵转移到粗网格上，即 r c = Rr f ；
在第 m +1层递归执行，直到在最粗的网格层直接求解 f c = A c u c ；
（3）将错误插值到细网格层 e f = Pu c ；
（4）在细网格层校正错误 u f = u f + e f ；
3.后光滑：在 f 层进行 n 2 次松弛 A fuf = f f 。
代数多重网格方法能够从存储空间、迭代次数等方面优化计算速度，下面简单分析一下存储空间和计算方面的优化效果。
f h 必须在每一阶段保存的内容有：
· 在第一次粗化过程中，粗网格的点数是细网格点数的1/2；
· 在第二次粗化过程中，粗网格的点数是细网格点数的1/4；
· 在第 d 次粗化过程中，粗网格的点数是细网格点数的2 -d 。总共的存储代价为
在第一、第二和第三次粗化过程中，粗网格的存储代价分别小于细网格的2倍、3/4倍和8/7倍。
代数多重网格方法每次迭代的代价：
· 在细网格上的一次松弛迭代为一个工作单元；
· 忽略限制与插值的花费（一般占20%的花费）；
· 考虑一次向前松弛迭代和一次向后松弛迭代的V循环，那么V循环的计算代价为
第一、第二、第三次向前松弛迭代计算代价分别为4倍、8/3倍和16/7倍。