沈海龙, 李红丽, 邵新慧
东北大学 理学院, 辽宁 沈阳 110819
收稿日期：2018-04-04
基金项目：国家自然科学基金资助项目(11371081);辽宁省自然科学基金资助项目(20170540323)。
作者简介：沈海龙(1971-), 男, 吉林延吉人, 东北大学讲师, 博士;
邵新慧(1970-), 女, 山东青岛人, 东北大学教授。

摘要：主要针对非Hermitian鞍点问题, 在已有Uzawa-PSS方法基础上构建了一种改进的Uzawa-PSS迭代法, 其主要求解思想是在Uzawa-PSS方法的每一步迭代中需求解系数矩阵αI+P和αI+S的两个线性子系统.第一个子系统可用CG方法求解, 但第二个子系统求解很困难.改进算法采用单步PSS迭代法逼近x_k+1, 然后用新方法分别求解了非奇异和奇异鞍点问题, 并给出了相应的收敛性分析.数值仿真实验验证了改进Uzawa-PSS迭代法在迭代步数、占用CPU时间和相对残差上都有明显的优势.
关键词：鞍点问题收敛半收敛奇异非奇异
An Improved Uzawa-PSS Method for to Solve Point Problems
SHEN Hai-long, LI Hong-li, SHAO Xin-hui
School of Sciences, Northeastern University, Shenyang 110819, China
Corresponding author: SHEN Hai-long, E-mail: hailong_shen@126.com
Abstract: Aiming at the non-Hermitian saddle point problem, an improved Uzawa-PSS iteration method is constructed based on the existing Uzawa-PSS method. The main idea of the new method is to solve two linear subsystems in each iteration step of Uzawa-PSS method, whose coefficient matrices are αI+P and αI+S, respectively. The first subsystem can be solved by CG method, but the second subsystem is very difficult to solve. The improved algorithm uses the single-step PSS iteration method to approximate the problem. Then the new method is used to solve the non-singular and singular saddle point problems respectively, and the corresponding convergence analysis is given. The numerical simulation also proves that the improved Uzawa-PSS iteration method has obvious advantages in iteration steps, CPU time and relative residuals.
Key words: saddle point problemconvergencesemi-convergencesingularnonsingular
鞍点问题在各种科学和工程中应用广泛, 如计算流体动力学、约束优化、最优控制、加权最小二乘问题、计算机图形等^[1-4], 从二阶椭圆问题的混合有限元离散化或一些偏微分方程的无网格离散均可得到鞍点问题^[5-7].
近年来涌现出大量求解鞍点问题的方法, 对于非奇异的鞍点问题, 人们提出了很多行之有效的算法, 除了直接法外, 还有许多迭代方法.这些迭代法一般可分为基于矩阵分裂的定常迭代法和基于Krylov子空间方法的非定常迭代法.定常迭代法分为Uzawa类、HSS类和SOR类^[8-10].1958年, Arrow等^[11]针对鞍点问题提出了基于矩阵分裂的Uzawa方法, 之后为了避免逆矩阵的复杂计算, Bramble等^[12-13]提出了应用不同鞍点问题的不精确Uzawa方法^[11-13]; Elman等^[14-15]给出了对称鞍点问题的不精确Uzawa方法的收敛性分析和预条件的Uzawa算法; Hu等^[16]提出了非线性不精确Uzawa方法的两种变体; Cao^[17]提出了用Uzawa方法来解决非对称鞍点问题; Lin等^[18]提出了一种新的非线性Uzawa方法, 且分析了该算法的收敛性; Zhou等^[19]基于GPIU方法求解了更复杂的鞍点问题; Shao等^[20]又基于GPIU方法成功解决了一类广义非对称的鞍点问题.
本文构造一种求解奇异和非奇异鞍点问题的改进Uzawa-PSS迭代法, 并进行了详细的理论分析和数值仿真, 通过比较表明了新方法的优势.
1 迭代格式鞍点问题的一般形式为

(1)

其中:A∈C^m×m为对称正定矩阵; B∈C^m×n.通常m>n, 向量x, f∈C^m, y, g∈Cⁿ.当rank(B)=n, 称式(1)为非奇异的; 当rank(B) < n, 称式(1)为奇异的.
对于非奇异鞍点问题, Uzawa解法^[19]格式:
其中, A是非Hermitian正定矩阵.将A作如下分裂:A=P+S, P是正定矩阵, S是Skew-Hermitian矩阵.基于ADI方法, PSS迭代方法为

(2)

