#おことわり
本記事は、あくまで自分の脳内の整理なので、数学的に厳密でない箇所（主に極限、微分、積分の交換に関すること）が多々あります。お願いしますたたくと痛いのでたたかないでください。
#フーリエ級数
$%$ 長さ$2\pi$の周期を持つ$C^1$級関数$f(x)$に対し、フーリエ級数は
f(x) = \dfrac{a_0}{2} + \sum^\infty_{n=1}(a_n\cos{n\pi x} + b_n\sin{n\pi x})
$%$で与えられます。ここで、$a_n$、$b_n$はそれぞれ、
\begin{align}
a_n &= \dfrac{1}{\pi}\int^\pi_{-\pi}dt\,f(t)\cos{n\pi t} &(n = 0, 1, 2, \cdots)\\
b_n &= \dfrac{1}{\pi}\int^\pi_{-\pi}dt\,f(t)\sin{n\pi t} &(n = 1, 2, \cdots)
\end{align}
$%$です。この関数の周期は$2\pi$に限らず任意の周期でも級数展開することができて、その周期を$T$とします。さらに、オイラーの公式$e^{ix} = \cos{x} + i\sin{x}$を用いて変形することで、
\begin{align}
f(x) &= \sum^{\infty}_{n = -\infty}c_n e^{i\frac{2\pi}{T}nx},& \\
c_n &= \dfrac{1}{T}\int^{T/2}_{-T/2}dt\,f(t)e^{-i\frac{2\pi}{T}nt} &(n \in \mathbb{Z})
\end{align}
$%$となります。これは複素フーリエ級数とよばれます。$c_n$の積分範囲は、長さが$T$であれば何でも良いです。
#フーリエ変換(連続編)
$%$ ここで、周期$T$を無限大にする極限をとってみましょう。周期が無限大ということは、$C^1$級非周期的関数に関してフーリエ級数を考察しよう、ということです。考えようとする極限を式に表すと、
f(x) = \lim_{T\rightarrow\infty}\dfrac{1}{T}\sum^{\infty}_{n = -\infty}e^{i\frac{2\pi}{T}nx}\int^{T/2}_{-T/2}dt\,f(t)e^{-i\frac{2\pi}{T}nt}
$%$です。次に、$1/T=\xi$とおきます。
f(x) = \lim_{\xi\rightarrow 0}\sum^{\infty}_{n = -\infty}\xi e^{2\pi in\xi x}\int^{1/2\xi}_{-1/2\xi}dt\,f(t)e^{-2\pi in\xi t}
$%$ここで、
G(n\xi) = e^{2\pi in\xi x}\int^{1/2\xi}_{-1/2\xi}dt\,f(t)e^{-2\pi in\xi t}
とおくと、
f(x) = \lim_{\xi\rightarrow 0}\sum^{\infty}_{n = -\infty}\xi G(n\xi)
$%$とおけますが、この級数において$\xi$を無限小にとると、和を積分に置き換えることができます。つまり、
f(x) = \int^{\infty}_{-\infty}d\xi G(\xi)
$%$と書き表すことができます。$\xi$を無限小にとっていることから、$G(\xi)$は、
G(\xi) = e^{2\pi i\xi x}\int^{\infty}_{-\infty}dt\,f(t)e^{-2\pi i\xi t}
です。まとめると、
f(x) = \int^{\infty}_{-\infty}d\xi \left\{\int^{\infty}_{-\infty}dt\,f(t)e^{-2\pi i\xi t}\right\}e^{2\pi i\xi x}
となります。ここで
F(\xi) = \int^{\infty}_{-\infty}dt\,f(t)e^{-2\pi i\xi t}
とおくと、
\begin{align*}
F(\xi) = \int^{\infty}_{-\infty}dt\,f(t)e^{-2\pi i\xi t} \\
f(t) = \int^{\infty}_{-\infty}d\xi\, F(\xi)e^{2\pi i\xi t}
\end{align*}
$%$となり、この、$f(t)$を$F(\xi)$にする変換をフーリエ変換、$F(\xi)$を$f(t)$にする変換を逆フーリエ変換といいます。これは周波数$(\xi)$領域での表現になっています。これを角周波数$\omega=2\pi\xi$の式に置き換えると、
\begin{align*}
F(\omega) &= \int^{\infty}_{-\infty}dt\,f(t)e^{-i\omega t} \\
f(t) &= \dfrac{1}{2\pi}\int^{\infty}_{-\infty}d\omega\, F(\omega)e^{i\omega t}
\end{align*}
$%$となります。$F(\omega)$と$f(t)$の積分の前の係数は、掛けて$1/2\pi$となっていれば何を選んでも良いです。他の係数でよく使うものは、
\begin{align*}
F(\omega) &= \dfrac{1}{\sqrt{2\pi}}\int^{\infty}_{-\infty}dt\,f(t)e^{-i\omega t} \\
f(t) &= \dfrac{1}{\sqrt{2\pi}}\int^{\infty}_{-\infty}d\omega\, F(\omega)e^{i\omega t}
\end{align*}
があります。
#フーリエ変換（離散編）
$%$ フーリエ級数およびフーリエ変換では、波および関数に、ある周波数成分がどれくらい含まれているかという情報を得ることができます。音声だったら音の高さ、光だったら色、などです。コンピュータは連続的な値を扱えないので、これらの情報の解析には、サンプリングしたデータに対して離散フーリエ変換を使います。ちなみに、この記事では、音声解析とか画像解析みたいな実用的な事柄は扱わないです。
$%$ 関数$f(t)$をサンプリング時間$T$の間隔でサンプリングすることを考えます。つまり、$n$番目のデータは$f(nT)$です。そして、サンプリング関数$f_T(t)$を
f_T(t) = \sum^\infty_{n=-\infty}f(nT)\delta(t-nT)
で定めます。ここで、$\delta(t)$は、デルタ関数（インパルス関数）で、
\begin{align}
\delta(t) = 0&(t \neq 0), \\
\int^\infty_{-\infty}dt\,\delta(t)f(t) &= f(0)
\end{align}
を満たす関数です。また、$f_T(t)$は、デルタ関数の性質から、
\begin{align}
f_T(t) &= \sum^\infty_{n=-\infty}f(t)\delta(t-nT) \\
&= f(t)\sum^\infty_{n=-\infty}\delta(t-nT)
\end{align}
$%$と表せます。ところで、これをフーリエ変換すると離散時間フーリエ変換が導けます。それは後で書きます。ここで、$f(nT)$が周期的、つまり、任意のnに対して$f(nT) = f(nT + NT)$なる
自然数$N$が存在するとします。このとき$f_T(t)$は周期$NT$の周期関数になることがわかります。
よって、$f_T(t)$を複素フーリエ級数展開したものを
f_T(t) = \sum^\infty_{n=-\infty}c_ne^{i\frac{2\pi}{NT}nt}
とおきます。ここで、$c_n$は、
c_n = \dfrac{1}{NT}\int^{NT-\delta}_{-\delta}dt\,f_T(t)e^{-i\frac{2\pi}{NT}nt}
$%$です。ここで、$\delta$は$T$に比べて十分小さな正の定数です。これは、$f_T(t)$の定義に立ち返ると、
\begin{align*}
c_n &= \dfrac{1}{NT}\int^{NT-\delta}_{-\delta}dt\,f(t)\sum^\infty_{m=-\infty}\delta(t-mT)e^{-i\frac{2\pi}{NT}nt} \\
&= \dfrac{1}{NT}\sum^\infty_{m=-\infty}\int^{NT-\delta}_{-\delta}dt\,f(t)\delta(t-mT)e^{-i\frac{2\pi}{NT}nt} \\
&= \dfrac{1}{NT}\sum^{N-1}_{m=0}f(mT)e^{-i\frac{2\pi}{N}nm} \\
\end{align*}
となります。よって、
f_T(t) = \dfrac{1}{NT}\sum^\infty_{n=-\infty}\sum^{N-1}_{m=0}f(mT)e^{-i\frac{2\pi}{N}nm}e^{i\frac{2\pi}{NT}nt}
$%$です。ふたたび$f_T(t)$の定義を思い出します。$f(nT)$を取り出すには、$(n-1)T<a<nT<b<(n+1)T$なる$a,b$を用いて
f(nT) = \int^b_a dt\, f_T(t)
$%$とするとよいことがわかります。ここで、$a=(n-1/2)T$、$b=(n+1/2)T$とします。これに$f_T(t)$の級数展開を代入して計算すると、
\begin{align}
f(nT) &= \int^{(n+1/2)T}_{(n-1/2)T} dt\, \dfrac{1}{NT}\sum^\infty_{k=-\infty}\sum^{N-1}_{m=0}f(mT)e^{-i\frac{2\pi}{N}km}e^{i\frac{2\pi}{NT}kt} \\
&= \dfrac{1}{NT}\sum^\infty_{k=-\infty}\sum^{N-1}_{m=0}f(mT)e^{-i\frac{2\pi}{N}km}\int^{(n+1/2)T}_{(n-1/2)T} dt\, e^{i\frac{2\pi}{NT}kt} \\
&= \dfrac{1}{NT}\sum^\infty_{k=-\infty}\sum^{N-1}_{m=0}f(mT)e^{-i\frac{2\pi}{N}km}\left[\dfrac{NT}{2\pi ik}e^{i\frac{2\pi}{NT}kt}\right]^{(n+1/2)T}_{(n-1/2)T} \\
&= \sum^\infty_{k=-\infty}\sum^{N-1}_{m=0}\dfrac{e^{i\frac{2\pi}{N}k(n+1/2)} - e^{i\frac{2\pi}{N}k(n-1/2)}}{2\pi ik}f(mT)e^{-i\frac{2\pi}{N}km} \\
&= \sum^\infty_{k=-\infty}\sum^{N-1}_{m=0}\dfrac{e^{i\frac{\pi}{N}k} - e^{-i\frac{\pi}{N}k}}{2\pi ik}f(mT)e^{-i\frac{2\pi}{N}km}e^{i\frac{2\pi}{N}kn} \\
&= \sum^\infty_{k=-\infty}\sum^{N-1}_{m=0}\dfrac{\sin{\frac{k\pi}{N}}}{k\pi}f(mT)e^{-i\frac{2\pi}{N}km}e^{i\frac{2\pi}{N}kn}
\end{align}
$%$ここで、$k = j + lN(0\le j\le N - 1, l\in \mathbb{Z})$とおきます。
$e^{i\frac{2\pi}{N}kn} = e^{i\frac{2\pi}{N}(j+lN)n} = e^{i\frac{2\pi}{N}jn}$、$\sin{\frac{k\pi}{N}} = \sin{\frac{(j+lN)\pi}{N}} = (-1)^l\sin{\frac{j\pi}{N}}$
などを利用して変形すると、
\begin{align}
f(nT) &= \sum^\infty_{l=-\infty}\sum^{N-1}_{j=0}\sum^{N-1}_{m=0}\dfrac{(-1)^l\sin{\frac{j\pi}{N}}}{(j+lN)\pi}f(mT)e^{-i\frac{2\pi}{N}jm}e^{i\frac{2\pi}{N}jn} \\
&= \dfrac{1}{N}\sum^{N-1}_{j=0}\sin{\frac{j\pi}{N}}\sum^\infty_{l=-\infty}\dfrac{(-1)^l}{(\frac{j}{N}+l)\pi}\sum^{N-1}_{m=0}f(mT)e^{-i\frac{2\pi}{N}jm}e^{i\frac{2\pi}{N}jn} \\
\end{align}
となります。ここで、無限和
\sum^\infty_{l=-\infty}\dfrac{(-1)^l}{\frac{j}{N}+l}
$%$を計算しましょう。$j=0$のところではこの無限和は発散してしまいますが、$f(nT)$としてはsinc関数の極限として収束するので$j\neq 0$とします。
ところで、$z$を整数でない複素数とするとき、複素関数
w_z(\xi) = \dfrac{1}{(\xi - z)\sin{\pi \xi}}
$%$は、$\xi\in\mathbb{Z}$と$\xi = z$で1位の極を持ちます。また、$|z|<M$を満たす整数$M$に対して、実数$R$を$M<R<M+1$となるようにとります。積分路$C$を半径$R$の円となるようにとって$w_z(\xi)$を積分します。留数定理から、
\begin{align*}
\int_C\dfrac{d\xi}{(\xi - z)\sin{\pi \xi}} &= 2\pi i\lim_{\xi\rightarrow z}\dfrac{1}{\sin{\pi \xi}} + 2\pi i\sum^M_{n=-M}\lim_{\xi\rightarrow n}\dfrac{(\xi - n)}{(\xi - z)\sin{\pi \xi}} \\
&= 2\pi i\dfrac{1}{\sin{\pi z}} + 2\pi i\sum^M_{n=-M}\dfrac{1}{\sin{\pi n} + \pi(n - z)\cos{\pi n}} \\
&= 2\pi i\dfrac{1}{\sin{\pi z}} + 2\pi i\sum^M_{n=-M}\dfrac{(-1)^n}{\pi(n - z)} \\
\end{align*}
となりますが、この左辺について$R\rightarrow\infty$の極限を取ってみると、
\begin{align}
\left|\int_C\dfrac{d\xi}{(\xi - z)\sin{\pi \xi}}\right| &= \left|\int^{2\pi}_0\dfrac{Rie^{i\theta}d\theta}{(Re^{i\theta} - z)\sin{\pi Re^{i\theta}}}\right| \\
&\le \int^{2\pi}_0\dfrac{Rd\theta}{|Re^{i\theta} - z||\sin{\pi Re^{i\theta}}|} \\
&= \int^{2\pi}_0\dfrac{2Rd\theta}{|Re^{i\theta} - z||e^{i\pi Re^{i\theta}} - e^{-i\pi Re^{i\theta}}|} \\
&\le \int^{2\pi}_0\dfrac{2Rd\theta}{(R - |z|)\left|e^{-\pi R\sin{\theta}} - e^{\pi R\sin{\theta}}\right|} \\
&\rightarrow 0
\end{align}
より、積分路を十分大きくとると0に収束します。結局、
\dfrac{1}{\sin{\pi z}} + \sum^\infty_{n=-\infty}\dfrac{(-1)^n}{\pi(n - z)} = 0
です。$z=-z$とすれば、
\sum^\infty_{n=-\infty}\dfrac{(-1)^n}{n + z} = \dfrac{\pi}{\sin{\pi z}}
となります。以上より、
\begin{align}
f(nT) &= \dfrac{1}{N}\sum^{N-1}_{k=0}\sum^{N-1}_{m=0}f(mT)e^{-i\frac{2\pi}{N}km}e^{i\frac{2\pi}{N}kn} \\
\end{align}
となります。ここで、
F[k] = \sum^{N-1}_{m=0}f(mT)e^{-i\frac{2\pi}{N}km}
$%$とします。これは$f(mT)$の離散フーリエ変換です。また、$f[m]=f(mT+kNT)(0\le m\le N-1, k\in \mathbb{Z})$とおくと、
F[k] = \sum^{N-1}_{m=0}f[m]e^{-i\frac{2\pi}{N}km} \\
f[n] = \dfrac{1}{N}\sum^{N-1}_{k=0}F[k]e^{i\frac{2\pi}{N}kn} \\
となり、それぞれ離散フーリエ変換、離散フーリエ逆変換です。
高速フーリエ変換までやる予定でしたが、重くなってきたので2につづきます。
###参考資料