解鞍点问题的新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