解鞍點問題的新SOR類迭代法的一個注記

張 理 濤

(鄭州航空工業管理學院 理學院， 河南 鄭州 450015)

?

解鞍點問題的新SOR類迭代法的一個注記

張 理 濤

(鄭州航空工業管理學院 理學院， 河南 鄭州 450015)

摘要：最近ZHENG等提出了新的SOR類(NSOR-Like)迭代法，研究了NSOR-類迭代矩陣特征值的性質. 基于NSOR類迭代法，提出了一種改進的NSOR類(INSOR-Like)迭代法，并分析了相應方法的收斂性. 此改進的NSOR類(INSOR-Like)迭代法是NSOR類迭代法的推廣.

關鍵詞：鞍點問題；SOR類迭代法；收斂性

0引言

考慮如下鞍點問題

(1)

其中，A∈Rm×m是對稱正定矩陣，B∈Rm×n是列滿秩矩陣，b∈Rm和q∈Rn是已知給定的向量，且m≥n.

鞍點問題(1)常出現在許多不同的科學計算應用中，譬如約束優化問題[1]、求解Navier-Stokes方程的有限元法[2-4]以及限制最小二乘問題和廣義最小二乘問題[1-8].最近有大量文獻研究求解廣義鞍點問題(1).文獻[6]研究求解廣義鞍點問題A=I時的預處理迭代法. 文獻[7-8]提出了幾種類型的SOR迭代法和預處理的共軛梯度法，求解問題都來源于廣義最小二乘離散得到的廣義鞍點，且系數矩陣A是對稱半正定的，B是秩虧矩陣. 對于每次迭代步，SOR類迭代法比其他方法要求的計算量相對較少，但是為了取得良好的收斂速度，須選擇一個最優的迭代參數. 因此，文獻[9]提出了SOR類迭代法. 文獻[10]研究了SSOR迭代法. 文獻[11-14]設計了GSOR迭代法、參數Uzawa(PU)和不精確的參數Uzawa(PIU)迭代法. 文獻[15]研究了廣義對稱SOR迭代法. 文獻[16]研究了非對稱塊超松弛類迭代法. 文獻[17-22]提出了分裂迭代法，譬如埃爾米特和反埃爾米特分裂(HSS)迭代格式，以及相應的預處理變形；Krylov子空間迭代法，譬如預處理共軛梯度法(PCG)、預處理MINRES(PMINRES)和限制預處理共軛梯度法(RPCG)；還提出了和預處理技術相關的Krylov子空間迭代法，譬如HSS、塊對角、塊三角和限制預處理技術等. 文獻[13,22]研究了與松弛分裂迭代法相關的廣義方法. 文獻[23]設計了改進的SSOR(MSSOR)迭代法. 文獻[24-25]確立了一種廣義的MSSOR(GMSSOR)迭代法，并且分析了相應方法的收斂性. 文獻[26]研究了廣義定常迭代法(GSI)的收斂性. 最近，文獻[27]提出了新SOR類(NSOR-Like)迭代法，并且研究了NSOR類法迭代矩陣特征值的性質.

本文設計了求解廣義鞍點問題的一種改進的NSOR類(INSOR-Like)迭代法，并分析了相應方法的收斂性.

1改進的NSOR類迭代法

為方便起見，文獻[9]把鞍點問題(1)重寫為

(2)

最近，文獻[27]針對廣義鞍點問題(1)的系數矩陣，給出了如下分裂:

(3)

這里，Q1∈Rm×m,Q2∈Rn×n,α,β∈[0,1],滿足A+Q1非奇異，Q2對稱正定且α+β=1.

基于上面的分裂，采用松弛技術，設計了如下的分裂：

其中，

(4)

(5)

令Q1∈Rm×m,Q2∈Rn×n,ξ是一個合適的參數,滿足A+ξQ1非奇異、Q2對稱正定. 給定初始向量x(0)∈Rm和y(0)∈Rn，且4個松弛參數ω≠0,τ≠0,ξ,α>0滿足ατ≠1.對于k=0,1,2,…計算下列迭代格式：

直到迭代序列{((xk)T,(yk)T)T}收斂.

