-
基于稀疏矩阵的逆和行列式的计算
摘要
：<
/p>
稀疏矩阵在现实中有很多应用，因此稀疏矩阵的计算近年来被广泛地研究
< br>.
周期三对角矩阵和箭状矩
阵作为两种常见的稀疏矩阵被
广泛地应用在工程计算中。
本文基于周期三对角矩阵和箭状矩阵的结构特点，
根据矩阵分解的一些方法，着重讨论了一些周期三对角矩阵和箭状矩阵的求逆与行列式运算问题，并 给出
了相应的算法。本文首先根据周期三对角矩阵的特点研究了周期三对角矩阵的求逆算
法，文中分别应用矩
阵的递归方法、矩阵的分块技术来研究周期三对角矩阵的逆矩阵运算
问题，并给出了相应于以上方法或技
术的求逆新算法，同时也考虑一种求周期三对角矩阵
的行列式算法，并通过一些数值例子验证了所给算法
的可行性以及有效性。其次根据箭状
矩阵的结构特点，利用矩阵的分块技术，给出了一个求解箭状矩阵的
逆矩阵及行列式的算
法，同时列举一个数值例子并给出了
matlab
程序，说明算
法是有效可行的。
关键词：
稀疏矩阵；周期三对角矩阵；箭状矩阵；逆矩阵
Based on sparse matrix
inverse and determinant calculation
Abstract:
Sparse matrix computation has attracted
extensive researches in recent years because it
can have a lot of applications in
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 periodic 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 created 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 periodic tri-
diagonal ly,
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 .
Key words
: sparse matrix
;periodic tri-diagonal matrix arrow matrix
;inverse matrix
1
引言
在科学与工程计算中，
经常会遇到稀疏矩阵的计算问题，
例如关于三对角矩阵、
周期三
对角矩阵和箭状矩阵的行列式计算、
确定逆矩阵
、
线性方程组求解问题。
它们在矩阵分析理
论、
样条插值函数确定、
微分方程的差分法求解等方面都有
非常广泛地应用前景。
稀疏矩阵
计算一直是矩阵计算中的关注点
之一，
近年来许多学者加强了这方面的研究，
也提出了许多
新的有效的计算方法，这些成果丰富了矩阵计算的理论和应用。
<
/p>
对于一般的矩阵计算，
主要是进行矩阵的行列式计算、
矩阵的求逆运算、
矩阵的特征值
和特征向量计算以
及求解相应的线性方程组。对一般矩阵来说，运算复杂度通常是
o
(
n
3
)
.
而对于稀疏矩阵，
它的结构比较特殊，
我们可以根据稀疏矩阵特殊结构特点，
采用不同的计
算方法，对
稀疏矩阵进行计算，从而可以减少运算的复杂度。例如，在本文中，主要解决两
个问题，
第一个是利用矩阵分块和递推技术求周期三对角矩阵的逆和行列式；
第二个是利用
分块技术计算箭状矩阵的逆和行列式。
由于在
许多科学与工程计算中，
经常会出现对大型稀
疏矩阵进行计算，
所以我们有必要对稀疏矩阵的计算进行研究。
对于稀疏矩阵的
的计算，
目前很多学者根据一些稀疏矩阵的特殊结构，
本文主要
解决两
类稀疏矩阵分别是周期三对角矩阵和箭状矩阵，
用不同的
方法对稀疏矩阵的逆矩阵计算做了
很多研究，得到了很多成果。例如
2009
年
i
和
Hadj
利用矩阵分块技巧
和递归一种求
Hessenberg
矩阵逆矩阵的新递归算法
[1]
；
2008
年，
等利用升阶
手段和
分块技术得到一种计算五对角矩阵行列式和逆的方法
；沈
光星、戴华、张振跃等分别给出
了对称三对角矩阵、
Jacob
i
矩阵关于特征值的一些算法
[3]
～
[7]
[2]
。
本文主要研究了周期三对角矩阵和箭状矩阵的逆
矩阵和行列式的求解方法，文中首先
介绍了矩阵分解的一些方法和技术，
如矩阵分块、
递归、
降阶等技术，
然后根据周期三对角
矩阵的特殊结构，利用上述分解方法分别对周期三对角矩阵的逆
矩阵和行列式进行了探讨，
最后分别给出了一些求解算法和数值算例。
< br>
其次，文中利用矩阵的分块技术，根据箭状
矩阵的特殊结构，给出了一个求解非奇异
逆箭状矩阵的逆和行列式的算法，
并给出了一个算例以验证算法有效可行，
从而丰富了求解
箭状矩阵的逆矩阵和行列式的计算方法。
1
利用矩阵分块和递归技术求周期三对角矩阵的逆和行列式
1.1
预备知识
对周期三对角矩阵进行如下分块：
2
a
1
?
?
b
1
c
1
?
a
b
?
c
2
< br>?
2
2
?
?
A
?
?
?
n
?
1
A
?
?
?
?
?
T
?
?
?
?
n
?
< br>1
a
n
?
1
b
n
?
1
c
n
?
1
?
?
?
a
n
b
n
?
?
c
n
?
< br>其中，
?
n
?
< br>1
?
[
c
n
,
0
,
?
,
0
,
a
n
]
?
R
1
?
(
n
?
1
)
,
< br>
T
?
n
?
1
?
（
1.1
）
?
?
n
?
1
?
?
n
?
1
?
b
n
,
?
< br>b
1
?
a
?
2
A
?
?
?
?
?
?
c
1
b
2
?
c
2
?
a
n
?
< br>2
?
b
n
?
2
a
n
?
1
?
a
1
?
?
?
0
?
?
?
?
?
(
n
?
< br>1
)
?
(
n
?
1
)
?
?
R
,
?
n
?
1
?
?
?
?
?
R
(
n
?
< br>1
)
?
1
.
?
?
?
c
n
?
2
?<
/p>
?
0
?
?
b
n
?
1
?
?
c
n
?
1
?
?
?
引理
1.1
< br>如果
A
n
?
1
是非奇异矩阵，那么
T
?
1
det(
A
)
?
det(
A<
/p>
n
?
1
)(
?
n
?
1
?
?
n
?
1
A
n
?
< br>1
?
n
?
1
)
.
证明：
由于
?
?<
/p>
I
n
?
1
T
?
1
?
?
?
n
?
1
A
n
?
1
0
?
?
A
n
?
1
?<
/p>
n
?
1
?
其中
I
n
?
1
,
两边取行列式后即可得到结论，
?
?
?
T
?
1
1
?
?
0
?
n
?
1
?
?
n<
/p>
?
1
A
n
?
1
?
n
?
1
?
是
n
?
1
阶单位矩阵
.
推论
1.1
设
A
和
A
n
?
1
都是非奇异
矩阵，则
T
?
1
d
?
?
n
?
1
?
?
n
?
1
A
n
< br>?
1
?
n
?
1
?
0
.
1.2
主要结论
?
A
n
?
1
?<
/p>
n
?
1
?
定理
1.1
A
是非奇异周期三对角矩阵，
A
?
?
T
?
,
且
A
n
?
1
非奇异，则
?
?
n
?
1
?
?
n
?
1
(
1
)
det(<
/p>
A
)
?
det(
A
n
?
1
)
?
d
?
1
?
1
T
?
1
?
< br>1
?
A
n
?
?
eA
n
?
1
?
eA
n
?
1
?
n
?
1
?
n
?
1
A
n
?
1
?
1
< br>?
n
?
1
(
2
)
A
?
?
?
（
1.2
）
T
?
1
?
?
n
?
1
A
n
?
1
e
?
?
?
< br>1
证明：
(1)
由引理
1.1
可以得出证明
.
.
3
?
1
T
?
1
?
1
?
(
I
?
e
?
?
A
)
< br>?
eA
?
A
n
?
1
?
n
?
1
?
?<
/p>
A
n
?
1
n
?
1
n
?
1
n
?
1
n
?
1
n
?
1
?
n
?
1
(2)
由于
<
/p>
?
T
?
?
?
T
?
1
?
?
n
?
1
A
n
?
1
< br>e
?
?
n
?
1
?
n
?
1
?
?
?
=
?
?
I
n
?
1
0
?
?
?
I
< br>n
，那么可知结论成立
. <
/p>
0
1
?
?
注：如果矩阵
A
是对角占优矩阵或者是对称正定矩阵，则定理
2.1
条件显然满足
.
为了求
?
1
?
1
T
?
1
出
A
的逆和行列式，必须求出
det(
A
n
?
1
),
A
n
?
1
< br>,
A
n
?
1
?
n
?
1
和
?
n
?
1
A
n
?
1
.
首先考虑三对角
矩阵
A
n
?
1
.
<
/p>
?
b
1
?
a
?
2
A
n
?
1
?
?
?
?
?
?
c
1
b
2
?
c
2<
/p>
?
a
n
?
2
?
b
n
?
2
a
n
?
1
?
?
?
?
,
(1.3)
?
c
n
?
2
?
b
n
?
1
?<
/p>
?
它是一个
n
?
1
阶的三
对角矩阵，且可以由三个向量
c<
/p>
?
?
c
1
c
2
?
c
n
?
2
?
,
a
?
?
a
2
a
3
?
a
n
?<
/p>
1
?
和
b
?
?
b
1
b
2
?
b
n
?
1
?
存储
.
为了简化，我们引进一个向量
d
?
?
d
1
d
2
?
d
n
?
1
?
< br>.
b
1
i
?
1
?
?
a
d
i
?
?
(1.4)
b
i
?
i
c
i
?
1
i
?
2<
/p>
,
3
?
,
n
?
1
?
d
i
?
1
?
定理
1.2
如果
A
n
?<
/p>
1
是形如
(1.3)
的三对角矩阵，它的各阶顺序主子式都不为零，则
(
1
)
det(
A<
/p>
n
?
1
)
?
?
d
i
i
?
1
n
?
1
(
2
)
A
n
?
1
的
LU
分
解式为：
?
1
?
a
2
?
d
?
1
A
n
?
1
?
LU
?
?
0
?
?
?
?
?
0
?
?
0
1
?
0
?
?
?
?
a
n
?
1
d
n
?
< br>2
a
3
1
d
2
?
?
?
0
0
?
?
0
?
?
d
1
c
1
0
?
?
?
0
< br>d
2
c
2
?
?
?
?
?
?
?
?
?
0
?
?
?
?
?
0
?
?
1
?
?
< br>?
?
0
?
?
?
?
?
?
0
?
,
?
?
c
n
?
2
?
0
d
n
?
1
< br>?
?
?
4
其中，
?
?
?
?
L
?
?
?
?
?
?
?
?
1
a
2
d
1
< br>0
?
0
0
1
a
3
d
2
?
?
?
0
1
?
0
?
?
?
?
a
n
?
1
d
< br>n
?
2
0
?
?
?
d
1
0
?
?
0
?
?
?
?
，
U
?
?
?
?
?
?
< br>?
?
0
?
?
?
0
1
?
?
?
c
1
d
2
?
?
0
c
2
?
?
?
?
?
< br>?
?
0
0
?
?
?
?
0
?
(1.5)
?
c
n
?
2
?
d
n
?
1
?<
/p>
?
?
1
在
A
n
?
1
为非奇异矩阵条件下，可设
A
n
?
1
?
(
q
ij
< br>)
1
?
i
,
j
?
n
?
1
?
?
t
1
1
t
2
?
t
n
?
1
?
,
其中
t
j
是
A
n
?
?
1
?
1
的第
j
列
.
根据
A
n<
/p>
?
1
A
n
?
1
?
I
n
?
1
,
经简单处理后，可得下列递推关系：
t
n
?
2
?
< br>1
c
n
?
2
(
e
n
?
1
?
b
n
?
1
t
n
?
1
),
t
j
?
1
(
e
j
?
1
?
b
j
?
1
t
j
?
1<
/p>
?
b
j
?
2
t
j
?
2
),
j
?
n
?
3
,
< br>n
?
4
,
?
,
1
(1.6)
c
j
其中
e
j
是
n
?
1
阶单位矩阵
I
n
?
1
的第
j
列
.
由
(1.
6)
可知，若最后一列
t
n
?
1
已知，可递推出其它列
t
n
?
2
,
t
n
?
3
,
?
t
1
另外
A
n
?
1
t
n
?
1
?
e
n
?
1
< br>
(1.7)
结合
< br>(1.5)
A
n
?
1
的
LU
分解式有
Ly<
/p>
?
e
n
?
1
(1.8)
Ut
n
?<
/p>
1
?
y
(1.9)
利用三对角矩阵方程组的追赶法和方程组
(1.8)
右端项
e
n
?
1
的特殊性可得
y
?
e
n
?
1
，<
/p>
再由
(1.9)
式，可以确定
t
n
?
1
的各元素如下：
1
?
q
?
n
?
1
,
n
?
1
?
d
n
?
1
?
?
(1.10)
c
< br>i
?
q
i
,
n
?
1
?
?
q
i
?
1
,
n
?
1
i
?
n
?
2
,
n
< br>?
3
,
?
1
?
d
i
?
综合上面的推导，可得如下一些算法：
算法
1.1
(
计算
de
t(
A
n
?
1
)
)
5
Step1
：
用
(1.4)
计算
d
的
n
?
1
各分量
.
特殊情况下，
会出现当
i
?
n
?
2
时有
d
i
?
0
，
此时可令
d
i
?
t
(
t
是一个符号
用
(1.4)
继续计算
(
d
i
?
1
,
?
,
d<
/p>
n
?
1
).
)
，
Ste
p2
：计算
det(
A
n
?
1
)
?
?
i
?
1
d
i
.
<
/p>
在特殊情况下，
p
?
?
i
?
1
d
i
是一个关于
t
的多项
式，那么
t
?
0
时多项式
p
的值也就是矩
阵
A
n
?
1<
/p>
的行列式值
.
?
1
算法
2.2 (
计算
A
n
?
1
< br>)
；
n
?
1
n
?
1
Ste
p1
：由
(2.10)
计算
t
n
?
1
列向量中的各分量
q
i
,
n
?
1
(
i
?
n
?
1
,
n
?
< br>2
,
?
1
,
);
Step2
：由
(2.6)
计算
t
j
(
j
?
n
< br>?
2
,
n
?
3
,
?
1
);
?
1
Step3
：得到
< br>A
n
?
1
?
?
t
1
t
2
?
t
n
?
1
?
.
?
1
T
?
1
T
对于
A
n
?
1
?
n
?
1
和
?
n
?
1<
/p>
A
n
?
1
,
可由线性方程组：
A
n
?
1
x
?
?
n
?
1
和
A
n
?
1
?
?
n
?
1
求得，进一步可转化
为
如下方程组：
Lz<
/p>
?
?
n
?
1
,
Ux
?
z
,
U
T
?
?
?
n
< br>?
1
,
L
T
y
?
?
.
其中，
L
,
U
,
?
n
?
1
,
?
n
?
1
是如
(1.5)
和
(1.1)
所定义
.
T
算法
2.3 (
求解
A
n
?
1
x
?
?
n
?
1
和
A
n
?
1
y
?
?
n
?
1
)
?
?
z
1
?
a
1
?
a
?
z
i
?
i
z<
/p>
i
?
1
步骤
1
：由
?
d
i
?
1
?
a
n
?
2
?
z
?
b
?
z
n
?
2
n
?
1
?<
/p>
n
?
1
d
n
?
2
?
i
?
2
,
3
?
,
n
?
2
1
?
x
?
z
n<
/p>
?
1
n
?
1
?
d
n
?
1
?
和
?
可得到向量
x
；
1
?
x
i
?
(
z
i
?
c
i
x
i
?
1
)
< br>i
?
n
?
2
,
n
?
3
,
?
1
?
d
i
?
步骤
2
：由
?
1
w
?
c
n
1
?
d
1
< br>?
c
?
w
i
?
i
?
1
w
i
?
1
?
d
i
?
1
?
w
?
?
n
?
1
< br>d
(
b
n
?
c
n
?
2
w
n
?
2
n
?
1
?
?
y
n
?
1
?
w
< br>n
?
1
?
a
i
?
2
,
3
?
,
n
?
2
?
y
i
?
w
i
?
i
?
< br>1
y
i
?
1
i
?
n
?
2
,
n
?
3
,
?
1
?
d
i
?
6
可得到向量
y
.
算法
2.4
(
计算
det(
A
)
和
A
?
1
)
Step1
：由算法
1.1
计算
det(
A
n
?
1
);
Step2
：由算法
1.3
得到向量
x
和
y
；
T
Step3
：计算
d
?
d
n
?
?
n
?
1
x
,
可得<
/p>
det(
A
)
?
det(
A
n
?
1
)
?
d<
/p>
;
?
1
Step4
：由算法
1.2
计算
A
n
?
1
;
?
1
T
Step5
：计算
e
?
d
?
1
,
B
?
xy
T
,
A<
/p>
得到矩
11
?
T
n
?
1
?
eB
,
A
12
?
?
ex
,
A
21
?
?
ey
和
A
22
，
阵：
A
?
1
?
?
?
A
11
?
A
21
A
12
?
?
A
22
?
2
可以估计求行列式值和逆矩阵的算法
1.4
运算复杂度分别为
o
(
n
)
和
o
(
n
).
1.3
数值算例
1
?
?
2
?
1
?
?
1
2
?
1
?<
/p>
?
?
?
?
?
1
2
?
1
?
1
例
1
求
6
< br>阶矩阵
A
?
?
< br>?
的行列式
det(
A
)
和逆矩阵
A
.
?
1
2
?
1
?
?
?
?
1
2
?
1
?
?
?
1
?
1
2<
/p>
?
?
?
?
?
2
?
1
?
?
?
1
2
?
1
?
?
?
?
A
n
?
1
?
n<
/p>
?
1
?
?
,
?
1
2
?
1
解：把
A
分块为
A
?
?
T
,
其中
A
n
?
1
< br>?
?
?
?
?
?
?
n
?
1
?
n
?
1
?
?
1
2
?
1
?
?
?
?
1
< br>2
?
?
?
?
n
?
1
?
?
n
?
1
?
?
1
0
0
0
?
1
?
T
和
?
< br>6
?
2
.
有
b
i
?
2
(
i
?
1
,
2
,
3
,
4
,
5
,
6
),
c
i
?
?
1
(
i
?
1
,
2
,
3<
/p>
,
4
,
5
),
c
6
?
1
,
a
1
?
1
和
a
< br>i
?
?
1
(
i
?
1
,
2
,
3
,
4
,
5
).
由算法
(1.4)
分别算得：
d
1
?
2
.
0000
< br>,
d
2
?
1
.
5000
,
d
3
?
1
.
3333
,
d
4
?
1
.
2
500
,
d
5
?
1
.
2000
;
det(
A
n
?
1
)
?
6
;
?
1<
/p>
?
,
x
?
A
n
?
1
?
n
?
1
?
?
0
.
6667
0
.
< br>3333
?
0
.
3333
?
0
.
6667
T
7
-
-
-
-
-
-
-
-
-
上一篇：反掩码详解
下一篇：异方差性的检验和补救