高校生がFFT(高速フーリエ変換)を理解してみた【第1回】単純なモデルを解いてなれる

#はじめに
とりあえず今回は連続フーリエ変換の形になれるために問題を1問解いてみます。
[【第0回】目次と概要](https://qiita.com/nekoMIMI_CatEye/items/d8fcb12132779cf4631c)
## 本記事の対象
高校3年生までの知識を持っている人
具体的には
* 三角関数(特に加法定理)
* 積分 (特に定積分)・積の積分公式
* 和記号
* 数列
* 平方完成

##問題を解こう。
【問題】下の式が最小になる$a_k$を求めよ.

```math
\int^{\pi}_{-\pi}\left(x-\sum^{n}_{k=1}a_{k}\sin kx \right)^2 dx　(a=\{a_1, a_2 ... a_{k}\})
```
この式は「$x$」と「$a_k \sin kx$の集まり」の差の「2乗」を集めたものです。
2乗すると, 出た誤差はすべて正の値として出てきます。
この値を最小にするということは、「$x$」を「$a_k \sin kx$の集まり」で近似してくださいね！
という意味になります。

いきなりなんで問題を解かないといけないの！？と思った方多いと思います。
詳しくは次回で書きますが、実は関数を周期関数($\sin$や$\cos$)の集まりで近似することがフーリエ変換の鍵(というかフーリエ変換そのもの)となっています。
今回は簡単なモデル(関数も近似する周期関数も単純なもの)を計算していこうと思います。

##とりあえず展開
2乗の部分を展開します

```math
= \int^{\pi}_{-\pi}\left[ x^2 - 2x \sum^{n}_{k=1}a_{k}\sin kx + \left(\sum^{n}_{k=1}a_{k}\sin kx \right)^2\right] dx
```
積分の中身が多項式なので分けます

```math
= \int^{\pi}_{-\pi} x^2 dx - \int^{\pi}_{-\pi}\left(2x \sum^{n}_{k=1}a_{k}\sin kx\right) dx + \int^{\pi}_{-\pi}\left(\sum^{n}_{k=1}a_{k}\sin kx \right)^2 dx
```
##1項目を計算
1項目の$\int^{\pi}_{-\pi} x^2$を計算します
これは$n$次式の積分の公式から導きます

```math
\begin{align}
\begin{array}{rcl}
\displaystyle \int^{\pi}_{-\pi} x^2 &=& \displaystyle \left[\frac{1}{3}x^3 \right]^{\pi}_{-\pi} \\
 &=& \displaystyle \frac{1}{3} \left[x^3 \right]^{\pi}_{-\pi} \\
 &=& \displaystyle \frac{1}{3} \left[\pi^3-(-\pi)^3 \right] \\
 &=& \displaystyle \frac{1}{3} \cdot 2\pi \\
 &=& \displaystyle \frac{2}{3}\pi \\
\end{array}
\end{align}
```

##2項目の変形
2項目の$-\int^{\pi}_{-\pi} 2x( \sum^{n} _{k=1} a_k \sin kx) dx$を変形します。
まず, 2を積分の外に, $x$を$\sum$の中に入れます

```math
= -2\int^{\pi}_{-\pi} \left(\sum^{n}_{k=1} a_kx \sin kx\right) dx
```
積分と和記号は入れ替えが可能です
***
【理由】
1. 和記号の中身を展開する
2. 多項式の積分になるため、積分を分けることができる
3. その後、和記号でまとめなおすと、あたかも和記号と積分記号が入れ替わったかのように見える
***
このことを利用して変形します

```math
= -2 \sum^{n}_{k=1}\left(\int^{\pi}_{-\pi} a_kx \sin kx\ dx\right)
```

-2を$\sum$の中に入れなおします

```math
= \sum^{n}_{k=1}\left(-2\int^{\pi}_{-\pi} a_kx \sin kx\ dx\right)
```

##3項目を変形
3項目の$-\int^{\pi}_{-\pi} ( \sum^{n} _{k=1} a_k \sin kx)^2 dx$を変形します。
まずは$\sum$を展開します。

```math
= \int^{\pi}_{-\pi}\left(a_{1}\sin x + a_{2}\sin 2x + ... + a_{n}\sin nx \right)^2 dx
```
けっこう複雑になりました。
このような表にすると多項式の展開がわかりやすいかと思います。
(逆にわかりにくいという人は飛ばして下さい.)

||$a_1\sin x$  |$a_2\sin 2x$  | ...  |<font color="red">$a_i\sin ix$</font> | ... |$a_n\sin nx$| 
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$a_1\sin x$|${a_1}^2\sin^2 x$|$a_2a_1\sin 2x \sin x$|**...**|$a_ia_1\sin ix \sin x$|**...**|$a_na_1\sin nx\sin x$|
|$a_2\sin 2x$|$a_2a_1\sin 2x \sin x$|${a_2}^2\sin^2 x$|**...**|$a_ia_2\sin ix \sin 2x$|**...**|$a_na_2\sin nx\sin 2x$|
|**...**|**...**|**...**|**...**|**...**|**...**|**...**|
|<font color="blue">$a_j\sin jx$</font>|$a_1a_j\sin x \sin jx$|$a_2a_j\sin 2x \sin jx$|**...**|<font color="green">$a_ia_j\sin ix \sin jx$</font>|**...**|$a_na_j\sin nx \sin jx$|
|**...**|**...**|**...**|**...**|**...**|**...**|**...**|
|$a_n\sin nx$|$a_1a_n\sin x \sin nx$|$a_2a_n\sin 2x \sin nx$|**...**|$a_ia_n\sin ix \sin nx$|**...**|${a_n}^2 \sin^2 nx$|

ここで計算した値をすべて加算すると展開後の値になります。
しかし, そのまますべて書き下すわけにはいかないため、何とかしてまとめたいところです。
ここで、表の中の色のついた部分に注目すると、下のようにまとめられることがわかります。

```math
= \int^{\pi}_{-\pi}\left( \sum^{n}_{i=1} \sum^{n}_{j=1} a_ia_j\sin ix\sin jx \right) dx
```
積分と和記号は交換可能なので交換します。

```math
= \sum^{n}_{i=1} \sum^{n}_{j=1}\left( \int^{\pi}_{-\pi}a_ia_j\sin ix\sin jxdx\right)
```
$a_i$, $a_j$は和記号の中では定数なので($x$の値によらないので)積分の外に出します。

```math
= \sum^{n}_{i=1} \sum^{n}_{j=1}\left( a_ia_j\int^{\pi}_{-\pi}\sin ix\sin jxdx\right)
```
##出てきた積分の式について
```math
\int^{\pi}_{-\pi}\sin ix\sin jx dx
```
3項目をまとめるには、この式のことがわかればよさそうです。
下の積和の公式を使って変形します。

```math
\sin \alpha x \sin \beta x = \frac{1}{2}\left[ \cos(\alpha-\beta) - \cos(\alpha+\beta) \right]
```
***
【積和の公式の証明】
$\cos$の加法定理から

```math
\begin{align}
\begin{array}{rcl}
\cos(\alpha+\beta) &=& \cos\alpha\cos\beta-\sin\alpha\sin\beta\\
\cos(\alpha-\beta) &=& \cos\alpha\cos(-\beta)-\sin\alpha\sin(-\beta)\\
&=& \cos\alpha\cos\beta+\sin\alpha\sin\beta\\
\end{array}
\end{align}
```
2つの式の差をとると

```math
\begin{align}
\begin{array}{rcl}
\cos(\alpha-\beta) - \cos(\alpha+\beta) &=& \cos\alpha\cos\beta+\sin\alpha\sin\beta - (\cos\alpha\cos\beta-\sin\alpha\sin\beta)\\
&=& \cos\alpha\cos\beta+\sin\alpha\sin\beta - \cos\alpha\cos\beta+\sin\alpha\sin\beta\\
 &=& 2\sin\alpha\sin\beta\\
\end{array}
\end{align}
```
両辺を半分にすると, 積和の公式が生まれます。
***
変形するとこのようになります。

```math
= \int^{\pi}_{-\pi}\frac{1}{2}\left[ \cos(i-j) - \cos(i+j) \right] dx
```
$\frac{1}{2}$を外に出します。

```math
= \frac{1}{2} \int^{\pi}_{-\pi}\left[ \cos(i-j) - \cos(i+j) \right] dx
```

多項式の積分なので分けます。

```math
= \frac{1}{2}\int^{\pi}_{-\pi}\cos(i-j) dx - \frac{1}{2} \int^{\pi}_{-\pi}\cos(i+j) dx
```

$i$, $j$ は$\sum$から来たものなので, 自然数です。この式は$i\neq j$のときと$i=j$のときで結果が異なります。

(i) もしも$i\neq j$なら (注: $n_1$, $n_2$は__整数__)

```math
\begin{align}
\begin{array}{rcl}
\displaystyle\frac{1}{2}\int^{\pi}_{-\pi}\cos(i-j) dx - \frac{1}{2} \int^{\pi}_{-\pi}\cos(i+j) dx &=& \displaystyle\frac{1}{2} \int^{\pi}_{-\pi}\cos n_1x dx - \frac{1}{2} \int^{\pi}_{-\pi}\cos n_2x dx\\\\
&=& \displaystyle\frac{1}{2} \left[n_1 \sin n_1x \right]^{\pi}_{-\pi} - \frac{1}{2} \left[n_2 \sin n_2x \right]^{\pi}_{-\pi}\\\\
&=& \displaystyle\frac{n_1}{2} \left[\sin n_1x \right]^{\pi}_{-\pi} - \frac{n_2}{2} \left[\sin n_2x \right]^{\pi}_{-\pi}\\\\
&=& \displaystyle\frac{n_1}{2} \left[\sin n_1\pi -\sin n_1 (-\pi)\right] - \frac{n_2}{2} \left[\sin n_2\pi -\sin n_2 (-\pi)\right]\\\\
&=& \displaystyle\frac{n_1}{2} \left[\sin n_1\pi -\sin (-n_1\pi)\right] - \frac{n_2}{2} \left[\sin n_2\pi -\sin (-n_2\pi)\right]\\\\
&=& \displaystyle\frac{n_1}{2} \left(0 -0\right) - \frac{n_2}{2} \left(0 -0\right) \cdots n_1, n_2が整数のため\\\\
&=& 0\\\\ 
\end{array}
\end{align}
```

(ii) もしも$i=j$なら (注: $n_3$は__整数__)

```math
\begin{align}
\begin{array}{rcl}
\displaystyle\frac{1}{2}\int^{\pi}_{-\pi}\cos(i-j) dx - \frac{1}{2} \int^{\pi}_{-\pi}\cos(i+j) dx &=& \displaystyle\frac{1}{2} \int^{\pi}_{-\pi}\cos 0 dx - \frac{1}{2} \int^{\pi}_{-\pi}\cos n_3x dx\\
&=& \displaystyle\frac{1}{2} \int^{\pi}_{-\pi}1 dx - \frac{1}{2} \int^{\pi}_{-\pi}\cos n_3x dx\\
&=& \displaystyle\frac{1}{2} \left[x\right]^{\pi}_{-\pi} - \frac{1}{2} \left[n_3 \sin n_3x \right]^{\pi}_{-\pi}\\
&=& \displaystyle\frac{1}{2} \left[x\right]^{\pi}_{-\pi} - \frac{n_3}{2} \left[ \sin n_3x\right]^{\pi}_{-\pi}\\
&=& \displaystyle\frac{1}{2} \left[\pi -(-\pi)\right] - \frac{n_3}{2} \left[\sin n_3\pi -\sin n_3 (-\pi)\right]\\
&=& \displaystyle\frac{1}{2} \left(\pi+\pi\right) - \frac{n_3}{2} \left[\sin n_3\pi -\sin (-n_3\pi)\right]\\
&=& \displaystyle\pi - \frac{n_3}{2} \left(0 -0\right) \cdots n_3が整数のため\\
&=& \pi
\end{array}
\end{align}
```

##3項目をまとめる
さて、積分の中身がわかりました。$i\neq j$のときに$0$、$i=j$のときに$\pi$でしたね。
ということで, $i=j(=k)$のときの項だけがのこるのでこのように変形できます。

```math
\begin{align}
\begin{array}{rcl}
\displaystyle \sum^{n}_{i=1} \sum^{n}_{j=1}\left( a_ia_j\int^{\pi}_{-\pi}\sin ix\sin jxdx\right) &=& \displaystyle \sum^{n}_{k=1}\left( a_k^2\int^{\pi}_{-\pi}\sin^2 kx dx\right)\\
&=& \displaystyle \sum^{n}_{k=1}a_k^2\pi\\
\end{array}
\end{align}
```

##変形後の式
さて、これですべての項をまとめることができました。
式をつなげ合わせると結局このような式になります。

```math
(元の式) = \frac{2}{3}\pi + \sum^{n}_{k=1}\left(-2\int^{\pi}_{-\pi} a_kx \sin kx\ dx\right) + \sum^{n}_{k=1}a_k^2\pi
```
2項目と3項目の両方についている$\sum$をまとめます。(2項目と3項目の順序を逆転してます。)

```math
= \frac{2}{3}\pi + \sum^{n}_{k=1}\left(a_k^2\pi-2\int^{\pi}_{-\pi} a_kx \sin kx\ dx\right)
```
$a_k$を積分の外に出します。

```math
= \frac{2}{3}\pi + \sum^{n}_{k=1}\left(a_k^2\pi-2a_k\int^{\pi}_{-\pi} x \sin kx\ dx\right)
```

積分の部分を$b_k$とおきます。数列表記にしているのは、積分の中身が$k$によって変化するためです。

```math
=\frac{2}{3}\pi + \sum^{n}_{k=1}\left(a_k^2\pi-2a_kb_k\right)\\
\left(b_k = \int^{\pi}_{-\pi} x \sin kx\ dx \right)
```

ここで$\sum$の中身を平方完成します。

```math
\begin{align}
\begin{array}{rcl}
\displaystyle \sum^{n}_{k=1}\left(a_k^2\pi-2a_kb_k\right) &=& \displaystyle \sum^{n}_{k=1}\pi\left(a_k^2-\frac{2}{\pi}a_kb_k\right)\\
&=& \displaystyle \sum^{n}_{k=1}\pi\left[\left(a_k-\frac{1}{\pi}b_k\right)^2 - \frac{1}{\pi^2}{b_k}^2 \right]\\ 
&=& \displaystyle \sum^{n}_{k=1}\left[\pi\left(a_k-\frac{1}{\pi}b_k\right)^2 - \pi \cdot \frac{1}{\pi}{b_k}^2\right]\\ 
&=& \displaystyle \sum^{n}_{k=1}\left[\pi\left(a_k-\frac{1}{\pi}b_k\right)^2 - \frac{1}{\pi}{b_k}^2\right]\\
&=& \displaystyle \sum^{n}_{k=1}\left[- \frac{1}{\pi}{b_k}^2 + \pi\left(a_k-\frac{1}{\pi}b_k\right)^2 \right]\cdots多項式の順序変更\\
\end{array}
\end{align}
```
$\sum$の中身が多項式なので分けることができます。

```math
= \sum^{n}_{k=1} - \frac{1}{\pi}{b_k}^2 + \sum^{n}_{k=1}\pi\left(a_k-\frac{1}{\pi}b_k\right)^2
```

1項目の$-\frac{1}{\pi}$と2項目の$\pi$を外に出します。

```math
= - \frac{1}{\pi}\sum^{n}_{k=1}{b_k}^2 + \pi\sum^{n}_{k=1}\left(a_k-\frac{1}{\pi}b_k\right)^2
```
よって, 全体的にはこのような式になります。

```math
=\frac{2}{3}\pi - \frac{1}{\pi}\sum^{n}_{k=1}{b_k}^2 + \pi\sum^{n}_{k=1}\left(a_k-\frac{1}{\pi}b_k\right)^2\\
```

##本題に戻ろう
問題の内容はこうでした。
【問題】下の式が最小になる$a_k$を求めよ.

```math
\int^{\pi}_{-\pi}\left(x-\sum^{n}_{k=1}a_{k}\sin kx \right)^2 dx　(a=\{a_1, a_2 ... a_{k}\})
```
問題の式はこのような式に変形できました。

```math
=\frac{2}{3}\pi - \frac{1}{\pi}\sum^{n}_{k=1}{b_k}^2 + \pi\sum^{n}_{k=1}\left(a_k-\frac{1}{\pi}b_k\right)^2\\
\left(b_k = \int^{\pi}_{-\pi} x \sin kx\ dx \right)
```

さて, 1,2項目は定数です。($b_k$は$k$によっては変化しますが, $a_k$が変化しても変化しません)
つまり、$a_k$を求めるには3項目を考えればよさそうです。
3項目の$\sum$を外すとこのようになります。

```math
\pi\sum^{n}_{k=1}\left(a_k-\frac{1}{\pi}b_k\right)^2 = \pi\left[\left(a_1-\frac{1}{\pi}b_1\right)^2 + \left(a_2-\frac{1}{\pi}b_2\right)^2 + \cdots + \left(a_n-\frac{1}{\pi}b_n\right)^2\right]\\
```
よって, 展開した各項を見てあげると最小にするための$a_k$は,このようになることがわかります。

```math
\begin{align}
\begin{array}{rcl}
\displaystyle a_k-\frac{1}{\pi}b_k &=& \displaystyle0\\
\displaystyle a_k &=& \displaystyle \frac{1}{\pi}b_k\\
\end{array}
\end{align}
```

$b_k$に戻ってきてもらうとこのようになります。

```math
a_k = \frac{1}{\pi}\int^{\pi}_{-\pi} x \sin kx\ dx \\
```

あと少しです。積の積分を使って答えを導きます。

```math
\begin{align}
\begin{array}{rcl}
\displaystyle a_k &=& \displaystyle \frac{1}{\pi}\int^{\pi}_{-\pi} x \sin kx\ dx \\
 &=& \displaystyle \frac{1}{\pi}\left \{ \left[x \int\sin kx\ dx \right]^{\pi}_{-\pi} + \int^{\pi}_{-\pi}\left(\frac{d}{dx}x \int\sin kx\ dx \right)dx \right\}\\
 &=& \displaystyle \frac{1}{\pi}\left\{ \left[x \left(-\frac{\cos kx}{k}\right) \right]^{\pi}_{-\pi} + \int^{\pi}_{-\pi}-\frac{\cos kx}{k}dx \right\}\\
 &=& \displaystyle \frac{1}{\pi}\left\{ \left[-x\frac{\cos kx}{k}\right]^{\pi}_{-\pi}-\int^{\pi}_{-\pi}\frac{\cos kx}{k}dx \right\}\\
 &=& \displaystyle \frac{1}{\pi}\left\{ \left[-\pi\frac{\cos k\pi}{k} - \pi\frac{\cos k(-\pi)}{k}\right] - \left[\frac{\sin kx}{k^2}\right]^{\pi}_{-\pi} \right\}\\
&=& \displaystyle \frac{1}{\pi}\left\{ \left[-\pi\frac{\cos k\pi}{k} - \pi\frac{\cos k(-\pi)}{k}\right] - \left[\frac{\sin k\pi}{k^2} - \frac{\sin k(-\pi)}{k^2}\right] \right\}\\
&=& \displaystyle \frac{1}{\pi}\left\{ \left[-\pi\frac{(-1)^k}{k} - \pi\frac{(-1)^k}{k}\right] - \left[\frac{0}{k^2} - \frac{0}{k^2}\right] \right\}\\
&=& \displaystyle \frac{1}{\pi}\left[-2\pi\frac{(-1)^k}{k}\right] \\
&=& \displaystyle -2\frac{(-1)^k}{k} \\
\end{array}
\end{align}
```

最小になる$a_k$が求められました。

```math
a_k = -2\frac{(-1)^k}{k} \\
```

##最後に
今回は一番単純なモデルで関数の近似をしました。第2～3回でこの式を一般化して、第3回ではフーリエ変換に足を踏み入れようと思います。
[【第2回】連続フーリエ変換の導入part1](https://qiita.com/nekoMIMI_CatEye/items/dbc0a90221dcd7c7cd73)