鞍点问题的PSS预处理技术

1、中国石油大学（华东）鞍点问题的PSS预处理技术学生姓名：王小二学 号：1209*专业班级：信息与计算科学12-*班 2013年7月8日线性表的设计和实现摘 要本文简要介绍了鞍点问题常用的预处理技术，重点介绍了PSS预处理技术，并首次研究了在参数很小的情况下，PSS预处理矩阵特征值的分布情况，用Navier-Stokes方程模型验证了所得理论结果的有效性。关键词：鞍点问题；特征值估计；预处理子；埃尔米特和反埃尔米特分裂ABSTRACTIn this paper, we provide a concise overview of some preconditioning techniques fo

2、r saddle point problems, and focus on PSS preconditioning technique. When parameter is sufficiently small, we firstly analysis the eigenvalue distribution of the preconditioned saddle point matrices. Navier-Stokes equation model is used to illustrate the effectiveness of the presented theoretical re

3、sults.Keywords: saddle point problem; eigenvalue estimate; preconditioner; Hermitian and skew-Hermitian splitting此处插入目录第1章 前 言1.1 鞍点问题背景鞍点问题经常出现在许多科学和工程的应用中，如约束最优化、约束与加权最小二乘问题、经济学、电磁学、图像重构、图像定位和识别等（文献2,10,12,15,18,21）。事实上大多数带约束条件的问题都可产生鞍点系统。许多应用问题可以用最小化约束问题阐述。通常一些问题是无限维的且非线性的， 通过离散化，可以产生大规模有限维问题。这些问

4、题通常被替换成一系列拥有线性等价约束条件的二次最小化约束问题：（1-1） （1-2）其中对称半正定， 和 是给定的向量，一阶最优化条件是通过下面的线性系统给出的：（1-3）其中，是拉格朗日乘子矢量。（1-3）这种类型的线性系统被称为鞍点问题，因为其解 是下列拉格朗日函数的一个鞍点：（1-4）拥有鞍点的线性系统也出现在一些离散的物理模型里，例如力学结构和RCL电路等。更一般的，认为拥有下列形式的线性系统是鞍点问题，其中和跟之前的形式一样，为对称半正定矩阵。（1-5）此系统产生于稳定的混合有限元法和描述微压缩流体，固体学的方程的离散化，加权最小二乘问题和优化中的内点法等，并且相对于其它块来说有较小

5、的模。这里，是大型稀疏矩阵，因此一般情况下（1-5）要用迭代法解（文献5,6,22,27,30,31），但不幸的是对鞍点系统直接使用Krylov法时收敛速度很慢，这就需要对（1-5）进行预处理再使用Krylov子空间法以获取更快的收敛速度。在过去的几年里，为了找到有效地预处理子，国内外学者做了很多的工作（文献1,33,14,15,17）。本文将介绍一些比较常用的预处理子，并对PSS预处理子进行谱分析。1.2 鞍点矩阵的性质本节介绍鞍点问题系数矩阵（鞍点矩阵）的有关性质，请见文9。称下面的高阶，稀疏和非奇异的线性系统为广义鞍点问题：（1-6）其中半正定，即对称半正定，满秩，对称半正定，且。改变（

6、6）中第二行块的符号可以产生一个等价的鞍点问题：（1-7）记为的特征值集合，不管是否对称，下面定理给出了不对称鞍点矩阵的一些特定性质：定理1.1 不对称鞍点矩阵都有一些特定的性质：1.非奇异。2.是半正定的，即对任意的有。3.是正半稳定的，也就是说的特征值的实部都是非负的，即对于所有，。4.如果是正定的，则是正稳定的：对于所有，。【证】证明第1个：构造，这里，则可以得到（1-8）从还可得到因为加号前后的两部分都是非负的，所以必定有且但是因为是对称半正定的，所以（看文献19第400页）。类似的，由对称半正定可得，因此（用（1-8）的第二个式子）。由可得。但是如果从（1-8）的第一个式子我们可以得

