大型稀疏线性代数系统迭代解法研究

论文摘要

科学与工程的很多领域如流体力学，高阶微分方程求解，计算电磁学，最优化问题和油藏模拟等都涉及到大规模稀疏线性代数系统的求解．大规模稀疏线性代数系统求解方法的研究甚至是大规模科学与工程计算的核心问题之一，具有重要的理论意义和实际应用价值．本文对与大规模稀疏线性代数系统迭代求解有关的特殊矩阵数值特征和求解方法进行了深入的研究．特别地，研究了矩阵分裂迭代法的收敛性和比较理论及迭代求解预处理技术．全文共六章，分四个部分：第一部分研究了严格对角占优M-矩阵逆的无穷大范数的上界估计．利用严格对角占优M-矩阵的特殊结构，逆M-矩阵和M-矩阵元素之间的关系，得到逆M-矩阵无穷大范数上界估计．进一步，得到对其谱半径的估计．第二部分研究了鞍点问题迭代求解预处理技术．首先，提出了松弛不精确Uzawa算法和预条件的Uzawa算法，这两种算法扩充原有算法，并且讨论了算法的收敛性，数值实验验证了这两种算法的有效性．其次，建立了两类求解（1，1）块矩阵为高奇异对称和非对称鞍点问题的预条件子，深入研究这两类预条件子的谱性质，通过数值例子说明所建立的预条件能很有效的解决此类病态鞍点问题．最后，对混合型时谐Maxwell方程离散得到的线性方程组，根据其系数矩阵特殊性质提出了带参数的免增广和兔Schur余块三角预处理技术，理论分析说明其构造及应用代价和已有的免增广和免Schur余块对角预条件子相当，但有更好的特征值聚集性质，特别是在给出的相对最优参数的时候更聚集．数值实验说明其性能大大优于免增广和免Schur余块对角预处理技术，而且也验证了在理论上给出最优参数情形下性能最佳．第三部分，首先研究了矩阵多分裂方法的收敛性和比较理论，提出了K+1参数的非定常多分裂算法和K+1参数的非定常二级多分裂算法．详细地讨论了在系数矩阵为H-矩阵时算法的收敛性，也研究了通过不同零模式得到的不完全LU分解形成的多分裂矩阵对上述算法的收敛性，并且利用迭代矩阵构造出预条件子．其次，对块三对角H-矩阵，根据其特殊结构和性质构造块LU预条件子，数值实验显示此预条件子是非常有效的．第四部分，首先分析了两类修正预条件子结合Gauss-Seidel方法和SOR方法对系数矩阵为L-矩阵情况的收敛性，并给出了比较结果，进而得到这两类预条件子的最优结构．其次，研究了Mixed-type分裂方法对系数矩阵为Z-矩阵的线性方程组的求解方法．最后，提出了松弛的交替迭代方法，并对系数矩阵为单调矩阵，Hermitian正定矩阵的情况下研究了其收敛性．

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 研究的现状
• 1.2.1 逆M-矩阵无穷大范数上界的估计
• 1.2.2 经典迭代法和Krylov子空间迭代法及其预处理基本思想
• 1.2.3 鞍点问题的预条件技术
• 1.3 本文主要研究内容、方法和创新点
• 1.4 本文结构安排
• 第二章 严格对角占优M-矩阵逆的无穷大范数上界的估计
• 2.1 引言
• 2.2 助记符,定义和性质
• -1‖_∞的上界'>2.3 ‖A^-1‖_∞的上界
• 2.4 本章小结
• 第三章 鞍点问题迭代求解预处理技术
• 3.1 求解鞍点问题的带松弛参数的Uzawa算法
• 3.1.1 引言
• 3.1.2 带松弛因子的不精确Uzawa算法的收敛性
• 3.1.3 带松弛因子预条件的Uzawa算法分析
• 3.1.4 数值实验
• 3.2 求解（1,1）块高奇异的鞍点问题的新预条件
• 3.2.1 引言
• 3.2.2 预条件子的建立及其谱分析
• 3.2.3 当B有一行稠密时预条件分析
• 3.2.4 数值实验
• 3.3 离散化混合型时谐Maxwell方程的块三角预处理技术
• 3.3.1 问题的提出
• 2<1时的块三角预条件子'>3.3.2 对k²<1时的块三角预条件子
• 2的块三角预条件子'>3.3.3 对任意k²的块三角预条件子
• 3.3.4 数值实验
• 3.4 本章小结
• 第四章 松弛多分裂算法及基于LU分解的预条件技术
• 4.1 K+1参数多分裂迭代法
• 4.1.1 引言
• 4.1.2 注记与算法
• 4.1.3 非定常K+1参数多分裂方法的收敛性
• 4.1.4 数值实验
• 4.2 块三对角矩阵的块ILU预条件
• 4.2.1 引言
• 4.2.2 块三对角的块LU预条件子的构造
• 4.2.3 块三角M-矩阵和H-矩阵线性方程组的块LU预条件子的理论分析
• 4.2.4 具体实现
• 4.2.5 数值实验
• 4.3 本章小结
• 第五章 基于基本迭代法的研究
• 5.1 修正的Gauss-Seidel迭代法和SOR迭代法
• 5.1.1 引言
• 5.1.2 收敛性分析和比较理论
• 5.1.3 数值实验
• 5.2 Mixed-type分裂迭代法
• 5.2.1 引言
• 5.2.2 收敛性分析与比较理论
• 5.2.3 数值实验
• 5.3 松弛交替迭代法的研究
• 5.3.1 引言
• 5.3.2 定义与引理
• 5.3.3 松弛交替迭代法收敛性的研究
• 5.3.4 比较理论
• 5.3.5 数值实验
• 5.4 本章小结
• 第六章 结论
• 致谢
• 参考文献
• 攻读博士学位期间的研究成果