代数多重网格算法.doc

代数多重网格算法.doc1
代数多重网格算法
2007年2月14日
基本思想
Gauss-Seidel算法的特点是,最初几步收敛的很快 ，但是很快就开始停滞不前 •到最后
几乎不收敛•从数值试验的图像可以看出 ,Gauss-Seidel迭代当插值点少的时候，收敛速度 极快，但当插值点多的时候，由于上述效应收敛速度极慢 .因此，代数多重网格(Algebraic
Multi-Grid)算法利用这些特点，将由具体方程离散出来的矩阵 ，重投到一系列由细到粗的网 格上，在每一层网格上只做若干次 Gauss- ，该算法不
.
假设Possion方程
-? u = f (1)
用某种离散方法(比如，有限元或有限差分),在某个相当细的网格上，最后产生线性问题
Ax = b.
现在考虑如何将其投影到一个较粗的网格上
假设© = {咖打二1,…,n为细网格上的一组分片一次线性有限元基函数 .贝y矩阵a是 一个N x N的矩阵，且元素aj可以看作是对应基函数的一个双线性运算 a(氛咖).我们如果
要将A重新投影到一个对应基函数为 书二Z},i = 1,…，M, M << N的粗网格上，则根据
用©表出书的关系，我们可以得到
如=P也 (3)
这里P是一个M X N的矩阵•相应的，如果令
A = PAP T,? = Px, ? = Pb, (4)
则
= b (5)
2
?该文档为李若教授讲授的 《数值分析高等算法》 的课堂笔记，由王何宇整理•
就可以看作是(2)投影到粗网格上以后的问题 •代数多重网格的做法，就是对第k步的线性问
题
A k x = b k (6)
先用Gauss-Seidel迭代进行几步迭代,得到一个近似解Xk,然后将残问题
Akx = bk - Akxk (7)
用投影矩阵Pk重投到粗一层的网格上得到第 k + 1步的问题
A k +1 x = b k +1 , A k +1 = P k A k Pk , bk +1 = Pk bk - A k x k , (8)
如此不断迭代和重投，直到得到一个规模相当小的线性问题后 ，可以用直接法(Gauss消去
法)求得精确解，然后用记录下的一系列 Pk矩阵，还原出原问题的解•在还原的时候，仍然使 用Gauss-Seidel迭代在每一层来改进数值解 .如此整个过程为一步 AMG迭代.
算法步骤
现在给出严格的算法步骤 .
对过程 AMG( Ak, xk, bk),
第一步如果Ak的阶数小于一个给定的整数 ，比如20,则用Gauss消去法解出并Xk并返回；否
则，对问题(6)做3至5步Gauss-Seidel迭代；
第二步产生问题(8),令Xk+1 = 0;
第三步 递归调用 AMG( Ak+1 , X k+1 , bk+1 );
第四步 Xk = Xk + PkT Xk+1 ;
第五步 做3至5步Gauss-Seidel迭代，返回.
所以对问题(2),执行AMG( A, x, b)完成一次AMG迭代(迭代更新了 x).而整个求解过程 为
do A