奇異鞍點問題的一類迭代算法的半收斂性

周小燕

(浙江科技學(xué)院 理學(xué)院，杭州 310023)

?

奇異鞍點問題的一類迭代算法的半收斂性

周小燕

(浙江科技學(xué)院 理學(xué)院，杭州 310023)

摘要:提出了奇異鞍點問題的一類基于對矩陣的一種帶2個實參數(shù)α和β的新的分裂的廣義的SOR-like方法，得到了此方法半收斂的條件，以及最優(yōu)參數(shù)與相應(yīng)的最優(yōu)半收斂因子。

關(guān)鍵詞:鞍點問題；GSOR-like方法；半收斂；最優(yōu)參數(shù)

考慮具有以下形式的鞍點問題：

(1)

式(1)中,A∈m×m為對稱正定(SPD)矩陣;B∈m×n(這里假定m≥n)；BT是B的轉(zhuǎn)置矩陣；向量x,b∈m,y,q∈n,b,q是已知向量。

鞍點問題來自于非線性約束最優(yōu)化(連續(xù)2次規(guī)劃問題和內(nèi)點法)、流體動力學(xué)(Stokes方程)、不可壓縮彈性分析、電路分析及結(jié)構(gòu)分析等。鞍點問題的求解與一般的線性方程組求解一樣，有直接法和迭代法2種。直接法只進(jìn)行有限步計算,所以，在不計入舍入誤差的情況下,可以在有限步求得方程組的精確解,它比較適合階數(shù)較低的線性方程組。迭代法是從解的一個初始估計值開始,逐步對它進(jìn)行改進(jìn),直到達(dá)到所需的精度,理論上說,須經(jīng)過無限次迭代才能收斂到真解；但實際上,只要用某種度量方式(如殘量的范數(shù))，當(dāng)度量的誤差已小于某個給定值時,迭代即可終止。當(dāng)系數(shù)矩陣是稀疏矩陣,且方程的階數(shù)較大時,迭代法就比較適合,因為它運(yùn)算量小,內(nèi)存需求小。

當(dāng)rank(B)=n，即B是列滿秩矩陣，鞍點問題(1)(式(1))有唯一解。許多研究者對鞍點問題(1)進(jìn)行了探討，構(gòu)造了大量有效的迭代算法，如Uzawa算法[1-3]、SOR-like法[4-7]、Krylov子空間法[8-9]、HSS迭代法[10-11]等。當(dāng)rank(B)=r

當(dāng)rank(B)=n，文獻(xiàn)[7]構(gòu)造了鞍點問題(1)的GSOR-like方法，討論了此方法的收斂性、最優(yōu)參數(shù)及相應(yīng)的最小譜半徑。本研究討論當(dāng)rank(B)=r

1基本概念和引理

用σ(A),ρ(A)分別表示矩陣A的譜集和譜半徑。

定義1[20]設(shè)T∈n×n，當(dāng)存在時，稱T是半收斂的。

引理1[20]設(shè)T∈n×n，那么T半收斂當(dāng)且僅當(dāng)以下條件成立：

1)ρ(T)≤1;

2)如果ρ(T)=1，那么矩陣T的特征值1的所有初等因子是線性的，即rank(I-T)2=rank(I-T)；

設(shè)A∈n×n，當(dāng)M可逆時，稱A=M-N為A的一個分裂?？紤]線性方程組Ax=b，令T=M-1N,c=M-1b，則迭代

x(k+1)=Tx(k)+c

(2)

有以下結(jié)果。

引理2[20]設(shè)A=M-N，其中M是可逆的，記T=M-1N,c=M-1b。那么對于任何初始向量x(0)，迭代(式(2))半收斂于線性方程組Ax=b的一解x*當(dāng)且僅當(dāng)T是半收斂的，且

x*=(I-T)Dc+(I-E)x0,E=(I-T)(I-T)D,

(3)

式(3)中，I是單位陣，(I-T)D是I-T的Drazin逆。

引理3[12]設(shè)H∈l1×l1,I∈l2×l2,l1,l2∈+,那么

(4)

半收斂當(dāng)且僅當(dāng)以下條件成立之一：

1)L=0,H是半收斂的；

2)ρ(H)<1。

2GSOR-like方法的半收斂性

方法1GSOR-like方法[7]:

設(shè)Q∈n×n是對稱非奇異的，x(0)∈m,y(0)∈n是給定的初始向量，α,β,ω是實數(shù)，滿足α>0,ω>0,α-ωβ≠0。對于k=0,1,2,…,計算

方法1等價于

(5)

式(5)中，

(6)

(7)

當(dāng)rank(B)=n，鞍點問題(1)的系數(shù)矩陣是非奇異的，因此有唯一的解，文獻(xiàn)[7]研究了收斂性質(zhì)并確定了最優(yōu)參數(shù)。當(dāng)rank(B)=r

定理1設(shè)A∈m×m，Q∈n×n為SPD矩陣，B∈m×n，rank(B)=r

GSOR-like方法收斂于奇異鞍點問題(1)的一解x*。

證明：由引理2，只需證明方法1的迭代矩陣M(ω,α,β)是半收斂的。

(8)

(9)

定義矩陣：

(10)

式(10)中，V1∈n×r,V2∈n×(n-r)，那么

計算可得，

(11)

式(11)中，

(12)