注記1當Q1=0,α=0(β=1),τ=ω,ξ=1時，INSOR類迭代法就變為SOR類迭代法[9]；當Q1=0,τ=ω,ξ=1時，INSOR類迭代法就變為廣義SOR類迭代法[28]；當Q1=0,α=0(β=1),ξ=1時，INSOR類迭代法就變為參數Uzawa迭代法[12,14].當ξ=1時，INSOR類迭代法就變為NSOR類迭代法[27].因此，INSOR類迭代法是這些方法的推廣. 而且，當選取合適的參數時，INSOR類迭代法將有更好的收斂速度.

2INSOR類迭代法的收斂性

基于NSOR類迭代法并采用與文獻[27]中定理3.1相似的證明過程，可以得到如下收斂定理.

定理1令Q1∈Rm×m,Q2∈Rn×n,α,ξ是2個實數，滿足A+ξQ1非奇異、Q2對稱正定和B∈Rm×m列滿秩. 且4個松弛參數ω≠0,τ≠0,ξ,α>0滿足ατ≠1.假定λ是迭代矩陣HINSOR的一個特征值，z=(u*,v*)∈Cm+n是2個復向量u∈Cm和v∈Cn的特征向量. 定義

(6)

則λ滿足如下二次方程：

(7)

證明假定λ是迭代矩陣HINSOR的一個特征值，z=(u*,v*)∈Cn+m是2個復向量u∈Cm和v∈Cn的特征向量.則有

(8)

得到

(9)

由文獻[27]引理3.1，得到λ≠1. 由式(9)的第2個方程得

代入式(9)的第1個方程，則有

(1-λ)Au + (1-λ)ξQ1u-ωAu=

等價于

-(λ-1)2Au-ξ(λ-1)2Q1u-ω(λ-1)Au=

由引理1，得到u≠0,因此有u*Au≠0.上式方程兩邊先乘u*再除u*Au，易知λ是二次方程式(7)的根.

定理2令Q1∈Rm×m,Q2∈Rn×n,α,ξ是2個實數，滿足A+ξQ1非奇異、Q2對稱正定和B∈Rm×m列滿秩. 且4個松弛參數ω≠0,τ≠0,ξ,α>0滿足ατ≠1.假定λ是迭代矩陣HINSOR的一個特征值，z=(u*,v*)∈Cm+n是2個復向量u∈Cm和v∈Cn的特征向量.η和γ由式(6)定義，且η是實數. 假定參數ω,γ,τ滿足

0<ω<2(1+ξηmin),

1+ηmin>0.

(10)

則INSOR迭代法收斂.

證明由定理1易知，λ滿足二次方程式(7)，即滿足

(11)

(12)

類似文獻[27]定理3.2的證明，可直接得到定理2的結論.

參考文獻(References)：

[1]WRIGHT S. Stability of augmented system factorizations in interior-point methods[J]. SIAM J Matrix Anal Appl,1997,18:191-222.

[2]ELMAN H , SILVESTER D. Fast nonsymmetric iterations and preconditioning for Navier-Stokes equations[J]. SIAM J Sci Comput,1996,17:33-46.

[3]ELMAN H, GOLUB G H. Inexact and preconditioned Uzawa algorithms for saddle point problems[J]. SIAM J Numer Anal,1994,31:1645-1661.

[4]FISCHER B, RAMAGE A, SILVESTER D J, et al. Minimum residual methods for augmented systems[J]. BIT,1998,38:527-543.

[5]ARIOLI M , DUFF I S , de RIJK P P M. On the augmented system approach to sparse least-squares problems[J]. Numer Math,1989,55:667-684.

[6]SANTOS C H , SILVA B P B , YUAN J Y . Block SOR methods for rank deficient least squares problems[J]. J Comput Appl Math,1998,100:1-9.

[7]YUAN J Y. Numerical methods for generalized least squares problems[J]. J Comput Appl Math,1996,66:571-584.

[8]YUAN J Y, IUSEM A N . Preconditioned conjugate gradient method for generalized least squares problems[J]. J Comput Appl Math,1996,71:287-297.

[9]GOLUB H , WU X, YUAN J Y.SOR-like methods for augmented systems[J]. BIT,2001,41:71-85.

[10]DARVISHIM T ,HESSARI P . Symmetric SOR method for augmented systems[J]. Appl Math Comput,2006,183:409-415.

[11]BAI Z Z, PARLETT B N, WANG Z Q. On generalized successive overrelaxation methods for augmented linear systems[J]. Numer Math,2005,102:1-38.

[12]BAI Z Z, WANG Z Q. On parameterized inexact Uzawa methods for generalized saddle point problems[J]. Linear Algebra Appl,2008,428:2900-2932.

