離散 Fourier 変換

C0 =∑

m≡0

cm =c0 +cN +c₋N +c2N +c₋2N +· · · , C₁ =∑

m≡1

c_m =c₁ +c_1−N +c_1+N +c_1−2N +c_1+2N +· · · , C₋₁ = ∑

m≡−1

c_m =c₋₁+c_−1+N +c_−1−N +c_−1+2N +c_−1−2N +· · · , C2 =∑

m≡2

cm =c2 +c2−N +c2+N +c2−2N +c2+2N +· · · , C₋₂ = ∑

m≡−2

c_m =c₋₂+c_−2+N +c_−2−N +c_−2+2N +c_−2−2N +· · · , ...

あるいは

C_n =c_n+

∑∞ p=1

(c_n+pN +c_n−pN). 次の問を考えよう。

Q Cn は cn の良い近似になっているか？

(もともと c_n の近似値を求めようとして、その定義式の積分を、台形則という数値積分公式で近似 したものが C_n であるわけだが、本当に C_n が c_n に近いかは、確かめる必要がある。)

A ある意味で Yes である。正確には、

任意のn ∈Z を固定するとき、

Nlim→∞C_n =c_n.

注意: h,x_j,f_j,ω,C_nは、N に依存していることに注意せよ。本来は、それぞれh_N,x_j,N, f_j,N,ω_N, C_n,N とでも書くべきものである。そうすると上の式は lim

N→∞C_n,N =c_n である。すなわち、ε-N で 表せば

(∀n∈N)(∀ε >0)(∃n^′ ∈N)(∀N ∈N:N ≥n^′) |C_n,N−c_n|< ε.

次に考えてもらいたいのは、

Q C_−1,N =C_N−1,N =c₋₁+c_−1+N +c_−1−N +c_−1+2N +c_−1−2N +· · · であるわけだが、これは c₋₁, c_N−1, いずれの近似か？

A C_N−1 は c₋₁ の近似になっているが、c_N−1 の近似ではない。

Nlim→∞(c_−1+N +c_−1−N +c_−1+2N +c_−1−2N +· · ·) = 0 であるから、確かに lim

N→∞C_−1,N =c₋₁.

結局、C_n (|n| ≪ N/2) は c_n の近似である、とまとめられるであろう。|n|≒ N/2 のときは、精 度はかなり悪くなる。

f =





 f₀ f₁ ... f_N−1





 ∈ C^N に対して、離散 Fourier 係数の式Cn = 1 N

N∑−1 j=0

ω^−njfj で定義される C =





 C₀ C1

... C_N−1





∈C^N を、f の離散 Fourier 変換と呼ぶ。また写像 C^N ∋f 7→C ∈C^N も離散 Fourier

変換と呼ぶ。これは線型写像であり、ある N 次正方行列をかけることで表現できる。その行列の性 質を詳しく述べよう。

線形代数では、ベクトルや行列の成分は 1から番号つける(行や列の番号は1から始める)のが普 通だが、ここでは 0から始めることにする。

またベクトルの一般の成分を表すのに第i成分、行列の一般の成分を表すのに(i, j)成分を指定す ることが多いが、i は虚数単位であるから、i の代わりに n を用いることにする。

命題 3.2.1 (離散Fourier変換の表現行列とその逆行列) N ∈N に対してω :=e^2πi/N,

W := 1 N











ω⁰ ω⁰ ω⁰ · · · ω⁰ ω⁰ ω⁻¹ ω⁻² · · · ω^−(N−1) ω⁰ ω⁻² ω⁻⁴ · · · ω^−2(N−1)

... ... ... . .. ... ω⁰ ω^−(N−1) ω^−(N−1)2 · · · ω^{−(N−1)(N−1)}









 ,

とおくとき、

f =





 f₀ f₁ ... fN−1





, C =





 C₀ C₁ ... CN−1







に対して

(3.7) C_n= 1 N

N∑−1 j=0

f_jω^−nj (n = 0,1,· · · , N−1) ⇔ C =Wf (明らか).

W は正則で、

W⁻¹ =











ω⁰ ω⁰ ω⁰ · · · ω⁰ ω⁰ ω¹ ω² · · · ω^N−1 ω⁰ ω² ω⁴ · · · ω^2(N−1)

