周期三對角Toeplitz矩陣的求逆算法及其穩(wěn)定性

藺小林, 藺彥玲

(陜西科技大學(xué) 文理學(xué)院， 陜西 西安　710021)

?

周期三對角Toeplitz矩陣的求逆算法及其穩(wěn)定性

藺小林, 藺彥玲

(陜西科技大學(xué) 文理學(xué)院， 陜西 西安710021)

摘要：提出了一種求解周期三對角Toeplitz矩陣逆的新算法，其思想為通過周期三對角Toeplitz矩陣的特殊結(jié)構(gòu)，利用矩陣的LU分解，以及矩陣方程的求解方法，先求出逆矩陣的第一列和最后一列，然后依次求出逆矩陣的其他列.該算法不需要對矩陣的各階順序主子式進(jìn)行限制，同時適用于計算機(jī)實(shí)現(xiàn)的代數(shù)系統(tǒng).算法穩(wěn)定性較好并且算法復(fù)雜性較低，最后通過數(shù)值例子驗證了算法的有效性和較強(qiáng)的穩(wěn)定性.

關(guān)鍵詞：周期三對角Toeplitz矩陣; LU分解; 逆矩陣; 穩(wěn)定性

0引言

在現(xiàn)代數(shù)據(jù)處理中，往往要求解決一些對角線性方程問題，包括三對角、五對角、七對角，以及三對角Toeplitz、五對角Toeplitz等線性方程問題.早期，便有學(xué)者研究了三對角、五對角及七對角線性方程問題，并給出了各種求解對角矩陣的逆矩陣的方法，在文獻(xiàn)[1-11]中給出了三對角和五對角矩陣以及其周期對角矩陣和塊對角矩陣的逆矩陣，在文獻(xiàn)[12-14]中給出了七對角矩陣和廣義七對角矩陣的逆，而其中利用LU分解和Doolittle分解進(jìn)行求解逆矩陣的見文獻(xiàn)[3-5,7,9,10,12-14]. 同時，三對角Toeplitz、五對角Toeplitz線性方程問題也在不斷研究中，見文獻(xiàn)[15-17]. 其中文獻(xiàn)[15]先將Toeplitz矩陣擴(kuò)展為循環(huán)矩陣，通過求出循環(huán)矩陣的逆以及對循環(huán)矩陣的分塊求出原Toeplitz矩陣的逆，同時討論了算法的穩(wěn)定性.文獻(xiàn)[16]給出了對角Toeplitz矩陣逆元素的解析計算表達(dá)式.

在以上文獻(xiàn)的啟發(fā)下，本文給出一個求解周期三對角Toeplitz矩陣的逆矩陣的快速穩(wěn)定算法，該算法適用于多種計算機(jī)代數(shù)系統(tǒng)，如：Mathematics,Macsyma,Matlab和Mapla等.并且該算法具有較低的復(fù)雜度和好的穩(wěn)定性.

本文其他部分組成結(jié)構(gòu)為：在第1節(jié)中，給出求解周期三對角Toeplitz矩陣的逆的求解方法，并討論了新算法的復(fù)雜度；在第2節(jié)中，通過2個數(shù)值例子驗證了算法的有效性，并證明了該算法的穩(wěn)定性；最后，進(jìn)行小結(jié).

1主要結(jié)論

周期三對角Teoplitz矩陣如下

(1)

其中abc≠0.

定理若n×n階廣義周期三對角矩陣T的順序主子式Dk≠0，k=1,2,…,n，則T有唯一的LU分解.

T=LU

其中

(2)

(3)

從而，有

(4)

該定理詳細(xì)證明過程略，可參閱文獻(xiàn)[17，18]相關(guān)內(nèi)容.

由T=LU可得以下方程

αi=a, i=1a-βi-1γi, i=2,3,…,n-1a-∑n-1i=1μivi i=nì?í????

(5)

βi=b,i=1,2,…,n-2

(6)

(7)

(8)

(9)

假設(shè)矩陣T非奇異且其逆矩陣為

T-1=(S1,S2,…,Sn)

其中Sj表示T-1的第j列，j=1,2,…,n.這里Sj可以寫成

Sj=(S1,S2,…,Sn)Ej

其中Ej=(δ1j,δ2j,…,δnj)t,j=1,2,…,n,且δij為Kronecker 符號.

通過T-1T=In(這里的In是n×n單位矩陣)，可以得到以下關(guān)系

