一种基于计算机的复数傅里叶级数的算法

《一种基于计算机的复数傅里叶级数的算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一种基于计算机的复数傅里叶级数的算法JamesW.Cooley和JohnW.Tukey提出Yates发明了一种有效计算2m交叉阶乘的方法并以此闻名，Box则给出了3m的算法，Good在此基础上进行了总结并给出了一个漂亮的算法，它的一类应用就是计算傅里叶序列。有一类问题中需要把N维向量乘以一个可以分解为m阶系数矩阵的N×N的矩阵，其中m正比于logN，而Good的方法可以应用于这个问题，使该过程需要的计算数量正比于NlogN而不是N2。这里我们使用这类方法来算复数傅里叶级数。当数据点为复数时这类方法很有效。这里我们

2、用另外一种形式来表示这种算法，关键在于对N值的选择。同样可以发现，使用二进制电脑采用N=2m计算会有很大优势，只用一个存放傅里叶系数的N维序列就可以完成整个计算。首先考虑计算如下复数傅里叶序列：（1）Xj=k=0N-1Ak∙Wjk,j=0,1,…,N-1,这里的系数A(k)是复数，W是N阶单位根；（2）W=e2πi/N直接用（1）来计算需要N2次运算，注意：本文所指的运算指的是一次复数乘法后接复数加法。本文所接介绍的算法通过迭代计算给出的复数傅里叶幅值，所用运算次数少于2Nlog2N，所需空间则不超过原序列A。现

3、假设N是复数，比如N=r1∙r2，然后可将（1）中的指数表示为：（3）j=j1r1+j0,j0=0,1,…,r1-1,j1=0,1,…,r2-1,k=k1r2+k0,k0=0,1,…,r2-1,k1=0,1,…,r1-1,然后我们可以写出：（4）Xj1,j0=k0k1A(k1,k0)∙Wjk1r2Wjk0因为：（5）Wjk1r2=Wj0k1r2,所以里面基于k1的以j0和k0为变量的和可以重新定义为一个新的数组：（6）A1(j0,k0)=k1A(k1,k0)∙Wj0k1r2.5结果可以写作：（7）Xj1,j0=k

4、0A1j0,k0∙Wj1r1+j0k0.数组A1里有N个元素，每个元素需要r1次运算，也就是说总共需要Nr1次运算来获得A1。同理，经Nr2次运算操作可以计算A1的子数组X。因此，(6)(7)所示的两步算法总共需要：（8）T=N(r1+r2)次运算。很容易发现，通过连续地应用以上从(6)式开始的过程，一个m阶的算法需要：（9）T=N(r1+r2+⋯+rm)次运算操作，其中（10）N=r1∙r2⋯rm如果rj=sjtj，且sj，tj>1,那么sj+tj

5、尽可能多的因子可以得到(9)式的最小值，但是因子2可以成对地组合而且没有数据损失。若果我们能够选择N为高阶复数，我就能获得非常真实的增益。如果所有的rj都等于r，那么由(10)式我们可以得到：（11）logrN并且总的运算量是：（12）Tr=rNlogrN.如果N=rmsntp….，我们就有：TN=m∙r+n∙s+p∙t+∙∙∙∙∙∙∙∙,(13)log2N=m∙log2r+n∙log2s+p∙log2t+⋯，所以：TNlog2N是一个加权平均数：rlog2r,slog2s,tlog2t,….,其值如下5rrlo

6、g2r22.0031.8842.0052.1562.3172.4982.6792.82103.01.使用rj=3是、最有效的，但是它带来的超过2或者4的优势只有大约6%，而后者则有其他方面的优势。如果需要，rj可以高达10，这样会够增加不超过50%的计算量。因此，我们找到了N的高度约合值，只是任何大数的百分之几。但我们尽可能使用r=2或4，二进制数学为计算机带来很大的优势，无论是在地址还是计算上都更为经济。使用r=2的算法可以由下列指数序列形式表达：(14)j=jm-1∙2m-1+⋯+j1∙2+j0,k=km-1

7、∙2m-1+⋯+k1∙2+k0,其中jv和kv等于0或者1，也就是j和k代表的位置的二进制值。现在所有的数组都被写作其指数的函数。那么，式(1)可以写成：(15)Xjm-1,⋯,j0=k0k1⋯km-1A(km-1,⋯,k0)∙Wjkm-1∙2m-1+⋯+jk0其中的和是基于kv=0,1的，由于：(16)Wjkm-1∙2m-1=Wj0km-1∙2m-1(15)式中最里面的和数是基于km-1的，只取决于：j0,km-2,…,k0，可以写成：(17)A1j0,km-2,⋯,k0=km-1A(km-1,⋯,k0)∙Wj

8、0km-1∙2m-1继续向外求和，基于km-2等等，继续，使用：(18)Wj∙km-l∙2m-l=W(kl-1∙2l-1+⋯+j0)km-l∙2m-l可以得到如下连续数组：(19)5Alj0,⋯,jl-1,km-l-1,⋯,k0=km-lAl-1j0,⋯,jl-2,km-l,⋯,k0∙Wjl-1∙2l-1+⋯+j0∙km-l∙2m-l,l=1,2,⋯,m写出其和的形式那就