基于PSS迭代分裂的广义鞍点问题求解

仝 秋 娟

(西安邮电大学 理学院,西安 710121)



基于PSS迭代分裂的广义鞍点问题求解

仝 秋 娟

(西安邮电大学 理学院,西安 710121)

基于正定和反Hermite分裂(PSS)迭代技术,给出求解广义鞍点问题的一种广义Uzawa迭代法——修正局部PSS迭代算法,分析了该方法的收敛性,并用数值算例验证了新算法的有效性.

广义鞍点问题；PSS迭代分裂；收敛

鞍点问题属于线性代数方程组,来源于科学计算的很多实际问题中,如流体动力学(Stokes问题)、最小二乘问题、优化问题、椭圆型偏微分方程的混合有限元离散、结构分析和图像处理等[1].目前,关于鞍点问题的迭代求解方法已有很多,其中最经典的是Uzawa方法[2].Uzawa方法实现简单,但耗时较长.为此,文献[3-5]提出了不精确Uzawa方法,避免了求逆困难;文献[6]提出了预条件Uzawa方法;文献[7-10]给出了非线性Uzawa算法及其收敛性.本文基于经典的Uzawa方法及正定和反Hermite分裂(PSS)迭代方法给出一种广义的Uzawa方法求解广义鞍点问题.数值实验表明新方法比经典Uzawa方法更有效.

1 预备知识

定义1[11]对于大型稀疏线性方程组

(1)

由文献[12]知,对于正定线性方程组

(2)

(3)

其中:α为给定的正常数;I为单位矩阵.

引理1[13]若A∈Cn×n是正定矩阵,且A=P+S,其中:P为正定矩阵;S为反Hermite矩阵;α为给定的正常数, 则PSS迭代法的迭代矩阵M(α)为

M(α)=(αI+S)-1(αI-P)(αI+P)-1(αI-S).

令V(α)=(αI-P)(αI+P)-1,则迭代矩阵M(α)谱半径ρ(M(α))的上界为‖V(α)‖2,且满足

ρ(M(α))≤‖V(α)‖2<1, ∀α>0.

即对于任意给定的初始向量,PSS迭代法收敛于线性方程组Ax=b的唯一解.

引理2[11]设Σ∈C(m+n)×(m+n)为式(1)的系数矩阵.给定A为非Hermite正定矩阵,B为行满秩;ρ(Σ)为矩阵Σ的谱半径,且λ∈ρ(Σ)为Σ的一个特征值.则有:

1)Σ为非奇异矩阵,且det(Σ)>0；

2)Σ为半定矩阵,即对于任何v∈Cm+n(v≠0)有Re(v*Σv)≥0；

3)Σ为正稳定矩阵,即对于任何λ∈ρ(Σ)有Re(λ)>0.

引理3[13]若S为反Hermite矩阵,则iS(i为虚数单位)为Hermite矩阵,且对于任意的u∈Cn,u*Su为纯虚数或0.

2 广义鞍点问题修正的局部PSS迭代算法及其收敛性

其中:U∈Cm×r和V∈Cm×(m-r)为C零空间的一组基;R∈Cr×r为对角矩阵,且其对角线元素为矩阵C的特征值.由

可得

(4)

下面求解式(1)的广义鞍点问题.为此,将式(4)分块写成如下形式:

(5)

对式(5)应用修正的局部PSS方法,即

(6)

(7)

即

(8)

其迭代矩阵为

(9)

可写成

(10)

写成矩阵乘积形式为

(11)

(12)

(13)

(14)

(15)

式(15)可写成

(16)

求解式(16)可得当式(13)成立时,迭代格式收敛.

3 数值实验

例1在Ω内考虑Navier-Stokes问题[15-18]:

(17)

其中:Ω=(0,1)×(0,1)⊂2为方形区域,∂Ω为Ω的边界条件;Δ为Laplace算子;向量函数μ为Ω上的速度;数量函数ω为压力.对问题(17)采用基于正方元的ne×ne均匀格有限元重分法,可得形如式(1)的广义鞍点问题.

表1～表3分别列出了用经典Uzawa方法、块LU方法[18]和修正局部PSS迭代法对例1的数值结果.

表1 经典Uzawa方法Table 1 Classical Uzawa method

表2 块LU方法Table 2 Block LU method

表3 修正局部PSS迭代法Table 3 Modified local PSS iterative method

由表1～表3可见,新算法在求解广义鞍点问题时优于其他两种方法.

[1] Benzi M,Golub G H,Liesen J.Numerical Solution of Saddle Point Problems [J].Acta Numer,2005,14:1-137.

[2] Arrow Z K,Hurwice L,Uzawa H.Studied in Nonlinear Programming [M].Stanford:Stanford University Press,1958.

