第28卷第2期 Vol. 28 No. 2
丽水学院学报
JOURNAL OF L ISHUI UNIVERSIT Y
2006年4月Apr. 2006
Hankel 矩阵求逆与相乘的一种快速算法Ξ
杨 毅
(丽水学院, 摘要:Hankel 矩阵求逆与相乘的一种快速算法, 推广了现
有的结果。O (log 2n ) 。
:; ; 矩阵相乘; 快速傅立叶变换; 计算复杂性
:O241.6 文献标识码:A 文章编号:1008-6749(2006) 02-0008-03
A F ast Algorithm for the Inverse Matrices and Multiplication
of H ankel Matrices
Yang Y i
(College of Mathematics and Physics ,Lishui University ,Lishui Zhejiang 323000,China )
Abstract :In this paper ,the author presents a fast algorithm for the inverse matrices and multiplication of the Hankel matrices ; not throught the calculation of the eigenvalues of Hankel matrices. The computation time complexity of the algorithm is O (log 2n ) by using FF T.
K ey w ords :Hankel matrix ;inverse matrix ; multiplication of the matrices ;fast Fourier transform ;computation time complextity
Hankel 矩阵是一类很重要的特殊矩阵, 它在信号处理、石油勘探、线性预测、自回归滤波器设计、计算机时序分析等领域有着广泛的应用, 因此对该矩阵的研究, 引起了许多数学工作者的关注。本文给出的算法, 推广了已有的结果, 若用FFT 计算, 其计算复杂性为O (log 2n ) 。
所谓Hankel 矩阵是指如下n 阶方阵:
a 0
A =
a 1
a 1a 2
a 2a 3
…a n -2…a n -1…
……a n -3
a n -
1a 0
, 其中a i (i =0, n -1) 为实数,
…
a n -1
…
a 0
…
a 1
…
a n -记作A =S C n (a 0, a 1, …, a n -1) ∈S CM n 。
1 Hankel 矩阵的求逆
Ξ
收稿日期:2005-12-05
) , 女, 浙江丽水人, 助教。 作者简介:杨 毅(1980-
第2期 杨 毅:Hankel 矩阵求逆与相乘的一种快速算法
令G =C n (0, 1, 0, …, 0) ∈CM n , G 1=S C n (1, 0, 0, …, 0) ∈S CM n , G 2=S C n (0, 1, 0, …, 1) ∈S CM n , ……………………
G n =S C n (0, 0, 0, …, 1) ∈S CM n , 不难证明:
引理1 G i =G 1G i -1(i =1, 2, …, n -1) , G 0=0, G n =I I 为9
引理2 若A =S C n (a 0, a 1, …, a n -1) ∈S CM n , 则A =f (G 1; =f (G , A =S C n (a 0, a 1, …, a n -1)
n-1
∈S CM n , 这里f (x ) =
引理3
[1]
i =0
6
a i x 。
i
- 若A 、B ∈S CM n , ∈S CM n ∈S CM n 。
引理4 若A ∈S A G 1j f w j ) F j , j =0, n -1, 其中
-j C n (w j , w j ) ∈S CM n , w k =e j
n
, k =0, n -1。
定理1A S C n (a 0, a 1, …, a n -1) ∈S CM n , 且为非奇异, 则A -1=S C n (b 1, b 2, …, b n -1, b 0) , 其中
n
b j =
n-1k =0n-1
66
-1
f (w k ) , j =0,
n
w k -j f (w k ) -1, j =1, n -1。
k =0
证明 由引理4知
A G 1F j =f (w j ) F j , j =0, n =1,
n -1
n-1
其中F j =S C n (n w j
, w j
n -1
, …, w j ) =
k =0
6
w j
n -k
G 1G =G 1
-1
k
k =0
6
w j
-1
n -k
G 。
k
因为A 可逆, 故f (w j ) ≠0, j =0, n -1, 因此A
n-1
G 1F j =f
n-1
(w j ) F j , j =0, n -1上式对j 求和, 得到
A
n-1
-1
G 1
j =0
6
F j =
n-1
j =0
6
f -1(w j ) -1F j ,
k
即A
-1
G 1
j =0k =0
n-1
66
-1
n-1
n-1n-1
G 1w j
-k
G
k
=G 1
-k
j =0
6
f (w j )
n -1
k =0
6
k
w j
n-1
-k
G 。 (1) 。
-1
n -1
(1) 式左端=A
j =0k =0
66
n-1
w j G
k
=A
-1
k =0n-1
6
G
j =0
6
w j
-k
)
当k =0时,
j =0
n-1
6
w j
-k
=n , 当k ≠0时,
n-1
j =0
6
w j
-k
=0, 所以(1) 式左端=nA
n-1
。
n-1
而(1) 式右端=G 1
n-1
j =0
6
-1
f (w j )
k =0
6
n-1
w j
-k
G
k
=G 1
j =0
6
G
k
k =0
6
-1-f (w j ) w j
k
=G 1
k =0
66
n-1j =0
-1-f (w j ) w j
k
G 。
k
j =0
比较(1) 式左右两端, 并由引理2立即可知
A
-1
=G 1
k =0
6
n
n-1
j =0
6
n-1
f (w j )
-1
w j
-k
G
k
=G 1
k =0
6
b k G ∈S CM n , 其中b k =
k
n 6
-1-k
f (w j ) w j , k =0, n -1。
定理1得证。
由定理1, 我们得到了计算Hankel 矩阵逆矩阵的一种快速算法, 步骤如下:
(1) 求方程x n =1的n 个相异根w k , k =0, n -1;
n-1
(2) 由f (x ) =
i =0
6
i
a i x , 计算出f (w k ) , k =0, n -1;
(3) 由(2) 计算f (w k ) -1, k =0, n -1; (4) 计算b j =
n
n-1
k =0
6
f (w k ) -1w k -j , k =0, n -1;
最后得到A
-1
=S C n (b 1, b 2, …, b n -1, b 0) 。
对上述算法, 若用FFT 计算f (x ) , 用逆FFT 计算b j (j =0, n -1) , 则得到计算n 阶Hankel 矩阵逆矩阵的快速算法, 由
10
丽水学院学报 2006年
文[4]知, 其计算复杂性为O (log 2n ) 。
2 Hankel 矩阵相乘
定理2 设A =S C n (a 0, a 1, …, a n -1) ∈S CM n , B =S C n (b 0, b 1, …, b n -1) ∈S CM n ,
n-1
则AB =C n
i =0
6
n-1
a i b i ,
i =0
6
n-1
a i b i +1,
…,
i =0
6
a i b i -
∈CM n 。
证明 直接计算可得
n-1
AB =
i =0
6
n-1
G 1a i G
i -1
i =0
6
G 1b i G
i -1
=(a 0b 0+a 1b 1+…+a n -1b n -1) I +(a 0b 1+a 1b 2+a b 0) G
+…+(a 0b n -1+a 1b 0+…+a n -1-2n 1。
n-容易得到AB 为n 阶循环矩阵, =C n 同理可证n , 且=C n
3=01
6
n-1
i b i , b i a i ,
i =0n-1
6
n-1
i i +1, …, b i a i +1, …,
i =0n-1
66
a i b i -1b i a i -1
∈CM n 。∈CM n 。
i =0i =0i =0
3 5 2 例1 设A =S C 4(3, 5, 2, 4) =
5 2 4 32 4 3 54 3 5 ∈S C 4, 求A -1。
解 利用定理1给出的算法
步骤1 计算得w 0=1, w 1=i , w 2=-1, w 3=-i 。
n-1
步骤2 由f (x ) =
i =0
6
a i x i , 利用FFT 计算得到f (w 0) =14, f (w 1) =1+i , f (w 2) =-4, f (w 3) =1-i 。
步骤3 由步骤2计算得到
-1
f (w 0) =
-1-1-1
, f (w 1) =, f (w 2) =-, f (w 3) =。14242
步骤4 由b i =
4
j =0
6
3
w j
-i
-1
f (w j ) , i =0, 3, 利用逆FFT 计算得到
b 0=-
, b 1=, b 2=, b 3=-。[1**********]2
23
37-33-19
-33-19
-最后得到
37112-33
2337
A
-1
=G 1C 4(b 0, b 1, b 2, b 3) =S C 4(b 1, b 2, b 3, b 0) =
23
。
-192337-例2 设A =S C (3, 1, 2) ∈S CM 3, B =S C (2, -3, 4) ∈S CM 3, 求AB 。
解 由定理2已知AB ∈CM 3, 利用定理1得到:C =AB =C 3(C 0, C 1, C 2) ∈CM 3, 且C 0=
i =0
6
2
a i b i =11, C 1=
i =0
6
2
a i b i +1=-1, C 2=
i =0
6
2
a i b i -1=8, 即C =C 3(11, -1, 8) ∈CM 3。
参考文献
[1]毛纲源. 循环矩阵及其在分子振动中的应用[M ].武汉:华中理工大学出版社,1995[2]江兆林. 关于两类循环矩阵的非异性[J].数学的实践与认识,1995, (2) :52～58[3]沈光星. 关于某些矩阵的特征值[J].应用数学,1991, (3) :76～82
[4]游兆泳. 线性代数与多项式的快速算法[M ].上海:上海科学技术出版社,1980
[5]沈光星. 卢诚波. 关于n 阶(n 1, n 2) 型二重(r 1, r 2) —循环矩阵求逆及相乘的计算方法[J].科技通报,2004, (2) :89～94
第28卷第2期 Vol. 28 No. 2
丽水学院学报
JOURNAL OF L ISHUI UNIVERSIT Y
2006年4月Apr. 2006
Hankel 矩阵求逆与相乘的一种快速算法Ξ
杨 毅
(丽水学院, 摘要:Hankel 矩阵求逆与相乘的一种快速算法, 推广了现
有的结果。O (log 2n ) 。
:; ; 矩阵相乘; 快速傅立叶变换; 计算复杂性
:O241.6 文献标识码:A 文章编号:1008-6749(2006) 02-0008-03
A F ast Algorithm for the Inverse Matrices and Multiplication
of H ankel Matrices
Yang Y i
(College of Mathematics and Physics ,Lishui University ,Lishui Zhejiang 323000,China )
Abstract :In this paper ,the author presents a fast algorithm for the inverse matrices and multiplication of the Hankel matrices ; not throught the calculation of the eigenvalues of Hankel matrices. The computation time complexity of the algorithm is O (log 2n ) by using FF T.
K ey w ords :Hankel matrix ;inverse matrix ; multiplication of the matrices ;fast Fourier transform ;computation time complextity
Hankel 矩阵是一类很重要的特殊矩阵, 它在信号处理、石油勘探、线性预测、自回归滤波器设计、计算机时序分析等领域有着广泛的应用, 因此对该矩阵的研究, 引起了许多数学工作者的关注。本文给出的算法, 推广了已有的结果, 若用FFT 计算, 其计算复杂性为O (log 2n ) 。
所谓Hankel 矩阵是指如下n 阶方阵:
a 0
A =
a 1
a 1a 2
a 2a 3
…a n -2…a n -1…
……a n -3
a n -
1a 0
, 其中a i (i =0, n -1) 为实数,
…
a n -1
…
a 0
…
a 1
…
a n -记作A =S C n (a 0, a 1, …, a n -1) ∈S CM n 。
1 Hankel 矩阵的求逆
Ξ
收稿日期:2005-12-05
) , 女, 浙江丽水人, 助教。 作者简介:杨 毅(1980-
第2期 杨 毅:Hankel 矩阵求逆与相乘的一种快速算法
令G =C n (0, 1, 0, …, 0) ∈CM n , G 1=S C n (1, 0, 0, …, 0) ∈S CM n , G 2=S C n (0, 1, 0, …, 1) ∈S CM n , ……………………
G n =S C n (0, 0, 0, …, 1) ∈S CM n , 不难证明:
引理1 G i =G 1G i -1(i =1, 2, …, n -1) , G 0=0, G n =I I 为9
引理2 若A =S C n (a 0, a 1, …, a n -1) ∈S CM n , 则A =f (G 1; =f (G , A =S C n (a 0, a 1, …, a n -1)
n-1
∈S CM n , 这里f (x ) =
引理3
[1]
i =0
6
a i x 。
i
- 若A 、B ∈S CM n , ∈S CM n ∈S CM n 。
引理4 若A ∈S A G 1j f w j ) F j , j =0, n -1, 其中
-j C n (w j , w j ) ∈S CM n , w k =e j
n
, k =0, n -1。
定理1A S C n (a 0, a 1, …, a n -1) ∈S CM n , 且为非奇异, 则A -1=S C n (b 1, b 2, …, b n -1, b 0) , 其中
n
b j =
n-1k =0n-1
66
-1
f (w k ) , j =0,
n
w k -j f (w k ) -1, j =1, n -1。
k =0
证明 由引理4知
A G 1F j =f (w j ) F j , j =0, n =1,
n -1
n-1
其中F j =S C n (n w j
, w j
n -1
, …, w j ) =
k =0
6
w j
n -k
G 1G =G 1
-1
k
k =0
6
w j
-1
n -k
G 。
k
因为A 可逆, 故f (w j ) ≠0, j =0, n -1, 因此A
n-1
G 1F j =f
n-1
(w j ) F j , j =0, n -1上式对j 求和, 得到
A
n-1
-1
G 1
j =0
6
F j =
n-1
j =0
6
f -1(w j ) -1F j ,
k
即A
-1
G 1
j =0k =0
n-1
66
-1
n-1
n-1n-1
G 1w j
-k
G
k
=G 1
-k
j =0
6
f (w j )
n -1
k =0
6
k
w j
n-1
-k
G 。 (1) 。
-1
n -1
(1) 式左端=A
j =0k =0
66
n-1
w j G
k
=A
-1
k =0n-1
6
G
j =0
6
w j
-k
)
当k =0时,
j =0
n-1
6
w j
-k
=n , 当k ≠0时,
n-1
j =0
6
w j
-k
=0, 所以(1) 式左端=nA
n-1
。
n-1
而(1) 式右端=G 1
n-1
j =0
6
-1
f (w j )
k =0
6
n-1
w j
-k
G
k
=G 1
j =0
6
G
k
k =0
6
-1-f (w j ) w j
k
=G 1
k =0
66
n-1j =0
-1-f (w j ) w j
k
G 。
k
j =0
比较(1) 式左右两端, 并由引理2立即可知
A
-1
=G 1
k =0
6
n
n-1
j =0
6
n-1
f (w j )
-1
w j
-k
G
k
=G 1
k =0
6
b k G ∈S CM n , 其中b k =
k
n 6
-1-k
f (w j ) w j , k =0, n -1。
定理1得证。
由定理1, 我们得到了计算Hankel 矩阵逆矩阵的一种快速算法, 步骤如下:
(1) 求方程x n =1的n 个相异根w k , k =0, n -1;
n-1
(2) 由f (x ) =
i =0
6
i
a i x , 计算出f (w k ) , k =0, n -1;
(3) 由(2) 计算f (w k ) -1, k =0, n -1; (4) 计算b j =
n
n-1
k =0
6
f (w k ) -1w k -j , k =0, n -1;
最后得到A
-1
=S C n (b 1, b 2, …, b n -1, b 0) 。
对上述算法, 若用FFT 计算f (x ) , 用逆FFT 计算b j (j =0, n -1) , 则得到计算n 阶Hankel 矩阵逆矩阵的快速算法, 由
10
丽水学院学报 2006年
文[4]知, 其计算复杂性为O (log 2n ) 。
2 Hankel 矩阵相乘
定理2 设A =S C n (a 0, a 1, …, a n -1) ∈S CM n , B =S C n (b 0, b 1, …, b n -1) ∈S CM n ,
n-1
则AB =C n
i =0
6
n-1
a i b i ,
i =0
6
n-1
a i b i +1,
…,
i =0
6
a i b i -
∈CM n 。
证明 直接计算可得
n-1
AB =
i =0
6
n-1
G 1a i G
i -1
i =0
6
G 1b i G
i -1
=(a 0b 0+a 1b 1+…+a n -1b n -1) I +(a 0b 1+a 1b 2+a b 0) G
+…+(a 0b n -1+a 1b 0+…+a n -1-2n 1。
n-容易得到AB 为n 阶循环矩阵, =C n 同理可证n , 且=C n
3=01
6
n-1
i b i , b i a i ,
i =0n-1
6
n-1
i i +1, …, b i a i +1, …,
i =0n-1
66
a i b i -1b i a i -1
∈CM n 。∈CM n 。
i =0i =0i =0
3 5 2 例1 设A =S C 4(3, 5, 2, 4) =
5 2 4 32 4 3 54 3 5 ∈S C 4, 求A -1。
解 利用定理1给出的算法
步骤1 计算得w 0=1, w 1=i , w 2=-1, w 3=-i 。
n-1
步骤2 由f (x ) =
i =0
6
a i x i , 利用FFT 计算得到f (w 0) =14, f (w 1) =1+i , f (w 2) =-4, f (w 3) =1-i 。
步骤3 由步骤2计算得到
-1
f (w 0) =
-1-1-1
, f (w 1) =, f (w 2) =-, f (w 3) =。14242
步骤4 由b i =
4
j =0
6
3
w j
-i
-1
f (w j ) , i =0, 3, 利用逆FFT 计算得到
b 0=-
, b 1=, b 2=, b 3=-。[1**********]2
23
37-33-19
-33-19
-最后得到
37112-33
2337
A
-1
=G 1C 4(b 0, b 1, b 2, b 3) =S C 4(b 1, b 2, b 3, b 0) =
23
。
-192337-例2 设A =S C (3, 1, 2) ∈S CM 3, B =S C (2, -3, 4) ∈S CM 3, 求AB 。
解 由定理2已知AB ∈CM 3, 利用定理1得到:C =AB =C 3(C 0, C 1, C 2) ∈CM 3, 且C 0=
i =0
6
2
a i b i =11, C 1=
i =0
6
2
a i b i +1=-1, C 2=
i =0
6
2
a i b i -1=8, 即C =C 3(11, -1, 8) ∈CM 3。
参考文献
[1]毛纲源. 循环矩阵及其在分子振动中的应用[M ].武汉:华中理工大学出版社,1995[2]江兆林. 关于两类循环矩阵的非异性[J].数学的实践与认识,1995, (2) :52～58[3]沈光星. 关于某些矩阵的特征值[J].应用数学,1991, (3) :76～82
[4]游兆泳. 线性代数与多项式的快速算法[M ].上海:上海科学技术出版社,1980
[5]沈光星. 卢诚波. 关于n 阶(n 1, n 2) 型二重(r 1, r 2) —循环矩阵求逆及相乘的计算方法[J].科技通报,2004, (2) :89～94