高速フーリエ変換のテスト（矩形関数）

有限区間のフーリエ変換

$0\leq x \leq L$ の範囲で定義される実関数 f(x) を正規直交系を成す三角関数の和で表される指数関数を用いて、次の通りに展開することを考えます。

$f(x)=\sum\limits_{n=0}^{N-1} c_n\exp\left (i\,\frac { 2\pi n }{ L }\, x\right)$

展開係数 c_n は一般的に複素数です。展開係数 c_n は指数関数の完全性から、元の関数から一意に

$c_n= \frac{1}{N}\,\sum\limits_{m=0}^{N-1} f(x_m) \exp\left (-i\,\frac { 2\pi n }{ L }\, x_m\right)$

と与えられます。これはフーリエ級数展開と呼ばれ、もとの関数が空間分布であれば波数成分が、時間分布であれば周波数成分を取得することができます。展開係数 c_n の実部を虚部をそれぞれ a_n と b_n 表したとき、元の関数が偶関数の場合は a_n のみ値を持ち b_n=0 となり、反対に元の関数が奇関数の場合は b_n のみ値を持ち a_n=0 となります。また、 f(x) が実関数の場合には、

$a_{N-n} = a_n$
$b_{N-n} = -b_n$

が一般的に成り立ちます。なお、Nが∞の極限で元の関数を完全に再現しますが、数値計算の場合には必要となる計算精度に応じて与えます。この展開係数を高速に計算するのが高速フーリエ変換（FFT）です。また、展開係数から元の関数を計算するのは逆フーリエ変換と呼ばれ、ほとんど同じ計算で得ることができます。

高速フーリエ変換の例：矩形関数

$0\leq x \leq L$ の範囲で定義される実関数の例として矩形関数

$f(x)= \left\{ \matrix{ 1 & (\frac{L}{2}-\frac{w}{2}\leq x\leq\frac{L}{2}+\frac{w}{2}) \cr 0 & (x < \frac{L}{2}-\frac{w}{2}\,, \, \frac{L}{2}+\frac{w}{2} < x ) } \right.$

の展開係数を高速フーリエ変換を用いて計算します。は矩形の幅を表します。以下の結果はN=128の場合（２のべきである必要があります）です。元の関数が偶関数なので a_n のみ値を持っていることが確認できます。

展開係数

逆フーリエ変換

上記で計算した展開系数を用いて逆フーリエ変換を行って元の関数を再現した結果です。元の矩形関数をほぼ再現していることがわかります。