计算方法研究报告

1、2016年计算方法研讨课题目 Toeplitz矩阵与向量的乘积课题小组：组长：李灵萱成员：仇天乐、肖晟远、赵海宁、寿立夫、张连炜、李怡宁一个n阶Toeplitz矩阵形如一 tottjt1to*aa+-t工- .t1t。1可以将T嵌入一个“循环矩阵”，然后利用FFT来快速计算矩阵-向量积Tx,其计算复杂度为 O(nlog n)。1.理论基础1)一个n阶循环矩阵C具有如下结构Co2)C =circc0, g , 。=c。,cnA一个n阶离散Fourier矩阵Fn为一1FnHC=Fn AFn，A =-001= diag%,%；：%上入nV12 7i ,八(nJ)e n包(n4)(n)e n这里的i是

2、虚数单位。3)数学上业已证明：一个 n阶循环矩阵C能被Fn对角化，即F 2T：jk且鼠=标(C) = cj e n (k =0,1，n 1)是C的特征值。可以用IFFT计算，即 j =0IA cici2-2r-1c2c2:=VnFn : =IFFT(:)3 n 1fn 1jcn 14) 利用FFT和IFFT ,则矩阵-向量积Cx可以表为Cx = FnHAFnx=、n FFT 上IFFT(x) =FFT(A，IFFT(x).5)对于n阶Toeplitz矩B$ T ,首先将T嵌入一个2n阶循环矩阵C ,即TIT，其中：T一0titn0ti 1.tn0将n维列向量x嵌入一个2n维列向量y =rI这时

3、有_oT Cy =M；.T叫(PlT JLoJ bTx_根据4)的事实，可用2n阶的FFT和IFFT计算矩阵-向量积Cy ,于是间接获得矩阵-向量积Tx。这样，矩2、阵-向重积Tx的计算受杂度从 O(n )降低到了 O(n log n)。6) 公式的数学证明我们令矩阵A=FnCFnH,则需要证明A为对角化的矩阵。根据矩阵的结合律，令 B=FnC一Tij岩j记列向重 c(i) =c0,G,，cn. ,i =0,1,.,n1,且Wn =en ,并且记c(i j) =c(i j)nR(n),即c(i j)以n为周期延拓后序列的主值序列，也就是循环矩阵 C 的第 j 个列向量，得到 C =c(i),c

4、(i -1),c(i -2),., c(i -n-1)on 1-1记 y(k)= JnMFnc(i)= c(i)W1k =/IDFT(c(i), i =0n1jk则由DFT的性质可以得到 Fnc(i j) =Ty(k)Wnj ,所以 、-nB =FnC =Fnc(i),c(i -1),c(i -2),.,c(i-n-1)=y(k),y(k)W：,., y(kW(n)k .n而 A = BFnH ,1 n1(k1)(j1)aij = - ；(i，j) =bikWn n yy(i) i=j=0 i = jn(J)k=-y(i)Wnn7综上，命题得证。.编程实现1)存储方案设计由于Toeplitz矩

5、阵与循环矩阵中有大量重复数据，因此，根据两者的特点，我们用长度为2n-1的向量aT来储存Toeplitz矩阵，即为=口1,.,3枭/1,.,3;用长度为n的向量出来储存循环2一矩阵，即ac =Q,G,.,a。将储存仝间从O(n )降低为O(n)。2)计算步骤设计.循环矩阵直接计算因为我们将循环矩阵存储在长度为n的向量a。中，所以可以利用n次向量积求得答案，在计算时只需要注意在每次向量积时调整出中元素的顺序即可。利用fft求解首先利用ifft函数求得循环矩阵的特征值， 注意到matlab中ifft函数并未做归一化处理， 因此需 要在ifft得到的向量上乘以系数 n；之后对向量X取ifft,并与特

6、征值做 matlab中的点乘操作，最后 对所得向量做fft运算即可得到结果。. Toeplitz 矩阵直接计算Toeplitz矩阵与向量乘法的步骤与循环矩阵类似，同样需要注意所存储向量在实际运算中元素的顺序；利用fft求解Toeplitz矩阵与向量乘法的关键是将Toeplitz矩阵转化为循环矩阵，只需要在存储n阶Toeplitz矩阵的向量中添加一个0,并调整元素顺序即可得到2n阶循环矩阵，之后的计算步骤与循环矩阵完全类似。3)编制Matlab程序Matlab程序已包含在文件夹中3.测试算例设计测试方法。进行测试时由随机数生成器生成矩阵为保证实验的准确性，我们要进行多阶多次实验分别取平均时间以减

7、小实验误差，因此我们对1-1000阶矩阵每阶分别进行 1000次实验并作出平均用时-阶数图像来直观地进行对比。测试步骤：1、确定实验矩阵的最小阶数与最大阶数2、循环矩阵C根据阶数n生成n个随机数，Toeplitz矩阵则要生成2n-1个随机数，并根据 5）变为 循环矩阵3、对生成的循环矩阵分别直接计算向量积和利用FFT计算向量积，分别统计时间，并取时间平均值4、分别作出用时-阶数图像，进行直观对比1）给定循环矩阵C不变，对随机生成的多个向量X连续计算矩阵-向量积Cx,并记录总时间。对比直接计算与借助FFT计算的速度。519 U一 一 eO 1 5 O o O ono00直接计算实额循环矩阵计算时

8、间一矩阵阶数图像20030040050060。7003009001000矩阵阶数nFFT计算实数循环矩阵计算时间一距阵阶数图像13-12003004005006007008009001000矩庠阶数fi直接计算复数循环矩阵计篁时间一矩阵阶数图像2003004006006007003009001000矩阵阶数nFFT计算复数循环矩阵计算时间一矩阵阶数图像02 O.5 19O1 5 o aH.OO600700S0090010009 O J20 0矩阵阶数n可以看到在计算实数循环矩阵时，利用fft的方法相比于直接计算大约块50100倍；而在计算复数矩阵时加速的效果则要差一些。2）给定Toeplitz

9、矩B$ T不变，对随机生成的多个向量X连续计算矩阵-向量积Tx ,并记录总时间。对比直接计算与借助 FFT计算的速度。x 10 1直接计算实缴T-pim福环矩阵 讨算时间一走眸阶数 图像二IIIII001002003004005006007008009001000炬阵阶数n1.5尸FT计算实数同汩匕循环矩阵计算时间一矩阵阶数图俅x 1 口.001004007Doo矩阵阶弟n直接L算复数Tgpli泛循环矩阵计算时间一粗障阶数图像FFT计算复数Tqm心循环矩阵计算时间一矩阵阶数图像1002003004005006。07008009001000矩阵阶数n利用fft计算Toeplitz的计算时间在512阶矩阵左右处有一个跳变，这是因为在