线性方程组预条件技术及在二维三温问题中的应用和实现

论文摘要

线性方程组的求解是当今不少研究领域遇到的一个共同问题,具有重大的理论价值和应用价值。而对于大型线性方程组,其阶数一般上几十万阶,甚至上百万阶,一般都要通过预处理后才能有效求解。目前预条件技术在诸多应用中远没有达到满意的程度。提高线性方程组求解的速度既是理论研究者也是工程技术应用者的追求目标。预条件技术作为线性方程组求解技术的重要组成部分,其重要性在未来还将不断增加。本文主要研究了一些特殊矩阵和实际问题的预条件技术,同时还设计开发了线性方程组求解技术开发的Matlab软件包,主要工作如下:1.对M-矩阵、非负矩阵在Jacobi迭代法和Gauss-Seidel迭代法下的预条件技术进行了研究。首先改进了I+S型预条件技术,并提出优化模型进行参数选择;另外利用LU分解方法,提出了两类Gauss型预条件技术,并给出了算法实现及算法比较。通过较充分的理论分析,本文证明了这些预条件技术的合理性和可靠性。数值实验进一步验证了这些预条件技术的明显改进效果和性能。2.通过构造“好”的预条件子的机理分析,并结合稀疏近似逆技术,提出了I+Hc型预条件技术。根据不同的预条件策略和思路,分别建立了估算I+Hc型预条件子中参数的优化模型。这类预条件技术的明显优点是计算量低,可并行性高的特点。数值实验表明了对于M-矩阵的情形,该类预条件技术联合Krylov子空间迭代法的预处理效果良好。3.本文对从一类二维PDE问题离散化得到的块三对角矩阵的预条件技术进行了研究。首先通过观察矩阵的逆有关的稀疏模式,提出了块七对角预条件子,并根据基于Frobenius模极小化这类稀疏近似逆技术的一种算法实现:最小残差算法（MR）,提出了构造块七对角预条件子的改进的最小残差算法。改进的MR算法的计算量大大低于原有的MR算法,而且改进MR算法预处理效果几乎与MR算法相同。这类预条件子的有效性在Krylov子空间迭代法下进行了测试。数值实验还表明改进的MR算法对于一些非对称情形同样适用。4.对二维三温问题的预条件技术从两个方向进行了研究。（1）对基于红黑排序下的分块系统的重排技术进行研究。在重排效果较好的hyperplane方法的基础上,提出了一类交替hyperplane（A-hyperplane）重排方法。数值方法表明,相对于RB、hyperplane预条件重排方法,当该重排预条件技术结合ILU（κ）预条件方法时,大大提高了收敛速度。（2）对二维三温问题的全局预处理,应用了一类区域分解方法进行了研究。数值实验表明了在二维三温问题的应用中,区域分解法在增加分解的区域个数以提高并行计算性的同时,迭代次数并没有明显增加,说明了区域分解对二维三温问题具有良好预处理效果。这些工作为今后基于区域分解方法对二维三温问题的并行求解做了一定准备工作。5.为了提高线性方程组求解方法的开发效率,特别是预条件技术的开发效率,我们开发了LINSOLKIT软件包。本文主要利用了Matlab数学软件的强大功能,并在分析研究了当前一些成熟的基于非Matlab语言开发的线性方程组求解软件包的情况下,借鉴了其中的一些成功设计经验,开发了线性方程组求解的Matlab软件包:LINSOLKIT。该软件包的主要接口包括预条件子构造接口、预条件的迭代法接口、预处理子求解接口等。由于LINSOLKIT是基于Matlab开发,因而LINSOLKIT在新增预条件技术、迭代求解方法等扩充方面都非常方便、高效。本文的大部分数值实验都是直接使用LINSOLKIT提供的图形操作界面完成。另外,本文还基于SparsKit软件包开发了一组Fortran程序用于二维三温问题和二维PDE测试。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 本文主要研究内容、方法和创新点
• 1.3 本文的结构安排
• 第二章 本文研究的准备工作
• 2.1 引言
• 2.2 明确研究问题
• 2.2.1 几类特殊矩阵
• 2.2.2 构造的特别矩阵
• 2.2.3 偏微分方程类问题
• 2.2.4 测试矩阵的其他来源
• 2.3 线性方程求解的迭代法
• 2.4 其他相关知识和准备工作
• 2.5 本章小结与展望
• 第三章 修正的预条件方法
• 3.1 引言
• 3.2 I+S型预条件子的改进
• 3.2.1 预条件子的构造与改进
• 3.2.2 收敛性分析
• 3.2.3 选择r和t的模型
• 3.3 改进Hadjidimos等人的预条件子
• 3.4 数值实验
• 3.5 本章小结与展望
• 第四章 Gauss型预条件子
• 4.1 引言
• 4.2 Gauss型预条件技术的推广
• 4.2.1 右Gauss型预条件技术
• 4.3 预条件算法
• 4.4 数值实验
• 4.5 本章小结与展望
• c型预条件技术'>第五章 基于最优化方法的I+H_c型预条件技术
• 5.1 引言
• 5.2 基于优化模型构造预条件子
• c稀疏模式的确定'>5.2.1 I+H_c稀疏模式的确定
• c参数的优化模型'>5.2.2 确定预条件子I+S_c参数的优化模型
• c型预条件子参数c的优化模型'>5.2.3 计算I+H_c型预条件子参数c的优化模型
• 5.3 推广的预条件子
• 5.4 数值实验
• 5.5 本章小结与展望
• 第六章 一类块三对角矩阵的预处理
• 6.1 引言
• 6.2 改进的稀疏近似逆算法与理论分析
• 6.3 数值实验
• 6.4 本章小结与展望
• 第七章 二维三温问题中的预条件技术研究
• 7.1 引言
• 7.2 重排技术设计与应用
• 7.2.1 基于红黑排序思想的分块系统构造
• 7.2.2 重排方法的设计
• 7.2.3 数值实验
• 7.3 区域分解方法的应用
• 7.3.1 区域分解方法
• 7.3.2 数值实验
• 7.4 本章小结与展望
• 第八章 线性方程组求解技术开发的软件包设计与实现
• 8.1 引言
• 8.2 Matlab环境下LINSOLKIT设计与实现
• 8.2.1 界面设计与系统文件
• 8.2.1.1 主界面
• 8.2.1.2 参数设置界面
• 8.2.1.3 系统文件
• 8.2.2 主要函数模块设计与实现
• 8.2.3 应用实例
• 8.3 Fortran研发平台
• 8.4 本章小结与展望
• 第九章 结论
• 致谢
• 参考文献
• 附录A LINSOLKIT软件包函数列表
• 攻读博士学位期间的研究成果