7、到，由满秩可得。因此唯一的解是零解，所以非奇异。证明第2个：对于任意的我们有，这里是的对称部分。很明显是半正定的。证明第3个：记的特征对为，这里。可得，=。因此。从而有证明第4个：记的特征对为，其中从而有只有当（因为假设正定）和时这个值才有可能为零。但是如果，由（1-8）的第一个式子可得，因为是满秩的，因此可得。所以，与题设矛盾。证明完毕。值得注意的是，通过改变（1-6）的后个方程的符号，鞍点问题可能会失去对称性（当对称时），但获得了（半）正定性，而且可使用特定的Krylov子空间法。1.3 一些鞍点问题预处理技术在本节我们介绍一些常用的鞍点问题的预处理子，包括块对角预处理子，块三角预处理子，

8、约束预处理子，HSS和PSS预处理子。1.3.1 块预处理子1.块对角预处理子如果是非奇异的，鞍点矩阵可进行块三角分解：（1-9）对于可逆的非对称鞍点矩阵:且为零矩阵，那么基本的块对角预处理子为：其中是Schur余，那么左预处理后的矩阵为=假设矩阵是非奇异的，像在文献9里指出的一样，它满足由此可见是可对角化的而且只有三个不同的特征值，即1,所以，将GMRES方法应用于此预处理系统中, 在不计舍入误差的情况下，只需要三步就能达方程组的准确解。2.块三角预处理子块三角预处理子首先由 Bramble 和 Pasciak提出，其基本形式为：（1-10）可以验证块三角预处理矩阵的谱为=1 , 并且最小特

9、征多项式的次数为 2, 也就是在一定条件下GMRES方法在最多两步内就能够达到方程组准确解（不计舍入误差）. 然而由于估计 的收敛性是比较困难的. Loghin 和Wathen（文献32）已经讨论了其预处理矩阵的特征值的界, 以及 GMRES 的收敛性估计。1.3.2 约束预处理子对于鞍点问题（1-3），约束预处理子具有如下形式：其中（见文献27,29），是原鞍点问题系数矩阵中的某种近似。如果对称正定的，那么左预处理矩阵为：其中当时，得出,而且预处理矩阵的特征值等于1，并且所以，此预处理矩阵的最小多项式的次数为2，将GMRES应用于此预处理系统中，只需要两步就能达到方程组的准确解（不计舍入误差

10、），约束预处理子已经被普遍应用于求解混合有限元所产生的鞍点问题。1.3.3 HSS和PSS预处理子鞍点问题（1-7）中系数矩阵的HSS分解为（文献4），其中对（1-7）的HSS预处理子是下面的形式Benzi和Golub（文献8）和Benzi,Gander,Golub（文献7）使用它来加快应用于广义鞍点问题的HSS迭代方法的收敛速度（文献4）。当对称正定且满秩时，文献8中可以看到预处理矩阵的特征值都包含在下面的集合中因此的特征值都有正实数部分。Simoncini和Benzi深入的研究了当=0时特征值分布情况（文献26,11,24）。他们发现当参数足够小时，的特征值全为实数，而且有两个聚集点，一个

11、是（0,0），另一个是（2,0）。类似的，鞍点矩阵（1-7）中的PSS分解为，其中对（1-7）的PSS预处理子是下面的形式经过PSS预处理子预处理后的鞍点矩阵特征值分布有一定的规律性，在接下来的章节我们会进行具体介绍。第2章 PSS预处理子谱性质研究2.1 PSS预处理子谱性质以往文献主要研究了鞍点问题（1-7）中的情况（文献3,11），本章将研究在的情况下使用PSS预处理子预处理后矩阵的特征值估计。在这里为正定矩阵。为了方便，记分别为的特征值，的特征值和的奇异值；并记下面的定理展示了对于充分小的，的特征值分布情况。定理2.1 当充分小时 (i)如果，则有个特征值聚集在（0,0）附近，有个特征

12、值集在（2,0）附近。(ii)如果，则有个特征值聚集在（0,0）附近，个特征值聚集在（2,0）附近。(iii)如果，则有个特征值聚集在（0,0）附近，有个特征值聚集在（2,0）附近，剩下的特征值聚集在附近，这里。【证】 根据文献8，的特征值同的特征值相同，这里因为是正定矩阵，是对称矩阵，因此存在正交矩阵和上三角矩阵及使得（2-1）其中考虑的奇异值分解（2-2）其中和是正交矩阵(文献19),根据分解（2-1）和（2-2）以及文献13中定理2.1的证明，我们有其中当时，容易得到综上可得 现在我们考虑下面三种情况：（1）：（2）：（3）：因为和都是正交矩阵，根据特征值的连续性和上面的（1）到（3）种

