鞍点问题的PSS预处理技术

1鞍点问题的PSS预处理技术学生姓名：王小二学号：1209****专业班级：信息与计算科学12-*班2013年7月8日中国石油大学（华东）线性表的设计和实现摘要本文简要介绍了鞍点问题常用的预处理技术，重点介绍了PSS预处理技术，并首次研究了在参数很小的情况下，PSS预处理矩阵特征值的分布情况，用Navier-Stokes方程模型验证了所得理论结果的有效性。关键词：鞍点问题；特征值估计；预处理子；埃尔米特和反埃尔米特分裂ABSTRACTInthispaper,weprovideaconciseoverviewofsomepreconditioningtechniquesforsaddlepointproblems,andfocusonPSSpreconditioningtechnique.Whenparameterissufficientlysmall,wefirstlyanalysistheeigenvaluedistributionofthepreconditionedsaddlepointmatrices.Navier-Stokesequationmodelisusedtoillustratetheeffectivenessofthepresentedtheoreticalresults.中国石油大学（华东）Keywords:saddlepointproblem;eigenvalueestimate;preconditioner;Hermitianandskew-Hermitiansplitting此处插入目录第1章前言中国石油大学（华东）1.1鞍点问题背景鞍点问题经常出现在许多科学和工程的应用中，如约束最优化、约束与加权最小二乘问题、经济学、电磁学、图像重构、图像定位和识别等（文献[2,10,12,15,18,21]）。事实上大多数带约束条件的问题都可产生鞍点系统。许多应用问题可以用最小化约束问题阐述。通常一些问题是无限维的且非线性的，通过离散化，可以产生大规模有限维问题。这些问题通常被替换成一系列拥有线性等价约束条件的二次最小化约束问题：ufAuuTT21J(u)min（1-1）..tsgBu（1-2）其中nRAn对称半正定，nnmRfnmRB;，和mRg是给定的向量，一阶最优化条件是通过下面的线性系统给出的：gfpuOBBAT（1-3）其中，mRp是拉格朗日乘子矢量。（1-3）这种类型的线性系统被称为鞍点问题，因为其解pu,是下列拉格朗日函数的一个鞍点：pgBuufAuupuTTT21,L（1-4）拥有鞍点的线性系统也出现在一些离散的物理模型里，例如力学结构和RCL电路等。更一般的，认为拥有下列形式的线性系统是鞍点问题，其中A和B跟之前的形式一样，mmRC为对称半正定矩阵。bgfpuCBBAMxT（1-5）此系统产生于稳定的混合有限元法和描述微压缩流体，固体学的方程的离散化，加权最小二乘问题和优化中的内点法等，并且C相对于其它块来说有较小的模。这里，M是大型稀疏矩阵，因此一般情况下（1-5）要用迭代法解（文献[5,6,22,27,30,31]），但不幸的是对鞍点系统直接使用Krylov法时收敛速度很慢，这就需要对（1-5）进行预处理再使用Krylov子空间法以获取更快的收敛速度。在过去的几年里，为了找到有效地预处理子，国内外学者做了很多的工作（文献[1,33,14,15,17]）。本文将介绍一些比较常用的预处理子，并对PSS预处理子进行谱分析。1.2鞍点矩阵的性质本节介绍鞍点问题系数矩阵（鞍点矩阵）的有关性质，请见文[9]。称下面的高阶，稀疏和非奇异的线性系统为广义鞍点问题：gfpuCBBAT（1-6）其中nnRA半正定，即)(21TAAH对称半正定，nmRB满秩，mmRC对称半正定，且}0{)()(BNAN。改变（6）中第二行块的符号可以产生一个等价的鞍点问题：中国石油大学（华东）bgfpuCBBAMxT（1-7）记M为M的特征值集合，不管A是否对称，下面定理给出了不对称鞍点矩阵M的一些特定性质：定理1.1不对称鞍点矩阵M都有一些特定的性质：1.M非奇异。2.M是半正定的，即对任意的mnvR有,0TMvvvMv。3.M是正半稳定的，也就是说M的特征值的实部都是非负的，即对于所有)(M，Re()0。4.如果)(21TAAH是正定的，则M是正稳定的：对于所有)(M，Re()0。【证】证明第1个：构造0Mx，这里pux，则可以得到0,0CpBupBAuT和（1-8）从0Mx还可得到0CppAuuMxxTTT因为加号前后的两部分都是非负的，所以必定有0AuuT且0CppT但是0HuuAuuTT因为H是对称半正定的，所以)(HNu（看文献[19]第400页）。类似的，0CppT，由C对称半正定可得0Cp，因此（用（1-8）的第二个式子）0Bu。由()(){0}uNBNH可得0u。但是如果0u从（1-8）的第一个式子我们可以得到0pBT，由B满秩可得0p。因此0Mx唯一的解是零解，所以M非奇异。证明第2个：对于任意的mnRv我们有vMvMvvTT，这里CHMMMT00)(21是M的对称部分。很明显M是半正定的。证明第3个：记M的特征对为),(v，这里12v。可得Mvv*，**)(Mvv=vMvT*。中国石油大学（华东）因此*1()Re()22TvMMv。从而有*()()()()()()()0TTTTTvMMvRvMMRvSvMMSv证明第4个：记M的特征对为),(v，其中puv从而有**()()()()()()()()()0TTTTRuHupCpRuHRuSuHSuRpCRpSpCSp只有当0u（因为假设H正定）和0Cp时这个值才有可能为零。但是如果0u，由（1-8）的第一个式子可得0pBT，因为B是满秩的，因此可得0p。所以0v，与题设矛盾。证明完毕。值得注意的是，通过改变（1-6）的后m个方程的符号，鞍点问题可能会失去对称性（当A对称时），但获得了（半）正定性，而且可使用特定的Krylov子空间法。1.3一些鞍点问题预处理技术在本节我们介绍一些常用的鞍点问题的预处理子，包括块对角预处理子，块三角预处理子，约束预处理子，HSS和PSS预处理子。1.3.1块预处理子1.块对角预处理子如果M是非奇异的，鞍点矩阵M可进行块三角分解：IOBAISOOAIBAOICBBAMTT11（1-9）对于可逆的非对称鞍点矩阵:CBBAMT21且C为零矩阵，那么基本的块对角预处理子为：SOOAPd其中TBABS112-是Schur余，那么左预处理后的矩阵为MPd1=OBSBAIT2111假设矩阵MPd1是非奇异的，像在文献[9]里指出的一样，它满足中国石油大学（华东）051215121111IMPIMPIMPddd由此可见MPd1是可对角化的而且只有三个不同的特征值，即1,5121,5121所以，将GMRES方法应用于此预处理系统中,在不计舍入误差的情况下，只需要三步就能达方程组的准确解。2.块三角预处理子块三角预处理子首先由Bramble和Pasciak提出，其基本形式为：SOBAPTt（1-10）可以验证块三角预处理矩阵的谱为)(1MPt={1},并且最小特征多项式的次数为2,也就是在一定条件下GMRES方法在最多两步内就能够达到方程组准确解（不计舍入误差）.然而由于估计MPt1的收敛性是比较困难的.Loghin和Wathen（文献[32]）已经讨论了其预处理矩阵的特征值的界,以及GMRES的收敛性估计。1.3.2约束预处理子对于鞍点问题（1-3），约束预处理子具有如下形式：0BBHpT其中nnRH（见文献[27,29]），是原鞍点问题系数矩阵中A的某种近似。如果H对称正定的，那么左预处理矩阵为：IXAHIBBABBHGTT0)(001其中TTTTIAHBBBHXBBBHBH)()()(111111当nm时，得出I,而且预处理矩阵的特征值等于1，并且0)(0002IMXIM所以，此预处理矩阵的最小多项式的次数为2，将GMRES应用于此预处理系统中，只需要两步就能达到方程组的准确解（不计舍入误差），约束预处理子已经被普遍应用于求解混合有限元所产生的鞍点问题。1.3.3HSS和PSS预处理子鞍点问题（1-7）中系数矩阵M的HSS分解为SHM（文献[4]），其中中国石油大学（华东）02,002BBAASCAAHTTT对（1-7）的HSS预处理子是下面的形式RSIHIPmnmn0),)((21Benzi和Golub（文献[8]）和Benzi,Gander,Golub（文献[7]）使用它来加快应用于广义鞍点问题的HSS迭代方法的收敛速度（文献[4]）。当A对称正定且B满秩时，文献[8]中可以看到预处理矩阵MP1的特征值都包含在下面的集合中}1|1||{zCz因此MP1的特征值都有正实数部分。Simoncini和Benzi深入的研究了当C=0时MP1特征值分布情况（文献[26,11,24]）。他们发现当参数足够小时，MP1的特征值全为实数，而且有两个聚集点，一个是（0,0），另一个是（2,0）。类似的，鞍点矩阵（1-7）中M的PSS分解为SPM，其中00,00BBSCAPT对（1-7）的PSS预处理子是下面的形式RSIPIPmnmn0),)((21经过PSS预处理子预处理后的鞍点矩阵特征值分布有一定的规律性，在接下来的章节我们会进行具体介绍。第2章PSS预处理子谱性质研究中国石油大学（华东）2.1PSS预处理子谱性质以往文献主要研究了鞍点问题（1-7）中0C的情况（文献[3,11]），本章将研究在0C的情况下使用PSS预处理子预处理后矩阵MP1的特征值估计。在这里A为正定矩阵。为了方便，记mmn...,...,...212121分别为A的特征值，C的特征值和B的奇异值；并记)(),(),(CrankrBrankrArankrcba下面的定理展示了对于充分小的0，MP1的特征值分布情况。定理2.1当0充分小时(i)如果mrb，则MP1有crm个特征值聚集在（0,0）附近，有crn个特征值集在（2,0）附近。(ii)如果mrc，则MP1有br2个特征值聚集在（0,0）附近，brmn2个特征值聚集在（2,0）附近。(iii)如果mrb，则MP1有)(brii个特征值聚集在（0,0）附近，有)(brnjj个特征值聚集在（2,0）附近，剩下的特征值聚集在)(,,...,2,1,-1jimnppkk附近，这里1,0)Im(kk。【证】根据文献[8]，MP1的特征值同MInm的特征值相同，这里11))(())((SISIHIHIMmnmnmnmn因为A是正定矩阵，C是对称矩阵，因此存在正交矩阵nnRE和上三角矩阵nnRQ及mmR