高 翔，溫瑞萍

(太原師范學(xué)院 數(shù)學(xué)系，山西 晉中 030619)

大型稀疏鞍點(diǎn)線性方程組廣泛來源于諸多實(shí)際問題[1]，如計(jì)算流體力學(xué)中的Stokes方程，電磁學(xué)Maxwell方程的有限元離散以及二階橢圓方程問題的混合有限元方法、無網(wǎng)格方法、約束優(yōu)化問題[2-3]和結(jié)構(gòu)分析應(yīng)用等.對稱鞍點(diǎn)問題形如:

(1)

其中A∈Rm×m是對稱正定的，B是m×n(m≥n)列滿秩矩陣，x,f∈Rm,y,g∈Rn,BT是矩陣B的轉(zhuǎn)置且C∈Rt×t,其中t=m+n.

當(dāng)問題(1)的系數(shù)矩陣C為大型稀疏時(shí)，許多學(xué)者提出了各種有效的迭代求解方法[4].例如，Uzawa迭代方法是經(jīng)典方法之一：

(2)

由此可見，該方法不可避免地要計(jì)算A-1，一般來說這是十分困難的.很多學(xué)者針對此進(jìn)行了研究和改進(jìn)，并得到了許多有效的方法.如Elman等[5]提出了不精確的預(yù)處理Uzawa方法，Gloub等[6]研究了SOR-like方法，Bai等[7]在SOR-like基礎(chǔ)上提出了GSOR方法，Darvishi等[8]提出了SSOR方法，Zhang等[9]提出了GSSOR方法，Bai等[10]提出了參數(shù)化的不精確Uzawa方法，Zhang等[11]提出了一類Uzawa-SOR方法.Yun[12]提出了三種Uzawa方法變體，即Uzawa-AOR方法、Uzawa-SAOR方法和Uzawa-Low方法.Li等[13]提出了3×3塊鞍點(diǎn)問題的Uzawa-Low方法，并且通過引入預(yù)處理子提出了CPU-Low方法.

本文考慮大型3×3塊鞍點(diǎn)問題的迭代求解.3×3塊鞍點(diǎn)問題是基于將問題(1)的系數(shù)矩陣和右邊的向量進(jìn)行劃分，然后通過求解幾個(gè)較低階的線性方程組來得到xk+1，而不是直接求解式(2)中較高階的第一個(gè)方程.將鞍點(diǎn)問題(1)的矩陣A劃分為2×2塊矩陣，然后對矩陣B分塊，向量x,f作相應(yīng)的分塊，結(jié)果得到了具有以下形式的3×3塊鞍點(diǎn)問題：

(3)

(4)

則得到如下形式：

(5)

1 算法描述

在詳細(xì)介紹基于新的一種解決三階塊鞍點(diǎn)問題的P3Uzawa-Low算法之前,首先簡要地回顧幾種與本文相關(guān)的算法.

1.1 Uzawa-Low算法

其中Q也是Schur補(bǔ)矩陣φ=BTA-1B的近似矩陣，也可以看作是預(yù)處理矩陣.

1.2 CPU-Low算法

則得到如下算法，將其稱為P3Uzawa-Low算法.

1.3 P3Uzawa-Low算法

不難得到算法1.3的迭代矩陣為：

其中I為單位矩陣.設(shè)ρ(H(ω,s,τ))表示迭代矩陣H(ω,s,τ)的譜半徑，則基于式(3)的Uzawa-Low算法在ρ(H(ω,s,τ))<1時(shí)收斂.為了證明迭代矩陣H(ω,s,τ)的譜半徑ρ(H(ω,s,τ))<1，給出以下兩個(gè)引理和一個(gè)定理.

定理1 在引理2的假設(shè)下，下列各條件均成立：

很容易得到條件1)與2)，下證其他3種情況.

可得到條件3)和4).

通過簡單計(jì)算可得:

化簡，得:

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

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

2 數(shù)值結(jié)果

本節(jié)給出一些原始數(shù)值實(shí)驗(yàn)結(jié)果.在3.40 GHz中央處理單元[Intel(R)Core(TM)i7-6700CPU]和具有16 G內(nèi)存的電腦上使用Matlab(版本R2013a)進(jìn)行數(shù)值實(shí)驗(yàn)說明P3Uzawa-Low算法的有效性.

表1 CPU-Low算法的參數(shù)Tab.1 The parameters of CPU-Low algorithm

表2 P3UL和CPUL算法的求解結(jié)果Tab.2 The numerical results of P3UL and CPUL algorithms

為了標(biāo)記方便，將CPU-Low簡寫為CPUL且P3Uzawa-Low簡寫為P3UL.

從表2中可以看出，基于問題(1)的Uzawa-Low算法改進(jìn)的P3Uzawa-Low算法和CPU-Low算法的收斂速度幾乎是相同的，而隨著矩陣階數(shù)的增加，后者的所用的“CPU”小于前者.例如當(dāng)m+n=12 288時(shí)，P3Uzawa-Low算法相比于CPU-Low算法節(jié)省了大約20%的時(shí)間，因此P3Uzawa-Low算法優(yōu)于CPU-Low算法.雖然兩種算法的迭代步數(shù)一樣，但是計(jì)算量的降低是迭代時(shí)間減少的重要原因.

3 結(jié)語

基于3×3鞍點(diǎn)問題的CPU-Low算法簡化了其迭代格式，改進(jìn)得到了P3Uzawa-Low算法.相比于CPU-Low算法，P3Uzawa-Low算法的計(jì)算復(fù)雜度得到了降低.進(jìn)行數(shù)值實(shí)驗(yàn)以后，數(shù)值結(jié)果表明迭代時(shí)間減少，也證實(shí)了計(jì)算復(fù)雜度有所下降.也就是說新的P3Uzawa-Low算法比CPU-Low算法在求解原鞍點(diǎn)問題時(shí)更具優(yōu)勢.