Remezのアルゴリズム

Remezアルゴリズム

Remezのアルゴリズムは、1934年にEvgeny Yakovlevich Remezによって提案された、関数の近似を行うための反復的手法です。このアルゴリズムは、特にL∞ノルムにおいてチェビシェフ空間での最適化を通じて、関数に対する簡便な近似を見つけるために使用されます。

チェビシェフ空間

チェビシェフ空間の代表的な例としては、区間 C = [a, b] における実連続関数の空間が挙げられます。この空間内で次数 n のチェビシェフ多項式の部分空間が定義され、最良近似の多項式は、与えられた関数と多項式の間の最大絶対差を最小化するように設定されます。この際、等振動定理が解の正確性を保証します。

アルゴリズムの手順

1. サンプル点の選定：近似する関数 f に対し、近似区間内の n + 2 個のサンプル点の集合 X = {x₁, x₂, ..., xₗ} を設定します。これらの点は通常、チェビシェフ多項式の極値によって決定されます。
2. 線形方程式の解決：未知数 b₀, b₁, ..., bₙ および誤差 E に関する連立方程式を解きます。方程式は次の形式を取ります：

b₀ + b₁xᵢ + ... + bₙxᵢⁿ + (-1)ⁱE = f(xᵢ)

ここで i は 1 から n + 2 までの整数です。
3. 多項式の構築：得られた係数 b₀, b₁, ..., bₙ を用いて、多項式 Pₙ(x) = Σ bᵢxⁱ を形成します。
4. 最大誤差の評価：受け取った多項式と実関数の間の絶対誤差が最大となる点の集合 M を探します。すべての点に対する誤差が等しい符号である場合、Pₙ は最良近似多項式になります。
5. 再評価：そうでない場合、サンプル点 X を M に置き換え、上記の手順を繰り返し行います。これにより、最終的に最良近似多項式（またはミニマックス近似）が得られるのです。

初期値の設定

多項式補間理論の観点から、チェビシェフノードが一般的に初期値として利用されます。最適化問題の初期化においては、理論的に初期値が特定の範囲に収束することが示されています。

技術的レビュー

W. FraserによるRemezアルゴリズムの実装に関する技術的なレビューがあります。特に、Maple言語による実装例が文献の第3.6節に掲載されており、その解説を通じて実際のアルゴリズムの動作を確認できます。

派生技術

Remezアルゴリズムには、複数のサンプル点の一斉調整や相対誤差の導入、無誤差点制約を含む修正アルゴリズムなど、多様な派生技術が存在します。これらの技術は、関数の近似を行う際の精度や効率を向上させるための手段として利用されています。

まとめ

Remezアルゴリズムは、関数を近似する際の強力なツールであり、実用例から論文に至るまで幅広く応用され続けています。数学的な根拠と実装例が数多く存在するため、数値解析や最適化の分野での重要な手法として位置づけられています。

もう一度検索