线性方程组和鞍点问题的迭代法与预处理技术研究

论文摘要

大规模科学计算和工程技术中许多问题的解决，最终归结为大型稀疏线性方程组的求解，其求解时间在整个问题求解时间中占有很大的比重，有的甚至达到80％．由于现今科学研究和大型项目中各种复杂的课题对计算精度和计算速度的要求越来越高．因此，作为大规模科学计算基础的线性代数方程组的高效数值求解引起了人们的普遍关注．这种方程组的求解一般采用迭代法，所以，迭代法的收敛性和收敛速度就成为人们关注的焦点，为许多专家和学者所研究．本文对与大型稀疏线性方程组迭代求解有关的特殊矩阵迭代法进行了深入和系统的研究，特别研究了松弛型矩阵多分裂迭代法的收敛性，两种Krylov子空间方法的性能和鞍点问题的预处理技术．全文共六章，分四个部分：研究了H-矩阵的松弛型矩阵多分裂法，并给出详细的理论分析和敛散速度的比较．一方面，给出了松弛型矩阵多分裂TOR法，研究了方法的收敛性，比较了他们的敛散速度，分别进行了串行和并行试验，验证了所提方法的优越性．另一方面，给出了松弛型矩阵多分裂USAOR法，研究了方法的收敛性，给出了实现算法的例子，并用数值试验与存在的方法进行了比较．进一步研究了一些H-矩阵松弛型矩阵多分裂法新的收敛性结果．分别为非线性方程组的非定常矩阵多分裂法，线性互补问题的矩阵多分裂法，松弛型矩阵多分裂SSOR法和松弛型矩阵多分裂TOR法，构建了相应方法的收敛性理论，得到了新的更弱的收敛性条件，进行了数值试验的比较．基于多分裂法的并行性，矩阵多分裂的研究和理论分析对于多分裂预处理子的构造有一定的理论和应用价值．我们的方法选取参数的余地更大，当选取近似最优参数时，能实现更快的收敛速度和构造出更有效的预处理子．基于BiCR算法设计了求解非对称线性方程组Krylov子空间平方共轭残差（CRS）算法和适合分布式并行计算的改进的平方共轭残差（ICRS）算法，并对两种算法进行了理论分析和算法比较，串行和并行数值试验表明所提方法具有较好的收敛速度和并行性能．研究了鞍点问题特殊矩阵迭代求解预处理技术．首先，对内点优化问题产生的一类鞍点问题给出了一种预处理技术，进行了相应的理论分析和数值试验．接着，基于离散化混合型时谐Maxwell方程的块三角鞍点问题和特殊矩阵的结构，提出了带多个参数的预处理技术，并进行了理论分析和参数的理论选取．理论分析表明提出的预处理子有更好的特征值聚集性．数值试验也表明本章提出的预处理子性能大大优于免增广和免Schur余块对角预处理子．

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究问题和背景
• 1.1.1 矩阵多分裂迭代法
• 1.1.2 Krylov子空间迭代法
• 1.1.3 鞍点问题预处理技术
• 1.2 本文主要研究内容、方法和创新点
• 1.3 本文结构安排
• 第二章 H-矩阵松弛型矩阵多分裂迭代法
• 2.1 概念和性质
• 2.2 H-矩阵松弛型矩阵多分裂TOR迭代法
• 2.2.1 引言
• 2.2.2 收敛性分析
• 2.2.3 敛散速度的比较
• 2.2.4 实现算法的两个矩阵
• 2.2.5 数值试验
• 2.2.5.1 串行试验
• 2.2.5.2 并行试验
• 2.3 H-矩阵松弛型矩阵多分裂USAOR迭代法
• 2.3.1 引言
• 2.3.2 收敛性分析
• 2.3.3 数值试验
• 2.4 本章小结与展望
• 第三章 松弛型矩阵多分裂迭代法的推广和改进
• 3.1 非线性矩阵多分裂迭代法
• 3.1.1 引言
• 3.1.2 算法和引理
• 3.1.3 收敛性分析
• 3.1.4 数值试验
• 3.2 线性互补问题矩阵多分裂迭代法
• 3.2.1 引言
• 3.2.2 概念，引理和算法
• 3.2.3 收敛性分析
• 3.3 松弛型矩阵多分裂SSOR法收敛性改进
• 3.3.1 引言
• 3.3.2 收敛性分析
• 3.3.3 数值试验
• 3.4 松弛型矩阵多分裂 TOR法收敛性改进
• 3.4.1 算法和引理
• 3.4.2 收敛性分析
• 3.4.3 数值试验
• 3.5 本章小结与展望
• 第四章 Krylov子空间 CRS和 ICRS迭代法
• 4.1 引言
• 4.2 预备知识
• 4.3 CRS算法设计
• 4.4 改进的CRS算法设计
• 4.5 两种算法理论分析
• 4.6 两种算法等效率分析
• 4.7 数值试验
• 4.7.1 并行试验
• 4.7.2 串行试验
• 4.8 本章小结和展望
• 第五章 鞍点问题迭代求解预处理技术
• 5.1 内点优化问题预处理技术
• 5.1.1 引言
• 5.1.2 广义预处理技术
• 5.1.3 数值试验
• 5.2 离散化混合型时谐Maxwell方程预处理技术
• 5.2.1 引言
• 5.2.2 带多个参数的预处理技术
• 5.2.3 参数的选取
• 5.2.4 数值试验
• 5.3 本章小结和展望
• 第六章 结论
• 致谢
• 参考文献
• 攻读博士学位期间的研究成果