论文总字数：15370字

摘 要

鞍点问题大多来自于科学和工程计算领域。其中包含解约束最小二乘问题、解带有限制条件的二次优化问题、方程的解法问题...，对于低维线性系统可以用直接法求得，而对于高维数系数矩阵的鞍点系统用直接法是不现实的。我们可以利用降维思想，将鞍点系统分解为两个低维的线性方程，而这两个线性方程可以用迭代法来求得。Uzawa算法就是在此思想上形成的有效求解鞍点系统的算法，Uzawa算法格式简单，但是收敛速度较慢，为了快速有效的解决鞍点问题，本文在Uzawa算法的基础上将经典的Jacobi迭代、Gauss-Seidel迭代、SOR迭代推广到鞍点系统，并对这些迭代方法的收敛性做了详细的研究，通过引入参数改进迭代方法用来加快收敛速度，并对最优参数的选取做了相应的研究。最后列举了经典的数值案例来检验这些算法的正确性和有效性。

关键词：鞍点问题；精确的Uzawa方法；非精确的Uzawa方法；Jacobi迭代法；Gauss-Seidel迭代法；SOR方法

Abstract

Saddle point problems arise from a wide range of scientific and engineering calculations. Among them are constraint least squares problem, quadratic optimization problem with constraint condition, computational fluid mechanics problem in engineering mechanics and the famous finite element method of Navier-Stokes equation. The saddle point problem of coefficient matrix are mostly high class and is sparse, for low dimensional linear system can be obtained by the direct method, and for high dimension matrix of saddle points system using the direct method is not realistic. We can decompose the saddle point system into two low dimensional linear equations by using the dimensionality reduction theory, and these two linear equations can be obtained by iterative method. Here is the Uzawa algorithm thought is formed on a saddle point system is an effective algorithm, Uzawa algorithm format is simple, but the convergence speed is slow, in order to quickly and efficiently solve the problem of saddle points, this article in Uzawa algorithm will be the basis of the classical Jacobi iteration, the Gauss-Seidel iterative, SOR iteration to saddle point system, and the convergence of these iterative methods made detailed research, by introducing a parameter improved iteration method is used to accelerate the convergence speed, and the selection of the optimal parameters to do the relevant research. Finally, the classical numerical examples are given to verify the correctness and validity of these algorithms.

Key words: saddle- point problem; the accurate uzawa method; the inaccurate uzawa method; jacobi iterative method; gauss-seidel iterative method; SOR method

目录

摘 要 I

Abstract Ⅱ

第一章 引言 1

1.1 研究相关背景 1

1.2 研究鞍点问题的意义 2

第二章 迭代方法的理论研究................................................. 2

2.1 迭代法的一般形式 2

2.2 几种常见的迭代格式 3

2.3 迭代法的收敛性 5

第三章 鞍点问题的迭代方法 8

3.1 精确的uzawa方法 8

3.2不精确的uzawa方法 9

3.2.1 uzawa-jacobi方法 10

3.2.2 uzawa-gauss-seidel方法 12

3.2.3 uzawa-sor 方法 13

第四章 数值案例 15

4.1 案例4.1 15

4.2 案例4.2 17

参考文献 20

致谢 21

第一章 引言

1.1 研究相关背景

本文主要考虑如下的块状线性系统

(1.1)

其中，，通常，，向量,。

当矩阵是正定对称的（即满足且是正定对称的），且矩阵是对称和半正定的，且矩阵是列满秩时，这样就能保证（1.1）存在唯一的解；当时，我们称（1.1）为广义的鞍点问题；当时，我们称（1.1）为鞍点问题。

科学与工程计算领域中大多会有鞍点问题的出现。比如工程力学中的计算流体力学问题，解Navier-Stokes方程[^[1]]，解电磁学问题等[^[2]]，，然而迭代法求解高阶线性系统具有降低计算开支、节省存储空间等好处，所以研究这些鞍点问题的有效迭代解法具有很重要的现实意义。

如今已经研究出很多有效的求解系统（1.1）的算法，其中包括基于矩阵分裂的Uzawa方法、非精确的Uzawa方法[^[3]]和预条件Uzawa方法[^[4]]、在Uzawa算法的基础上可以引入不同的迭代法，如Sor-like方法[^[5]]、Gsor[^[6]]方法以及一些与此类似的基本迭代方法等。为了加快收敛速度，这些方法都引入了合适的参数，并详细地研究了怎样选取最优参数。本文在Uzawa算法的基础上将经典的迭代方法如Jacobi迭代,Gauss-Seidel迭代,SOR迭代推广到鞍点系统，对迭代方法的收敛性做了详细的研究，通过引入参数改进迭代方法以加快收敛速度。

请支付后下载全文，论文总字数：15370字