塊對稱三對角不定線性系統的預處理方法?

梁 璇, 王衛國

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

?

塊對稱三對角不定線性系統的預處理方法?

梁 璇, 王衛國

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

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

廣義Cholesky分解；預條件；廣義條件數；不定系統

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

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

Kx=b。

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

1 塊對稱三對角不定系統

本節將討論塊對稱三對角不定系統的預條件選取方法。設

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分解較小的存儲空間和計算量等優點。

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

定理1.1 設對稱不定矩陣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的預條件矩陣,可驗證

(8)

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

定義1.1 廣義條件數定義如下：

注1.1 當A是實對稱矩陣時,廣義條件數等于譜條件數,即

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

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

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

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

(9)

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

(10)

令

此處考慮2種情況：

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

另一方面,

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

另一方面,

和

進一步,可得

和

從而

因此,我們有：

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

(11)

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

2 數值算例

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

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

例2.1: 矩陣K形如(1),其中m=200,n=100,l=50。構造如下,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之間的隨機數生成,A1的其余元素均為0。矩陣Bi(i=1:t-1)和Ai(i=2:t)均由0～1之間的隨機數生成,其中Ai(i=2:t-1)的對角線元素由0～30之間的隨機數生成,而At的對角線元素由0～20之間的隨機數生成。

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

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

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

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

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

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

其中M是預條件矩陣。

表1 10個較大的特征值

表2 10個較小的特征值

下面給出廣義條件數：

κ(K)=731.887 2,

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

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

圖1 SYMMLQ方法

圖2 SYMMLQ方法

3 結語

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

[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

責任編輯 陳呈超

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

中央高校基本科研業務費數理類專項(201362030);山東省自然科學基金項目(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