離散パーセバルの等式と巡回畳み込み

$\sum_{k} ∣ X_{k} ∣^{2} = N \sum_{n} ∣ x_{n} ∣^{2}$ と、巡回畳み込みの DFT が積になることを使える。自己相関を経由して、 $\sum_{k} ∣ X_{k} ∣^{4}$ のような和を求められる

前提

離散フーリエ変換の計算と逆変換（大学院数学フーリエ解析）

この技能までの道筋（53 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
平方完成と 2 次関数のグラフ（数学I 2次関数）
複素数と 2 次方程式の虚数解（数学II 複素数と方程式）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
極形式と積・商（数学C 複素数平面）
ド・モアブルの定理（数学C 複素数平面）
方程式 $z^{n} = a$ の解（数学C 複素数平面）
$1 + cos θ + i sin θ$ の極形式（数学C 複素数平面）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
平行線と線分の比（中学数学相似と三平方の定理）
2点間の距離と内分点・外分点（数学II 図形と方程式）
複素数平面と絶対値・共役複素数（数学C 複素数平面）
3 次式までの展開と因数分解（数学I 数と式）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
$z^{n} = a$ の解を使った和と積（数学C 複素数平面）
（等差）×（等比）の数列の和（数学B 数列）
離散フーリエ変換の計算と逆変換（大学院数学フーリエ解析）

説明

長さ $N$ の複素数列 $x_{0}, \dots, x_{N - 1}$ の離散フーリエ変換（DFT） $X_{k}$ について、「エネルギー」 $\sum_{k} ∣ X_{k} ∣^{2}$ はもとの数列のエネルギーの $N$ 倍になります（離散パーセバルの等式）。また、添字を $N$ を法として回しながら掛けて足す「巡回畳み込み」の DFT は、それぞれの DFT の積になります。この 2 つを組み合わせると、 $∣ X_{k} ∣^{2}$ が自己相関の DFT であることがわかり、 $X_{k}$ を 1 つずつ計算しなくても $\sum_{k} ∣ X_{k} ∣^{4}$ のような和をもとの数列だけから求められます。信号処理や、指数和の評価・組合せ論で頻繁に使う計算です。

なぜそうしてよいのか

以下 $ω = cos \frac{2 π}{N} + i sin \frac{2 π}{N}$ 、 $X_{k} = \sum_{n = 0}^{N - 1} x_{n} ω^{- nk}$ とし、数列の添字はすべて $N$ を法として読みます（ $x_{n + N} = x_{n}$ ）。鍵になるのは 1 の $N$ 乗根の和の性質 $\sum_{k = 0}^{N - 1} ω^{j k} = N$ （ $j \equiv 0 (mod N)$ ）、 $= 0$ （それ以外）です。

パーセバルの等式: $∣ X_{k} ∣^{2} = X_{k} X_{k} = \sum_{n} \sum_{m} x_{n} x_{m} ω^{- (n - m) k}$ を $k$ について足すと、 $\sum_{k} ω^{- (n - m) k}$ は $n = m$ のときだけ $N$ で他は $0$ なので、 $\sum_{k} ∣ X_{k} ∣^{2} = N \sum_{n} ∣ x_{n} ∣^{2}$ が出ます。 $\frac{1}{N} X_{k}$ に直すと「長さ（2 乗和）が変わらない」ということです。

巡回畳み込み: $(x * y)_{n} = \sum_{m = 0}^{N - 1} x_{m} y_{n - m}$ と定めると、その DFT は $\sum_{n} \sum_{m} x_{m} y_{n - m} ω^{- nk} = \sum_{m} x_{m} ω^{- mk} \sum_{n} y_{n - m} ω^{- (n - m) k} = X_{k} Y_{k}$ です（ $n - m$ は $n$ とともに $0, \dots, N - 1$ を $N$ を法として 1 周するので、内側の和は $m$ によらず $Y_{k}$ ）。特に自己相関 $r_{n} = \sum_{m = 0}^{N - 1} x_{m + n} x_{m}$ の DFT は、同じ計算で $R_{k} = \sum_{n} \sum_{m} x_{m + n} x_{m} ω^{- (m + n) k} ω^{mk} = X_{k} X_{k} = ∣ X_{k} ∣^{2}$ になります。そこで $r$ にパーセバルの等式を使うと
$k \sum ∣ X_{k} ∣^{4} = k \sum ∣ R_{k} ∣^{2} = N n \sum ∣ r_{n} ∣^{2}$
となり、4 乗和が自己相関の 2 乗和に帰着します。

手順

