Remezのアルゴリズム
多項式補間の理論における役割のため、近似の初期値としてチェビシェフノードが一般的に使用される。 ラグランジュ補間 L n ( f ) {\displaystyle L_{n}(f)} を用いた関数 f {\displaystyle f} の最適化問題の初期化では、この近似の初期値が次の範囲にあることが示される。
‖ f − L n ( f ) ‖ ∞ ≤ ( 1 + ‖ L n ‖ ∞ ) inf p ∈ P n ‖ f − p ‖ {\displaystyle \lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert f-p\rVert }
ここで、ノード( t 1 , ... , t n + 1 {\displaystyle t_{1},\ldots ,t_{n+1}} )のラグランジュ補間演算子 L n {\displaystyle L_{n}} のノルム(ルベーグ定数(英語版))は
‖ L n ‖ ∞ = Λ ̄ n ( T ) = max − 1 ≤ x ≤ 1 λ n ( T ; x ) {\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x)}
と表される。
以下のような派生が有る。
複数のサンプル点を、同時に最大絶対差の近くの場所に置き換える。
すべてのサンプル点を、すべての位置、交互の符号、最大差となるよう単一の反復で置き換える。
浮動小数点演算を使用するコンピューターで関数を計算するために近似を使用する場合は、 相対誤差を使用して近似と関数の差を定義することがある。
修正されたRemez交換アルゴリズムには、無誤差点制約が含まれることがある。
まず近似する関数fに対し、近似区間中の n + 2 {\displaystyle n+2} のサンプル点の集合 X = { x 1 , x 2 , . . . , x n + 2 } {\displaystyle X=\{x_{1},x_{2},...,x_{n+2}\}} を考える。 X {\displaystyle X} は通常、区間中に線形に射影されたチェビシェフ多項式の極値を用いる。
未知数 b 0 , b 1 . . . b n {\displaystyle b_{0},b_{1}...b_{n}} および E {\displaystyle E} について以下の線形連立方程式を解く b 0 + b 1 x i + . . . + b n x i n + ( − 1 ) i E = f ( x i ) {\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})} ( i = 1 , 2 , . . . n + 2 {\displaystyle i=1,2,...n+2} )