兰州大学机构库 >数学与统计学院
鞍点结构线性系统的迭代求解
Alternative TitleIterative solution of linear systems in saddle point form
梁兆正
Thesis Advisor张国凤
2017-09-15
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name博士
Keyword鞍点问题 异线性系统 矩阵分裂 迭代方法 预处理 Krylov子空间方法 PDE约束优化
Abstract

鞍点结构线性系统具有丰富的应用背景, 广泛地产生于科学计算和工程应用领域相关问题的数值求解过程. 这类线性系统作为一类特殊的分块线性系统, 具有大型稀疏的结构特点, 适用于迭代求解. 鞍点结构系数矩阵的不定性和较差的谱性质, 对相应线性系统的有效迭代求解造成了很大困难。 

本文主要关注产生于Navier-Stokes方程, 复线性系统等价变换, PDE约束优化等问题的鞍点结构线性系统的数值求解. 针对具体问题, 构造有效的迭代方法和预处理子。研究了非奇异鞍点问题的有效迭代求解. 设计了适用于产生于数值离散Navier-Stokes方程的鞍点问题的SIMPLE-like (SL)预处理子, 与若干同类预处理子相比SL预处理子可导出更好的收敛性质和谱分布结果. 构造了两类适用于广义鞍点问题的修正HSS(MHSS)预处理子, 相应MHSS迭代方法具有无条件收敛性, 且MHSS预处理的矩阵的谱性质优于HSS预处理的矩阵的谱性质. 通过技巧性利用Sherman-Morrison-Woodbury公式, 进一步改进了求解广义鞍点问题的非线性不精确Uzawa(NIU)迭代法的收敛性结果, 并构造和分析了三类具有更好收敛表现的变参数的NIU迭代法. 将子矩阵的经典矩阵分裂与Uzawa型迭代法相结合, 分别构造和分析了适用于系数矩阵(1,1)块为对称正定矩阵或具有非对称占优性质的非对称正定矩阵的鞍点问题的新的迭代法, 有效提升了同类方法的求解效率。研究了子矩阵为方阵的鞍点问题的有效迭代求解. 分析了SSOR迭代法求解由复线性系统的等价变换所得的块二乘二线性系统的收敛性和最优迭代参数的选取问题, 并构造和分析了具有更好的收敛表现的ASSOR迭代法且给出了更为实用的最优迭代参数选取值. 构造了适用于求解产生于时谐抛物优化控制问题的高效的结构化预处理子. 该预处理子的算法实现简单且相应的被预处理后的矩阵的特征值聚集在区间[1/2,1]内. 用于加速Krylov子空间方法时, 其数值表现稳定且优于已知的若干有效预处理子。研究了奇异鞍点问题的有效迭代求解. 将DPSS迭代法进行参数化和预处理变形, 构造了适用于求解奇异鞍点问题的具有无条件半收敛性的PDPSS迭代法, 并通过适当的松弛变形, 设计了具有更好的收敛表现和谱性质的RPDPSS预处理子. 加速求解奇异鞍点问题的GMRES方法时, 这两类预处理子展现出了优于HSS预处理子的加速效果. 通过奇异的预处理变形, 将产生于PU迭代法的PU分裂推广为了满足恰当分裂条件的GPU分裂. 基于该分裂, 构造了适用于求解奇异鞍点问题的GPU迭代法. GPU迭代法以及GPU预处理子加速的GMRES方法均可收敛到奇异鞍点问题的最小范数最小二乘解, 显著改善了PU迭代法求解奇异鞍点问题的数值表现。

Other Abstract

Within plenty of application backgrounds, linear systems of saddle point form arise widely from numerical solution procedure of related problems in scientific computing and engineering applications. As a class of special block linear systems, such linear systems have large and sparse structural features, which are suitable for iteration solution methods. Due to the indefiniteness and poor spectral properties of their coefficient matrices, it is difficult to solve them efficiently.

The primary focus of this thesis is the numerical solution of saddle point linear systems arising from problems such as Navier-Stokes equations, equivalent transformation of complex linear system and PDE-constrained optimization. Based on the specific problems, we construct efficient iteration methods and robust preconditioners. Iterative solution methods for nonsingular saddle point problems are studied. A class of SIMPLE-like (SL) preconditioners are constructed for solving saddle point problems arising form the Navier-Stokes equations. Compared with some similar preconditioners, the SL preconditioners can result in much better convergence and spectral distribution properties. Two modified HSS (MHSS) preconditioners are constructed for solving generalized saddle point problems. The corresponding MHSS iteration methods are convergent unconditionally. Moreover, the MHSS preconditioned matrices display much better spectral properties than the HSS and some other preconditioners. By technically using Sherman-Morrison-Woodbury formula, a further improved convergence result of the NIU algorithm for generalized saddle point problems is presented. Some adaptive versions of the NIU algorithm with variable iteration parameters are constructed, which exhibit much better numerical performance than the original NIU algorithms to solve generalized saddle point problems. Combining the classical matrix splitting of sub-matrix with Uzawa-type methods, we construct two class of iteration methods which are suitable for solving saddle point problems of coefficient matrix with symmetric positive definite (1,1) block and nonsymmetric positive definite but nonsymmetric dominate (1,1) block, respectively. The proposed methods improve the solving efficiency of the similar methods. Iterative solution methods for saddle point problems of coefficient matrix with square blocks are studied. The SSOR method is analyzed for solving block two-by-two linear systems arising from the equivalent transformation of the complex linear systems and the corresponding optimal iteration parameters are presented. An accelerated variant of the SSOR method, called ASSOR, is given, which has much better convergence properties. Moreover, a practical way to choose iteration parameters for the ASSOR method is proposed. A robust structured preconditioner is constructed for solving block two-by-two linear systems arising from optimal control problems constrained by the time-harmonic parabolic equations. The algorithmic implementation of the preconditioner is simple and the eigenvalues of the corresponding preconditioned matrix are located in the interval [1/2, 1]. When using to accelerate Krylov subspace methods, it outperforms some efficient known preconditioners. Iterative solution methods for singular saddle point problems are studied. Based on suitable parameterizing and preconditioning techniques, the DPSS iteration method is generalized to a PDPSS iteration method which is semi-convergent unconditionally for solving singular saddle point problems. Moreover, spectral properties of the corresponding DPSS preconditioned matrix are studied. A relaxed variant, called RPDPSS, is given, which results in much better convergence and spectral properties. The PDPSS and RPDPSS preconditioned GMRES method perform much better than the HSS preconditioned GMRES method for solving singular saddle point problems. By using a singular preconditioning technique, the PU splitting resulting from the PU iteration method is generalized to a GPU splitting which can result in proper splitting. Based on this splitting, a GPU iteration method is constructed for solving singular saddle point problems. The GPU iteration method and the GPU preconditioned GMRES method can both converge to the least squares solution. The obtained convergence results improve those for the PU method for solving singular saddle-point problems.

URL查看原文
Language中文
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/225638
Collection数学与统计学院
Recommended Citation
GB/T 7714
梁兆正. 鞍点结构线性系统的迭代求解[D]. 兰州. 兰州大学,2017.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[梁兆正]'s Articles
Baidu academic
Similar articles in Baidu academic
[梁兆正]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[梁兆正]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.