?

鞍點問題的SSOR半迭代求解方法*

王慧勤,雷剛

(寶雞文理學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院,陜西 寶雞 721013)

摘要：針對鞍點問題的特點和SSOR迭代方法的運算優(yōu)勢，給出一種SSOR類型的半迭代求解方法，運用矩陣代數(shù)理論分析該迭代方法的收斂性，得到不依賴于矩陣對稱正定的收斂條件.最后列舉矩陣對稱正定及非對稱正定條件下的兩個數(shù)值例子，檢驗該方法的可行性.

關(guān)鍵詞：鞍點問題；迭代法；收斂性

鞍點問題是一種系數(shù)矩陣對角塊中含有奇異矩陣且對稱不定的稀疏線性系統(tǒng).經(jīng)常出現(xiàn)在二次優(yōu)化、電磁學(xué)、圖像處理、最小二乘問題以及線性彈性力學(xué)等科學(xué)計算問題中，它們的數(shù)值求解最后都?xì)w結(jié)為對線性系統(tǒng)的求解，這些求解占據(jù)了計算量的80%以上，已經(jīng)成為科學(xué)計算中的瓶頸.近年來，不確定的Uzawa方法、預(yù)處理的HSS交替方法、SOR-LIKE方法、預(yù)處理的Krylov子空間方法等[1-3]已成為求解這類問題的常用迭代方法.

與其他迭代法相比，SSOR半迭代法具有明顯的優(yōu)點.首先，在一些特殊問題中構(gòu)造的其他迭代法不收斂，但是仍然可以構(gòu)造出收斂的SSOR半迭代法[4]；其次，常見的SOR迭代法、AOR迭代法對參數(shù)的選取一般是比較敏感的，而SSOR半迭代法對參數(shù)的選擇并不敏感[5]；第三，SSOR半迭代法能充分利用內(nèi)外存交換時所得到的信息，減少內(nèi)外存的交換次數(shù)，提高計算效率[6].因此，科學(xué)合理的SSOR半迭代方法能夠快速求解鞍點問題.

1引言

鞍點問題通常具有如下的形式

(1)

其中矩陣A∈Rm×m是對稱正定矩陣，矩陣B∈Rm×n(m≥n)為列滿秩矩陣，向量x、f∈Rm，向量y、g∈Rn，向量BT是B的轉(zhuǎn)置矩陣，x、y是未知向量，f、g是已知向量.在實際問題中通常m>>n，此時鞍點問題的解是唯一的[7].

一般地，令

(2)

那么鞍點問題就轉(zhuǎn)化為Wz=b.

通常的做法[1-2]是將W分解為W=D-L-U,其中

引入?yún)?shù)ω，將鞍點問題的系數(shù)矩陣分解為如下兩種形式

那么建立的SSOR形式的半迭代方法為

(3)

即為

此時生成的SSOR迭代矩陣為

T=(D-ωU)-1[(1-ω)D+ωL](D-ωL)-1[(1-ω)D+ωU]

其中

X11=(1-ω)2I-ω2(1-ω)A-1BQ-1BT-ω2(1-ω)2A-1BQ-1BT

X12=-ω(1-ω)A-1B+ω3A-1BQ-1BTA-1B+ω3(1-ω)A-1BQ-1BTA-1B-ω(1-ω)A-1B

X21=ω+ω(1-ω)Q-1BT

H=[(1-ω)D+ωL](D-ωL)-1ωb+ω(D-ωU)-1b

那么可得半迭代形式下的SSOR迭代算法如下：

設(shè)A∈Rm×m是對稱正定矩陣，B∈Rm×n(m≥n)為列滿秩矩陣，Q∈Rn×n是對稱正定矩陣.設(shè)定精度ε>0，參數(shù)0<ω<2，給定初始向量(x(0),y(0))，k=0,1,2,…,n,….

第二步：計算x(k+1)和y(k+1)

第三步：判斷誤差，如果

2迭代法的收斂性

引理1[1]設(shè)方程組Ax=b,且A為對稱正定矩陣，則當(dāng)0<ω<2時，SOR迭代法和SSOR迭代法是收斂的.

