Remezのアルゴリズム
ここで z i := p ( x ̄ i ) − f ( x ̄ i ) {\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})} とする。 各 z i {\displaystyle z_{i}} に対して絶対値 | z i | {\displaystyle |z_{i}|} はE以上となる。 de La Vallée Poussinの定理とその証明は、 z 0 , . . . , z n + 1 {\displaystyle z_{0},...,z_{n+1}} についての min { | z i | } ≥ E {\displaystyle \min\{|z_{i}|\}\geq E} についても適用可能で、次数 n {\displaystyle n} の最良多項式近似の最大誤差の下限と考えることができる。
また、 max { | z i | } {\displaystyle \max\{|z_{i}|\}} は最大誤差の上限となる。
ステップ4
min { | z i | } {\displaystyle \min \,\{|z_{i}|\}} と max { | z i | } {\displaystyle \max \,\{|z_{i}|\}} を最良多項式近似の最大誤差の下限と上限として、十分な精度、すなわち max { | z i | } − min { | z i | } {\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}} 十分に小さいか、減少しなくなったら繰り返しを終了する。 これらの上下限は反復処理の収束状況を示していると考えられる。
p ( x ) {\displaystyle p(x)} を b 0 + b 1 x + . . . + b n x n {\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}} とする。
ステップ3
次のように入力ノード x 0 , . . . , x n + 1 {\displaystyle x_{0},...,x_{n+1}} とそのエラー ± E {\displaystyle \pm E} を更新する。
p ( x ) − f ( x ) {\displaystyle p(x)-f(x)} について、零点によって区切られる正負の領域にそれぞれついて、正の領域で x i {\displaystyle x_{i}} を極大値 x ̄ i {\displaystyle {\bar {x}}_{i}} に置き換え、負の領域では x i {\displaystyle x_{i}} 極小値 x ̄ i {\displaystyle {\bar {x}}_{i}} に置き換える。 (期待する x ̄ 0 {\displaystyle {\bar {x}}_{0}} Aで x ̄ i {\displaystyle {\bar {x}}_{i}} 近く x i {\displaystyle x_{i}} 、そして x ̄ n + 1 {\displaystyle {\bar {x}}_{n+1}} Bで 。)このステップでは高い精度は必要なく2つの2次近似を使用した直線探索で十分である。 ( )