Si=(En-aSn-cS1)/b, i=n-1(Ei+1-aSi+1-cSi+2)/b, i=n-2,…,2{

(10)

由(10)式可以看出，只要求出Sn和S1，便可迭代求出Sn-1,Sn-2,…,S2，以下進(jìn)行求解Sn和S1.

由于

TT-1=T(S1,S2,…,Sn)=(E1,E2,…,En),

從而由第一個和最后一個方程可得TS1=E1和TSn=En，即L(US1)=E1和L(USn)=En，那么可得出以下四個方程

LY=E1

(11)

US1=Y

(12)

LX=En

(13)

USn=X

(14)

其中Y=(y1,y2,…,yn)t，S1=(s11,s21,…,sn1)t，

X=(x1,x2,…,xn)t，Sn=(s1n,s2n,…,snn)t.

由式(11)得

yi=1, i=1-γiyi-1, i=2,3,…,n-1-∑n-1i=1μiyi i=nì?í????

(15)

由式(12)和(15)可得

si1=ynαn, i=nyn-1-vn-1sn1αn-1, i=n-1yi-βisi+1-visn1αi, i=n-2,…,1ì?í????????

(16)

同樣，根據(jù)式(13)和(14)可得

X=(0,0,…,0,1)t

(17)

(18)

因此，將Sn和S1帶入式(10)，便可迭代得到T-1的其他列向量Sn-1,Sn-2,…,S2，如此便得出周期三對角Toeplitz矩陣T的逆矩陣.

矩陣T求逆算法

輸入：矩陣的階n，矩陣元素a,b,c；

輸出：逆矩陣T-1；

步驟1：當(dāng)i=1,2,…,n-2時，令βi=b；

步驟3：令v1=c，當(dāng)i=2,3,…,n-2時，計算vi=-viγi，并令vn-1=b-vn-2γn-1；

步驟10：將Sn和S1帶入式(10)，依次求出Sn-1,Sn-2,…,S2.

算法復(fù)雜度

步驟1和步驟10的算法復(fù)雜度均為n-2階，步驟2的算法復(fù)雜度為2n-3階，步驟3至步驟5的算法復(fù)雜度均為n-1階，步驟6至步驟9的算法復(fù)雜度均為n階.綜上所述，該算法的算法復(fù)雜度為11n-10階，因此該算法的復(fù)雜度僅僅與矩陣的大小n有關(guān)，而文獻(xiàn)[15]中求三對角與五對角Toeplitz矩陣求逆的算法中的算法2的復(fù)雜度為O(nlog2n)階.

2數(shù)值例子

例1考慮6×6周期三對角Toeplitz矩陣

的逆矩陣.

通過矩陣T求逆算法可得

β=(2,2,2,2)

(步驟1)

γ=(0,3,-0.6,1.3637,-1.7368)

(步驟2)

v=(3,-9,-5.4,7.3636,14.7895)

(步驟3)

μ=(2,0.8,-0.7273,-0.8421,1.0471)

(步驟4)

α=(1,-5,2.2,1.7273,4.4737,-11.0118)

(步驟 2,5)

det(T)=-936

(步驟6)

y=(1,-3,-1.8,2.4545,4.2632,-3.3059)

(步驟7)

S1=(-0.09081196581197,0.09508547008547,0.08867521367521,-0.18696581196581,-0.03952991452991,0.30021367521368)

(步驟8)

Sn=(0.09508547008547,0.08867521367521,

-0.18696581196581,-0.03952991452991,

0.300213675368,-0.09081196581197)

(步驟9)

因此，由步驟10可得

T-1=

例2考慮n×n階的周期三對角Toeplitz矩陣

表1　求周期三對角Toeplitz矩陣各階

例2的數(shù)據(jù)表明，對于正常態(tài)周期三對角Toeplitz矩陣的逆，矩陣T求逆算法是穩(wěn)定的.

3結(jié)論

本文主要給出了一個求解周期三對角Toeplitz矩陣的快速穩(wěn)定的新算法，該算法既結(jié)合了求解對角矩陣的逆矩陣的LU分解方法，又結(jié)合了求解Toeplitz矩陣的逆矩陣的思想，不僅求解出了周期三對角Toeplitz矩陣的逆，同時也保證了算法的高度穩(wěn)定性.為該類問題的求解提供了新的方法.

參考文獻(xiàn)

[1] Ahmed Driss Aiat Hadj,Mohamed Elouafi.A fast numerical algorithm for the inverse of a tridiagonal and pentadiagonal matrix[J].Applied Mathematics and Computation,2008,202:441-445.

[2] M.E.Kanal,N.A.Baykara,M.Demiralp.Theory and algorithm of the inversion method for pentadiagonal matrices[J].J Math Chem,2012,20:289-299.

[3] Emrah Kihc.Explicit formula for the inverse of a tridiagonal matrix by backward continued fractions[J].Applied Mathematics and Computation,2008，197:345-357.

[4] Moawwad El Mikkawy,El Desouky Rahmo.A new recursive algorithm for inverting general periodic pentadiagonal and anti-pentadiagonal matrices[J].Applied Mathematics and Computation,2009,207:164-170.

[5] A.A.Karawia.A computational algorithm for solving periodic penta-diagonal linear systems[J].Applied Mathematics and Computation,2006,174:613-618.

[6] 余承依,陳躍輝.周期三對角矩陣逆的一種新算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識,2010,40(22):192-198.

[7] 冉瑞生,黃廷祝,劉興平，等.三對角矩陣求逆的算法[J].應(yīng)用數(shù)學(xué)和力學(xué),2009,30(2):238-244.

[8] 唐達(dá).周期三對角矩陣求逆的快速算法[J].上海電機(jī)學(xué)院學(xué)報,2013,16(5):300-304.

[9] Moawwad EI Mikkawy,EI Desouky Rahmo.Symbolic algorithm for inverting cyclic pentadiagonal matrices recursively-derivation and implementation[J].Computer and Mathematics with Applications,2010,59:1 386-1 396.

[10] 冉瑞生,黃廷祝.塊三對角矩陣的逆[J].電子科技大學(xué)學(xué)報,2007,36(2):341-342.

[11] 陳芳,陸全,袁志杰.分塊五對角矩陣求逆的快速算法[J].合肥工業(yè)大學(xué)學(xué)報,2008,31(11):1 904-1 907.

[12] Lin Xiao-lin,Huo Pei-pei,Jia Ji-teng.A new recursive algorithm for inverting general periodic sevendiagonal and anti-sevendiagonal matrices[J].Far East Journal of Applied Mathematics,2014,86(1):41-55.

[13] 賈紀(jì)騰,藺小林.廣義周期七對角矩陣求逆的新算法[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(6):1 040-1 046.

[14]A.A.Karawia.Inversionofgeneralcyclicheptadiagonalmatrices[J].MathematicsProblemsinEngineering,2013(2013):1-9.

[15] 劉剛,黃廷祝.三對角與五對角Toeplitz矩陣求逆的算法[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(2):292-299.

[16] 宋以勝，張傳定，張書華.三對角、五對角對稱Toeplitz矩陣的解析逆陣[J].測繪學(xué)院學(xué)報，2004,21(2):82-84.

[17]DieleF,LopezL.Theuseofthefactorizationoffive-diagonalmatricesbytridiagonalToeplitzmatrices[J].Appl.Math.Lett.,1998,11:61-69.

[18]RaoS.Appliednumericalmethodsforengineersandscientists[M].Prentice-Hall:UpperSaddleRiver,2002.

【責(zé)任編輯：蔣亞儒】

An algorithm for computing the inverse of a periodic tridiagonal toeplitz matrix and the steadiness

LIN Xiao-lin, LIN Yan-ling

(College of Arts and Sciences， Shaanxi University of Science & Technology, Xi′an 710021, China)

Abstract:In this article, we presents a new algorithm for solving a periodic tridiagonal Toeplitz matrix inversion, which is thought by the special structure of a periodic Toeplitz tridiagonal matrix and using the LU factorization,as well as a method for solving the matrix equations.We get the first column and the last column of the inverse matrix firstly,then obtain the others.By using this method, the condition that each principal minor sequence of the matrix must nonzero is unnecessary.What′s more,the algorithm is suited for implementation using computer algebra systems with better algorithm steadiness and low algorithmic complexity.Finally, illustrative examples are given to demonstrates the effectiveness and steadiness of the algorithm.

Key words:a periodic tridiagonal Toeplitz matrix; LU factorization; inverse matrix; steadiness

中圖分類號：O151.21

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

文章編號：1000-5811(2016)03-0171-04

作者簡介:藺小林(1961-)，男，陜西洛川人，教授，博士，研究方向：數(shù)值計算理論及其應(yīng)用

基金項目：陜西省科技廳重點(diǎn)實(shí)驗室科研計劃項目(2011HBSZS014)； 陜西科技大學(xué)學(xué)術(shù)團(tuán)隊計劃項目(2013XSD39)

收稿日期:2016-03-30