求解3×3對稱鞍點問題的一種簡化算法

高 翔，溫瑞萍

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

大型稀疏鞍點線性方程組廣泛來源于諸多實際問題[1]，如計算流體力學中的Stokes方程，電磁學Maxwell方程的有限元離散以及二階橢圓方程問題的混合有限元方法、無網(wǎng)格方法、約束優(yōu)化問題[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)的系數(shù)矩陣C為大型稀疏時，許多學者提出了各種有效的迭代求解方法[4].例如，Uzawa迭代方法是經(jīng)典方法之一：

(2)

由此可見，該方法不可避免地要計算A-1，一般來說這是十分困難的.很多學者針對此進行了研究和改進，并得到了許多有效的方法.如Elman等[5]提出了不精確的預處理Uzawa方法，Gloub等[6]研究了SOR-like方法，Bai等[7]在SOR-like基礎上提出了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塊鞍點問題的Uzawa-Low方法，并且通過引入預處理子提出了CPU-Low方法.

本文考慮大型3×3塊鞍點問題的迭代求解.3×3塊鞍點問題是基于將問題(1)的系數(shù)矩陣和右邊的向量進行劃分，然后通過求解幾個較低階的線性方程組來得到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 數(shù)值結果

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

表1 CPU-Low算法的參數(shù)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算法的收斂速度幾乎是相同的，而隨著矩陣階數(shù)的增加，后者的所用的“CPU”小于前者.例如當m+n=12 288時，P3Uzawa-Low算法相比于CPU-Low算法節(jié)省了大約20%的時間，因此P3Uzawa-Low算法優(yōu)于CPU-Low算法.雖然兩種算法的迭代步數(shù)一樣，但是計算量的降低是迭代時間減少的重要原因.

3 結語

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