Remezのアルゴリズム
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} のように表現できる。
この節では、上記の手順の詳細について説明する。 i {\displaystyle i} は 0 ≤ i ≤ n + 1 {\displaystyle 0\leq i\leq n+1} である。
ステップ1
与えられた x 0 , x 1 , . . . x n + 1 {\displaystyle x_{0},x_{1},...x_{n+1}} に対して 、以下の線形連立方程式を未知数 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})}
( − 1 ) i E {\displaystyle (-1)^{i}E} の項が存在しているためノード x 0 , . . . , x n + 1 {\displaystyle x_{0},...,x_{n+1}} は整列(単調増加もしくは単調減少)している必要があることがわかる。 このとき、この線形方程式には一意の解が存在する。また、標準的なライブラリのソルバーで線形方程式を解く場合は O ( n 3 ) {\displaystyle O(n^{3})} の計算量となるが、この処理は O ( n 2 ) {\displaystyle O(n^{2})} の計算量で得られることがわかっている。