求解3×3对称鞍点问题的一种简化算法

高 翔，温瑞萍

(太原师范学院 数学系，山西 晋中 030619)

大型稀疏鞍点线性方程组广泛来源于诸多实际问题[1]，如计算流体力学中的Stokes方程，电磁学Maxwell方程的有限元离散以及二阶椭圆方程问题的混合有限元方法、无网格方法、约束优化问题[2-3]和结构分析应用等.对称鞍点问题形如:

(1)

其中A∈Rm×m是对称正定的，B是m×n(m≥n)列满秩矩阵，x,f∈Rm,y,g∈Rn,BT是矩阵B的转置且C∈Rt×t,其中t=m+n.

当问题(1)的系数矩阵C为大型稀疏时，许多学者提出了各种有效的迭代求解方法[4].例如，Uzawa迭代方法是经典方法之一：

(2)

由此可见，该方法不可避免地要计算A-1，一般来说这是十分困难的.很多学者针对此进行了研究和改进，并得到了许多有效的方法.如Elman等[5]提出了不精确的预处理Uzawa方法，Gloub等[6]研究了SOR-like方法，Bai等[7]在SOR-like基础上提出了GSOR方法，Darvishi等[8]提出了SSOR方法，Zhang等[9]提出了GSSOR方法，Bai等[10]提出了参数化的不精确Uzawa方法，Zhang等[11]提出了一类Uzawa-SOR方法.Yun[12]提出了三种Uzawa方法变体，即Uzawa-AOR方法、Uzawa-SAOR方法和Uzawa-Low方法.Li等[13]提出了3×3块鞍点问题的Uzawa-Low方法，并且通过引入预处理子提出了CPU-Low方法.

本文考虑大型3×3块鞍点问题的迭代求解.3×3块鞍点问题是基于将问题(1)的系数矩阵和右边的向量进行划分，然后通过求解几个较低阶的线性方程组来得到xk+1，而不是直接求解式(2)中较高阶的第一个方程.将鞍点问题(1)的矩阵A划分为2×2块矩阵，然后对矩阵B分块，向量x,f作相应的分块，结果得到了具有以下形式的3×3块鞍点问题：

(3)

(4)

则得到如下形式：

(5)

1 算法描述

在详细介绍基于新的一种解决三阶块鞍点问题的P3Uzawa-Low算法之前,首先简要地回顾几种与本文相关的算法.

1.1 Uzawa-Low算法

其中Q也是Schur补矩阵φ=BTA-1B的近似矩阵，也可以看作是预处理矩阵.

1.2 CPU-Low算法

则得到如下算法，将其称为P3Uzawa-Low算法.

1.3 P3Uzawa-Low算法

不难得到算法1.3的迭代矩阵为：

其中I为单位矩阵.设ρ(H(ω,s,τ))表示迭代矩阵H(ω,s,τ)的谱半径，则基于式(3)的Uzawa-Low算法在ρ(H(ω,s,τ))<1时收敛.为了证明迭代矩阵H(ω,s,τ)的谱半径ρ(H(ω,s,τ))<1，给出以下两个引理和一个定理.

定理1 在引理2的假设下，下列各条件均成立：

很容易得到条件1)与2)，下证其他3种情况.

可得到条件3)和4).

通过简单计算可得:

化简，得:

而且ξ-η=-2ωsχ(δ1-2α1+δ2-2α2)<0.由于ξ>0,η>0，则条件(e)得证.

上述引理1、2及定理1可以说明P3Uzawa-Low算法的收敛性[13].

2 数值结果

本节给出一些原始数值实验结果.在3.40 GHz中央处理单元[Intel(R)Core(TM)i7-6700CPU]和具有16 G内存的电脑上使用Matlab(版本R2013a)进行数值实验说明P3Uzawa-Low算法的有效性.

表1 CPU-Low算法的参数Tab.1 The parameters of CPU-Low algorithm

表2 P3UL和CPUL算法的求解结果Tab.2 The numerical results of P3UL and CPUL algorithms

为了标记方便，将CPU-Low简写为CPUL且P3Uzawa-Low简写为P3UL.

从表2中可以看出，基于问题(1)的Uzawa-Low算法改进的P3Uzawa-Low算法和CPU-Low算法的收敛速度几乎是相同的，而随着矩阵阶数的增加，后者的所用的“CPU”小于前者.例如当m+n=12 288时，P3Uzawa-Low算法相比于CPU-Low算法节省了大约20%的时间，因此P3Uzawa-Low算法优于CPU-Low算法.虽然两种算法的迭代步数一样，但是计算量的降低是迭代时间减少的重要原因.

3 结语

基于3×3鞍点问题的CPU-Low算法简化了其迭代格式，改进得到了P3Uzawa-Low算法.相比于CPU-Low算法，P3Uzawa-Low算法的计算复杂度得到了降低.进行数值实验以后，数值结果表明迭代时间减少，也证实了计算复杂度有所下降.也就是说新的P3Uzawa-Low算法比CPU-Low算法在求解原鞍点问题时更具优势.