張 理 濤

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

?

解鞍點(diǎn)問題的新SOR類迭代法的一個(gè)注記

張 理 濤

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

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

關(guān)鍵詞：鞍點(diǎn)問題；SOR類迭代法；收斂性

0引言

考慮如下鞍點(diǎn)問題

(1)

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

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

本文設(shè)計(jì)了求解廣義鞍點(diǎn)問題的一種改進(jìn)的NSOR類(INSOR-Like)迭代法，并分析了相應(yīng)方法的收斂性.

1改進(jìn)的NSOR類迭代法

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

(2)

最近，文獻(xiàn)[27]針對(duì)廣義鞍點(diǎn)問題(1)的系數(shù)矩陣，給出了如下分裂:

(3)

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

基于上面的分裂，采用松弛技術(shù)，設(shè)計(jì)了如下的分裂：

其中，

(4)

(5)

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

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

注記1當(dāng)Q1=0,α=0(β=1),τ=ω,ξ=1時(shí)，INSOR類迭代法就變?yōu)镾OR類迭代法[9]；當(dāng)Q1=0,τ=ω,ξ=1時(shí)，INSOR類迭代法就變?yōu)閺V義SOR類迭代法[28]；當(dāng)Q1=0,α=0(β=1),ξ=1時(shí)，INSOR類迭代法就變?yōu)閰?shù)Uzawa迭代法[12,14].當(dāng)ξ=1時(shí)，INSOR類迭代法就變?yōu)镹SOR類迭代法[27].因此，INSOR類迭代法是這些方法的推廣. 而且，當(dāng)選取合適的參數(shù)時(shí)，INSOR類迭代法將有更好的收斂速度.

2INSOR類迭代法的收斂性

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

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

(6)

則λ滿足如下二次方程：

(7)

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

(8)

得到

(9)

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

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

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

等價(jià)于

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

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

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

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

1+ηmin>0.

(10)

則INSOR迭代法收斂.

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

(11)

(12)

類似文獻(xiàn)[27]定理3.2的證明，可直接得到定理2的結(jié)論.

參考文獻(xiàn)(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

中圖分類號(hào)：TP 391.7

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

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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(11226337, 11501525)；航空科學(xué)基金資助項(xiàng)目(2013ZD55006)；河南省自然科學(xué)基金資助項(xiàng)目(152300410126)；河南省高等學(xué)校青年骨干教師資助計(jì)劃項(xiàng)目(2013GGJS-142,2015GGJS-179)；河南省高?？萍紕?chuàng)新人才支持計(jì)劃(16HASTIT040); 鄭州市科技局自然科學(xué)基金資助項(xiàng)目(141PQYJS560)；鄭州航空工業(yè)管理學(xué)院科研創(chuàng)新團(tuán)隊(duì)建設(shè)計(jì)劃項(xiàng)目(2014TD02).

收稿日期：2015-12-01.

DOI:10.3785/j.issn.1008-9497.2016.03.007