在運用迭代方法求解方程組的過程中，判別迭代法能否收斂的關(guān)鍵條件就是看迭代矩陣的譜半徑能否小于1，而矩陣的譜半徑又是通過矩陣的特征值來得到的.

引理3如果令μ為矩陣Q-1BTBQ-1的一個特征值，那么當(dāng)常數(shù)λ滿足如下等式

[ω(1-ω)+λω]2μ=[(1-ω)2-λ](λ-1)[(1-ω)-ωμ]

時，可以得到常數(shù)λ為迭代矩陣T的一個非零的特征值.

(4)

整理可得

由于矩陣A和Q都是對稱正定矩陣，并且非奇異，結(jié)合(5)可知

[(1-ω)2-λ]A2x=[ω(1-ω)+λω]ABy

求出x的表示式后代入(6)有

[ω(1-ω)+λω]2BTBy=[(1-ω)2-λ](λ-1)[(1-ω)Q2-ωBTB]y

(7)

再利用B∈Rm×n為列滿秩矩陣，Q∈Rn×n是對稱可逆正定矩陣，令μ為矩陣Q-1BTBQ-1的一個特征值，那么就有

[ω(1-ω)+λ ω]2μ=[(1-ω)2-λ](λ-1)[(1-ω)-ωμ]

(8)

定理1設(shè)鞍點問題的系數(shù)矩陣中A∈Rm×m是對稱正定矩陣，B∈Rm×n(m≥n)為列滿秩矩陣，Q∈Rn×n是對稱可逆正定矩陣，

(2)當(dāng)ω=1時，λ=1是矩陣T的一個特征值，對應(yīng)的特征向量是(1,0,0,…,0)T，SSOR半迭代法不收斂.

證明由引理3可以看出迭代矩陣T的特征值λ滿足如下關(guān)系

[ω(1-ω)+λω]2μ=[(1-ω)2-λ](λ-1)[(1-ω)-ωμ]

整理可得

λ2[(1-ω)+(ω2-ω)μ]+λ{{2ω2(1-ω)-[ω(1-ω)2+1]}μ

-(1-ω)3-(1-ω)}+(1-ω)3=0

當(dāng)[(1-ω)+(ω2-ω)μ]≠0時,可得

(1)當(dāng)0<ω<1時，上述不等式可以轉(zhuǎn)化為

進一步可知

分析上述不等式有

-3ω3+3ω2-ω<0和-3ω3+5ω2-3ω<0

后兩個不等式的解為

結(jié)合0<ω<1可得到結(jié)論.

(2)當(dāng)ω=1時，由(4)式可得

從上可得，當(dāng)λ=1時，x=0，此時，λ=1為T的一個特征值，對應(yīng)的特征向量是(1,0,0,…,0)T.

從式(7)可以看出，SSOR半迭代法的收斂性不依賴于鞍點問題中系數(shù)矩陣A的選擇，收斂性要求的特征值μ的選取只與系數(shù)矩陣中的B和任意選取的矩陣Q有關(guān)，這是SSOR半迭代法求解鞍點問題的一個優(yōu)點.它同時也可以解決鞍點問題中當(dāng)矩陣A不是對稱正定情況下的類鞍點問題.

3數(shù)值例子

在數(shù)值算例中，由于計算機技術(shù)的快速發(fā)展，更多配置高、運算速度快的計算機層出不窮，但是為了方便比較，依然將計算機條件設(shè)置為較陳舊的T1600，1.66GHz CPU，2.56G RAM Memory，與以往的設(shè)置條件完全相同[8-9]，選取求解常見的Stokes方程

通常在數(shù)值求解過程中首先運用有限元方法進行離散化處理，就可以得到和(1)式相同的方程，這類方程都具有一個重要的特點，那就是系數(shù)矩陣的對稱性和高度稀疏性，不失一般性假設(shè)矩陣A和B分別如下

為了方便計算，向量f和向量g取初始零向量，給定初始向量(x(0),y(0))為單位向量，把預(yù)處理需要的矩陣設(shè)置為Q=-BTB,那么殘量記為

