Remezのアルゴリズム

Remezのアルゴリズム（）、Remez法またはRemezの交換アルゴリズム（）とはによって1934年に発表された、関数に簡単な近似関数を見つけるために使用される反復アルゴリズムであり、具体的には、関数をで一様ノルム "L"∞を最適化することで求める。 
チェビシェフ空間の典型的な例は、 区間 formula_1上の実連続関数空間における次数formula_2の チェビシェフ多項式の部分空間であり、与えられた部分空間内の最良近似の多項式は、多項式と関数の間の最大絶対差を最小にするものと定義される。 この場合、解の形式はによって正確性が保証される。
手順.
まず近似する関数"f"に対し、近似区間中のformula_3のサンプル点の集合formula_4を考える。formula_5は通常、区間中に線形に射影されたチェビシェフ多項式の極値を用いる。 
結果は、最良近似多項式またはと呼ばれる。 
Remezアルゴリズムの実装における技術のレビューはW. Fraserによってなされた。 
初期値の選択.
多項式補間の理論における役割のため、近似の初期値としてチェビシェフノードが一般的に使用される。 ラグランジュ補間formula_19を用いた関数formula_20"の"最適化問題の初期化では、この近似の初期値が次の範囲にあることが示される。 
formula_21
ここで、ノード（formula_22）のラグランジュ補間演算子formula_23のノルム（）は 
formula_24
と表される。
formula_25はチェビシェフ多項式の零点であり、ルベーグ関数は 
formula_26
となる。
Theodore A. Kilgore、 Carl de Boor、およびAllan Pinkus は、各"formula_23"に一意の"formula_28"が存在することを証明したが、（通常の）多項式については明示的に知られていない。 同様に、 formula_29 、およびノードの選択の最適性はformula_30のように表現できる。 
準最適ではあるが分析的に明示的な選択肢を提供するチェビシェフノードの場合、漸近的挙動は以下の様になることが知られている 
formula_31
（ はオイラー・マスケローニ定数 ） 
ここで、 
formula_32for formula_33 
であり、および上限 
formula_34
があたえられる。
Lev Brutman はformula_35 かつformula_36が拡張されたチェビシェフ多項式の零点であるとき以下を示した。 
formula_37
また、Rüdiger Günttner は、 formula_38について 
formula_39
を示した。
詳細な議論.
この節では、上記の手順の詳細について説明する。formula_40 はformula_41である。 
ステップ1 
与えられたformula_42に対して 、以下の線形連立方程式を未知数formula_6およびformula_7について解く 
formula_45
formula_46の項が存在しているためノードformula_47 は整列（単調増加もしくは単調減少）している必要があることがわかる。 このとき、この線形方程式には一意の解が存在する。また、標準的なライブラリのソルバーで線形方程式を解く場合はformula_48の計算量となるが、この処理はformula_49の計算量で得られることがわかっている。 
以下に簡単な証明を次に示す。 
formula_50に対して"formula_2"次補間関数formula_52を、formula_53について"formula_2"次補間関数formula_55を最初の"formula_56"ノード（formula_57）について計算する。 
formula_58
この計算のため、各補間関数の計算においてformula_59階の差商を使用したニュートン補間を用いるとそれぞれformula_49の計算量となる。 
多項式formula_55のformula_62とformula_63の間にformula_40番目の零点がある（ formula_65）。したがって、formula_66とformula_67の間に零点はなく、formula_68とformula_69はformula_70 と同符号である。 
線形結合formula_71は、formula_2次"の"多項式であり、 
formula_73
と変形できる。
これは任意の"formula_7"に対して、formula_75において式formula_76と同じである。formula_77とのときは 
formula_78 
となり、"formula_7"について以下の式を得ることができる。 
formula_80 
上述の通り、分母の2項は同じ符号を持つため、formula_7"及び" formula_82常に一意に定まる。 
与えられたformula_83の整列したノードでの誤差は、以下の通り正負の交互の順になる。 
formula_84
"de La Vallée Poussin"の定理によれば、この条件下では誤差が"formula_7"より小さい"formula_2"次の多項式は存在しない。もしそのような多項式formula_87が存在した場合、formula_88はノードformula_63において正負交互のままでありformula_56個の零点を有することになるが、次数formula_2の多項式ではありえない。 したがって、この"formula_7"は、次数"formula_2の"多項式におけるで達成できる誤差の下限となる。 
ステップ2
formula_94をformula_95とする。 
ステップ3 
次のように入力ノードformula_96とそのエラーformula_97を更新する。 
formula_98について、零点によって区切られる正負の領域にそれぞれついて、正の領域でformula_63を極大値formula_100に置き換え、負の領域ではformula_63極小値formula_100に置き換える。 （期待するformula_103 "A"でformula_104近くformula_63 、そしてformula_106 "Bで" 。）このステップでは高い精度は必要なく2つの"2次近似"を使用した直線探索で十分である。 （ ） 
ここでformula_107 とする。 各formula_108に対して絶対値formula_109は"E"以上となる。 "de La Vallée Poussin"の定理とその証明は、 formula_110についてのformula_111についても適用可能で、次数"formula_2の"最良多項式近似の最大誤差の下限と考えることができる。 
また、 formula_113は最大誤差の上限となる。 
ステップ4
formula_114とformula_115を最良多項式近似の最大誤差の下限と上限として、十分な精度、すなわち formula_116十分に小さいか、減少しなくなったら繰り返しを終了する。 これらの上下限は反復処理の収束状況を示していると考えられる。 
派生.
以下のような派生が有る。