Remezのアルゴリズム

Remezのアルゴリズム（）、Remez法またはRemezの交換アルゴリズム（）とはによって1934年に発表された、関数に簡単な近似関数を見つけるために使用される反復アルゴリズムであり、具体的には、関数をチェビシェフ空間で一様ノルム L∞を最適化することで求める。E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Math. Kharkov 10, 41 (1934);"Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. 198, 2063 (1934);"Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Acade. Sc. 199, 337 (1934). 

チェビシェフ空間の典型的な例は、 区間 上の実連続関数空間における次数の チェビシェフ多項式の部分空間であり、与えられた部分空間内の最良近似の多項式は、多項式と関数の間の最大絶対差を最小にするものと定義される。 この場合、解の形式はによって正確性が保証される。

 手順 
まず近似する関数fに対し、近似区間中ののサンプル点の集合を考える。は通常、区間中に線形に射影されたチェビシェフ多項式の極値を用いる。 

 未知数およびについて以下の線形連立方程式を解く 
  （ ） 
 を多項式を形成する係数とする。
 絶対誤差 が極大となる点の集合を見つける。
 誤差がすべてのについて大きさが等しく、符号が交互である場合、 は、最大誤差最小の近似多項式となる。 そうでない場合は、 をに置き換え、上記の手順を繰り返す。
 上記の手順を繰り返す。 

結果は、最良近似多項式またはと呼ばれる。 

Remezアルゴリズムの実装における技術のレビューはW. Fraserによってなされた。  

（文献Jean-Michel Muller: Elementary Functinos: Algorithms and Implementation(3rd Ed), Birkhäuser, ISBN 978-1-4899-7983-4 (2016)の第3.6節:'Remez's Algorithm'には解説と共にMaple言語による実装例が載っている.）

 初期値の選択 
多項式補間の理論における役割のため、近似の初期値としてチェビシェフノードが一般的に使用される。 ラグランジュ補間を用いた関数の最適化問題の初期化では、この近似の初期値が次の範囲にあることが示される。 

ここで、ノード（）のラグランジュ補間演算子のノルム（）は 

と表される。

はチェビシェフ多項式の零点であり、ルベーグ関数は 

となる。

Theodore A. Kilgore、  Carl de Boor、およびAllan Pinkus は、各に一意のが存在することを証明したが、（通常の）多項式については明示的に知られていない。 同様に、  、およびノードの選択の最適性はのように表現できる。  

準最適ではあるが分析的に明示的な選択肢を提供するチェビシェフノードの場合、漸近的挙動は以下の様になることが知られている 

（ はオイラー・マスケローニ定数 ） 

ここで、 

for  

であり、および上限T. Rivlin, "The Lebesgue constants for polynomial interpolation", in Proceedings of the Int. Conf. on Functional Analysis and Its Application, edited by H. G. Garnier et al. (Springer-Verlag, Berlin, 1974), p. 422; The Chebyshev polynomials (Wiley-Interscience, New York, 1974). 

があたえられる。

Lev Brutman は かつが拡張されたチェビシェフ多項式の零点であるとき以下を示した。 

また、Rüdiger Günttner は、 について 

を示した。

 詳細な議論 
この節では、上記の手順の詳細について説明する。 はである。 

ステップ1 

与えられたに対して 、以下の線形連立方程式を未知数およびについて解く 

の項が存在しているためノード は整列（単調増加もしくは単調減少）している必要があることがわかる。 このとき、この線形方程式には一意の解が存在する。また、標準的なライブラリのソルバーで線形方程式を解く場合はの計算量となるが、この処理はの計算量で得られることがわかっている。  

以下に簡単な証明を次に示す。 

に対して次補間関数を、について次補間関数を最初のノード（）について計算する。 

この計算のため、各補間関数の計算において階の差商を使用したニュートン補間を用いるとそれぞれの計算量となる。 

多項式のとの間に番目の零点がある（ ）。したがって、との間に零点はなく、とは と同符号である。 

線形結合は、次の多項式であり、 

と変形できる。

これは任意のに対して、において式と同じである。とのときは 



となり、について以下の式を得ることができる。 



上述の通り、分母の2項は同じ符号を持つため、及び 常に一意に定まる。 

与えられたの整列したノードでの誤差は、以下の通り正負の交互の順になる。 

de La Vallée Poussinの定理によれば、この条件下では誤差がより小さい次の多項式は存在しない。もしそのような多項式が存在した場合、はノードにおいて正負交互のままであり個の零点を有することになるが、次数の多項式ではありえない。 したがって、このは、次数の多項式におけるで達成できる誤差の下限となる。 

ステップ2

をとする。 

ステップ3 

次のように入力ノードとそのエラーを更新する。 

について、零点によって区切られる正負の領域にそれぞれついて、正の領域でを極大値に置き換え、負の領域では極小値に置き換える。 （期待する Aで近く 、そして Bで 。）このステップでは高い精度は必要なく2つの2次近似を使用した直線探索で十分である。 （ David G. Luenberger: Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company 1973.） 

ここで とする。 各に対して絶対値はE以上となる。 de La Vallée Poussinの定理とその証明は、 についてのについても適用可能で、次数の最良多項式近似の最大誤差の下限と考えることができる。 

また、 は最大誤差の上限となる。 

ステップ4

とを最良多項式近似の最大誤差の下限と上限として、十分な精度、すなわち 十分に小さいか、減少しなくなったら繰り返しを終了する。 これらの上下限は反復処理の収束状況を示していると考えられる。 

 派生 
以下のような派生が有る。 

  複数のサンプル点を、同時に最大絶対差の近くの場所に置き換える。 
  すべてのサンプル点を、すべての位置、交互の符号、最大差となるよう単一の反復で置き換える。 2/73 "The Optimization of Bandlimited Systems" – G. C. Temes, F. C. Marshall and V. Barcilon. Proceedings IEEE. 
  浮動小数点演算を使用するコンピューターで関数を計算するために近似を使用する場合は、 相対誤差を使用して近似と関数の差を定義することがある。 
  修正されたRemez交換アルゴリズムには、無誤差点制約が含まれることがある。 
 最良有理関数近似を求めるためのRemezの算法。

 関連項目 

 近似法 

 参考文献 

 日本語の文献 
 有本卓：「数値解析(1)」、コロナ社、ISBN 4-339-00124-4 (1981年4月30日)、§5.4.4:”最良近似有理関数の構成法”。
 A.ラルストン、P.ラビノヴィッツ：「電子計算機のための数値解析の理論と応用<下>」、丸善、ISBN 4-89241-046-2 (1986年3月8日)、§7.9："ミニマックス近似の構成"。


Category:数値解析
Category:多項式
Category:近似理論
Category:未査読の翻訳があるページ
Category:数学に関する記事