実離散フーリエ変換(中編)-離散三角関数の直交性-
前編：
実離散フーリエ変換(前編)-基底変換-
中編：ここ
後編：
実離散フーリエ変換(後編)-実離散フーリエ変換の証明-
中編では離散三角関数が直交系をなすことを示す。
言葉の定義
$N$を自然数、$n,\ m$を整数、$\tau=2\pi$を二倍円周率としたとき、
\begin{align}
C_m(n) = \cos(\dfrac{m}{N} n \tau)\\
S_m(n) = \sin(\dfrac{m}{N} n \tau)
\end{align}
をまとめて、$n$を変数とする周期$\dfrac{N}{m}$の離散三角関数と呼ぶことにする。
\begin{align}
\mathbf{c}_m
&=\begin{bmatrix}
C_m(0)\\ C_m(1)\\ \vdots \\ C_m(N-1)
\end{bmatrix}
=\begin{bmatrix}
1\\ \cos(\dfrac{m}{N}\tau)\\
\vdots \\ \cos\left( \dfrac{m}{N}(N-1)\tau \right)
\end{bmatrix}\\
\mathbf{s}_m
&=\begin{bmatrix}
S_m(0)\\ S_m(1)\\ \vdots \\ S_m(N-1)
\end{bmatrix}
=\begin{bmatrix}
0\\ \sin(\dfrac{m}{N}\tau)\\
\vdots \\ \sin\left( \dfrac{m}{N}(N-1)\tau \right)
\end{bmatrix}\\
E' &=\{\mathbf{e'}_n \mid n \in \mathbb{Z},\ 0 \leq n < N\}\\
\mathbf{e'}_n &=\begin{cases}
\mathbf{c}_0 & (n=0)\\
\mathbf{c}_k & (n=2k-1,\ 0< n< N,\ k \in \mathbb{N})\\
\mathbf{s}_k & (n=2k,\quad \quad 0< n< N,\ k \in \mathbb{N})\\
\end{cases}
\end{align}
とする。このとき、$N$個の$N$次ベクトルの集合$E'$を離散三角関数直交基底と呼ぶことにする。また、
\begin{align}
E &=\{\mathbf{e}_n \mid n \in \mathbb{Z},\ 0 \leq n < N\}\\
\mathbf{e'}_n &=\begin{cases}
\sqrt{\dfrac{1}{N}} \mathbf{c}_0 & (n=0)\\
\sqrt{\dfrac{1}{N}} \mathbf{c}_{N/2} & (n=N-1,\ N = 2k,\ \quad \quad \quad \ k \in \mathbb{N})\\
\sqrt{\dfrac{2}{N}} \mathbf{c}_k & (n=2k-1,\ 0< n< N-1,\ k \in \mathbb{N})\\
\sqrt{\dfrac{2}{N}} \mathbf{s}_k & (n=2k,\quad \quad 0< n< N,\quad \quad k \in \mathbb{N})\\
\end{cases}
\end{align}
を離散三角関数正規直交基底と呼ぶことにする。
定義1,2の名称は筆者独自のものです。
また、離散三角関数直交基底と離散三角関数正規直交基底がそれぞれ直交基底と正規直交基底になることはこれから証明します。
$N$が偶数のとき
\begin{align}
E'&= \{
\mathbf{c}_0,\
\mathbf{c}_1,\
\mathbf{s}_1,\
\cdots ,\
\mathbf{c}_{N/2-1},\
\mathbf{s}_{N/2-1},\
\mathbf{c}_{N/2} \}\\
E&= \left\{
\sqrt{\dfrac{1}{N}}\mathbf{c}_0,\
\sqrt{\dfrac{2}{N}}\mathbf{c}_1,\
\sqrt{\dfrac{2}{N}}\mathbf{s}_1,\
\cdots ,\
\sqrt{\dfrac{2}{N}}\mathbf{c}_{N/2-1},\
\sqrt{\dfrac{2}{N}}\mathbf{s}_{N/2-1},\
\sqrt{\dfrac{1}{N}}\mathbf{c}_{N/2} \right\}
\end{align}
$N$が奇数のとき
\begin{align} E'&= \{ \mathbf{c}_0,\ \mathbf{c}_1,\ \mathbf{s}_1,\ \cdots ,\ \mathbf{c}_{(N-1)/2},\ \mathbf{s}_{(N-1)/2}\}\\ E&= \left\{ \sqrt{\dfrac{1}{N}}\mathbf{c}_0,\ \sqrt{\dfrac{2}{N}}\mathbf{c}_1,\ \sqrt{\dfrac{2}{N}}\mathbf{s}_1,\ \cdots ,\ \sqrt{\dfrac{2}{N}}\mathbf{c}_{(N-1)/2},\ \sqrt{\dfrac{2}{N}}\mathbf{s}_{(N-1)/2} \right\} \end{align}
直交性の証明
$m$を$1\leq \abs{m}< N$となる整数とすると
\begin{align}
\sum_{n=0}^{N-1} \cos(\dfrac{m}{N} n \tau ) =
\sum_{n=0}^{N-1} \sin(\dfrac{m}{N} n \tau) =0
\end{align}
$0<\abs{\dfrac{m}{N}} < 1$より$\exp(i \dfrac{m}{N} \tau) \neq 1$となるから
\begin{align}
\sum_{n=0}^{N-1} \exp(i \dfrac{m}{N}n\tau)
&= \dfrac{1 - \exp(i \dfrac{1}{N}N\tau)}
{1 - \exp(i \dfrac{m}{N}\tau)}\\
&= \dfrac{1 - 1}{1 - \exp(i \dfrac{m}{N}\tau)}\\
&=0\\
\sum_{n=0}^{N-1} \cos(\dfrac{m}{N}n\tau)
&= \Re\left(\sum_{n=0}^{N-1}
\exp(i \dfrac{m}{N}n\tau)\right)\\
&=0\\
\sum_{n=0}^{N-1} \sin(\dfrac{m}{N}n\tau)
&= \Im\left(\sum_{n=0}^{N-1}
\exp(i \dfrac{m}{N}n\tau)\right)\\
&=0
\end{align}
せっかくなので複素数を用いない証明も考えてみます。
行列$A$を角度$\dfrac{m}{N}\tau$の2次元回転行列とする。
\begin{align}
A=\begin{bmatrix}
\cos(\dfrac{m}{N}\tau) & -\sin(\dfrac{m}{N}\tau)\\
\sin(\dfrac{m}{N}\tau) & \cos(\dfrac{m}{N}\tau)
\end{bmatrix}
\end{align}
行列を$n$回かけることは$\dfrac{m}{N}n\tau$回転することを意味するから
\begin{align}
A^n=\begin{bmatrix}
\cos(\dfrac{m}{N}n\tau) & -\sin(\dfrac{m}{N}n\tau)\\
\sin(\dfrac{m}{N}n\tau) & \cos(\dfrac{m}{N}n\tau)
\end{bmatrix}
\end{align}
(数学的帰納法によって示すこともできる。)
また、
\begin{align}
\det(I-A)
&=\left(1-\cos(\dfrac{m}{N}\tau)\right)^2
+\sin^2(\dfrac{m}{N}\tau)\\
&=1-2\cos(\dfrac{m}{N}\tau)+\cos^2(\dfrac{m}{N}n\tau)
+\sin^2(\dfrac{m}{N}\tau)\\
&=2-2\cos(\dfrac{m}{N}\tau)
\end{align}
$0<\abs{\dfrac{m}{N}} < 1$より$\cos(\dfrac{m}{N}\tau) \neq 1$となるから$\det(I-A) \neq 0$
つまり$(I-A)^{-1}$が存在する。よって、
\begin{align}
\sum_{n=0}^{N-1} A^n
&= (1-A^N)(1 - A)^{-1}\\
&=\begin{bmatrix}
1-\cos(n\tau) & -\sin(n\tau)\\
\sin(n\tau) & 1-\cos(n\tau)
\end{bmatrix}(1 - A)^{-1}\\
&=\begin{bmatrix}
1-1 & 0\\
0 & 1-1
\end{bmatrix}(1 - A)^{-1}\\
&=\begin{bmatrix}
0 & 0\\
0 & 0
\end{bmatrix}\\
\sum_{n=0}^{N-1} A^n
&=
\begin{bmatrix}
\displaystyle{
\sum_{n=0}^{N-1} \cos(\dfrac{m}{N}n\tau) }
& \displaystyle{
-\sum_{n=0}^{N-1} \sin(\dfrac{m}{N}n\tau)}\\
\displaystyle{
\sum_{n=0}^{N-1} \sin(\dfrac{m}{N}n\tau) }
& \displaystyle{
\sum_{n=0}^{N-1} \cos(\dfrac{m}{N}n\tau)}
\end{bmatrix}\\
\end{align}
したがって、
\begin{align}
\sum_{n=0}^{N-1} \cos(\dfrac{m}{N} n \tau ) =
\sum_{n=0}^{N-1} \sin(\dfrac{m}{N} n \tau) =0
\end{align}
次は行列も複素数も用いない証明です。
まずコサインの総和を示す。
積和の公式
\begin{align}
\cos\alpha \sin\beta
&= \frac{1}{2}(
\sin(\alpha+\beta) - \sin(\alpha-\beta))
\end{align}
より、
$\theta=\dfrac{m}{N}\tau,\
\alpha=n\theta,\
\beta=\dfrac{\theta}{2},\
I_n=\cos(n \theta) \sin(\dfrac{\theta}{2})$とすると、
\begin{align}
I_n
&=\cos(n \theta) \sin(\dfrac{\theta}{2})\\
&= \frac{1}{2}\left(
\sin\left( n\theta+\frac{\theta}{2} \right)
- \sin\left( n\theta-\frac{\theta}{2} \right)
\right)\\
\end{align}
よって、
\begin{align}
2\sum_{n=0}^{N-1} I_n
&= \sum_{n=0}^{N-1}
\left(
\sin\left( n\theta+\frac{\theta}{2} \right)
- \sin\left( n\theta-\frac{\theta}{2} \right)
\right)\\
&=-\sin(-\frac{\theta}{2})
+ \sum_{n=1}^{N-1}
\left(
\sin\left( (n-1)\theta+\frac{\theta}{2} \right)
- \sin\left( n\theta-\frac{\theta}{2} \right)
\right)\\
&\quad\
+ \sin( \left( N-1 \right) \theta+\frac{\theta}{2})
\\
&= \sin( N\theta-\frac{\theta}{2})
+ \sin(\frac{\theta}{2})\\
&= \sin( N\dfrac{m}{N}\tau-\frac{\theta}{2})
+ \sin(\frac{\theta}{2})\\
&= -\sin(\frac{\theta}{2})
+ \sin(\frac{\theta}{2})\\
&=0
\end{align}
一方で
\begin{align}
\sum_{n=0}^{N-1} I_n
&=\sin(\dfrac{\theta}{2})
\sum_{n=0}^{N-1} \cos(n \theta)\\
\end{align}
仮定$1\leq \abs{m}< N$より$0<
\abs{\dfrac{\theta}{2}} = \abs{\dfrac{m}{2N}\tau}
< \dfrac{\tau}{2}$となるから$\sin(\dfrac{\theta}{2}) \neq 0$
よって、
\begin{align}
\sum_{n=0}^{N-1} \cos(n \theta)
=\sum_{n=0}^{N-1} \cos(\dfrac{m}{N}n\tau)
=0
\end{align}
次にサインの総和を示す。
積和の公式
\begin{align}
\sin\alpha \sin\beta
&= \frac{1}{2}(
-\cos(\alpha+\beta) + \cos(\alpha-\beta))
\end{align}
より、
$\theta=\dfrac{m}{N}\tau,\
\alpha=n\theta,\
\beta=\dfrac{\theta}{2},\
J_n=\sin(n\theta) \sin(\dfrac{\theta}{2})$とすると、
\begin{align}
J_n
&=\sin(n \theta) \sin(\dfrac{\theta}{2})\\
&= \frac{1}{2}\left(
-\cos\left( n\theta+\frac{\theta}{2} \right)
+\cos\left( n\theta-\frac{\theta}{2} \right)
\right)\\
\end{align}
よって、
\begin{align}
2\sum_{n=0}^{N-1} J_n
&= \sum_{n=0}^{N-1}
\left(
-\cos\left( n\theta+\frac{\theta}{2} \right)
+ \cos\left( n\theta-\frac{\theta}{2} \right)
\right)\\
&=\cos(-\frac{\theta}{2})
+ \sum_{n=1}^{N-1}
\left(
\cos\left( (n-1)\theta+\frac{\theta}{2} \right)
- \cos\left( n\theta-\frac{\theta}{2} \right)
\right)\\
&\quad\
- \cos( \left( N-1 \right) \theta+\frac{\theta}{2})
\\
&= \cos(\frac{\theta}{2}) - \cos( N\theta-\frac{\theta}{2})\\
&= \cos(\frac{\theta}{2}) - \cos( N\dfrac{m}{N}\tau-\frac{\theta}{2})\\
&= \cos(\frac{\theta}{2})
- \cos(\frac{\theta}{2})\\
&=0
\end{align}
一方で
\begin{align}
\sum_{n=0}^{N-1} J_n
&=\sin(\dfrac{\theta}{2})
\sum_{n=0}^{N-1} \sin(n \theta)\\
\end{align}
仮定$1\leq \abs{m}< N$より$0<
\abs{\dfrac{\theta}{2}} = \abs{\dfrac{m}{2N}\tau}
< \dfrac{\tau}{2}$となるから$\sin(\dfrac{\theta}{2}) \neq 0$
よって、
\begin{align}
\sum_{n=0}^{N-1} \sin(n \theta)
=\sum_{n=0}^{N-1} \sin(\dfrac{m}{N}n\tau)
=0
\end{align}
離散三角関数直交基底$E'$は直交系となる。
また、離散三角関数正規直交基底$E$は正規直交系となる。
- $\cos$どうしの内積
$j,k$を$0\leq j,k \leq \dfrac{N}{2}$となる整数とする。
\begin{align} \mathbf{c}_j \cdot \mathbf{c}_k &= \sum_{n=0}^{N-1} \cos(\dfrac{j}{N}n\tau) \cos(\dfrac{k}{N}n\tau)\\ &= \sum_{n=0}^{N-1}\dfrac{1}{2}\left( \cos\left(\dfrac{j+k}{N}n\tau \right) + \cos\left(\dfrac{j-k}{N}n\tau \right) \right) \end{align}- $j \neq k$のとき
$1 \leq \abs{j+k} \leq N-2,\quad 1 \leq\abs{j-k} \leq \dfrac{N-1}{2}$より前編の補題3から
\begin{align} \mathbf{c}_j \cdot \mathbf{c}_k &= 0 \end{align} - $j = k$のとき
$j-k=0$より
\begin{align} \mathbf{c}_j \cdot \mathbf{c}_k &= \sum_{n=0}^{N-1}\dfrac{1}{2}\left( \cos\left(\dfrac{j+k}{N}n\tau \right) + \cos0 \right)\\ &= \dfrac{N}{2} + \sum_{n=0}^{N-1}\dfrac{1}{2} \cos\left( \dfrac{j+k}{N}n\tau \right) \\ \end{align}- $j = k = 0$のとき
$j+k=0$より
\begin{align} \mathbf{c}_j \cdot \mathbf{c}_k = \dfrac{N}{2} + \sum_{n=0}^{N-1}\dfrac{1}{2} \cos0 =N \end{align} - $0<j = k< \frac{N}{2}$のとき
$0< \abs{j+k} < N$より補題3から
\begin{align} \mathbf{c}_j \cdot \mathbf{c}_k =\dfrac{N}{2} \end{align} - $j = k = \frac{N}{2}$のとき
$j + k = N$より
\begin{align} \mathbf{c}_j \cdot \mathbf{c}_k = \dfrac{N}{2}+ \sum_{n=0}^{N-1}\dfrac{1}{2} \cos(n\tau) = N \end{align}
- $j = k = 0$のとき
- $j \neq k$のとき
- $\sin$どうしの内積
$j,k$を$1\leq j,k \leq \dfrac{N-1}{2}$となる整数とする。
\begin{align} \mathbf{s}_j \cdot \mathbf{s}_k &= \sum_{n=0}^{N-1} \sin(\dfrac{j}{N}n\tau) \sin(\dfrac{k}{N}n\tau)\\ &= -\sum_{n=0}^{N-1}\dfrac{1}{2}\left( \cos\left(\dfrac{j+k}{N}n\tau \right) - \cos\left(\dfrac{j-k}{N}n\tau \right) \right) \end{align}- $j \neq k$のとき
$1 \leq \abs{j+k} \leq N-2,\quad 1 \leq\abs{j-k} \leq \dfrac{N-1}{2}-1$より補題3から
$\mathbf{s}_j \cdot \mathbf{s}_k = 0$ - $j = k$のとき
$2 \leq \abs{j+k} \leq N-1,\quad j-k=0$より補題3から
\begin{align} \mathbf{s}_j \cdot \mathbf{s}_k = -\sum_{n=0}^{N-1}\dfrac{1}{2} (-\cos0) =\dfrac{N}{2} \end{align}
- $j \neq k$のとき
- $\cos$と$\sin$の内積
$j$を$0\leq j \leq \dfrac{N}{2}$、$k$を$1\leq k \leq \dfrac{N-1}{2}$となる整数とする。
\begin{align} \mathbf{c}_j \cdot \mathbf{s}_k &= \sum_{n=0}^{N-1} \cos(\dfrac{j}{N}n\tau) \sin(\dfrac{k}{N}n\tau)\\ &= \sum_{n=0}^{N-1}\dfrac{1}{2}\left( \sin\left(\dfrac{j+k}{N}n\tau \right) - \sin\left(\dfrac{j-k}{N}n\tau \right) \right)\\ \end{align}- $j \neq k$のとき
$1 \leq \abs{j+k} \leq N-\dfrac{1}{2},\quad 1 \leq\abs{j-k} \leq \dfrac{N}{2}$より補題3から
\begin{align} \mathbf{c}_j \cdot \mathbf{s}_k = 0 \end{align} - $j = k$のとき
$1 \leq \abs{j+k} \leq N-1,\quad j-k=0$より補題3から
\begin{align} \mathbf{c}_j \cdot \mathbf{s}_k = \sum_{n=0}^{N-1}\dfrac{1}{2} \sin0 =0 \end{align}
内積は可換であるため、$\mathbf{s}_j \cdot \mathbf{c}_k=\mathbf{c}_k \cdot \mathbf{s}_j=0$
- $j \neq k$のとき
- まとめ
- $j$を$0\leq j \leq \dfrac{N}{2}$、$k$を$0\leq k \leq \dfrac{N}{2}$となる整数とすると
\begin{align} \mathbf{c}_j \cdot \mathbf{c}_k =\begin{cases} 0 & (j \neq k)\\ N & (j=k=0,\ j=k=\dfrac{N}{2})\\ \dfrac{N}{2} & (0< j=k<\dfrac{N}{2})\\ \end{cases} \end{align} - $j$を$1\leq j \leq \dfrac{N-1}{2}$、$k$を$1\leq k \leq \dfrac{N-1}{2}$となる整数とすると
\begin{align} \mathbf{s}_j \cdot \mathbf{s}_k =\begin{cases} 0 & (j \neq k)\\ \dfrac{N}{2} & (j=k=0)\\ \end{cases} \end{align} - $j$を$0\leq j \leq \dfrac{N}{2}$、$k$を$1\leq k \leq \dfrac{N-1}{2}$となる整数とすると
\begin{align} \mathbf{c}_j \cdot \mathbf{s}_k = 0 \end{align}
- $j$を$0\leq j \leq \dfrac{N}{2}$、$k$を$0\leq k \leq \dfrac{N}{2}$となる整数とすると
$N$が奇数の時
\begin{align}
E'= \{
\mathbf{c}_0,\
\mathbf{c}_1,\
\mathbf{s}_1,\
\cdots ,\
\mathbf{c}_{(N-1)/2},\
\mathbf{s}_{(N-1)/2}\}
\end{align}
はそれぞれ自身以外との内積が0となるため直交系となる。
$N$が偶数の時
\begin{align}
E'= \{
\mathbf{c}_0,\
\mathbf{c}_1,\
\mathbf{s}_1,\
\cdots ,\
\mathbf{c}_{N/2-1},\
\mathbf{s}_{N/2-1},\
\mathbf{c}_{N/2} \}
\end{align}
はそれぞれ自身以外との内積が0となるため直交系となる。
つまり$E'$ は直交系となる。
また、$E$ はそれに加えて各ノルムが$1$となるため正規直交系となる。
$E'$は直交基底である。
また、$E$は正規直交基底である。
命題2より$E'$は直交系であり、$E$は正規直交系である。
また前編の命題7「$N$個の$N$次ベクトルは互いに直交するなら$N$次ベクトル空間の基底になる。」より、$E'$は直交系かつ基底であり、$E$は正規直交系かつ基底である。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