[13]CHEN F, JIANG Y L. A generalization of the inexact parameterized Uzawa methods for saddle point problems[J]. Appl Math Comput,2008,206:765-771.

[14]ZHENG B, BAI Z Z, YANG X. On semi-convergence of parameterized Uzawa methods for singular saddle point problems[J]. Linear Algebra Appl,2009,431:808-817.

[15]ZHANG G F , LU Q H. On generalized symmetric SOR method for augmented systems[J]. J Comput Appl Math,2008,1(15):51-58.

[16]PENG X F , LI W . On unsymmetric block overrelaxation-type methods for saddle point[J]. Appl Math Comput,2008,203(2):660-671.

[17]BAI Z Z, YANG X . On HSS-based iteration methods for weakly nonlinear systems[J]. Appl Numer Math,2009,59:2923-2936.

[18]BAI Z Z, GOLUB G H, MICHAEL K N .On inexact hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems[J]. Linear Algebra Appl,2008,428:413-440.

[19]BAI Z Z. Several splittings for non-Hermitian linear systems[J]. Science in China, Ser A: Math,2008,51:1339-1348.

[20]BAIZ Z, GOLUB G H,LU L Z , et al. Block-Triangular and skew-Hermitian splitting methods for positive definite linear systems[J].SIAM J Sci Comput,2005,26:844-863.

[21]BAI Z Z, GOLUB G H, NG M K. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems[J]. SIAM J Matrix Anal A,2003,24:603-626.

[22]WANG L , BAI Z Z . Convergence conditions for splitting iteration methods for non-Hermitian linear systems[J]. Linear Algebra Appl,2008,428:453-468.

[23]WU S L , HUANG T Z , ZHAO X L. A modified SSOR iterative method for augmented systems[J]. J Comput Appl Math,2009,228(1):424-433.

[24]ZHANG L T,HUANG T Z,CHENG S H, et al. Convergence of a generalized MSSOR method for augmented systems[J]. J Comput Appl Math,2012,236:1841-1850.

[25]ZHANG L T. A new preconditioner for generalized saddle matrices with highly singular(1,1) blocks[J].Int J Comput Math, 2014, 91(9):2091-2101.

[26]MIAO S X , WANG K . On generalized stationary iterative method for solving the saddle point problems[J].J Appl Math Comput,2011,35:459-468.

[27]ZHENG Q Q, MA C F. A new SOR-Like method for the saddle point problems[J]. Appl Math Comput,2014,233:421-429.

[28]SHAO X, SHEN H, LI C. The generalized SOR-Like method for the augmented systems[J]. Int J Inf Syst Sci,2006(2):92-98.

[29]YOUNG D M . Iteration Solution for Large Systems[M]. New York:Academic Press, 1971.

ZHANG Litao
(DepartmentofMathematicsandPhysics,ZhengzhouUniversityofAeronautics,Zhengzhou450015,China)
A note on new SOR-Like method for the saddle point problems. Journal of Zhejiang University(Science Edition), 2016,43(3):292-295

Abstract:Recently, ZHENG et al presented the new SOR-Like (NSOR-Like) method and studied the characteristic of eigenvalue of the iteration matrix of this NSOR-Like method. In this paper, we present an improved NSOR-Like (INSOR-Like) method based on NSOR-Like method, and analyze the convergence of the corresponding method. Moreover, the improved NSOR-Like (INSOR-Like) method is the generalization of NSOR-Like method.

Key Words:saddle point problems; SOR-Like method; convergence

中圖分類號：TP 391.7

文獻標志碼：A

文章編號：1008-9497(2016)03-292-04

作者簡介：張理濤(1980-)，ORCID:http://orcid.org/0000-0002-6087-8611,男，博士，副教授，主要從事數值代數與科學計算及應用研究，E-mail:litaozhang@163.com.

基金項目：國家自然科學基金資助項目(11226337, 11501525)；航空科學基金資助項目(2013ZD55006)；河南省自然科學基金資助項目(152300410126)；河南省高等學校青年骨干教師資助計劃項目(2013GGJS-142,2015GGJS-179)；河南省高校科技創新人才支持計劃(16HASTIT040); 鄭州市科技局自然科學基金資助項目(141PQYJS560)；鄭州航空工業管理學院科研創新團隊建設計劃項目(2014TD02).

收稿日期：2015-12-01.

DOI:10.3785/j.issn.1008-9497.2016.03.007