1、1基于稀疏矩阵的逆和行列式的计算摘要：稀疏矩阵在现实中有很多应用，因此稀疏矩阵的计算近年来被广泛地研究.周期三对角矩阵和箭状矩阵作为两种常见的稀疏矩阵被广泛地应用在工程计算中。本文基于周期三对角矩阵和箭状矩阵的结构特点，根据矩阵分解的一些方法，着重讨论了一些周期三对角矩阵和箭状矩阵的求逆与行列式运算问题，并给出了相应的算法。本文首先根据周期三对角矩阵的特点研究了周期三对角矩阵的求逆算法，文中分别应用矩阵的递归方法、矩阵的分块技术来研究周期三对角矩阵的逆矩阵运算问题，并给出了相应于以上方法或技术的求逆新算法，同时也考虑一种求周期三对角矩阵的行列式算法，并通过一些数值例子验证了所给算法的可行性以及
2、有效性。其次根据箭状矩阵的结构特点，利用矩阵的分块技术，给出了一个求解箭状矩阵的逆矩阵及行列式的算法，同时列举一个数值例子并给出了 matlab 程序，说明算法是有效可行的。关键词：稀疏矩阵；周期三对角矩阵；箭状矩阵；逆矩阵Based on sparse matrix inverse and determinant calculationAbstract: Sparse matrix computation has attracted extensive researches in recent years because it can have a lot of applications i
3、n reality .It is acknowledged that periodic tri-diagonal matrix and arrow matrix in sparse matrix have been widely applied in engineering calculation .Based on the structures of periodic tri-diagonal matrix and arrow matrix ,this paper focuses on the arithmetic of the inverse and determinant of peri
4、odic tri-diagonal matrix and arrow matrix ,and presents some new computational algorithms by using some methods of matrix decomposition . Firstly, it discusses the inverse of periodic tri-diagonal matrix on matrix structure of periodic tri-diagonal matrix. And some new computational algorithms are c
5、reated by matrix recursion, blocking matrix technique of the inverse of periodic tri-diagonal matrix on its structure ,and then the feasibility and the effectiveness of these computational algorithms are verified by numerical examples in consideration of a simple algorithm of the determinant of peri
6、odic tri-diagonal matrix.Secondly, on the basis of the structure of arrow matrix ,an algorithm of the inverse and determinant of arrow matrix is presented by using the matrix blocking .At the same time ,the effectiveness and the feasibility are tested by numerical examples and the matlab algorithm .
7、Key words: sparse matrix ;periodic tri-diagonal matrix ;arrow matrix ;inverse matrix 2引言在科学与工程计算中，经常会遇到稀疏矩阵的计算问题，例如关于三对角矩阵、周期三对角矩阵和箭状矩阵的行列式计算、确定逆矩阵、线性方程组求解问题。它们在矩阵分析理论、样条插值函数确定、微分方程的差分法求解等方面都有非常广泛地应用前景。稀疏矩阵计算一直是矩阵计算中的关注点之一，近年来许多学者加强了这方面的研究，也提出了许多新的有效的计算方法，这些成果丰富了矩阵计算的理论和应用。对于一般的矩阵计算，主要是进行矩阵的行列式计算、矩阵
8、的求逆运算、矩阵的特征值和特征向量计算以及求解相应的线性方程组。对一般矩阵来说，运算复杂度通常是.而对于稀疏矩阵，它的结构比较特殊，我们可以根据稀疏矩阵特殊结构特点，采用)(3no不同的计算方法，对稀疏矩阵进行计算，从而可以减少运算的复杂度。例如，在本文中，主要解决两个问题，第一个是利用矩阵分块和递推技术求周期三对角矩阵的逆和行列式；第二个是利用分块技术计算箭状矩阵的逆和行列式。由于在许多科学与工程计算中，经常会出现对大型稀疏矩阵进行计算，所以我们有必要对稀疏矩阵的计算进行研究。对于稀疏矩阵的的计算，目前很多学者根据一些稀疏矩阵的特殊结构，本文主要解决两类稀疏矩阵分别是周期三对角矩阵和箭状矩阵
9、，用不同的方法对稀疏矩阵的逆矩阵计算做了很多研究，得到了很多成果。例如 2009 年 M.Elouafi 和 A.D.Aiat Hadj 利用矩阵分块技巧和递归一种求 Hessenberg 矩阵逆矩阵的新递归算法 1 ；2008 年，X.G.Lv 等利用升阶手段和分块技术得到一种计算五对角矩阵行列式和逆的方法 2；沈光星、戴华、张振跃等分别给出了对称三对角矩阵、Jacobi 矩阵关于特征值的一些算法 37 。本文主要研究了周期三对角矩阵和箭状矩阵的逆矩阵和行列式的求解方法，文中首先介绍了矩阵分解的一些方法和技术，如矩阵分块、递归、降阶等技术，然后根据周期三对角矩阵的特殊结构，利用上述分解方法分
10、别对周期三对角矩阵的逆矩阵和行列式进行了探讨，最后分别给出了一些求解算法和数值算例。其次，文中利用矩阵的分块技术，根据箭状矩阵的特殊结构，给出了一个求解非奇异逆箭状矩阵的逆和行列式的算法，并给出了一个算例以验证算法有效可行，从而丰富了求解箭状矩阵的逆矩阵和行列式的计算方法。1 利用矩阵分块和递归技术求周期三对角矩阵的逆和行列式1.1 预备知识对周期三对角矩阵进行如下分块：3（1.1） 1112211 nTnnnAbaccbaacA其中， ,0,)(1TnR,1n.12221nnbaccbaA ,)1(n 1)(110nnRca引理 1.1 如果 是非奇异矩阵，那么1n.)(det)t( 11n
11、TnAA证明：由于 两边取行列式后即可得到结论，其中,0111nTnnT AAI 是 阶单位矩阵.1nI推论 1.1 设 和 都是非奇异矩阵，则1n.011nTnAd1.2 主要结论定理 1.1 是非奇异周期三对角矩阵， 且 非奇异，则A,1nTA1ndn)et()dt(11（1.2） eAnTn112 证明：(1)由引理 1.1 可以得出证明.4.(2) 由于 eAAeIAnTnnnT 1111 )(= ，那么可知结论成立.nnII01注：如果矩阵 是对角占优矩阵或者是对称正定矩阵，则定理 2.1 条件显然满足.为了求A出 的逆和行列式，必须求出 和11,)det(nnA1nT首先考虑三对角
12、矩阵 .1n(1.3),122211 nnn baccbaA它是一个 阶的三对角矩阵，且可以由三个向量 1n ,22和 存储. 为了简化，我们引进一个向量32naa 121nbb.11dd(1.4)1,321nicdabiii 定理 1.2 如果 是形如(1.3)的三对角矩阵，它的各阶顺序主子式都不为零，则1nA1)det()1id ,00010002 1221223121 nnnn dcdcdadaLUA 分 解 式 为 ：的5其中， (1.5)100010012232ndadaL 1221000ndcdcU 在 为非奇异矩阵条件下，可设 其中 是1nA ,)( 121,11 nnjin t
13、tqA jt的第 列.根据 经简单处理后，可得下列递推关系：j,11nI(1.6) ),(),( 21112 jjjjnn tbtectbect 1,4,3n其中 是 阶单位矩阵 的第 列.j 1nIj由(1.6)可知，若最后一列 已知，可递推出其它列t 132,ttn另外 (1.7)11nnetA结合(1.5) 的 分解式有1nALU(1.8)1ney(1.9)t利用三对角矩阵方程组的追赶法和方程组(1.8)右端项 的特殊性可得 ，再由(1.9) 式，1ne1ney可以确定 的各元素如下：1nt(1.10)1,3211,1, niqdcnini综合上面的推导，可得如下一些算法：算法 1.1
14、(计算 )det1nA6Step1：用(1.4)计算 的 各分量. 特殊情况下，会出现当 时有 ，d1n 2ni0id此时可令 用(1.4)继续计算，是 一 个 符 号 )(tdi ).,(11nidStep2：计算 在特殊情况下， 是一个关于 的多项.et(11ninAipt式，那么 时多项式 的值也就是矩阵 的行列式值.0tp1nA算法 2.2 ( )；1n计 算Step1：由(2.10)计算 列向量中的各分量1nt );,12,(1, niqnStep2：由(2.6)计算 );,32(jStep3：得到 .11nnttA对于 可由线性方程组： 求得，进一步可转化,11Tn和 11nTnA
15、x和为如下方程组：.,11 yLUzLzTnTn其中， (1.5)和(1.1)所定义.是 如1,nUL算法 2.3 (求解 )11nTnyAx和步骤 1：由 2112,3nniizdabz niz和 可得到向量 ；1,32)(11nixczdxiiinn x步骤 2：由 2111( 2,3nnniinwcbdwni71,3211 niydawyiiin可得到向量 .算法 2.4 ( 计算 )1et(A和Step1：由算法 1.1 计算 );det(1nStep2：由算法 1.3 得到向量 和 ；xyStep3：计算 可得,1Tn;)det()t(1AnStep4：由算法 1.2 计算 ;ASt
16、ep5：计算 得到矩，和 2211211 , AeyxeBxyBde TnT 阵：21A可以估计求行列式值和逆矩阵的算法 1.4 运算复杂度分别为 ).(2no和1.3 数值算例例 1 求 6 阶矩阵 的行列式 和逆矩阵211211A)det(A.1解：把 分块为 其中A,1nT,211 nA有.20161和Tn ),6543,(ibi).,11,)5,432(6acicii 和由算法(1.4)分别算得：8;6)det(;20.1,5.,3.1,50.,0.2 1421 nAdd ,67.0.67.1 TnAx Ty,.016xdn;4)et()t(dA ,167.03.50.67.83.01
17、,5.5. ,83.067.5.3.7.12345 TTtt ;83.067.50.3.167.015.5.1 nA,5.1, 221 AAde TT，5.15.05.0.1.0. .1.5.A. 5.15.0.15.00.1.1A1.4 小结首先对周期三对角矩阵进行分块，然后利用矩阵的递归方法给出了另外一种求解周期三对角矩阵逆矩阵和行列式的算法，该算法经过数值算例验证有效可行，从而丰富了求解9周期三对角矩阵逆矩阵和行列式的计算方法。2 利用分块技术计算箭状矩阵的逆和行列式2.1 概念和引理定义 2.1 称如下形式的 n 阶实矩阵为箭状矩阵，(2.1),3321nnnacabbA其中 即除第一
18、行，第一列及对角线元素外其余元素都为零的矩,2,1iRcbaii 阵。引理 2.18 设 为一个分块矩阵，其中 为 阶可逆方阵， 阵，DCBAMArsrB为则 (2.2)阶 方 阵 ，为阵 ，为 srsCBC1引理 2.2 设 则有,nRyx.)det(yxITT证明：由于 ,1010IyxII TTT,TII而 所以,10,110yxyIxIyI TTTT ,10yxxyITT即 .)det(yI引理 2.3 设 可逆，且逆矩阵 111, nTTnn IcbcbIRcb可 逆 时 ， 矩 阵则 当.00111 nTnn IIIc10引理 2.4 设 则当 可逆时，矩阵 且逆矩阵,1nRcbT
19、ncbI1 可 逆 ，TncbI1.)(01111 TnTnIbcI引理 2.59 设 则矩阵 可逆的充要条件是 ，且当,RcbTnI1 0-cbT时，有如下关系式： 0-1T .1)(11IcbTnn2.2 相关求行列式与求逆矩阵的定理定理 2.110 (求行列式值) 设 是形如(2.1)的可逆箭状矩阵，其中A可 逆 ，则 矩 阵 Tni cbInia1,21(,0 ).(212niini acb证明：将(2.1)式进行化简，然后利用引理 2.1 有 .1TncID故由 的可逆性，可推知 再由引理 2.2，进一步得A也 可 逆 ，TncbI1 ).()()( 212211 niininiii acbabcD定理 2.210 (求逆矩阵)设 是形如(2.1)的可逆箭状矩阵，其中A 则,0i11DCb其中， ., 11 cbcIcbb TTnT 根据定理 2.2 的结论，可整理成如下的箭状矩阵的求逆算法。算法 2.110 ：Step1：输入箭状矩阵 的元素A );,2(),2(),2,( niniiaStep2：判断，如果对某个 否则，转到0)1输 出 “失 败 ”， 则 停 机iniStep3;Step3：计算 ;1,321132 cbacacbab Tnn