... ... ... . .. ... ω⁰ ω^N−1 ω^(N−1)2 · · · ω^{(N−1)(N−1)}









 .

すなわち C_n= 1

N

N∑−1 j=0

f_jω^−nj (n = 0,1,· · ·, N −1) ⇔ f_j =

N−1

∑

n=0

ω^jnC_n (j = 0, . . . , N −1).

(添字の番号を 0 から始めるという約束のもとで、W の (n, j) 成分は 1

Nω^−nj, W⁻¹ の (j, n) 成 分はω^jn である。)

証明 前半の (3.7)は行列の積の定義からすぐ分かる。

以下、この証明の最後まで、行列の添字は 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⁻¹ =(

ω^jk) .

余談 3.2.1 前節から続けて、関数 f の話をしている場合は、既に fj =

N∑−1 n=0

cnω^nj であることは示 してあるので、絶対収束を仮定すれば、和の順序を交換して

f_j =

N∑−1 n=0

∑

m≡n

c_mω^mj =

N∑−1 n=0

∑

m≡n

c_mω^nj =

N∑−1 n=0

ω^nj ∑

m≡n

c_m =

N−1

∑

n=0

ω^njC_n

と出来て、これからW⁻¹ の成分ω^jn であると分かるが、W の性質は関数f とは関係ないので、こ の証明の方が良いであろう。

注意 3.2.2 (W をちょっと修正すると unitary 行列になる) U :=√

N W とおくと、

(3.8) U = 1

√N

(ω^−nj)

, U⁻¹ = 1

√NW⁻¹ = 1

√N (ω^nj)

となる。ω =ω⁻¹ に注意すると、U の Hermite 共役U^∗ は U^∗ = 1

√N (

ω^−jn )

= 1

√N (ω^nj)

=U⁻¹. すなわち U は unitary 行列である。

(以下は余談) 通常は Fourier級数展開は c_n= 1

2π

∫ 2π 0

f(x)e^−inx dx, f(x) =

∑∞ n=−∞

c_ne^inx と定義されるが、

c_n = 1

√2π

∫ _2π

0

f(x)e^−inx dx, f(x) = 1

√2π

∑

n∈Z

c_ne^inx と定義し直して(これは正規直交系{

√1 2πe^inx

}で展開したことになる)、それに基づいて離散Fourier 係数を定めると、変換の行列として U が導かれる。

以上のように定義し直したい誘惑があるけれど、混乱する人が出て来ると思うのでやめておく。

次のように命題としてまとめておくことにする。

系 3.2.3 命題 3.2.1 の行列を W とするとき、U := √

N W = 1

√N (ω^−nj) は、対称な unitary 行列である。

余談 3.2.2 (離散Fourier変換の応用上の強力さを別にしても、個人的に面白いと感じるところ) Fourier 級数展開

c_n = 1 2π

∫ π

−π

f(x)e^−inx dx, f(x) =

∑∞ n=−∞

c_ne^inx と、Fourier 変換と反転公式 (Fourier変換を逆Fourier変換すると元に戻る)

f(ξ) =b 1

√2π

∫ _∞

−∞

f(x)e^−ixξdx, f(x) = 1 2π

∫ _∞

−∞

fb(ξ)e^ixξdξ

の対応について既に話してあるが、離散 Fourier 変換とその反転公式 (離散Fourier変換を逆離散 Fourier 変換すると元に戻る)

C_n= 1 N

N∑−1 j=0

f_jω^−nj, f_j =

N∑−1 n=0

C_nω^nj

も良く対応している。むしろ、Fourier 級数よりもバランスの良い変換になっていて(f は周期関数 で {c_n} は無限数列であるが、{f_j} と {C_n}は周期数列になる)、むしろ Fourier変換に似ていると も言える。

実は Fourier 変換、逆 Fourier変換は、L²(R)における unitary変換というものになっている(ま すます似ていると感じる)。

f :=









 f₀ f₁ f₂ ... f_N−1











, φ_n :=









 ω^n·0 ω^n·1 ω^n·2 ... ω^n·(N−1)











とおくと、

