Remezのアルゴリズム
Remezのアルゴリズム(Remez algorithm)、Remez法またはRemezの交換アルゴリズム(Remez exchange algorithm)とはEvgeny Yakovlevich Remezによって1934年に発表された、関数に簡単な近似関数を見つけるために使用される反復アルゴリズムであり、具体的には、関数をチェビシェフ空間で一様ノルム L∞を最適化することで求める。
チェビシェフ空間の典型的な例は、 区間 C=[a,b]上の実連続関数空間における次数nの チェビシェフ多項式の部分空間であり、与えられた部分空間内の最良近似の多項式は、多項式と関数の間の最大絶対差を最小にするものと定義される。 この場合、解の形式は等振動定理によって正確性が保証される。
まず近似する関数fに対し、近似区間中のn + 2のサンプル点の集合 X=\{x_1, x_2, ...,x_{n+2}\}を考える。Xは通常、区間中に線形に射影されたチェビシェフ多項式の極値を用いる。
未知数b_0, b_1...b_nおよびEについて以下の線形連立方程式を解く
b_0 + b_1 x_i+ ... +b_n x_i ^ n + (-1)^ i E = f(x_i)  ( i=1, 2, ... n+2  )
b_iを多項式P_n (x) =\sum b_i x^iを形成する係数とする。
絶対誤差 |P_n (x) - f(x)|が極大となる点mの集合Mを見つける。
誤差がすべてのmについて大きさが等しく、符号が交互である場合、 P_nは、最大誤差最小の近似多項式となる。 そうでない場合は、 XをMに置き換え、上記の手順を繰り返す。
上記の手順を繰り返す。
結果は、最良近似多項式またはミニマックス近似と呼ばれる。
Remezアルゴリズムの実装における技術のレビューはW. Fraserによってなされた。
多項式補間の理論における役割のため、近似の初期値としてチェビシェフノードが一般的に使用される。 ラグランジュ補間L_n(f)を用いた関数fの最適化問題の初期化では、この近似の初期値が次の範囲にあることが示される。
\lVert f - L_n(f)\rVert_\infty \le (1 + \lVert L_n\rVert_\infty) \inf_{p \in P_n} \lVert f - p\rVert
ここで、ノード(t_1,\ldots,t_{n+1})のラグランジュ補間演算子L_nのノルム(ルベーグ定数)は
\lVert L_n\rVert_\infty = \overline{\Lambda}_n(T) = \max_{-1 \le x \le 1} \lambda_n(T; x)
と表される。
Tはチェビシェフ多項式の零点であり、ルベーグ関数は
\lambda_n(T; x) = \sum_{j = 1}^{n + 1} \left| l_j(x) \right|, \quad l_j(x) = \prod_{\stackrel{i = 1}{i \ne j}^{n + 1} \frac{(x - t_i)}{(t_j - t_i)}
となる。
Theodore A. Kilgore、  Carl de Boor、およびAllan Pinkus は、各L_nに一意のt_iが存在することを証明したが、(通常の)多項式については明示的に知られていない。 同様に、 \underline{\Lambda}_n(T) = \min_{-1 \le x \le 1} \lambda_n(T; x) 、およびノードの選択の最適性は\overline{\Lambda}_n - \underline{\Lambda}_n \ge 0のように表現できる。
準最適ではあるが分析的に明示的な選択肢を提供するチェビシェフノードの場合、漸近的挙動は以下の様になることが知られている
\overline{\Lambda}_n(T) = \frac{2}{\pi} \log(n + 1) + \frac{2}{\pi}\left(\gamma + \log\frac{8}{\pi}\right) + \alpha_{n + 1}
( γはオイラー・マスケローニ定数 )
ここで、
0 < \alpha_n < \frac{\pi}{72 n^2}for n \ge 1,
であり、および上限
\overline{\Lambda}_n(T) \le \frac{2}{\pi} \log(n + 1) + 1
があたえられる。
Lev Brutman はn \ge 3 かつ\hat{T}が拡張されたチェビシェフ多項式の零点であるとき以下を示した。
\overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) < \overline{\Lambda}_3 - \frac{1}{6} \cot \frac{\pi}{8} + \frac{\pi}{64} \frac{1}{\sin^2(3\pi/16)} - \frac{2}{\pi}(\gamma - \log\pi)\approx 0.201
また、Rüdiger Günttner は、 n \ge 40について
\overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) < 0.0196
を示した。
この節では、上記の手順の詳細について説明する。i は0 \le i \le n+1である。
ステップ1
与えられたx_0, x_1, ... x_{n+1}に対して 、以下の線形連立方程式を未知数b_0, b_1...b_nおよびEについて解く
b_0 + b_1 x_i+ ... +b_n x_i ^ n + (-1) ^ i E = f(x_i)
(-1)^i Eの項が存在しているためノードx_0, ...,x_{n+1} は整列(単調増加もしくは単調減少)している必要があることがわかる。 このとき、この線形方程式には一意の解が存在する。また、標準的なライブラリのソルバーで線形方程式を解く場合はO(n^3)の計算量となるが、この処理はO(n^2)の計算量で得られることがわかっている。
以下に簡単な証明を次に示す。
f(x)に対してn次補間関数p_1(x)を、(-1)^iについてn次補間関数p_2(x)を最初のn+1ノード(x_0, ...,x_{n})について計算する。
p_1(x_i) = f(x_i), p_2(x_i) = (-1)^i, i = 0, ..., n.
この計算のため、各補間関数の計算において0, ...,n階の差商を使用したニュートン補間を用いるとそれぞれO(n^2)の計算量となる。
多項式p_2(x)のx_{i-1}とx_iの間にi番目の零点がある( i=1, \ldots,n)。したがって、x_nとx_{n+1}の間に零点はなく、p_2(x_n)とp_2(x_{n+1})は(-1)^n と同符号である。
線形結合p(x) := p_1 (x) - p_2(x)\!\cdot\!Eは、n次の多項式であり、
p(x_i) = p_1(x_i) - p_2(x_i)\!\cdot\! E \ = \ f(x_i) - (-1)^i E,\ \ \ \ i =0, \ldots, n.
と変形できる。
これは任意のEに対して、i = 0,\ldots,nにおいて式 b_0 + b_1 x_i+ ... +b_n x_i ^ n + (-1) ^ i E と同じである。i = n+1とのときは
p(x_{n+1}) \ = \ p_1(x_{n+1}) - p_2(x_{n+1})\!\cdot\!E \ = \ f(x_{n+1}) - (-1)^{n+1} E
となり、Eについて以下の式を得ることができる。
E \ := \ \frac{p_1(x_{n+1}) - f(x_{n+1})}{p_2(x_{n+1}) + (-1)^n}.
上述の通り、分母の2項は同じ符号を持つため、E及び p(x) \equiv b_0 + b_1x + \ldots + b_nx^n常に一意に定まる。
与えられたn+2の整列したノードでの誤差は、以下の通り正負の交互の順になる。
p(x_i) - f(x_i) \ = \ -(-1)^i E,\ \ i = 0, ..., n\!+\!1.
de La Vallée Poussinの定理によれば、この条件下では誤差がEより小さいn次の多項式は存在しない。もしそのような多項式\tilde p(x)が存在した場合、p(x)-\tilde p(x) = (p(x) - f(x)) - (\tilde p(x) - f(x))はノードx_iにおいて正負交互のままでありn+1個の零点を有することになるが、次数nの多項式ではありえない。 したがって、このEは、次数nの多項式におけるで達成できる誤差の下限となる。
ステップ2
p(x)をb_0 + b_1x + ... + b_nx^nとする。
ステップ3
次のように入力ノードx_0, ..., x_{n+1}とそのエラー\pm Eを更新する。
p(x) - f(x) について、零点によって区切られる正負の領域にそれぞれついて、正の領域でx_iを極大値\bar{x}_iに置き換え、負の領域ではx_i極小値\bar{x}_iに置き換える。 (期待する\bar{x}_0 Aで\bar {x}_i近くx_i 、そして\bar{x}_{n+1} Bで 。)このステップでは高い精度は必要なく2つの2次近似を使用した直線探索で十分である。 ( )
ここでz_i := p(\bar{x}_i) - f(\bar{x}_i) とする。 各z_iに対して絶対値|z_i|はE以上となる。 de La Vallée Poussinの定理とその証明は、 z_0, ... ,z_{n+1}についての\min\〔z_i|\} \geq Eについても適用可能で、次数nの最良多項式近似の最大誤差の下限と考えることができる。
また、 \max\〔z_i|\}は最大誤差の上限となる。
ステップ4
\min\,\〔z_i|\}と\max\,\〔z_i|\}を最良多項式近似の最大誤差の下限と上限として、十分な精度、すなわち \max\〔z_i|\} - \min\〔z_i|\}十分に小さいか、減少しなくなったら繰り返しを終了する。 これらの上下限は反復処理の収束状況を示していると考えられる。
以下のような派生が有る。
複数のサンプル点を、同時に最大絶対差の近くの場所に置き換える。
すべてのサンプル点を、すべての位置、交互の符号、最大差となるよう単一の反復で置き換える。
浮動小数点演算を使用するコンピューターで関数を計算するために近似を使用する場合は、 相対誤差を使用して近似と関数の差を定義することがある。
修正されたRemez交換アルゴリズムには、無誤差点制約が含まれることがある。