高速フーリエ変換を自前で作りたい (1) - フーリエ級数展開

木瓜丸です。

実は音楽関係のサービスを絶賛開発中で、少し波形を扱う関係上、自前で高速フーリエ変換(FFT)を実装することにしました。

そこで、備忘録がてら、そもそもフーリエ変換ってなんだっけ？というところから解説記事を書いてみようと思います。よかったら最後まで読んでみてください。

今回はフーリエ級数展開についてざっとまとめてみます。

関数の直行性

フーリエ変換のことについて調べているとよく 「関数の直行性」 という言葉が引っかかりますが、どういうことなんでしょうか。直行といえば、すぐさま直角を思い浮かべると思います。ということは、関数が直行する…つまり直角に交わるということでしょうか。

調べてみた所、どうやら違うっぽいです（すみません僕も完全には分かってないです）すごくわかりやすい解説をしている記事があったので、内容をお借りしたいと思います。

「直角」をベクトルを用いて表現すると、次のようになりますね。

\vec{a} \cdot \vec{b} = 0

では、関数を次のような無限次元のベクトルとして捉えてみるとどうでしょうか。

\vec{f(x)} = \left( \begin{array}{c} f(-\infty)\\ \vdots\\ f(-1.0)\\ \vdots\\ f(0)\\ \vdots\\ f(1.0)\\ \vdots\\ f(\infty)\\ \end{array} \right)

これも内積が0になったらベクトル同士が直行してそうですね。想像できんけど。

仮にこのベクトル同士の内積を出すとしたら、次のようになります。

\vec{f(x)} \cdot \vec{g(x)} = \sum_{-\infty}^{\infty} f(x)g(x) \Longleftrightarrow \int_{-\infty}^{\infty} f(x)g(x) dx

そんなわけで、関数同士の内積は関数の積の積分で表すことができるみたいです。（実際には関数空間というもっと~~ややこしい~~高尚な概念があり、そこから考えなきゃいけないっぽい）

さて、関数同士の内積がわかりましたが、これが0になるとき、直交しているということが言えそうです。図形的にはまったく想像がつきませんが、雰囲気で飲み込んでしまい、sinとcosの組み合わせについて直交性を検証してみましょう。

まずは $sin(nx) \cdot sin(mx)(n,m\in\mathbf{Z})$ の内積です。

\begin{align*} &\int_{-\pi}^{\pi} sin(nx)sin(mx) dx\\ &=\int_{-\pi}^{\pi} \frac{cos((m-n)x) - cos((m+n)x)}{2} dx\\ &=\left\{ \begin{array}{l} \frac{1}{2} \left[ \frac{sin((m-n)x)}{m-n} - \frac{sin((m+n)x)}{m+n} \right]_{-\pi}^{\pi} = \pi (m \neq n)\\ \frac{1}{2} \left[ x - \frac{sin((m+n)x)}{m+n} \right]_{-\pi}^{\pi} = 0 (m = n)\\ \end{array} \right\} \end{align*}

次に $cos(nx) \cdot cos(mx)(m,n\in\mathbf{Z})$ の内積です。

\begin{align*} &\int_{-\pi}^{\pi} cos(nx)cos(mx) dx\\ \\ &(i). m \neq nの時、\\ &(与式)=\int_{-\pi}^{\pi} \frac{cos((m+n)x) + cos((m-n)x)}{2} dx\\ &=- \frac{1}{2} \left[ \frac{sin((m+n)x)}{m+n} + \frac{sin((m-n)x)}{m-n} \right]_{-\pi}^{\pi} = 0\\ \\ &(ii). m = nの時、\\ &(与式)=\int_{-\pi}^{\pi} cos^{2}(mx) dx\\ &=\frac{1}{2} \int_{-\pi}^{\pi} 1 - cos(2mx) dx\\ &=\frac{1}{2} \left[x - \frac{\sin(2mx)}{2m}\right]_{-\pi}^{\pi} = \pi\\ \end{align*}

最後に $sin(nx) \cdot cos(mx)(m,n \in \mathbf{Z})$ の内積です。

\begin{align*} &\int_{-\pi}^{\pi} sin(nx)cos(mx) dx\\ \\ &(i). m \neq nの時、\\ &(与式)= \int_{-\pi}^{\pi} sin((m-n)x) + sin((m+n)x) dx\\ &= -\left[\frac{cos((m-n)x)}{m-n} + \frac{cos((m+n)x)}{m+n}\right]_{-\pi}^{\pi}\\ &=0\\ \\ &(ii). m = nの時、\\ &(与式)= \int_{-\pi}^{\pi} \frac{1}{2}sin(2mx) dx\\ &= \frac{1}{2}\left[-\frac{cos(2mx)}{2m}\right]_{-\pi}^{\pi}\\ &= 0 \end{align*}