f =

N∑−1 n=0

c_nφ_n

これは、C^N の直交系 {φ_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.1 の系にしておくべきかな)、{φ_n} は直交系である。そして、f =

∑_N−1

n=0 C_nφ_n と展開したときの係数は、直交系による展開の係数の公式によれば Cn= (f,φ_n)

(φ_n,φ_n) =

∑N−1 j=0 f_jω^nj

N = 1

N

N∑−1 j=0

fjω^−nj. なかなかきれいに出来ているものである。

定理 3.2.4 (離散Fourier変換に関するサンプリング定理) 周期T の関数 u:R→C が、有限 Fourier級数

u(t) =

∑M n=−M

cne^in2πTt で表せるとき、すなわち u の Fourier 係数{c_n} について

|n|> M ⇒ c_n = 0

が成り立つとき、N >2M を満たす N に対して、N 項離散Fourier 係数{C_n}^N_n=0⁻¹ は、

Cn =cn (0≤n≤M), C_N−n=c_−n (1≤n≤M), (★)

C_n = 0 (M < n < N−M)

を満たす。(特に、全ての(0でない) Fourier係数{c_n}^Mn=−M は、離散Fourier係数 {C_n}^N_n=0⁻¹ か ら求まる。)

この定理を5章の定理5.0.1 と較べてみると良い。

例 3.2.5 M = 1, N = 10 の場合、

C₀ =c₀+c₋₁₀+c₂₀+c₋₂₀+c₃₀+· · ·=c₀ + 0 + 0 +· · ·=c₀, C₁ =c₁+c₋₉+c₁₁+c₋₁₉+c₂₁+· · ·=c₁+ 0 + 0 +· · ·=c₁,

C₉ =c₉+c₋₁+c₁₉+c₋₁₁+c₂₉+c₋₂₁+· · ·= 0 +c₋₁+ 0 + 0 +· · ·=c₋₁, C2 =c2+c₋8+c12+c₋18+· · ·= 0 + 0 +· · ·= 0,

C8 =c8+c₋2+c18+c₋12+· · ·= 0 + 0 +· · ·= 0, 同様にして 2≤n≤8に対して、 C_n = 0.

一方、M = 5, N = 10 の場合は

C₀ =c₀+c₋₁₀+c₂₀+c₋₂₀+c₃₀+· · ·=c₀ + 0 + 0 +· · ·=c₀, C₁ =c₁+c₋₉+c₁₁+c₋₁₉+c₂₁+· · ·=c₁+ 0 + 0 +· · ·=c₁,

C₉ =c₉+c₋₁+c₁₉+c₋₁₁+c₂₉+c₋₂₁+· · ·= 0 +c₋₁+ 0 + 0 +· · ·=c₋₁, C₂ =c₂+c₋₈+c₁₂+c₋₁₈+· · ·= 0 + 0 +· · ·=c₂,

C₈ =c₈+c₋₂+c₁₈+c₋₁₂+· · ·= 0 + 0 +· · ·=c₋₂, ... ...

C₄ =c₄+c₋₆+c₁₄+c₋₁₆+· · ·=c₄ + 0 + 0 +· · ·=c₄, C6 =c6+c₋4+c16+c₋14+· · ·= 0 +c₋4+ 0 +· · ·=c₋4, ここまでは調子が良い。ところが

C₅ =c₅+c₋₅+c₁₅+c₋₁₅+· · ·=c₅+c₋₅+ 0 + 0 +· · ·=c₅+c₋₅. C5 =c5 も C5 =c₋5 も成り立たない。

少し考えると、M = 5 であっても、N > 10 であれば、うまく行く ((★)が成り立つ) ことが分 かる。

落ち着いて考えると、N >2M であれば (★)が成り立つ。

証明 すでに示したように

C_n= ∑

m≡n

c_m =c_n+

∑∞ p=1

(c_n+pN +c_n−pN). 0≤n≤M であれば、

• n+pN ≥N >2M > M であるから、c_n+pN = 0.

• n−pN ≤M −N <−M であるから、cn−pN = 0.

ゆえに C_n =c_n.

残りも同様にして証明できる。

ドキュメント内 , (ページ 61-66)