式中:α, ω是给定正常数; I是单位矩阵.将Uzawa方法和PSS方法相结合, 可得到如下Uzawa-PSS方法.
给定初始向量x⁽⁰⁾, y⁽⁰⁾, 直到迭代序列(x^(k), y^(k))^T收敛, 计算:

(3)

其中: Q是Hermitian正定矩阵; M_α=(αI+S)^-1(αI+P)^-1(αI-P)(αI-S); N_α=2α(αI+S)^-1(αI+P)^-1.将Uzawa-PSS方法进行改进, 称其为改进Uzawa-PSS方法.具体格式为
给定初始向量x⁽⁰⁾, y⁽⁰⁾∈C^m, 直到迭代序列(x^(k), y^(k))^T收敛, 计算:

(4)

其中: T(α)=(αI+P)^-1(αI-S); N(α)=(αI+P)^-1.
将改进的Uzawa-PSS方法写成等价形式:
其中, G(α, ω)是改进Uzawa-PSS方法的迭代矩阵,

(5)

(6)

2 收敛性分析2.1 非奇异鞍点问题令ρ(G(α, ω))是G(α, ω)的谱半径, 则改进Uzawa-PSS方法收敛当且仅当ρ(G(α, ω)) < 1.令λ是G(α, ω)特征值, (x, y)^T是对应特征向量, 有

(7)

引理1^[20]??复一元二次方程λ²-?λ+φ=0两根之模均小于1, 当且仅当方程系数满足|?-?φ|+|φ|² < 1, 其中?表示?的共轭复数.
引理2??令A是非Hermitian正定矩阵, B是列满秩矩阵.设λ是G(α, ω)的特征值, (x, y)^T是相应特征向量, x∈Cⁿ, y∈C^m, 则λ≠1且x≠0.
证明??假设λ=1, 从式(7)知

(8)

可得x=0, y=0, 又(x, y)^T是G(α, ω)的特征向量, 矛盾, 所以λ≠1.假设x=0, 由式(8)可得By=0, 因B列满秩, 与y=0矛盾, 因此x≠0.
定理1??令A=P+S, P是正定矩阵, S是Skew-Hermitian矩阵, B列满秩, Q是Hermitian正定矩阵.则改进Uzawa-PSS方法收敛当且仅当α和ω满足条件:
其中:
证明??由引理2知λ≠1, x≠0.又因Q是Hermitian正定, 则由式(8)可得

(9)

将式(9)两边同时左乘, 可得

(10)

令由于α+a+bi≠0, 将式(10)改写成
由引理1知|λ| < 1当且仅当|?-?φ|+|φ|² < 1, 其中:
则|?-?φ|+|φ|² < 1当且仅当满足:
结论得证.
2.2 奇异鞍点问题引理3 ??改进Uzawa-PSS方法半收敛当且仅当满足:
1) index(I-G(α, ω))=1;
2) v(G(α, ω))=max{|λ|:λ∈σ(G(α, ω)), λ≠1} < 1,
其中, σ(G(α, ω))是矩阵G(α, ω)的谱集.
定理2??令A=P+S, P是正定矩阵, S是Skew-Hermitian矩阵, B是秩亏矩阵, Q是Hermitian正定矩阵, G(α, ω)是改进的Uzawa-PSS方法的迭代矩阵, 则rank(I-G(α, ω))²=rank(I-G(α, ω)).
证明??由式(5), 式(6)有G(α, ω)=I-M(α, ω)A, 即
令其中M(α, ω)非奇异, 则

(11)

因A非奇异, 由式(11)得即再由式(11)得=0.令由式(4)有

(12)

得于是可知
又因null((M(α, ω)A)²)?null((M(α, ω) A)), 得证.
下面验证改进Uzawa-PSS迭代法满足引理3中的第二个条件.令r=rank(B), B=U[B_r, 0]V^*是B的奇异值分解, 其中, B_r=[Σ_r, 0]^T, Σ_r=diag[σ₁, …, σ_r].U∈C^n×n和V=[V₁, V₂]∈C^m×m是酉矩阵, 其中V₁∈C^m×r, V₂∈C^m×(m-r).定义(n+m)×(n+m)阶酉矩阵：令则矩阵G(α, ω)和的特征值相同.定义可得

(13)

(14)