これらから、三角関数ではsinとcos同士であれば常に直交することがわかりました。

フーリエ級数展開

一旦話は変わります。フーリエ変換といえば「周期関数はsinとかcosの和の関数で表現できるよ」とかまではなんとなく知ってるかもしれません。では、この足し方はどうやって導出するのか。それがフーリエ級数展開って技術です。

基底

まずは基底という概念を導入します。xy軸でおなじみの直交座標系を思い浮かべてください。例えば、 $A(2,3)$ という座標があります。この位置ベクトルは

\vec{a} = \left( \begin{array}{c} 2\\ 3\\ \end{array} \right)

と表しますね。これは次のように考えることもできます。

\vec{a} = 2 \left( \begin{array}{c} 1\\ 0\\ \end{array} \right) + 3\left( \begin{array}{c} 0\\ 1\\ \end{array} \right)

この場合、 $\left( \begin{array}{c} 1\\ 0\\ \end{array} \right)$ と $\left( \begin{array}{c} 0\\ 1\\ \end{array} \right)$ のことを基底ベクトルと言います。基底のとり方は一つではなく、n次元の空間の中で、次の条件を満たせばどんなn個のベクトルをとっても基底にすることができます。

すべてのベクトル同士が 直交する
すべてのベクトルが 単位ベクトルである

三角関数を基底にする

先程、三角関数が直交する条件を見つけましたね。中でもsinとcosは常に直交することがわかりました。なので、これをうまく使ってやれば三角関数を基底にした系を作ることができます。とりあえず、三角関数の無限次元のベクトルの大きさを出してみましょう。大きさは各成分の二乗和の平方根なので、積分しちゃいます。

\begin{align*} & \int_{-\pi}^{\pi} sin^{2}(x) dx\\ & = \int_{-\pi}^{\pi} \frac{1}{2} - \frac{cos(2x)}{2} dx\\ & = \left[\frac{1}{2}x - \frac{sin(2x)}{4}\right]_{-\pi}^{\pi}\\ & = \pi\\ \\ & \int_{-\pi}^{\pi} cos^{2}(x) dx\\ & = \int_{-\pi}^{\pi} \frac{cos(2x)}{2} + \frac{1}{2} dx\\ & = \left[\frac{sin(2x)}{4} + \frac{1}{2}x\right]_{-\pi}^{\pi}\\ & = \pi \end{align*}

二乗和は $\pi$ なので、大きさは $\sqrt{\pi}$ です。つまり、 $\frac{sin(x)}{\sqrt{\pi}}$ と $\frac{cos(x)}{\sqrt{\pi}}$ は基底に取ることができます。

…ということは？

周期関数を三角関数で表す

そう、無限次元のベクトルと捉えることで三角関数をベクトルみたいに扱ってきましたが、これはどの関数に対しても行えます。つまり、周期関数は三角関数で表せてしまいそうな気がします。やってみると次のような形になります。

f(x) = \frac{a_{0}}{2} + \sum_{n=1}^{\infty}(a_{n}cos(nx) + b_{n}sin(nx))

$a_{n}$ と $b_{n}$ をフーリエ係数と言います。なんとかしてこの係数を求めてやりましょう。 $f(x) \cdot cos(mx)$ を求めてみます。

\begin{align*} & f(x) \cdot cos(mx)\\ & = \int_{-\pi}^{\pi} f(x)cos(mx) dx\\ & = \frac{a_{0}}{2} \int_{-\pi}^{\pi} cos(mx) dx + \sum_{n=1}^{\infty}(a_{n}\int_{-\pi}^{\pi} cos(mx)cos(nx) + b_{n}\int_{-\pi}^{\pi} cos(mx)sin(nx)) \end{align*}

難しい式になってしまいましたが、先程導出した三角関数同士の直交性を考えるとかんたんになります。cos同士の内積は $m=n$ の場合は $\pi$ 、それ以外は0でした。また、sinとcosは常に直交します。よって、

= a_{m}\pi

これを $a_{m}$ について解くと、

a_{m} = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x)cos(mx) dx

$b_{m}$ についても、同じ要領で導出できます。

b_{m} = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x)sin(mx) dx

この公式を使うことで、任意の関数についてフーリエ係数を求めることができます。

まとめ

今回はフーリエ級数展開について、必要な知識と理屈をまとめてみました。

直交していて大きさが1の関数同士を基底にすることで、周期関数を三角関数だけで表現することができるということの解説と、公式の導出を行ってみました。

次回はここから発展させて フーリエ変換 についてまとめたいと思います。