13、情况，定理得证。注：（1）一个好的聚合性质通常可以使预处理Krylov子空间迭代法有一个快的收敛速度，可以参考文献23。当对称正定且满秩时，上述定理证明了在正参数足够小的情况下，PSS预处理矩阵的特征值有两个聚集点，一个是（0,0），另一个是（2,0）。当和均为对称正定时有相似的结论。这个定理解释了为什么“最佳”迭代参数（可以使收敛速度最快的参数）通常很小。（2）当时，在足够小的情况下，的特征值不仅聚集在（0，0）和（2,0）附近，还会聚集在别的点周围。因此如果不满秩的话，的性质可能会恶化。（3）当（文献26中命题3.3）时，在足够小的情况下，的特征值都是实数，且聚集在0和2附近。但是当时，不

14、管多小，都会有复特征值。例如，考虑下面的不对称鞍点矩阵有的特征值是这表明除非=1否则没有实特征值。就像上面定理所讲，我们还会得到这个结论。（4）在文献20中也研究了的谱性质。作者提出，当是赫尔米特矩阵，满秩，是赫尔米特半正定矩阵时，在充分小的情况下，的特征值都聚集在（0,0）附近和（2,0）附近（看文献20中定理3.1）。但不幸的是，当对称半正定时，上面的结论是不成立的。例如，令通过MATLAB计算，表一是对应于不同的，的特征值。表2-1 特征值情况特征值11.000000000000001.999996000807682.000000000000002.000000000000002.000

15、000000000002.00000000000000很明显，当趋向于零时，的三个特征值趋向于1+i,1-i和2。因此在足够小的时候，复特征值是不聚集在（0,0）或（2,0）附近的。2.2 数值试验本节将进行一些数值试验来佐证提出的定理（文献28,29）。IFISS软件是由Silvester,Elman和Ramage（文献25）开发的，它可用来离散不可压缩的稳态Stokes方程： in -div in 其中，是速度，表示流体的压力。所测试的问题是在方形区域上的二维漏盖驱动腔问题。边界条件是狄利克雷无流量条件。在上表面的水平非零速度选为。混合有限元使用的是对有限元。这里产生的非对称鞍点矩阵的（1

16、,1）块是正定的，（1,2）块是不满秩的。现构建三个不对称鞍点矩阵：:当稳定参数选为0.25时，产生。:去掉中的后两行和的后两行和后两列，这时的是满秩的。:中替换为。现验证所得理论结果。对应于的预处理子记为。在16*16网格上取不同的，图1，2，3展示了特征值的情况。 图2-1 图2-2 图2-3 随着的逐渐减小，的特征值聚集在（2,0）和（0,0）附近，就像定理2.1中（i）所示。图4,5,6展示特征值分布情况，此时不满秩。图2-4 图2-5 图2-6 随着逐渐减小，特征值部分在（0,0），（2,0）附近聚集，部分不在，这验证了定理2.1的（iii）。图7,8,9展示了特征值的分布情况，此时

17、是满秩的。图2-7 图2-8 图2-9 由图可以明显看出随着的减小，特征值逐渐聚集在（0,0）和（2,0）附近。这验证了定理2.1的（ii）。第3章 结 论本文简要介绍了鞍点问题常用的预处理技术，包括块对角预处理技术，块三角预处理技术，约束预处理技术，HSS和PSS预处理技术等，重点介绍了PSS预处理技术，研究了在参数很小的情况下，PSS预处理矩阵特征值的分布情况，具体结论如下所示：（1）当鞍点矩阵的（2,1）块满秩时，预处理矩阵的特征值聚集在（0,0）附近的个数为的秩数加的秩数，其余的聚集在（2,0）附近。（2）当鞍点矩阵的（2,2）块满秩时，预处理矩阵的特征值聚集在（0,0）附近的个数为二

18、倍的的秩数，其余的聚集在（2,0）附近。（3）当鞍点矩阵的（2,2）块不满秩时，预处理矩阵的特征值聚集在（0,0）附近的个数为（的秩数），有（的秩数减去的秩数）。其余的比较分散，但模为1。以后的研究应着重于PSS预处理技术的实际执行与应用，并和HSS预处理技术进行比较。参考文献1 O. Axelsson. Preconditioning of indefinite problems by regularization. SIAM J. Numer. Anal.,16 (1979): pp. 5869.2 O. Axelsson and M. Neytcheva. Preconditioning

