ニュートン補間

数値解析におけるニュートン補間（ニュートンほかん、英: Newtonian interpolation）は、アイザック・ニュートンに名を因む、ラグランジュ多項式をニュートン基底多項式の線型結合として得る多項式補間法を言う。

例えばエルミート補間などと異なり、ニュートン補間では多項式の計算方法が異なるだけで得られる多項式はラグランジュ補間と同じものである。それがゆえに、ニュートン補間多項式と言うよりはラグランジュ補間多項式の「ニュートン形」と言った方が適切である。

定義

与えられた k + 1 個の点 ${\textstyle (x_{0},y_{0}),\ldots ,(x_{k},y_{k})}$（どの二つの x_j も一致しないものとする）に対する補間多項式

$$N(x)=\sum _{j=0}^{k}a_{j}n_{j}(x)$$

がニュートン基底の線型結合というのは、基底となる多項式が

$$n_{j}(x)=\prod _{0\leq i<j}(x-x_{i})\qquad (j=0,\dotsc ,k)$$

で与えられている（特に n₀ = 1 は空積の規約に従う）ことを言い、このとき各係数は差商 ${\textstyle a_{j}=[y_{0},\ldots ,y_{j}]}$ で与えられる。

すなわち:

${\textstyle (x_{0},y_{0}),\dotsc ,(x_{k},y_{k})}$ に付随するニュートン補間多項式とは

$$N(x)=[y_{0}]+[y_{0},y_{1}](x-x_{0})+\dotsb +[y_{0},\ldots ,y_{k}](x-x_{0})\ldots (x-x_{k-1})$$

のことを言う。

以下の定理は、この N が「補間多項式」呼ばれるものであることを保証するものである:

ニュートン補間定理

この多項式 N は与えられた k + 1 個の点に対応するラグランジュ補間多項式と一致する。言い換えれば、L(x_i) = y_i (∀i ∈ {0, …, k}) を満たす次数高々 k の多項式は一つしかない。

証明

初めに、k に関する帰納法で、L の k-次係数が ${\textstyle [y_{0},\dots ,y_{k}]}$ であることを示そう。k = 1 点の場合は明らか。k 点の場合に正しいと仮定して、x₀, …, x_k−1 の k 点に対応する補間多項式を P, x₁, …, x_k の k 点に対応する補間多項式を Q とすれば、

$$L(x)={\frac {(x-x_{0})Q(x)-(x-x_{k})P(x)}{x_{k}-x_{0}}}$$

と書けるから、帰納法の仮定により L の k-次係数は

$${\frac {[y_{1},\dots ,y_{k}]-[y_{0},\dots ,y_{k-1}]}{x_{k}-x_{0}}}=[y_{0},\dots ,y_{k}]$$

となる。

同じ記号を使い、やはり k に関する帰納法で L = N を示す。k = 1 点のときは明らか。k 点の場合に正しいと仮定して、L − P は高々 k-次、かつ x₀, …, x_k−1 で零になり、k-次係数は上で見たように L のそれと同じく ${\textstyle [y_{0},\dots ,y_{k}]}$ である。したがって L(x) は

$$P(x)+[y_{0},\ldots ,y_{k}](x-x_{0})\ldots (x-x_{k-1})$$

となり、帰納法の仮定によりこれは N(x) に等しい。

注意

ラグランジュ補間多項式 L は次数高々 k の多項式全体の成すベクトル空間に属し、上で定義した「ニュートン基底」$n:=(n_{0},\dots ,n_{k})$ が実際にその基底を成す。ニュートン補間定理により、n に関する L の座標 ${\textstyle (a_{0},\dots ,a_{k})}$ は各 a_i が差商で与えられる。素朴に L の n に関する座標を直接計算することは、線型方程式系 ${\textstyle \sum _{j=0}^{i}a_{j}n_{j}(x_{i})=y_{i}\qquad (i=0,\dots ,k)}$ すなわち

$${\begin{pmatrix}1&&&&0\\1&x_{1}-x_{0}&&&\\1&x_{2}-x_{0}&(x_{2}-x_{0})(x_{2}-x_{1})&&\\\vdots &\vdots &&\ddots &\\1&x_{k}-x_{0}&\ldots &\ldots &\prod _{j=0}^{k-1}(x_{k}-x_{j})\end{pmatrix}}{\begin{pmatrix}a_{0}\\\vdots \\a_{k}\end{pmatrix}}={\begin{pmatrix}y_{0}\\\vdots \\y_{k}\end{pmatrix}}$$

を解くことに他ならない。この方程式系は階段形かつ下三角行列であるから、a₀ が決まれば a₁ が決まり、以下順番に a_k まで求めることができる。

応用

差商の定義からわかる通り、新たな点を追加して新しい補間多項式を得るのに既知の係数の再計算は必要ない。さらには、点を変更しても係数すべてを再計算する必要がない。他の利点として、x_i が均等に配置されているときには差商の計算はとても早くなる。したがって、補間多項式のニュートン形はラグランジュ形や素朴な直接計算よりも実用向きである。

ニュートン補間定理により、任意の多項式函数がそのニュートン級数に等しいことを示すこともできる。

関連項目

• ネヴィルのアルゴリズム
• 多項式補間
• ラグランジュ補間
• バーンスタイン多項式
• エルミート補間
• カールソンの定理
• ニュートン級数の一覧

外部リンク

• Weisstein, Eric W. "Newton's Divided Difference Interpolation Formula". mathworld.wolfram.com (英語).
• Hazewinkel, Michiel, ed. (2001), “Newton interpolation formula”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Newton_interpolation_formula 

• Interpolation polynômiale (sic) de type Newton et différences divisées sur math-linux.com