塊對稱三對角不定線性系統(tǒng)的預(yù)處理方法?

梁 璇, 王衛(wèi)國

(中國海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山東 青島 266100)

?

塊對稱三對角不定線性系統(tǒng)的預(yù)處理方法?

梁 璇, 王衛(wèi)國

(中國海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山東 青島 266100)

本文研究一類塊對稱三對角不定系統(tǒng)的預(yù)處理技術(shù)。把鞍點(diǎn)問題的一種矩陣分解方法推廣至塊對稱三對角不定系統(tǒng)。文中研究了這類矩陣的廣義Cholesky分解,利用這種矩陣分解法構(gòu)造預(yù)條件矩陣,證明了新的預(yù)條件矩陣使線性方程組具有更小的條件數(shù)。最后利用數(shù)值算例驗證了新給數(shù)值方法的有效性。

廣義Cholesky分解；預(yù)條件；廣義條件數(shù)；不定系統(tǒng)

科學(xué)計算中經(jīng)常遇到對稱不定系數(shù)矩陣的線性方程組,例如Stokes方程及其他偏微分方程的離散,最優(yōu)化問題的求解,很多領(lǐng)域都出現(xiàn)的KKT方程組。由于計算問題具有大型稀疏特征,從而經(jīng)常使用迭代法求解此類方程組。為了提高收斂速度,需要合適的預(yù)條件。不定系統(tǒng)的預(yù)條件方法已有很多研究,文獻(xiàn)[1]研究了鞍點(diǎn)問題中塊2×2的不定系統(tǒng)的預(yù)條件方法，文獻(xiàn)[2]給出了對稱不定矩陣的LDLT分解。文獻(xiàn)[3]研究了一類擾動矩陣的不完全Cholesky分解。文獻(xiàn)[4]對系數(shù)矩陣是分塊非對稱矩陣的方程組提出了利用塊LU分解得到預(yù)條件子的方法。文獻(xiàn)[5]中,Wu和Huang對分塊三對角H-矩陣給出了塊LU分解,研究了所提出的方法在求解系數(shù)矩陣為H-矩陣的線性系統(tǒng)的收斂性及其應(yīng)用。

本文將討論一類塊對稱三對角不定線性系統(tǒng)的矩陣分解及預(yù)條件方法,記作

Kx=b。

其中K是塊t×t對稱三對角不定矩陣。由于分塊對稱三對角不定線性系統(tǒng)經(jīng)常是壞條件的,將選擇合適的正定矩陣M=NNT作為K的預(yù)條件矩陣,使得N-1KN-T具有較小的條件數(shù)或者更好的特征值分布。并通過數(shù)值算例驗證本文所給數(shù)值方法的有效性。

1 塊對稱三對角不定系統(tǒng)

本節(jié)將討論塊對稱三對角不定系統(tǒng)的預(yù)條件選取方法。設(shè)

Kt=

(1)

其中：A1∈Rn1×n1是對稱正定矩陣；Bi∈Rni+1×ni,(i=1:t-1)是行滿秩矩陣；Ai∈Rni×ni,(i=2:t)是對稱半正定矩陣(或Bi(i=1:t-1)任意,但Ai(i=1:t)均是對稱正定矩陣)。

首先介紹廣義Cholesky分解[6],其具有Cholesky分解較小的存儲空間和計算量等優(yōu)點(diǎn)。

下面定理給出了分塊對稱三對角不定矩陣的廣義Cholesky分解。

定理1.1 設(shè)對稱不定矩陣Kt如(1)所示,則存在廣義Cholesky分解

Kt=LJtLT,

(2)

其中

Jt=diag(In1,-In2,…,(-1)t-1Int)。

矩陣L是容易得到的,以t=3為例：矩陣Lij(0≤i-j≤1)可由下列等式計算得到：

(3)

(4)

(5)

(6)

(7)

如果將LLT作為Kt的預(yù)條件矩陣,可驗證

(8)

這意味著Kt的“最優(yōu)”預(yù)條件矩陣是Mt=LLT。實際中,用的是“不精確”矩陣分解得到預(yù)條件矩陣,即由Kt的“不精確”廣義Cholesky分解得到。

定義1.1 廣義條件數(shù)定義如下：

注1.1 當(dāng)A是實對稱矩陣時,廣義條件數(shù)等于譜條件數(shù),即

κ(A)=‖A‖2‖A-1‖2。

下面定理說明利用“不精確”廣義Cholesky分解給出預(yù)條件矩陣是可行的。

定理1.2 設(shè)分塊對稱三對角矩陣Kt如(1)所示,廣義Cholesky分解由(2)給出。令Mt=LLT,則對于任意的對稱正定矩陣S,可得

κ(S-1Kt)≤κ(S-1Mt)。

(9)

S-1Kt=S-1(LJtLT)～(LTS-1L)

(10)

令

此處考慮2種情況：

(1)如果t是奇數(shù),可得

另一方面,

(2)如果t是偶數(shù),可得

另一方面,

和

進(jìn)一步,可得

和

從而

因此,我們有：

注1.2 設(shè),Kt，L和Jt如定理1.1中所示,且Mt=LLT。如果正定矩陣S是Mt的一個近似矩陣,且‖I-S-1Mt‖2≤ε<1,則

(11)

上述說明：利用廣義Cholesky分解或“不精確”的廣義Cholesky分解可以得到較好的預(yù)條件矩陣。

2 數(shù)值算例

