ニュートン補間

数値解析におけるニュートン補間（ニュートンほかん、）は、アイザック・ニュートンに名を因む、ラグランジュ多項式をニュートン基底多項式の線型結合として得る多項式補間法を言う。
例えばなどと異なり、ニュートン補間では多項式の計算方法が異なるだけで得られる多項式はラグランジュ補間と同じものである。それがゆえに、ニュートン補間多項式と言うよりはラグランジュ補間多項式の「ニュートン形」と言った方が適切である。
定義.
与えられた 個の点 formula_1（どの二つの も一致しないものとする）に対する補間多項式 formula_2 がニュートン基底の線型結合というのは、基底となる多項式が formula_3 で与えられている（特に は空積の規約に従う）ことを言い、このとき各係数は差商 formula_4 で与えられる。
すなわち:
以下の定理は、この が「補間多項式」呼ばれるものであることを保証するものである:
注意.
ラグランジュ補間多項式 は次数高々 の多項式全体の成すベクトル空間に属し、上で定義した「ニュートン基底」formula_5 が実際にその基底を成す。ニュートン補間定理により、 に関する の座標 formula_6 は各 が差商で与えられる。素朴に の に関する座標を直接計算することは、線型方程式系 formula_7 すなわち formula_8 を解くことに他ならない。この方程式系は階段形かつ下三角行列であるから、 が決まれば が決まり、以下順番に まで求めることができる。
応用.
差商の定義からわかる通り、新たな点を追加して新しい補間多項式を得るのに既知の係数の再計算は必要ない。さらには、点を変更しても係数すべてを再計算する必要がない。他の利点として、 が均等に配置されているときには差商の計算はとても早くなる。したがって、補間多項式のニュートン形はラグランジュ形や素朴な直接計算よりも実用向きである。
ニュートン補間定理により、任意の多項式函数がそのに等しいことを示すこともできる。