Linear Algebra Done Left - A Taste of Multigrid Methods for Linear Systems （Guguing）

Posted on Edited on

多重网格法是Graphics\text{Graphics}从业者的标配。——胡渊鸣

每次大更新博客的时候就是遇到了各种麻烦的时候…因为GAMES201GAMES201中胡渊鸣大佬的一句话，这个系列有了第四篇——到现在为止还不会多重网格法，实在惭愧。考虑到这一块如此重要，有必要单独用一篇博客来总结。

主要参考资料是经典的A Multigrid Tutorial\text{A Multigrid Tutorial}

1. 经典迭代方法的问题\text{1. 经典迭代方法的问题}

这部分对应于书中的第二章，关于Jacobi\text{Jacobi}迭代和Gauss-Seidel\text{Gauss-Seidel}迭代这里不再赘述，我们重点考虑如何分析误差。

考虑线性方程组Ax=fA\bold{x} = \bold{f}，记u\bold{u}为该方程的精确解，v\bold{v}为我们求出的解，e=u−v\bold{e}=\bold{u}-\bold{v}为误差向量，r=f−Av\bold{r} = \bold{f}-A\bold{v}为残向量。

简而言之，我们的经典迭代法，本质上可以视为在不断滤波误差向量，滤去高频分量，然而在实际应用中，当迭代到一定程度时，收敛就会变得极其缓慢，这是因为此时误差向量中的低频分量仍然存在，而经典迭代法对这些低频分量的滤波效果并不好。

2. 多重网格法的基本思想\text{2. 多重网格法的基本思想}

如果在当前的网格上是低频分量，那在更粗的网格上不是就成了高频分量吗？这就是多重网格法的基本思想。我们需要考虑的事情也就是对网格进行下采样。

3. 自适应的多重网格\text{3. 自适应的多重网格}

4. 代数多重网格\text{4. 代数多重网格}