本節(jié)，將利用共軛梯度法(即SYMMLQ方法[7])求解塊對稱三對角不定線性系統(tǒng),此方法也可以見文獻(xiàn)[8]。數(shù)值實驗是在Matlab7.11.0環(huán)境下完成的。

范數(shù)型相對誤差(Normalized Residual：NRes)定義如下：

例2.1: 矩陣K形如(1),其中m=200,n=100,l=50。構(gòu)造如下,A1的非零元部分為：

ai,i+1=ai+1,i=-1,其中i=1:m-1；

ai,i+10=ai+10,i=-1,其中i=1:m-10。

對角線元素由4～50之間的隨機(jī)數(shù)生成,A1的其余元素均為0。矩陣Bi(i=1:t-1)和Ai(i=2:t)均由0～1之間的隨機(jī)數(shù)生成,其中Ai(i=2:t-1)的對角線元素由0～30之間的隨機(jī)數(shù)生成,而At的對角線元素由0～20之間的隨機(jī)數(shù)生成。

矩陣K的廣義Cholesky分解(2)由公式(3)～(7)給出,其中L11,L22,L33…Ltt的計算將利用Matlab中的不完全Cholesky分解給出,分別應(yīng)用以下2種方法：

(a) cholinc(A,,0,)；

(b) cholinc(A,opts),其中opts為參數(shù)。

上述2種方法給出的預(yù)條件矩陣分別記為M1和M2,利用Matlab中的symmlq函數(shù)計算線性方程組的解。運(yùn)行命令如下：

[x,flag,relres,ITER,RESVEC]=

symmlq(K,b,tol,maxit,M,[]);

其中M是預(yù)條件矩陣。

表1 10個較大的特征值

表2 10個較小的特征值

下面給出廣義條件數(shù)：

κ(K)=731.887 2,

圖1顯示選取預(yù)條件M1，M2以及沒有預(yù)條件3種情況下的計算結(jié)果。計算預(yù)條件矩陣M2時,不完全Cholesky分解中的參數(shù)選取為opts=10-5。收斂曲線說明對塊三對角不定線性系統(tǒng)做矩陣分解和預(yù)處理,可以用更少的迭代次數(shù)達(dá)到相同的精度。且M1和M2的選取不同,達(dá)到確定精度所需要的迭代次數(shù)也不同。

文中也對不完全分解中的參數(shù)opts的不同選擇進(jìn)行了計算,參數(shù)opts的選擇不同,計算的速度也有很大差別。opts越小計算速度越快,計算結(jié)果見圖2。

圖1 SYMMLQ方法

圖2 SYMMLQ方法

3 結(jié)語

本文利用廣義Cholesky分解給出了塊對稱三對角不定線性系統(tǒng)的預(yù)條件方法。通過選取預(yù)條件矩陣,可以使得收斂速度有顯著提高。且預(yù)條件矩陣的選取不同,其收斂速度也有明顯不同。

[1]GeneCG,GolubH,VarahJM.Analgebraicanalysisofablockdiagonalpreconditionerforsaddlepointsystems[J].SIAMJournalonMatrixAnalysisandApplications, 2005, 27: 779-792.

[2]HRenFang.SatbilityanalysisofblockLDLfactorizationforsymmetricindefinitematrices[J].IMAJournalofNumericalAnalysis. 2011, 31: 528-555.

[3]MeurantG.Ontheincompletecholeskydecompositionofaclassofperturbeomatrices[J].SIAMJSciComput2001, 23: 419-429.

[4]YSLeighLittle,SmochL.BlockLUpreconditionersforsymmetricandnonsymmetricsaddlepointproblems[J].SIAMJSciComput, 2003, 25: 729-748.

[5]WuCY,HuangTZ.StabilityofblockLUfactorizationforblocktridiagonalblockH-matrices[J].JComputApplMath, 2012, 236: 673-2684.

[6]ZhaoJX.ThegeneralizedCholeskyfactorizationmethodforsolvingsaddlepointpointproblems[J].AppliedMathematicsandComputation, 1998, 92: 49-58.

[7]PaigeCC,SaundersA.Solutionofsparseindefinidesystemsoflinearequations[J].SIAMJNumerAnal, 1975, 12: 617-629.

[8]RenWQ,ZhaoJX.Iterativemethodswithpreconditionersforindefinitesystems[J].JComputMath, 1999, 17: 89-96.

AMS Subject Classification:65F08

責(zé)任編輯 陳呈超

On Preconditioners for Block Tridiagonal Symmetric Indefinite Linear Systems

LIANG Xuan, WANG Wei-Guo

(School of Mathematical Sciences, Ocean University of China, Qingdao 266100, China)

We discuss a class of preconditioning methods for an iterative solution of block tridiagonal symmetric indefinite linear systems. A kind of matrix decomposition method of saddle point problem is generalized to block tridiagonal symmetric indefinite linear systems. It makes a research on generalized Cholesky decomposition of block tridiagonal symmetric indefinite linear systems in this paper as well as preconditioners are designed in this way. The new preconditioners make a smaller condition number of linear equations. Finally, a numerical example is presented to illustrate the effectiveness of the proposed approach.

generalized Cholesky decomposition； preconditioning； generalized condition number； indefinite linear systems

中央高?；究蒲袠I(yè)務(wù)費(fèi)數(shù)理類專項(201362030);山東省自然科學(xué)基金項目(ZR2013AM025)資助

2013-10-28;

2014-06-10

梁 璇(1988-)，女，碩士生。E-mail:448793833@qq.com

O241.6

A

1672-5174(2015)12-131-04

10.16441/j.cnki.hdxb.20130387