Remezのアルゴリズム
以下に簡単な証明を次に示す。
f ( x ) {\displaystyle f(x)} に対して n {\displaystyle n} 次補間関数 p 1 ( x ) {\displaystyle p_{1}(x)} を、 ( − 1 ) i {\displaystyle (-1)^{i}} について n {\displaystyle n} 次補間関数 p 2 ( x ) {\displaystyle p_{2}(x)} を最初の n + 1 {\displaystyle n+1} ノード( x 0 , . . . , x n {\displaystyle x_{0},...,x_{n}} )について計算する。
p 1 ( x i ) = f ( x i ) , p 2 ( x i ) = ( − 1 ) i , i = 0 , . . . , n . {\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.}
この計算のため、各補間関数の計算において 0 , . . . , n {\displaystyle 0,...,n} 階の差商を使用したニュートン補間を用いるとそれぞれ O ( n 2 ) {\displaystyle O(n^{2})} の計算量となる。
多項式 p 2 ( x ) {\displaystyle p_{2}(x)} の x i − 1 {\displaystyle x_{i-1}} と x i {\displaystyle x_{i}} の間に i {\displaystyle i} 番目の零点がある( i = 1 , .