式中: 由式(13)知记V₁^*Q^-1V₁是Hermitian正定矩阵, 与改进Uzawa-PSS方法相比, 可看作是改进Uzawa-PSS方法用于解决如下非奇异问题的迭代矩阵:
V₁^*Q^-1V₁是预条件矩阵.令的特征值, 是相应特征向量, 记其中i是虚数单位, 根据定理2, 得到如下收敛定量.
定理3??令A=P+S, P是正定矩阵, S是Skew-Hermitian矩阵, B是秩亏矩阵, Q是Hermitian正定矩阵, 改进Uzawa-PSS方法收敛当且仅当参数α和ω满足:
3 数值算例取零向量作为初始向量, 当x_k满足
< 10^-6时停止, 所有的实验都在软件Matlab上实现, 迭代主机参数为Intel (R) Pentium (R) CPU P6200 @ 2.13 GHz和2.00 GB内存.
为验证改进Uzawa-PSS方法的有效性, 选取迭代步数(IT)、占用CPU时间(CPU)和相对残差(RES)作为比较指标.选取Uzawa-HSS方法和Uzawa-PSS方法与本文所提方法进行比较, 为使迭代步数最少, 经过多次实验选取最优参数α和ω.在实际的计算过程中, 选取右边向量[f, g]^T∈R^3l2使式(3)为非奇异问题, [f, g]^T∈R^3l2+2使式(3)为奇异问题, 且方程组的精确解均是所有元素为1的向量.
例1 ??考虑非奇异鞍点问题(3), 系数矩阵为
其中:
表示克罗内克积, 是步长.
例2 ??考虑奇异鞍点问题(3), 系数矩阵为
其中:
图 1、图 2为例1、例2中A的特征值分布.图 1和图 2表明, 在控制最优参数的条件下, 改进Uzawa-PSS法的特征值分布接近于零, 随着系数矩阵A的阶数不断增大, 特征值聚集趋势逐渐减弱, 但是大部分特征值仍然保持在区间[-0.1, 0.1]内.
图 1(Fig. 1)

图 1 例1矩阵A的特征值分布Fig.1 Dstributions of the eigenvalues of matrix A examples 1 (a)—l=8; (b)—l=16；(c)—l=24；(d)—l=32.

图 2(Fig. 2)

图 2 例2矩阵A的特征值分布Fig.2 Distributions of the eigenvalues of matrix A of examples 2 (a)—l=8; (b)—l=16；(c)—l=24；(d)—l=32.

表 1为非奇异、奇异鞍点问题的三种迭代方法的数值结果比较, 选取Q=tridiag(B^TD^-1B), 其中D是A的对角矩阵.可以看出, 在选择最优参数时, 三种方法在有限迭代步数内都能达到指定的精度，且都能收敛到各自对应问题的近似解.但当A阶数较大时, Uzawa-HSS和Uzawa-PSS方法收敛非常缓慢, 新Uzawa-PSS方法更有效, 且它的迭代次数和占CPU的时间最少.
表 1(Table 1)

表 1 非奇异、奇异鞍点问题的三种迭代方法的数值结果比较Table 1 Numerical comparison of three iteration methods for nonsingular and singular saddle point problems l 方法 非奇异 奇异 α ω IT/次 CPU/s RES×107 α ω IT/次 CPU/s RES×107 8 New Uzawa-PSS 800 0.6 97 0.039 5 8.69 700 0.8 51 0.026 2 7.53 Uzawa-PSS 450 1.2 158 0.065 4 8.97 450 0.4 104 0.324 5 8.97 Uzawa-HSS 750 0.55 177 0.073 8 9.44 550 0.5 123 0.578 6 9.26 16 New Uzawa-PSS 500 1.2 104 1.068 3 8.90 500 1.2 61 0.508 3 8.46 Uzawa-PSS 850 1.85 212 2.298 2 9.11 750 0.7 135 1.876 3 9.29 Uzawa-HSS 650 0.5 227 2.943 3 9.56 700 1.35 157 2.348 2 9.33 24 New Uzawa-PSS 740 0.55 112 7.249 9 9.01 650 0.85 76 4.784 2 8.87 Uzawa-PSS 500 0.8 235 17.952 5 9.35 550 0.65 168 8.349 6 9.47 Uzawa-HSS 600 0.65 278 24.119 2 9.76 820 1.0 183 10.563 7 9.55 32 New Uzawa-PSS 550 1.5 135 40.506 8 9.24 750 1.0 101 32.333 8 9.13 Uzawa-PSS 700 1.0 254 66.633 2 9.67 400 0.55 207 40.349 3 9.66 Uzawa-HSS 800 0.75 280 80.674 4 9.95 450 1.25 234 53.242 9 9.78

表 1 非奇异、奇异鞍点问题的三种迭代方法的数值结果比较 Table 1 Numerical comparison of three iteration methods for nonsingular and singular saddle point problems