19、 methods for linear systems arising in constrained optimization problems. Numer. Linear Algebra Appl., 10 (2003): pp. 331.3 O. Axelsson and M. Neytcheva. Eigenvalue estimates for preconditioned saddle point matrices. Numer. Linear Algebra Appl., 13 (2006): pp. 339360.4 Z. Z. Bai, G. H. Golub, and M.

20、 K. Ng. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl., 24 (2003): 603626.5 R. E. Bank, B. D. Welfert, and H. Yserentant. A class of iterative methods for solving saddle point problems. Numer. Math., 56 (1990): 645666.6 M

21、. Benzi. A generalization of the Hermitian and skew-Hermitian splitting iteration. SIAM J. Matrix Anal. Appl., 31 (2009): 360374.7 M. Benzi, M. J. Gander, and G. H. Golub. Optimization of the Hermitian and skew-Hermitian splitting iteration for saddle-point problems. BIT, 43 (2003): 881900.8 M. Benz

22、i and G. H. Golub. A preconditioner for generalized saddle point problems. SIAM J.Matrix Anal. Appl., 26 (2004): 2041. 9 M. Benzi, G. H. Golub, and J. Liesen. Numerical solution of saddle point problems. Acta Numer., 14 (2005): 1137. 10 M. Benzi and M. K. Ng. Preconditioned iterative methods for wei

23、ghted Toeplitz least squares problems. SIAM J. Matrix Anal. Appl., 27 (2006): 11061124. 11 M. Benzi and V. Simoncini. On the eigenvalues of a class of saddle point matrices. Numer. Math., 103 (2006): 173196.12 J. H. Bramble and J. E. Pasciak. A preconditioning technique for indefinite systems result

24、ing from mixed approximations of elliptic problems. Math. Comp., 50 (1988): 117.13 L. C. Chan, M. K. Ng, and N. K. Tsing. Spectral analysis for HSS preconditioners. Numer. Math. Theory Methods Appl., 1 (2008): 5577.14 C. R. Dohrmann and R. B. Lehoucq. A primal-based penalty preconditioner for ellipt

25、ic saddle point systems. SIAM J. Numer. Anal., 44 (2006): 270282.15 H. S. Dollar. Constraint-style preconditioners for regularized saddle point problems. SIAMJ. Matrix Anal. Appl., 29 (2007): 672684.16 B. Fischer, A. Ramage, D. J. Silvester, and A. J. Wathen. Minimum residual methods for augmented s

26、ystems. BIT, 38 (1998): 527543.17 M. V. Gorelova and E. V. Chizhonkov. Preconditioning saddle point problems with the help of saddle point operators. Comput. Math. Math. Phys., 44 (2004): 14451455.18 C. Greif and D. Schotzau. Preconditioners for the discretized time-harmonic Maxwell equations in mix

27、ed form. Numer. Linear Algebra Appl., 14 (2007): 281297.19 R. A. Horn and C. A. Johnson. Matrix analysis. Cambridge University Press, Cambridge,1985.20 T. Z. Huang, S. L. Wu, and C. X. Li. The spectral properties of the Hermitian and skew-Hermitian splitting preconditioner for generalized saddle poi

28、nt problems. J. Comput. Appl.Math., 229 (2009): 3746.21 C. Keller, N. I. M. Gould, and A. J. Wathen. Constraint preconditioning for indefinite linear systems. SIAM J. Matrix Anal. Appl., 21 (2000): 13001317.22 J. Liesen and B. N. Parlett. On nonsymmetric saddle point matrices that allow conjugate gr

29、adient iterations. Numer. Math., 108 (2008): 605624.23 Y. Saad. Iterative methods for sparse linear systems. 2nd ed., SIAM, Philadelphia, PA, 2003.24 S. Q. Shen, T. Z. Huang, and G. H. Cheng. A condition for the nonsymmetric saddle point matrix being diagonalizable and having real and positive eigenvalues. J. Comput. Appl. Math., 220 (2008): 812.25 D. J. Silvester, H. C. Elman,and A. Ramage. IFISS: Incompressible Flow Iterative Solution Software http:/www.manchester.ac.uk/ifiss.26 V. Simoncini and M. Benzi. Spectral properties of the Hermitian