鞍點(diǎn)問(wèn)題的SSOR半迭代求解方法*

?

鞍點(diǎn)問(wèn)題的SSOR半迭代求解方法*

王慧勤,雷剛

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

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

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

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

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

1引言

鞍點(diǎn)問(wèn)題通常具有如下的形式

(1)

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

一般地，令

(2)

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

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

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

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

(3)

即為

此時(shí)生成的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是對(duì)稱正定矩陣，B∈Rm×n(m≥n)為列滿秩矩陣，Q∈Rn×n是對(duì)稱正定矩陣.設(shè)定精度ε>0，參數(shù)0<ω<2，給定初始向量(x(0),y(0))，k=0,1,2,…,n,….

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

第三步：判斷誤差，如果

2迭代法的收斂性

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

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

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

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

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

(4)

整理可得

由于矩陣A和Q都是對(duì)稱正定矩陣，并且非奇異，結(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是對(duì)稱可逆正定矩陣，令μ為矩陣Q-1BTBQ-1的一個(gè)特征值，那么就有

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

(8)

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

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

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

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

整理可得

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

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

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

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

進(jìn)一步可知

分析上述不等式有

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

后兩個(gè)不等式的解為

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

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

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

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

3數(shù)值例子

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

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

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

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

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

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

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

4總結(jié)

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

參考文獻(xiàn):

[1]潘春平.鞍點(diǎn)問(wèn)題的預(yù)處理HSS-SOR二級(jí)分裂迭代方法[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào),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]姜曉林,呂全義,謝公南.一種求解鞍點(diǎn)問(wèn)題的預(yù)處理并行算法[J].應(yīng)用數(shù)學(xué)和力學(xué),2014,35(9):1011-1019.

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

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

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

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

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

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

[10]張秀梅,王川龍.解鞍點(diǎn)問(wèn)題的等價(jià)模型及其求解[J].工程數(shù)學(xué)學(xué)報(bào),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

中圖分類號(hào)：O241

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

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

通信作者：雷剛.

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

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