2022年7月 – 門前の小僧

過去サンプルのDFTの再帰的計算

\arg \max \arg \min \providecommand ∁ rect \erf \providecommand ℜ \providecommand ℑ \providecommand Pr

はじめに

信号処理に於いて、時刻 $n$ 毎に直近 $N$ 個のサンプルの(時間的に逆向きの)DFTを計算したい状況がある。例えばDCTによる近似的な直交変換 LMS (Least Mean Square) アルゴリズムがそうである。その際に毎度 $N$ 点FFTを実行すると毎時刻 $O (N \log N)$ の計算量となる。しかし実は漸化式を用いてこれを回避し、毎度 $O (N)$ の計算量とする方法がある([1] p65)。本記事ではこれについて述べ、Mathematicaによる数値例を載せる。

Gauss-Seidel法の収束の十分条件

はじめに

Gauss-Seidel法が厳密解へ収束する主要な十分条件の一つに、係数行列が狭義優対角であることが知られている。腕試しに証明を試みたらできたので書き残しておく。