代数多重网格算法.pdf

代数多重网格算法∗
2007 年 2 月 14 日
1 基本思想
Gauss-Seidel算法的特点是, 最初几步收敛的很快, {ψ }, i = 1, · · · , M,M << N 的粗网格上, 则根据
i
用φ表出ψ的关系, 我们可以得到
ψ = Pφ, (3)
这里P是一个M × N的矩阵. 相应的, 如果令
A˜ = PAP T , x˜ = Px, b˜ = Pb, (4)
则
A˜x˜ = b˜ (5)
∗ 该文档为李若教授讲授的《数值分析高等算法》的课堂笔记, 由王何宇整理.
1就可以看作是(2)投影到粗网格上以后的问题. 代数多重网格的做法, 就是对第k步的线性问
题
A x = b (6)
k k
先用Gauss-Seidel迭代进行几步迭代, 得到一个近似解x , 然后将残问题
k
A x = b − A x (7)
k k k k
用投影矩阵P 重投到粗一层的网格上得到第k + 1步的问题
k
A x = b , A = P A P T , b = P b − A x , (8)
k+1 k+1 k+1 k k k k+1 k k k k
如此不断迭代和重投, 直到得到一个规模相当小的线性问题后, 可以用直接法(Gauss消去
法)求得精确解, 然后用记录下的一系列P 矩阵, 还原出原问题的解. 在还原的时候, 仍然使
k
用Gauss-Seidel迭代在每