[3] Elman H C,Golub G H.Inexact and Preconditioned Uzawa Algorithms for Saddle Point Problems [J].SIAM J Numer Anal,1994,31(6):1645-1661.

[4] Bramble J H,Pasciak J E,Vassilev A T.Analysis of the Inexact Uzawa Algorithm for Saddle Point Problems [J].SIAM J Numer Anal,1997,34(3):1072-1092.

[5] Bramble J H,Pasciak J E,Vassilev A T.Uzawa Type Algorithms for Non Symmetric Saddle Point Problems [J].Math Comput,2000,69(230):667-689.

[6] Elman H,Silvester D.Fast Nonsymmetric Iterations and Preconditioning for Navier-Stokes Equations [J].SIAM J Sci Comput,1996,17(1):33-46.

[7] CAO Zhihao.Fast Uzawa Algorithm for Generalized Saddle Point Problems [J].Appl Numer Math,2003,46(2):157-171.

[8] CAO Zhihao.Fast Uzawa Algorithms for Sloving Non-symmetric Stabilized Saddle Point Problems [J].Numer Linear Algebra Appl,2004,11(1):1-24.

[9] LIN Yiqin,CAO Yanhua.A New Nonlinear Uzawa Algorithm for Generalized Saddle Point Problems [J].Appl Math Comput,2006,175(2):1432-1454.

[10] 吴静.线性方程组分裂迭代法与广义鞍点问题Uzawa算法研究 [D].成都：电子科技大学,2009.(WU Jing.The Study of Splitting Iterative Methods for Equations of Linear Systems and Uzawa-Type Algorithms for Generalized Saddle Point Problems [D].Chengdu:University of Electronic Science and Technology of China,2009.)

[11] 曹阳,谈为伟,蒋美群.广义鞍点问题的松弛维数分解预条件子 [J].计算数学,2012,34(4):350-360.(CAO Yang,TAN Weiwei,JIANG Meiqun.A Relaxed Dimensional Factorization Preconditioner for Generalized Saddle Point Problems [J].Mathematica Numerica Sinica,2012,34(4):350-360.)

[12] BAI Zhongzhi,Golub G H,LU Linzhang,et al.Block Triangular and Skew-Hermitian Splitting Methods for Positive-Definite Linear System [J].SIAM J Sci Comput,2005,26(3):844-863.

[13] JIANG Meiqun,CAO Yang.On Local Hermitian and Skew-Hermitian Splitting Iteration Methods for Generalized Saddle Point Problems [J].Journal Comput Appl Math,2009,231(2):973-982.

[14] BAI Zhongzhi,WANG Zengqi.On Parameterized Inexact Uzawa Methods for Generalized Saddle Point Problems [J].Linear Algebra Appl,2008,428(11/12):2900-2932.

[15] BAI Zhongzhi,Parlett B N,WANG Zengqi.On Generalized Successive Overrelaxation Methods for Augmented Linear Systems [J].Numer Math,2005,102(1):1-38.

[16] Benzi M,Ng M,NIU Qiang,et al.A Relaxed Dimensional Factorization Preconditioner for the Incompressible Navier-Stokes Equations [J].J Comput Phys,2011,230(16):6185-6202.

[17] Benzi M,GUO Xueping.A Dimensional Split Preconditioner for Stokes and Linearized Navier-Stokes Equations [J].Appl Numer Math,2011,61(1):66-76.

[18] 胡泽均.基于预处理Navier-Stokes方程的一类子系统的求解方法研究 [D].成都：电子科技大学,2013.(HU Zejun.Study on Solution Methods for Subsystems Based on Preconditioned Navier-Stokes Equations [D].Chengdu:University of Electronic Science and Technology of China,2013.)

(责任编辑：赵立芹)

SolvingtheGeneralizedSaddle-PointProblemsBasedonthePSSSplittingIterativeMethod

TONG Qiujuan

(SchoolofSciences,Xi’anUniversityofPostandTelecommunications,Xi’an710121,China)

We presented a generalized Uzawa iterative method for solving the generalized saddle-point problems based on the positive definite and skew-Hermitian splitting (PSS)iterative method,that is,the modified local PSS iterative method,and analyzed the convergence of the method.Numerical results are illustrated to show that the effectiveness of the new algorithm.

generalized saddle-point problems;PSS splitting iterative;convergence

10.13413/j.cnki.jdxblxb.2015.03.10

2014-10-08.

仝秋娟(1977—),女,汉族,博士,副教授,从事数值代数、矩阵理论和快速算法的研究,E-mail：xiaotong0929@163.com.

国家自然科学基金(批准号：11401469)和陕西省自然科学基金(批准号：2014JQ1030).

O241.6

：A

：1671-5489(2015)03-0401-06