外推多网格法——大规模科学计算的新算法

摘要

快速求解由差分法或有限元法导出的大型线性方程组是大规模科学和工程计算中的重要问题。人们的目标是对N阶方程组用O(N)次乘除运算得到所需精度的解。而多网格法(MG)第一次实现了这个目标，成为求解大规模问题最有效的方法。经典MG的理论方法已经比较成熟，由于使用了3种运算：插值，限制和迭代，求解时需要在多重粗细网格上反复迭代，所以程序较为复杂。1996年德国Bornemann等人提出瀑布式多网格法(CMG)，即从粗网到细网的单向计算，只采用了插值与迭代两种运算，程序容易实现,令人注目。
　　 本文研究一类新的瀑布式多重网格法，主要工作和创新点如下。
　　 首次提出了外推瀑布式多网格法(EXCMG)。本论文基于有限元的渐近展开式，导出了新的外推公式.新算法沿用CMG的思想，但将粗网上的线性插值改为新外推与二次插值，为密网提供更好的初值，本质上减小了初始误差，对加速收敛起着关键的作用。新算法对函数和导数都收敛，且都有高精度。本论文在PC机上用EXCMG求解了400万未知数的问题，对函数和导数都达到8-10位精度，仅费时10分钟，进一步证实了这些优势。
　　 首次证明了共轭梯度法(CG)按l2模的有界性和收敛性.对CG法至今只有按能量模的收敛估计，因此这是一个新结果。本文还发现当第i层网格的迭代次数取幂指数形式(mLβL-i)时，基于CG迭代的多重网格法，存在着一个网格层数的“阀值”i0，即当i＜i0时，第i层上的误差快速衰减，CG迭代压缩效果非常明显；而当i＞i0时，CG主要起磨光作用.此特性对证明EXCMG按离散L2模的收敛性起重要作用。
　　 对正则性较弱的解u∈H3，首次证明了双线性元的渐近展开在节点集上按离散L2模有高精度O(h3)，因此EXCMG仍有效.已有的渐近展开式研究主要是对光滑解(如u∈C3)，并只得到了在逐点意义下的结果。上述结果拓宽了EXCMG的应用范围。数值试验表明，EXCMG对非光滑解u∈H3甚至H2仍有很高精度。

目录

文摘

英文文摘

声明

1 绪论

1.1大规模计算的困难

1.2多网格法研究背景和国内外研究状况

1.3主要创新点

1.4本文结构

2 有限元的超收敛性和渐近展开

2.1有限元的基本误差估计

2.2单元正交分析法(EOA)及其基本技巧

2.3线性元与双线性元的超收敛性和高次插值

2.4一维线性元的渐近展开式分析

3 外推多网格法(EXCMG)

3.1有限元逼近及其二次插值分析

3.2新外推公式

3.3新外推瀑布式多重网格法(EXCMG)

4 光滑解的数值试验与分析

4.1一维数值试验分析

4.2二维数值试验分析

4.3二维问题PC机上大规模计算与比较

5 共轭梯度法的收敛性分析

5.1有限元方程组的特点综述

5.2两种经典迭代法(Jacobi和Gauss-Seidel)

5.3共轭梯度法(Conjugate Gradient Method)

5.4 CG迭代法的H1收敛性

5.5 CG迭代法的l2-收敛性

5.6 CG迭代对多网格误差的压缩效果分析

6 EXCMG收敛性分析

6.1三层网格上的初始误差分析

6.2按任意模的误差传递公式

6.3 EXCMG按L2模的收敛性

7 非光滑解的分析与计算

7.1单元上的正交展开

7.2在L2中的误差渐近展开式

7.3非光滑解的数值试验与分析

8 研究展望

参考文献

攻读博士学位期间发表或接受发表的学术论文

致谢