1、精選優(yōu)質(zhì)文檔-傾情為你奉上復(fù)數(shù)傅里葉級數(shù)的計算機算法Yates提出的計算2m 交叉階乘的有效方法已聞名，而Box將其推導(dǎo)至3m 的情況。Good總結(jié)了這些方法并且給出了一個可以用于計算傅里葉級數(shù)的漂亮算法。在他們完整的總結(jié)中，Good的方法可以應(yīng)用于解決用可被分解成m（m正比于N）個稀疏矩陣的N×N階矩陣乘以N維向量的這一類問題。結(jié)果是這個過程所需的計算數(shù)量正比于N2N而不是N2。這種方法下面用于計算復(fù)雜傅里葉級數(shù)。這方法的有用性體現(xiàn)在數(shù)據(jù)量是或可被選擇為高階復(fù)數(shù)時。這種算法在這篇文章里將被以相當不同的形式推出和呈現(xiàn)。特別是N的選取，使用N=2m 時二進制計算機的特殊優(yōu)勢將被體現(xiàn)，且

2、整個計算能在給定傅里葉系數(shù)的N維存儲空間內(nèi)進行?？紤]計算下式的傅里葉級數(shù)給定傅里葉系數(shù)A（k）是復(fù)數(shù)，W是N次主方根，直接使用（1）計算需要N2次計算（此時計算意味復(fù)數(shù)乘法與復(fù)數(shù)加法）。這里描述的算法在給定傅里葉復(fù)振幅組成的數(shù)組上重復(fù)并且結(jié)果是少于2N2N次計算和除所給數(shù)組A之外不再需要更多數(shù)據(jù)存儲空間。為推演這個算法，考慮合數(shù)N，例如N=r1·r2，那么（1）中的指數(shù)可以表達為然后可以寫出因為與k1的內(nèi)積只與j0 和k0有關(guān)，可以被定義為一個新數(shù)組，結(jié)果可寫成數(shù)組A1中有N個元素，每個需要做r1次計算，獲得A總共需要Nr1次計算。類似的，根據(jù)A1計算X需要Nr2次計算。所以，（6）

3、（7）這兩步算法共需要次計算。從它在（6）的應(yīng)用可以容易看出這個過程的成功，給出一個m級的算法要求次計算，其中如果rj=sjtj,且sjtj>1,那么sj+tj<rj除非sj=tj=2,其中sj+tj=rj?？傊褂帽M可能多的因子使（9）最小，但是因子2成對結(jié)合沒有損失。如果N可以選擇為高階復(fù)數(shù)，我們可以得到很好的增益。如果所有的r等于r,那么，從（10）我們得到和所有計算數(shù)是如果N=rmsntp那么我們發(fā)現(xiàn)因此是以下數(shù)的加權(quán)平均值這些數(shù)的值如下rj=3的使用理論上是最有效的，但是增益只有2和4的6%，而使用2和4有其他的優(yōu)勢。如果有必要，范圍至10的rj 的使用只會增加少于50%

4、的計算量。因此，我們可以發(fā)現(xiàn)N的“高階復(fù)數(shù)”值，滿足只是任何大數(shù)的百分之幾。如果可能，N=rm在r=2或4中的使用會為使用二進制計算的電腦在存儲和計算效率上提供很多優(yōu)勢。r=2的算法從由將指數(shù)寫成以下形式推出其中jv和kv等于0或1，且是j和k在二進制表示時對應(yīng)位上的內(nèi)容。所有矩陣可以被寫成他們指數(shù)的位運算。這樣（1）可以寫成kv等于0或1，因為（15）中最內(nèi)部的和基于km-1,只與j0,km-2,k0有關(guān)，可被寫成繼續(xù)到下一個基于km-2的最內(nèi)部的和并使用得到接下來的一系列數(shù)組其中l(wèi)=1,2,m和為根據(jù)指數(shù)守恒，它將被存儲在指數(shù)如下的位置(20)式表明，只有兩個指數(shù)位是0或者1的在2m-l比

5、特位的存儲單元被用于計算需要。因為(20)式所示的運算操作，只要借助j0,jl-2和k0,km-l-1的值，就能夠被同時完成，所以可以進行并行運算。在一些應(yīng)用中，我們可以很方便地使用(20)式,用Al-2的表達式來表示Al，也就是得到r=4時的等效表達式。通過將X中所示的下標在二進制意義上的反轉(zhuǎn)之后，我們就可以得到數(shù)組Am中的下標了。在一些應(yīng)用中，傅里葉和需要計算2次，以上的過程就能被程序化，所以位反轉(zhuǎn)就沒有必要了。例如，考慮以下差分方程的解：已有的方法可以用來計算方程解的傅里葉幅值解的傅里葉幅值是B(k)和A(k)數(shù)組的順序經(jīng)過位反轉(zhuǎn)，但是通過對(20)式的修改，我們可以由A(k)得到正確的下標。一個基于以上方法的用于計算三維傅里葉和的程序已經(jīng)編寫好并被用于IBM 7094。計算一個2a×2b×2c數(shù)