第 3 章 離散 Fourier 変換 56
3.2 離散 Fourier 変換
ここからは N 次元ベクトルの変換の話で、無限和は登場せず、線形代数の話になる。
f =
f0 f1 ... fN−1
∈ CN に対して、離散 Fourier 係数の式Cn = 1 N
N∑−1 j=0
ω−njfj で定義される C =
C0 C1
... CN−1
∈CN を、f の離散 Fourier 変換と呼ぶ。また写像 CN ∋f 7→C ∈CN も離散 Fourier
変換と呼ぶ。これは線型写像であり、ある N 次正方行列をかけることで表現できる。その行列の性 質を詳しく述べよう。
線形代数では、ベクトルや行列の成分は 1から番号つける(行や列の番号は1から始める)のが普 通だが、ここでは 0から始めることにする。
またベクトルの一般の成分を表すのに第i成分、行列の一般の成分を表すのに(i, j)成分を指定す ることが多いが、i は虚数単位であるから、i の代わりに n を用いることにする。
命題 3.2.1 (離散Fourier変換の表現行列とその逆行列) N ∈N に対してω :=e2πi/N,
W := 1 N
ω0 ω0 ω0 · · · ω0 ω0 ω−1 ω−2 · · · ω−(N−1) ω0 ω−2 ω−4 · · · ω−2(N−1)
... ... ... . .. ... ω0 ω−(N−1) ω−(N−1)2 · · · ω−(N−1)(N−1)
,
とおくとき、
f =
f0 f1 ... fN−1
, C =
C0 C1 ... CN−1
に対して
(3.9) Cn= 1 N
N∑−1 j=0
fjω−nj (n = 0,1,· · · , N−1) ⇔ C =Wf (明らか).
W は正則で、
W−1 =
ω0 ω0 ω0 · · · ω0 ω0 ω1 ω2 · · · ωN−1 ω0 ω2 ω4 · · · ω2(N−1)
... ... ... . .. ... ω0 ωN−1 ω(N−1)2 · · · ω(N−1)(N−1)
.
すなわち Cn= 1
N
N∑−1 j=0
fjω−nj (n = 0,1,· · ·, N −1) ⇔ fj =
N−1
∑
n=0
ωjnCn (j = 0, . . . , N −1).
(添字の番号を 0 から始めるという約束のもとで、W の (n, j) 成分は 1
Nω−nj, W−1 の (j, n) 成 分はωjn である。)
証明 前半の (3.9)は行列の積の定義からすぐ分かる。
以下、この証明の最後まで、行列の添字は 0 から始める(N −1 までということになる) という ルールで記述する。
W の (n, j)成分は 1
Nω−nj である。
この W に、(j, k)成分が ωjk である行列 (ωjk) を右からかけた行列の(n, k) 成分は
N−1
∑
k=0
1
Nω−njωjk = 1 N
N−1
∑
k=0
ω(k−n)j = 1 N
{
N (k−n ≡0) 0 (それ以外) =
{
1 (k=n)
0 (それ以外) =δkn. これは積が単位行列であることを示す。すなわち W−1 =(
ωjk) .
余談 3.2.2 前節から続けて、関数 f の話をしている場合は、既に fj =
N∑−1 n=0
cnωnj であることは示 してあるので、絶対収束を仮定すれば、和の順序を交換して
fj =
N∑−1 n=0
∑
m≡n
cmωmj =
N∑−1 n=0
∑
m≡n
cmωnj =
N∑−1 n=0
ωnj ∑
m≡n
cm =
N−1
∑
n=0
ωnjCn
と出来て、これからW−1 の成分ωjn であると分かるが、W の性質は関数f とは関係ないので、こ の証明の方が良いであろう。
注意 3.2.3 (W をちょっと修正すると unitary 行列になる) U :=√
N W とおくと、
(3.10) U = 1
√N
(ω−nj)
, U−1 = 1
√NW−1 = 1
√N (ωnj)
となる。ω =ω−1 に注意すると、U の Hermite 共役U∗ は U∗ = 1
√N (
ω−jn )
= 1
√N (ωnj)
=U−1. すなわち U は unitary 行列である。
(以下は余談) 通常は Fourier級数展開は cn= 1
2π
∫ 2π
0
f(x)e−inx dx, f(x) =
∑∞ n=−∞
cneinx と定義されるが、
cn = 1
√2π
∫ 2π
0
f(x)e−inx dx, f(x) = 1
√2π
∑
n∈Z
cneinx と定義し直して(これは正規直交系{
√1 2πeinx
}で展開したことになる)、それに基づいて離散Fourier 係数を定めると、変換の行列として U が導かれる。
以上のように定義し直したい誘惑があるけれど、混乱する人が出て来ると思うのでやめておく。
次のように命題としてまとめておくことにする。
系 3.2.4 命題 3.2.1 の行列を W とするとき、U := √
N W = 1
√N (ω−nj) は、対称な unitary 行列である。
余談 3.2.5 (離散Fourier変換の応用上の強力さを別にしても、個人的に面白いと感じるところ) Fourier 級数展開
cn = 1 2π
∫ π
−π
f(x)e−inx dx, f(x) =
∑∞ n=−∞
cneinx と、Fourier 変換と反転公式 (Fourier変換を逆Fourier変換すると元に戻る)
f(ξ) =b 1
√2π
∫ ∞
−∞
f(x)e−ixξdx, f(x) = 1 2π
∫ ∞
−∞
fb(ξ)eixξdξ
の対応について既に話してあるが、離散 Fourier 変換とその反転公式 (離散Fourier変換を逆離散 Fourier 変換すると元に戻る)
Cn= 1 N
N∑−1 j=0
fjω−nj, fj =
N∑−1 n=0
Cnωnj
も良く対応している。むしろ、Fourier 級数よりもバランスの良い変換になっていて(f は周期関数 で {cn} は無限数列であるが、{fj} と {Cn}は周期数列になる)、むしろ Fourier変換に似ていると も言える。
実は Fourier 変換、逆 Fourier変換は、L2(R)における unitary変換というものになっている(ま すます似ていると感じる)。
f :=
f0 f1 f2 ... fN−1
, φn :=
ωn·0 ωn·1 ωn·2 ... ωn·(N−1)
とおくと、
f =
N∑−1 n=0
cnφn
これは、CN の直交系 {φn}による f の展開になっている。実際、
(φn,φm) =
N∑−1 j=0
ωnjωmj =
N−1
∑
j=0
ωnjω−mj =
N∑−1 j=0
ω(n−m)j = {
N (n=m) 0 (n̸=m)
であるから(これは補題3.1.2 の系にしておくべきかな)、{φn} は直交系である。そして、f =
∑N−1
n=0 Cnφn と展開したときの係数は、直交系による展開の係数の公式によれば Cn= (f,φn)
(φn,φn) =
∑N−1 j=0 fjωnj
N = 1
N
N∑−1 j=0
fjω−nj. なかなかきれいに出来ているものである。
定理 3.2.6 (離散Fourier変換に関するサンプリング定理) 周期T の関数 u:R→C が、有限 Fourier級数
u(t) =
∑M n=−M
cnein2πTt で表せるとき、すなわち u の Fourier 係数{cn} について
|n|> M ⇒ cn = 0
が成り立つとき、N >2M を満たす N に対して、N 項離散Fourier 係数{Cn}Nn=0−1 は、
Cn =cn (0≤n≤M), CN−n=c−n (1≤n≤M), (★)
Cn = 0 (M < n < N−M)
を満たす。(特に、全ての(0でない) Fourier係数{cn}Mn=−M は、離散Fourier係数 {Cn}Nn=0−1 か ら求まる。)
この定理を5章の定理5.0.2 (通常のサンプリング定理)と比べてみると良い。
例 3.2.7 M = 1, N = 10 の場合、
C0 =c0+c−10+c20+c−20+c30+· · ·=c0 + 0 + 0 +· · ·=c0, C1 =c1+c−9+c11+c−19+c21+· · ·=c1+ 0 + 0 +· · ·=c1,
C9 =c9+c−1+c19+c−11+c29+c−21+· · ·= 0 +c−1+ 0 + 0 +· · ·=c−1, C2 =c2+c−8+c12+c−18+· · ·= 0 + 0 +· · ·= 0,
C8 =c8+c−2+c18+c−12+· · ·= 0 + 0 +· · ·= 0, 同様にして 2≤n≤8に対して、 Cn = 0.
一方、M = 5, N = 10 の場合は
C0 =c0+c−10+c20+c−20+c30+· · ·=c0 + 0 + 0 +· · ·=c0, C1 =c1+c−9+c11+c−19+c21+· · ·=c1+ 0 + 0 +· · ·=c1,
C9 =c9+c−1+c19+c−11+c29+c−21+· · ·= 0 +c−1+ 0 + 0 +· · ·=c−1, C2 =c2+c−8+c12+c−18+· · ·= 0 + 0 +· · ·=c2,
C8 =c8+c−2+c18+c−12+· · ·= 0 + 0 +· · ·=c−2, ... ...
C4 =c4+c−6+c14+c−16+· · ·=c4 + 0 + 0 +· · ·=c4, C6 =c6+c−4+c16+c−14+· · ·= 0 +c−4+ 0 +· · ·=c−4, ここまでは調子が良い。ところが
C5 =c5+c−5+c15+c−15+· · ·=c5+c−5+ 0 + 0 +· · ·=c5+c−5. C5 =c5 も C5 =c−5 も成り立たない。
少し考えると、M = 5 であっても、N > 10 であれば、うまく行く ((★)が成り立つ) ことが分 かる。
落ち着いて考えると、N >2M であれば (★)が成り立つ。
証明 すでに示したように
Cn= ∑
m≡n
cm =cn+
∑∞ p=1
(cn+pN +cn−pN). 0≤n≤M であれば、
• n+pN ≥N >2M > M であるから、cn+pN = 0.
• n−pN ≤M −N <−M であるから、cn−pN = 0.
ゆえに Cn =cn.
残りも同様にして証明できる。