Remezのアルゴリズム

Remezのアルゴリズム（英: Remez algorithm）、Remez法またはRemezの交換アルゴリズム（英: Remez exchange algorithm）とはEvgeny Yakovlevich Remez（英語版）によって1934年に発表された、関数に簡単な近似関数を見つけるために使用される反復アルゴリズムであり、具体的には、関数をチェビシェフ空間で一様ノルム L∞を最適化することで求める。 チェビシェフ空間の典型的な例は、 区間 C = [ a , b ] {\displaystyle C=[a,b]} 上の実連続関数空間における次数 n {\displaystyle n} の チェビシェフ多項式の部分空間であり、与えられた部分空間内の最良近似の多項式は、多項式と関数の間の最大絶対差を最小にするものと定義される。 この場合、解の形式は等振動定理（英語版）によって正確性が保証される。 まず近似する関数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} ） b i {\displaystyle b_{i}} を多項式 P n ( x ) = ∑ b i x i {\displaystyle P_{n}(x)=\sum b_{i}x^{i}} を形成する係数とする。 絶対誤差 | P n ( x ) − f ( x ) | {\displaystyle |P_{n}(x)-f(x)|} が極大となる点 m {\displaystyle m} の集合 M {\displaystyle M} を見つける。 誤差がすべての m {\displaystyle m} について大きさが等しく、符号が交互である場合、 P n {\displaystyle P_{n}} は、最大誤差最小の近似多項式となる。 そうでない場合は、 X {\displaystyle X} を M {\displaystyle M} に置き換え、上記の手順を繰り返す。 上記の手順を繰り返す。 結果は、最良近似多項式またはミニマックス近似（英語版）と呼ばれる。 Remezアルゴリズムの実装における技術のレビューはW. Fraserによってなされた。 多項式補間の理論における役割のため、近似の初期値としてチェビシェフノードが一般的に使用される。 ラグランジュ補間 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)} と表される。 T {\displaystyle T} はチェビシェフ多項式の零点であり、ルベーグ関数は λ n ( T ; x ) = ∑ j = 1 n + 1 | l j ( x ) | , l j ( x ) = ∏ i ≠ j i = 1 n + 1 ( x − t i ) ( t j − t i ) {\displaystyle \lambda _{n}(T;x)=\sum _{j=1}^{n+1}\left|l_{j}(x)\right|,\quad l_{j}(x)=\prod _{\stackrel {i=1}{i\neq j}}^{n+1}{\frac {(x-t_{i})}{(t_{j}-t_{i})}}} となる。 Theodore A. Kilgore、 Carl de Boor、およびAllan Pinkus は、各 L n {\displaystyle L_{n}} に一意の t i {\displaystyle t_{i}} が存在することを証明したが、（通常の）多項式については明示的に知られていない。 同様に、 Λ _ n ( T ) = min − 1 ≤ x ≤ 1 λ n ( T ; x ) {\displaystyle {\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)} 、およびノードの選択の最適性は Λ ¯ n − Λ _ n ≥ 0 {\displaystyle {\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0} のように表現できる。 準最適ではあるが分析的に明示的な選択肢を提供するチェビシェフノードの場合、漸近的挙動は以下の様になることが知られている Λ ¯ n ( T ) = 2 π log ⁡ ( n + 1 ) + 2 π ( γ + log ⁡ 8 π ) + α n + 1 {\displaystyle {\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}} （ γはオイラー・マスケローニ定数 ） ここで、 0 < α n < π 72 n 2 {\displaystyle 0<\alpha _{n}<{\frac {\pi }{72n^{2}}}} for n ≥ 1 , {\displaystyle n\geq 1,} であり、および上限 Λ ¯ n ( T ) ≤ 2 π log ⁡ ( n + 1 ) + 1 {\displaystyle {\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1} があたえられる。 Lev Brutman は n ≥ 3 {\displaystyle n\geq 3} かつ T