添字を $N$ を法として読む約束を確認し、DFT が $X_{k} = \sum_{n} x_{n} ω^{- nk}$ （ $ω = e^{2 π i / N}$ ）の流儀であることを確かめる
2 乗和なら、パーセバルの等式 $\sum_{k} ∣ X_{k} ∣^{2} = N \sum_{n} ∣ x_{n} ∣^{2}$ をそのまま使う
積 $X_{k} Y_{k}$ や $∣ X_{k} ∣^{2}$ が出てきたら、巡回畳み込み $(x * y)_{n} = \sum_{m} x_{m} y_{n - m}$ や自己相関 $r_{n} = \sum_{m} x_{m + n} x_{m}$ の DFT とみなす
4 乗和は $\sum_{k} ∣ X_{k} ∣^{4} = N \sum_{n} ∣ r_{n} ∣^{2}$ に直し、 $r_{0}, \dots, r_{N - 1}$ を数列から直接数える
検算として $r_{0} = \sum ∣ x_{n} ∣^{2}$ 、 $\sum_{n} r_{n} = \sum_{n} x_{n}^{2}$ （ $= R_{0} = ∣ X_{0} ∣^{2}$ ）が成り立つことを確かめる

例題

$N = 5$ とし、 $x = (x_{0}, x_{1}, x_{2}, x_{3}, x_{4}) = (1, 1, 1, 0, 0)$ の DFT を $X_{k} = \sum_{n = 0}^{4} x_{n} ω^{- nk}$ （ $ω = e^{2 π i /5}$ ）とする。 $k = 0 \sum 4 ∣ X_{k} ∣^{4}$ を求めよ。

例題の解答

手順 1: 添字は $5$ を法として読む。

手順 3: 自己相関 $r_{n} = \sum_{m = 0}^{4} x_{m + n} x_{m}$ （ $x$ は実数）の DFT が $∣ X_{k} ∣^{2}$ 。 $x_{m} = 1$ となるのは $m \in {0, 1, 2}$ なので、 $r_{n}$ は「 $m \in {0, 1, 2}$ かつ $m + n mod 5 \in {0, 1, 2}$ 」となる $m$ の個数。
- $r_{0} = 3$
- $r_{1}$ : $m = 0, 1$ → $2$
- $r_{2}$ : $m = 0$ のみ → $1$
- $r_{3}$ : $m = 2$ （ $2 + 3 \equiv 0$ ）のみ → $1$
- $r_{4}$ : $m = 1, 2$ （ $1 + 4 \equiv 0, 2 + 4 \equiv 1$ ）→ $2$

手順 5（検算）: $r_{0} = 3 = \sum x_{n}^{2}$ 、 $\sum r_{n} = 3 + 2 + 1 + 1 + 2 = 9 = (\sum x_{n})^{2}$ 。

手順 4: $\sum_{k} ∣ X_{k} ∣^{4} = 5 \sum_{n} r_{n}^{2} = 5 (9 + 4 + 1 + 1 + 4) = 5 \cdot 19 = 95$ 。

答え: $95$

よくある誤り

パーセバルの等式で係数を落として $\sum_{k} ∣ X_{k} ∣^{2} = \sum_{n} ∣ x_{n} ∣^{2}$ としてしまう誤り。この DFT の流儀（ $\frac{1}{N}$ を逆変換側に付ける）では正しくは $\sum_{k} ∣ X_{k} ∣^{2} = N \sum_{n} ∣ x_{n} ∣^{2}$ 。例えば $x = (1, 0, 0, 0)$ なら $X_{k} = 1$ で左辺は $4$
畳み込みの添字を $N$ を法として回さず、普通の（線形の）畳み込み $\sum_{m \leq n} x_{m} y_{n - m}$ にしてしまう誤り。長さ $N$ の DFT の積 $X_{k} Y_{k}$ に対応するのは、正しくは $n - m$ を $N$ を法として読む巡回畳み込み $(x * y)_{n} = \sum_{m = 0}^{N - 1} x_{m} y_{(n - m) mod N}$
$\sum_{k} ∣ X_{k} ∣^{4}$ を $N \sum_{n} ∣ x_{n} ∣^{4}$ としてしまう誤り。パーセバルは 2 乗和にしか使えない。正しくは $∣ X_{k} ∣^{2}$ が自己相関 $r$ の DFT なので $\sum_{k} ∣ X_{k} ∣^{4} = N \sum_{n} ∣ r_{n} ∣^{2}$ （上の例では $5 \cdot 3 = 15$ ではなく $95$ ）
複素数列の自己相関で共役を落として $r_{n} = \sum_{m} x_{m + n} x_{m}$ としてしまう誤り。その DFT は $∣ X_{k} ∣^{2}$ にならない。正しくは $r_{n} = \sum_{m} x_{m + n} x_{m}$ で、その DFT が $X_{k} X_{k} = ∣ X_{k} ∣^{2}$

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$N = 8$ とし、 $ω = e^{2 π i /8}$ とおく。数列 $x = (x_{0}, x_{1}, \dots, x_{7}) \in C^{8}$ を
$x = (1, 2, 1, 0, 0, 0, 0, 0)$
で定め、その離散フーリエ変換を
$X_{k} = n = 0 \sum 7 x_{n} ω^{- nk} (k = 0, 1, \dots, 7)$
とする。このとき
$k = 0 \sum 7 ∣ X_{k} ∣^{4}$
の値を求めよ。

離散パーセバルの等式と巡回畳み込み

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題