对称Toeplitz矩阵特征值的快速算法

啊

第7卷第3期2009年6月

福建工程学院学报

JournalofFujianUniversityofTechnology

Vol.7No.3Jun.2009

文章编号:1672-4348(2009)03-0301-03

对称Toeplitz矩阵特征值的快速算法

曾祝明

(福建工程学院数理系,福建　福州　350108)

摘要:利用n阶对称Toeplitz矩阵的结构特点和对称性,给出了计算该类矩阵所有特征值的一个快速算法,该算法的计算复杂度仅为O(n2logn)。关键词:Toeplitz矩阵;Lanczos算法;特征值中图分类号:O241.6

文献标识码:A

Afasteigenvaluealgorithmforetrim(Mathematicsandment,Technology,Fuzhou350108,China)

andsymmetryofsymmetricToeplitzmatricesofthenthorder,we

2

presentalgorithmthatcansolvealltheeigenvaluesofansymmetricO(nlogn)Toeplitzmatrixinoperations.

Keywords:Toeplitzmatrix;Lanczosalgorithm;eigenvalue

引言

Toeplitz矩阵的特征值问题在科学与工程计

确定(共有n个元素)。

定义2　n阶对称Toeplitz矩阵定义如下:

t0t1…tn-1

TS=

t1

t0

算、图像和信号处理领域中有着重要的应用,已引

起不少学者的关注,然而对于计算Toeplitz矩阵的部分或全部特征值的研究,相应的数值算法涉

[1-5]

及不多。本文介绍一种求解对称Toeplitz矩阵特征值问题的快速算法。

…ω…

tn-2

…

tn-1

…

tn-2

t0

(2)

即TS=(tl,k),tl,k=t|k-l|,l,k=0,1,…,n-1。显然,对称Toeplitz矩阵完全由它的第一行或第一列元素确定(共有n个元素)。

1　两个定义

定义1　n阶Toeplitz矩阵定义如下

t0t1…tn-1

T=

t-1

t1

2　算法推导

我们思路是利用对称Toeplitz矩阵的对称

(1)

…ω

…

tn-2

…

t1-n

…

t2-n

…

t0

性。记n阶对称Toeplitz矩阵为TS,假设TS为非亏损矩阵,则矩阵TS的特征值分解为

TS=PDP

-1

(3)

即T=(tl,k),tl,k=t|k-l|,l,k=0,1,…,n-1。显然,Toeplitz矩阵完全由它的第一行和第一列元素

其中,D为对角矩阵;P为非奇异矩阵。这时取矩阵P为正交矩阵,即

收稿日期:2009-01-06

基金项目:福建工程学院科研发展青年基金(GY-Z08119)

作者简介:曾祝明(1982-),男(汉),福建泉州人,助教,硕士,研究方向:数值代数.

啊

302

PP

T

福建工程学院学报

=I

(4)

第7卷

因而有TS=PDP。

首先对矩阵TS实施Lanczos三对角化,则

TS=QJQ,

T

T

(5)

其中,Q为正交矩阵;J为对称三角矩阵。再对矩阵J实施对角化,得

J=WDW

T

(6)

其中,W为正交矩阵;D为对角矩阵。因而根据式(5)和(6),我们可得矩阵的特征值分解式(3),其中

P=QW

(7)

　　我们知道Lanczos算法主要运算量是计算矩阵与向量的乘积。一般来说,n阶矩阵与任一n

2

维向量的乘积的计算复杂度为O(n)。这里我们

利用计算n阶对称Toeplitzn的乘积的一种快速算法,O(nlogn),os,阶对称os,所需

2

的计算量为(logn),上述得到的三对角矩阵仍具有对称性。为了保持它的对称性和三对角结构,我们在QR迭代的对角化过程中采用正交变换。

下面我们给出一个重要的引理。

引理1　任一n阶Toeplitz矩阵与任一n维向量的乘积的计算复杂度为O(nlogn)。

证明:考虑n阶实Toeplitz矩阵T,见式(1),我们将它嵌入一个(2n-1)×(2n-1)阶的循环矩阵C,即

t0t-1

t1t0

　　令x^为一(2n-1)维的向量

T

(9)x^=(x1,x2,…,xn,0,0,…,0)

容易看出,y为向量z的前n个分量,其中

z≡Cx^

　　由于循环矩阵与向量的积可以利用FFT来计算,即

Cx^=ifft(fft(d)) 3fft(x^))

其中,d为矩阵T的第一列;fft(d)表示向量的快速傅里叶变换;ifft(v)表示向量v的逆快速傅里叶变换;“.3”表示2个向量对应元素的积。由于fft(v)的计算复杂度为O(nlogn),这样引理得证。

注:T[1我们可以得到如下算法。　　算法1

该算法利用FFT计算一n维向量x与n阶Toeplitz矩阵的乘积y,即y=Tx,

1)定义一个(2n-1)一维的向量x^,其中

T

x^=(x1,x2,…,xn,0,0,…,0),

2)由公式Cx^=ifft(fft(d) 3fft(x^))计算向量z,其中d为循环矩阵C的第一列,

T

3)令z=(z1,z2,…,z2n-1,z2n-1),则y=(z1,

z2,…,zn)。

T

matlab程序具体如下:

Functiony=FastToep(T,v)n=length(T);

v=[v’,zeros(n-1,1)’]’;d=T(:,1)’;d1=T(1,n:-1:2);d=[d,d1];

z=ifft(fft(d).3fft(v));y=z(1:n);

……ω

………ω…

tn-1tn-2

t1-ntn-1

t2-nt1-n

……ω………ω…

t-1t-2

…

C=

t1-ntn-1tn-2

…

t2-nt1-ntn-1

…

t0t-1t-2

…

t1t0t-1

…

t2t1t0

…

tn-1tn-2tn-3

…

t1

T。

…

t2

…

t1-n

…

t2-n

…

t3-n

…

t0

根据前面所述,我们可以得到一个计算n阶对称Toeplitz矩阵所有特征值的算法,它的计算

2

复杂度仅为O(nlogn),比文献[1]、[2]来得少。　　算法2　(对称Toeplitz矩阵特征值快速算法)

给定一n阶对称Toeplitz矩阵TS,如式(2)。　　1)利用Lanczos算法把对称Toeplitz矩阵TS约化成三对角矩阵(过程运用算法1)。

容易看出,C的n阶顺序主子阵即为Toeplitz矩阵

给定一个n维的向量

x=(x1,x2,…,xn)

T

(8)

计算矩阵与向量的乘积

y=Tx

啊

第3期曾祝明:对称Toeplitz矩阵特征值的快速算法303

　　2)利用带Wilkinson位移的隐式 …… 此处隐藏：2150字，全部文档内容请下载后查看。喜欢就下载吧 ……