4 结语本文提出了一种改进的Uzawa-PSS迭代法, 可以用于求解奇异鞍点问题和非奇异鞍点问题, 并对所提方法的非奇异鞍点问题收敛性及奇异鞍点问题半收敛性做了详细分析.数值算例表明在时间花费和迭代次数上新改进Uzawa-PSS迭代法有很大优势.
参考文献

[1]	Benzi M, Golub G H, Liesen J. Numerical solution of saddle point problems[J].Acta Numerica, 2005, 14(1): 1–137.
[2]	Bai Z Z, Parlett B N, Wang Z Q. On generalized successive over relaxation methods for augmented linear systems[J].Numerische Mathematik, 2005, 102(1): 1–38.
[3]	Santos C H, Silva B P B, Yuan J Y. Block SOR methods for rank-deficient least-squares problems[J].Journal of Computational and Applied Mathematics, 1998, 100: 1–9.DOI:10.1016/S0377-0427(98)00114-9
[4]	Golub G H, Wathen A J. An iteration for indefinite systems and its application to the Navier-Stokes equations[J].SIAM Journal on Scientific Computing, 1998, 19: 530–539.DOI:10.1137/S106482759529382X
[5]	Brezzi F, Fortin M. Mixed and hybrid finite elements methods[M]. New York: Springer-Verlag, 1991.
[6]	Cao Y, Yao L Q, Jiang M Q, et al. A relaxed HSS preconditioner for saddle point problems from meshfree discretization[J].Journal of Computational and Applied Mathematics, 2013, 21(4): 398–421.
[7]	Leem K H, Oliveira S, Stewart D E. Algebraic multigrid (AMG) for saddle point systems from meshfree discretizations[J].Numerical Linear Algebra with Applications, 2004, 11: 293–308.DOI:10.1002/(ISSN)1099-1506
[8]	Elman H C, Silvester D J, Wathen A J. Finite elements and fast iterative solvers:with application in incompressible fluid dynamics[M]. Oxford: Oxford University Press, 1988.
[9]	Varge R S. Matrix iterative analysis[M]. New York: Springer, 2000.
[10]	Bai Z Z, Golub G H, Ng M K. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems[J].SIAM Journal on Matrix Analysis and Applications, 2003, 24(3): 603–626.DOI:10.1137/S0895479801395458
[11]	Arrow K, Hurwicz L, Uzawa H. A studies in linear and nonlinear programming[M]. Palo Alto: Stanford University Press, 1958.
[12]	Bramble J H, Pasciak J E, Vassilev A T. Analysis of the inexact Uzawa algorithm for saddle point problems[J].SIAM Journal on Numerical Analysis, 1997, 34: 1072–1092.DOI:10.1137/S0036142994273343
[13]	Bramble J H, Pasciak J E, Vassilev A T. Uzawa type algorithms for non-symmetric saddle point problems[J].Mathematics Computation, 2000, 69: 667–689.
[14]	Elman H C, Golub G H. Inexact and preconditioned Uzawa algorithms for saddle point problems[J].SIAM Journal on Numerical Analysis, 1994, 31(6): 1645–1661.DOI:10.1137/0731085
[15]	Elman H C, Silvester D J. Fast nonsymmetric iterations and preconditioning for Navier-Stokes equations[J].SIAM Journal on Scientific Computing, 1996, 17: 33–46.DOI:10.1137/0917004
[16]	Hu Q, Zou J. Two new variants of nonlinear inexact Uzawa algorithms for saddle point problems[J].Numerische Mathematik, 2002, 93: 333–359.DOI:10.1007/s002110100386
[17]	Cao Z H. Fast Uzawa algorithm for sloving non-symmetric stabilized saddle point problems[J].Numerical Linear Algebra with Applications, 2004, 11(1): 1–24.
[18]	Lin Y Q, Cao Y H. A new nonlinear Uzawa algorithm for generalized saddle point problems[J].Applied Mathematics and Computation, 2006, 175: 1432–1454.DOI:10.1016/j.amc.2005.08.036
[19]	Zhou Y Y, Zhang G F. A generalization of parameterized inexact Uzawa method for generalized saddle point problems[J].Applied Mathematics and Computation, 2009, 215(2): 599–607.DOI:10.1016/j.amc.2009.05.036
[20]	Shao X H, Li C. A generalization of preconditioned parameterized inexact Uzawa method for indefinite saddle point problems[J].Applied Mathematics and Computation, 2015, 269(115): 691–698.