表1　對稱正定矩陣下的SSOR半迭代方法的運算結(jié)果

從上述的運算結(jié)果可以看出，在相同的運算精度的要求下，不同的m和n 取值時，運算所需要的迭代次數(shù)和占用CPU的時間不同.與其他已有的迭代方法相比優(yōu)勢也不明顯，但是這種半迭代方法能夠求解當(dāng)矩陣A為非對稱正定矩陣的情形，像在一些偏微分方程的數(shù)值求解過程中[10]，系數(shù)矩陣只具有高度的系數(shù)性，可能并不具備對稱性時，這種方法依然可以求解.為同上例比較，取矩陣A和B分別如下

其他向量不變，精度要求也不變，運算結(jié)果如下表2.

表2　非對稱正定矩陣下的SSOR半迭代方法的運算結(jié)果

4總結(jié)

依據(jù)SSOR迭代方法的特點，把對鞍點問題的求解和SSOR迭代方法結(jié)合起來，給出半迭代形式的鞍點問題的求解方法，和其他已有鞍點問題的求解方法相比，在數(shù)值運算上看不具有優(yōu)勢，但是它能解決在數(shù)值運算中出現(xiàn)的矩陣為非對稱時的鞍點問題求解.

參考文獻:

[1]潘春平.鞍點問題的預(yù)處理HSS-SOR二級分裂迭代方法[J].高校應(yīng)用數(shù)學(xué)學(xué)報,2009,30(6):905-908.

[2]GUO PENG,LI CUI-XIA,WU SHI-LIANG.A modified SOR-like method for the augmented systems[J].Journal of Computational and Applied Mathematics,2014 (274):58-69.

[3]姜曉林,呂全義,謝公南.一種求解鞍點問題的預(yù)處理并行算法[J].應(yīng)用數(shù)學(xué)和力學(xué),2014,35(9):1011-1019.

[4]胡家贛.線性代數(shù)方程組的迭代解法[M].北京:科學(xué)出版社,1991.

[5]邵新慧.大型線性方程組的迭代解法[D].沈陽：東北大學(xué),2006.

[6]韋志輝，周榮富.SSOR數(shù)值方法的穩(wěn)定性[J].東南大學(xué)學(xué)報:自然科學(xué)版,1990,20(3):108-113.

[7]黃卓紅.PDE離散方程組和鞍點問題的預(yù)處理方法[D].成都：成都電子科技大學(xué),2010.

[8]朱雪芳.求解鞍點問題的一類廣義SSOR預(yù)條件子[J].數(shù)值計算與計算機應(yīng)用,2014,35(2):117-124.

[9]沈海龍,邵新慧,張鐵,等.求解鞍點問題的修正SOR-LIKE方法[J].東北大學(xué)學(xué)報:自然科學(xué)版,2009,30(6):905-908.

[10]張秀梅,王川龍.解鞍點問題的等價模型及其求解[J].工程數(shù)學(xué)學(xué)報,2014,31(1):75-84.

The SSOR Semi-iterative Method for Solving the Saddle Point Problem

WANG Hui-qin, LEI Gang

(College of Mathematics and Information Science,Baoji University of Arts and Sciences,Baoji 721013,China)

Abstract:On the base of the feature of saddle point problems and the operational advantages of the SSOR iterative method,this study make a kind of the SSOR semi-iterative method for solving the saddle point problems.Then analyze convergence of this iterative method using matrix algebra theory,and obtain a convergence condition in non-symmetric positive definite.At last two numerical examples were given for testing application of the method.

Keywords:The saddle point problem; Iteration method; Convergence

中圖分類號：O241

文獻標(biāo)志碼：A

文章編號：1007-9793(2015)06-0028-06

通信作者：雷剛.

作者簡介：王慧勤(1979-),女，陜西榆林人，碩士，講師，主要從事矩陣計算與數(shù)學(xué)教育方面研究.

收稿日期：*2015-06-12基金項目：國家自然科學(xué)基金資助項目(11371031)；陜西省教育廳科學(xué)研究計劃資助項目(14JK1052)；寶雞文理學(xué)院科研基金重點資助項目(ZK15008).