最小二乗近似とミニマックス近似

最小二乗近似は二乗誤差の総和が最小になるような係数を求めるのに対してミニマックス近似は絶対値最大の誤差が最小になるように係数を求めます。最小二乗近似より面倒くさいです。某音ゲーで例えるとライブ成功とフルコンボの違いのようなものです。

最小二乗フィルタ

遮断周波数が1.0の51次の最小二乗ローパスフィルタです。Raspberry PiのMathematicaでお手軽に計算することが出来ます。

等リプルフィルタ

遮断周波数が1.0の51次の等リプルローパスフィルタです。今回はこれを自前で計算するのが目標です。

ミニマックス近似

最良近似多項式

$f(x)$は区間$[a,b]$で連続な関数でそれを近似する$n$次多項式を

f_n(x)=\sum_{k=0}^n a_k x^k

とします。$n$を固定したときに

 \max_{a<x<b} |f(x)-f_n(x)|

を最小にするような多項式を最良近似多項式といいます。最良近似多項式は次のような性質を持っています。

$f_n(x)$が最良近似多項式であるための必要十分条件は、誤差関数$\epsilon(x)$を
\epsilon(x) = f(x)-f_n(x)
と置いたとき、$|\epsilon(x)|$が区間$[a,b]$で少なくとも$n+2$点で等しい最大値をとり、最大値における$\epsilon(x)$の符号が交互に並んでいることである。

あと最良近似多項式の一意性についてもいわないとですが割愛します。

最良近似三角多項式

$g(x)$は区間$[0,\pi]$で連続な関数でそれを近似する三角多項式を

g_n(x)= \sum_{k=0}^n a_k \cos(kx)

とします。今回は偶関数を扱うので$\sin$関数は無しとさせてください。実は多項式の場合と同じような性質を持っています。

$g_n$が区間$[0,\pi]$で連続な関数$g$の最良近似とのなる必要十分条件は、誤差関数$\epsilon(x)$を
\epsilon(x) = g(x)-g_n(x)
と置いたとき、$|\epsilon(x)|$が区間$[0,\pi]$で少なくとも$n+2$点で等しい最大値をとり、最大値における$\epsilon(x)$の符号が交互に並んでいることである。

Remez algorithm

今回はRemez algorithmを用いて等リプルフィルタを作成します。アルゴリズムは次のようになっています。

区間$[0, \pi]$上に$n+2$個の検査点$x_0, \cdots x_{n+1}$を適当に用意する

検査点での誤差関数$\epsilon(x)$の絶対値が等しくかつ誤差の符号が交互に並ぶような三角多項式$g(x)$の係数$a_0, \cdots, a_n$と誤差$d$を求め、三角多項式を更新する

誤差関数$\epsilon(x)$の絶対値が最大となる$n+2$個の点$x_0, \cdots x_{n+1}$を求め、検査点を更新する

検査点での誤差関数$\epsilon(x)$の絶対値が等しくかつ誤差の符号が交互に並んでいれば終了し、そうでなければ2へ戻る

4はそのまんま、2は連立一次方程式を解けば良さそう（解き方はいろいろありますが）、しかし1と3は試行錯誤が必要そうですね。

実装

Pythonで200行程度で実装しました。入力値によってはコケるので万能ではないです。

https://github.com/fukuroder/Remez_algorithm_test