稀疏矩阵方程组预处理迭代技术研究

论文摘要

大型稀疏线性方程组的求解是对自然科学和社会科学中许多问题进行数值模拟的关键技术之一。而GMRES算法是目前求解大型稀疏非对称线性方程组最为有效的迭代算法之一。在执行整体的GMRES算法时,所需的计算量和存储量会随着迭代步数的增加而变得不可接受。为了克服这一困难,可以使用重新开始策略或混合迭代策略。最近,重新开始GMRES算法在迭代过程中表现出的补足收敛性质引起了人们的兴趣。特别地,基于这一性质所提出的积混合GMRES算法能够显著改善混合迭代策略求解方程组的效率。积混合GMRES算法在执行过程中,需要首先计算出多次迭代GMRES迭代循环的残量多项式,然后重复使用这些多项式的乘积进行Richardson迭代。然而,当迭代循环的步长较大时,计算出的残量多项式可能是不稳定的,从而导致Richardson迭代的发散。为了提高积混合GMRES算法的稳定性以及收敛速率,本文提出了多项式预处理积混合广义极小剩余算法。首先,本文介绍了求解大型稀疏矩阵的预处理Krylov子空间方法的原理以及在此基础上发展起来的各种迭代法,包括共轭梯度法,广义极小剩余法。其次,本文重点介绍了在重新开始GMRES循环的残量多项式在矩阵的谱上收敛的互补性以及在此基础了得到的积混合广义极小剩余算法,构造出了多项式预处理矩阵,并将该矩阵作为积混合广义极小剩余算法的预处理矩阵,改善其系数矩阵谱的性质,提高了该算法的收敛速率和稳定性。最后,本文对预处理后的新算法做了数值实验模拟与分析,将新算法与经典的成熟算法进行了对比,结果均表明,新算法更适合大型稀疏矩阵问题的求解,在计算量和存储量方面都有相应的改进。求解大型稀疏矩阵的积混合广义极小剩余算法得到了进一步的改善。

论文目录

• 摘要
• Abstract
• 符号表
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究内容
• 第二章 GMRES 算法及其补足性质
• 2.1 理论背景
• 2.1.1 GMRES 算法及其收敛性
• 2.1.2 重新开始GMRES（m）算法及混合GMRES 算法
• 2.1.3 最小二乘问题
• 2.1.4 子空间维数m 的确定
• 2.2 残量多项式的互补性
• 2.3 积混合GMRES 算法
• 2.3.1 积混合GMRES 算法
• 2.3.2 积混合GMRES 算法的分析
• 2.4 本章小结
• 第三章 预处理技术及改进算法
• 3.1 预处理技术
• 3.2 不完全Cholesky 预处理共轭梯度法（ICCG）
• 3.3 多项式预处理积混合 GMRES 算法（PHGMRES-PP（s,m））
• 3.3.1 预处理多项式的构造
• 3.3.2 多项式预处理积混合GMRES 算法（PHGMRES-PP（s，m））流程图
• 3.3.3 多项式预处理的积混合GMRES 算法（PHGMRES-PP（s，m））
• 3.4 本章小结
• 第四章 数值实验模拟与分析
• 4.1 稀疏矩阵的存储技术
• 4.2 数值实验
• 4.2.1 算法效果比较试验
• 4.2.2 PHGMRES-PP（s,m）算法性能分析
• 结论
• 参考文献
• 攻读硕士学位期间取得的研究成果
• 致谢