鞍点问题在各种科学和工程中应用广泛, 如计算流体动力学、约束优化、最优控制、加权最小二乘问题、计算机图形等[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∈Cm×m为对称正定矩阵; B∈Cm×n.通常m>n, 向量x, f∈Cm, y, g∈Cn.当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(0), y(0), 直到迭代序列(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(0), y(0)∈Cm, 直到迭代序列(x(k), y(k))T收敛, 计算:
(4) |
其中: T(α)=(αI+P)-1(αI-S); N(α)=(αI+P)-1.
将改进的Uzawa-PSS方法写成等价形式:
其中, G(α, ω)是改进Uzawa-PSS方法的迭代矩阵,
(5) |
(6) |
令ρ(G(α, ω))是G(α, ω)的谱半径, 则改进Uzawa-PSS方法收敛当且仅当ρ(G(α, ω)) < 1.令λ是G(α, ω)特征值, (x, y)T是对应特征向量, 有
(7) |
引理1[20] 复一元二次方程λ2-ϕλ+φ=0两根之模均小于1, 当且仅当方程系数满足|ϕ-ϕφ|+|φ|2 < 1, 其中ϕ表示ϕ的共轭复数.
引理2 令A是非Hermitian正定矩阵, B是列满秩矩阵.设λ是G(α, ω)的特征值, (x, y)T是相应特征向量, x∈Cn, y∈Cm, 则λ≠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) |
令
由引理1知|λ| < 1当且仅当|ϕ-ϕφ|+|φ|2 < 1, 其中:
则|ϕ-ϕφ|+|φ|2 < 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(α, ω))2=rank(I-G(α, ω)).
证明 由式(5), 式(6)有G(α, ω)=I-M(α, ω)A, 即
令
(11) |
因A非奇异, 由式(11)得
(12) |
得
又因null((M(α, ω)A)2)⊇null((M(α, ω) A)), 得证.
下面验证改进Uzawa-PSS迭代法满足引理3中的第二个条件.令r=rank(B), B=U[Br, 0]V*是B的奇异值分解, 其中, Br=[Σr, 0]T, Σr=diag[σ1, …, σr].U∈Cn×n和V=[V1, V2]∈Cm×m是酉矩阵, 其中V1∈Cm×r, V2∈Cm×(m-r).定义(n+m)×(n+m)阶酉矩阵:
(13) |
(14) |
式中:
V1*Q-1V1是预条件矩阵.令
定理3 令A=P+S, P是正定矩阵, S是Skew-Hermitian矩阵, B是秩亏矩阵, Q是Hermitian正定矩阵, 改进Uzawa-PSS方法收敛当且仅当参数α和ω满足:
取零向量作为初始向量, 当xk满足
< 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∈R3l2使式(3)为非奇异问题, [f, g]T∈R3l2+2使式(3)为奇异问题, 且方程组的精确解均是所有元素为1的向量.
例1 考虑非奇异鞍点问题(3), 系数矩阵为
其中:
例2 考虑奇异鞍点问题(3), 系数矩阵为
其中:
图 1、图 2为例1、例2中A的特征值分布.图 1和图 2表明, 在控制最优参数的条件下, 改进Uzawa-PSS法的特征值分布接近于零, 随着系数矩阵A的阶数不断增大, 特征值聚集趋势逐渐减弱, 但是大部分特征值仍然保持在区间[-0.1, 0.1]内.
表 1为非奇异、奇异鞍点问题的三种迭代方法的数值结果比较, 选取Q=tridiag(BTD-1B), 其中D是A的对角矩阵.可以看出, 在选择最优参数时, 三种方法在有限迭代步数内都能达到指定的精度,且都能收敛到各自对应问题的近似解.但当A阶数较大时, Uzawa-HSS和Uzawa-PSS方法收敛非常缓慢, 新Uzawa-PSS方法更有效, 且它的迭代次数和占CPU的时间最少.
本文提出了一种改进的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.
|