(13)

因為

(14)

所以，ρ同時也是Q-1BTA-1B的最大特征值。證畢。

3最優(yōu)迭代參數(shù)

定理2設(shè)A∈m×m，Q∈n×n為SPD矩陣，分別是Q-1BTA-1B的最大和最小特征值，那么方法1的最優(yōu)半收斂因子是

最優(yōu)參數(shù)是

(15)

參考文獻(xiàn):

[1]ELMANHC，GOLUBGH.InexactandpreconditionedUzawaalgorithmsforsaddlepointproblems[J].SiamJournalonNumericalAnalysis, 1994, 31(6):1645.

[2]BRAMBLEJH,PASCIAKJE,VASSILEVAT.AnalysisoftheinexactUzawaalgorithmforsaddlepointproblems[J].SiamJournalonNumericalAnalysis, 1997, 34(3):1072.

[3]BAIZZ,WANGZQ.OnparameterizedinexactUzawamethodsforgeneralizedsaddlepointproblems[J].LinearAlgebraanditsApplications,2008,428:2900.

[4]GOLUBGH,WUX,YUANJY.SOR-likemethodsforaugmentedsystems[J].BitNumericalMathematics, 2001,41(1):71.

[5]BAIZZ,PARLETTBN,WANGZQ.Ongeneralizedsuccessiveoverrelaxionmethodsforaugmentedlinearsystems[J].NumerischeMathematic, 2005,102(1):1.

[6]HUANGZD,ZHOUXY.OntheminimumconvergencefactorofaclassofGSOR-likemethodsforaugmentedsystems[J].NumericalAlgorithms, 2015,70(1):113.

[7]ZHOUXY.AgeneralizedSOR-likemethodforaugmentedsystems[J].JournalofZhejiangUniversityofScienceandTechnology,2015,27(6):459.

[8]SAADY.IterativeMethodsforSparseLinearSystems[M]. 2nded.Philadelphia:SocietyforIndustrialandAppliedMathematics, 2003.

[9]VANDERVORSHA.IterativeKrylovMethodsforLargeLinearSystems[M]∥Vol. 13ofCambridgeMonographsonAppliedandComputationalMathematics.NewYork:CambridgeUniversityPress,2003.

[10]BENZIM,GOLUBGH.Apreconditionerforgeneralizedsaddlepointproblems[J].SIAMJournalonMatrixAnalysisandApplications，2004, 26(1):20.

[11]BAIZZ,GOLUBGH.AcceleratedHermitianandskew-Hermitiansplittingiterationmethodsforsaddle-pointproblems[J].ImaJournalofNumericalAnalysis, 2007, 27(1):1.

[12]ZHENGB,BAIZZ,YANGX.Onsemi-convergenceofparameterizedUzawamethodsforsingularsaddlepointproblems[J].LinearAlgebraandItsApplications, 2009,431:808.

[13]ZHANGGF,WANGSS.AgeneralizationofparameterizedinexactUzawamethodforsingularsaddlepointproblems[J].AppliedMathematicsandComputation, 2013, 219(9):4225.

[14]CHAOZ,CHENG.Anoteonsemi-convergenceofgeneralizedparameterizedinexactUzawamethodforsingularsaddlepointproblems[J].NumericalAlgorithms, 2014, 68(1):95.

[15]ZHANGN,LUTT,WEIY.Semi-convergenceanalysisofUzawamethodsforsingularsaddlepointproblems[J].JournalofComputationalandAppliedMathematics, 2014, 255(285):334.

[16]LIANGZZ,ZHANGGF.Semi-convergenceanalysisoftheGPIUmethodforsingularnonsymmetricsaddle-pointproblems[J].NumericalAlgorithms, 2014, 70(1):151.

[17]BAIZZ.Onsemi-convergenceofHermitianandskew-Hermitiansplittingmethodsforsingularlinearsystems[J].Computing, 2010, 89:171.

[18]CHAOZ,ZHANGN.AgeneralizedpreconditionedHSSmethodforsingularsaddlepointproblems[J].NumericalAlgorithms, 2014, 66(2):203.

[19]WANGSS,ZHANGGF.PreconditionedAHSSiterationmethodforsingularsaddlepointproblems[J].NumericalAlgorithms, 2013, 63(3):521.

[20]BERMANA,PLEMMONSRJ.NonnegativeMatricesintheMathematicalSciences[M].Philadelphia:SocietyforIndustrialandAppliedMathematics,1994.

doi:10.3969/j.issn.1671-8798.2016.03.001

收稿日期:2016-04-10

作者簡介:周小燕(1976—)，女，浙江省蕭山人，副教授，碩士，主要從事計算數(shù)學(xué)研究。

中圖分類號:O241.6

文獻(xiàn)標(biāo)志碼:A

文章編號:1671-8798(2016)03-0177-05

On semi-convergence of a generalized SOR-like method for singular augmented systems

ZHOU Xiaoyan

(School of Sciences, Zhejiang University of Science and Technology, Hangzhou 310023, China)

Abstract:A generalized SOR-like method for singular augmented systems based on a new splitting of the iterative matrix with two real parameters α and β is presented. The semi-convergence conditions and the optimal iteration parameters and the corresponding optimal semi-convergence factor of this method are derived.

Keywords:augmented systems; GSOR-like methods; semi-convergence; the optimal parameters