基于PSS迭代分裂的廣義鞍點問題求解

仝 秋 娟

(西安郵電大學 理學院,西安 710121)

?

基于PSS迭代分裂的廣義鞍點問題求解

仝 秋 娟

(西安郵電大學 理學院,西安 710121)

基于正定和反Hermite分裂(PSS)迭代技術,給出求解廣義鞍點問題的一種廣義Uzawa迭代法——修正局部PSS迭代算法,分析了該方法的收斂性,并用數(shù)值算例驗證了新算法的有效性.

廣義鞍點問題；PSS迭代分裂；收斂

鞍點問題屬于線性代數(shù)方程組,來源于科學計算的很多實際問題中,如流體動力學(Stokes問題)、最小二乘問題、優(yōu)化問題、橢圓型偏微分方程的混合有限元離散、結構分析和圖像處理等[1].目前,關于鞍點問題的迭代求解方法已有很多,其中最經典的是Uzawa方法[2].Uzawa方法實現(xiàn)簡單,但耗時較長.為此,文獻[3-5]提出了不精確Uzawa方法,避免了求逆困難;文獻[6]提出了預條件Uzawa方法;文獻[7-10]給出了非線性Uzawa算法及其收斂性.本文基于經典的Uzawa方法及正定和反Hermite分裂(PSS)迭代方法給出一種廣義的Uzawa方法求解廣義鞍點問題.數(shù)值實驗表明新方法比經典Uzawa方法更有效.

1 預備知識

定義1[11]對于大型稀疏線性方程組

(1)

由文獻[12]知,對于正定線性方程組

(2)

(3)

其中:α為給定的正常數(shù);I為單位矩陣.

引理1[13]若A∈Cn×n是正定矩陣,且A=P+S,其中:P為正定矩陣;S為反Hermite矩陣;α為給定的正常數(shù), 則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)的系數(shù)矩陣.給定A為非Hermite正定矩陣,B為行滿秩;ρ(Σ)為矩陣Σ的譜半徑,且λ∈ρ(Σ)為Σ的一個特征值.則有:

1)Σ為非奇異矩陣,且det(Σ)>0；

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

3)Σ為正穩(wěn)定矩陣,即對于任何λ∈ρ(Σ)有Re(λ)>0.

引理3[13]若S為反Hermite矩陣,則iS(i為虛數(shù)單位)為Hermite矩陣,且對于任意的u∈Cn,u*Su為純虛數(shù)或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 數(shù)值實驗

例1在Ω內考慮Navier-Stokes問題[15-18]:

(17)

其中:Ω=(0,1)×(0,1)?2為方形區(qū)域,?Ω為Ω的邊界條件;Δ為Laplace算子;向量函數(shù)μ為Ω上的速度;數(shù)量函數(shù)ω為壓力.對問題(17)采用基于正方元的ne×ne均勻格有限元重分法,可得形如式(1)的廣義鞍點問題.

表1～表3分別列出了用經典Uzawa方法、塊LU方法[18]和修正局部PSS迭代法對例1的數(shù)值結果.

表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可見,新算法在求解廣義鞍點問題時優(yōu)于其他兩種方法.

[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] 曹陽,談為偉,蔣美群.廣義鞍點問題的松弛維數(shù)分解預條件子 [J].計算數(shù)學,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方程的一類子系統(tǒng)的求解方法研究 [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—),女,漢族,博士,副教授,從事數(shù)值代數(shù)、矩陣理論和快速算法的研究,E-mail：xiaotong0929@163.com.

國家自然科學基金(批準號：11401469)和陜西省自然科學基金(批準號：2014JQ1030).

O241.6

：A

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