ニュートン補間のソースを表示

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

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

== 定義 ==
与えられた {{math|''k'' + 1}} 個の点 <math display="inline">(x_0, y_0),\ldots,(x_k, y_k)</math>（どの二つの {{mvar|x{{sub|j}}}} も一致しないものとする）に対する補間多項式 <math display="block">N(x)=\sum_{j=0}^ka_jn_j(x)</math> がニュートン基底の線型結合というのは、基底となる多項式が <math display="block">n_j(x)=\prod_{0\le i<j}(x-x_i)\qquad (j=0,\dotsc,k)</math> で与えられている（特に {{math|1=''n''{{sub|0}} = 1}} は[[空積]]の規約に従う）ことを言い、このとき各係数は[[差商]] <math display="inline">a_j=[y_0,\ldots,y_j]</math> で与えられる。

すなわち:
{{énoncé|<math display="inline">(x_0, y_0),\dotsc,(x_k, y_k)</math> に付随するニュートン補間多項式とは <math display="block">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})</math> のことを言う。}}

以下の定理は、この {{mvar|N}} が「補間多項式」呼ばれるものであることを保証するものである:
{{énoncé|
; ニュートン補間定理: この多項式 {{mvar|N}} は与えられた {{math|''k'' + 1}} 個の点に対応するラグランジュ補間多項式と一致する。言い換えれば、{{math|1=''L''(''x{{sub|i}}'') = ''y{{sub|i}}'' (∀''i'' ∈ {{mset|0, …, ''k''}})}} を満たす次数高々 {{mvar|k}} の多項式は一つしかない。
}}

{{math proof|drop=yes|continue=
初めに、{{mvar|k}} に関する帰納法で、{{mvar|L}} の {{mvar|k}}-次係数が <math display="inline">[y_0,\dots,y_k]</math> であることを示そう。{{math|1=''k'' = 1}} 点の場合は明らか。{{mvar|k}} 点の場合に正しいと仮定して、{{math|''x''{{sub|0}}, …, ''x''{{sub|''k''&minus;1}}}} の {{mvar|k}} 点に対応する補間多項式を {{mvar|P}}, {{math|''x''{{sub|1}}, …, ''x{{sub|k}}''}} の {{mvar|k}} 点に対応する補間多項式を {{mvar|Q}} とすれば、<math display="block">L(x)=\frac{(x-x_0)Q(x)-(x-x_k)P(x)}{x_k-x_0}</math> と書けるから、帰納法の仮定により {{mvar|L}} の {{mvar|k}}-次係数は<math display="block">\frac{[y_1,\dots,y_k]-[y_0,\dots,y_{k-1}]}{x_k-x_0}=[y_0,\dots,y_k]</math> となる。

同じ記号を使い、やはり {{mvar|k}} に関する帰納法で {{mvar|1=''L'' = ''N''}} を示す。{{math|1=''k'' = 1}} 点のときは明らか。{{mvar|k}} 点の場合に正しいと仮定して、{{math|''L'' &minus; ''P''}} は高々 {{mvar|k}}-次、かつ {{math|''x''{{sub|0}}, …, ''x''{{sub|''k''&minus;1}}}} で零になり、{{mvar|k}}-次係数は上で見たように {{mvar|L}} のそれと同じく <math display="inline">[y_0,\dots,y_k]</math> である。したがって {{math|''L''(''x'')}} は <math display="block">P(x)+[y_0,\ldots,y_k](x-x_0)\ldots(x-x_{k-1})</math> となり、帰納法の仮定によりこれは {{math|''N''(''x'')}} に等しい。
}}

== 注意 ==
ラグランジュ補間多項式 {{mvar|L}} は次数高々 {{mvar|k}} の多項式全体の成す[[ベクトル空間]]に属し、上で定義した「ニュートン基底」<math>n:=(n_0,\dots,n_k)</math> が実際にその基底を成す。ニュートン補間定理により、{{mvar|n}} に関する {{mvar|L}} の座標 <math display="inline">(a_0,\dots,a_k)</math> は各 {{mvar|a{{sub|i}}}} が差商で与えられる。素朴に {{mvar|L}} の {{mvar|n}} に関する座標を直接計算することは、[[線型方程式系]] <math display="inline">\sum_{j=0}^ia_jn_j(x_i)=y_i\qquad (i=0,\dots,k)</math> すなわち <math display="block"> 
\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}
</math> を解くことに他ならない。この方程式系は階段形かつ[[下三角行列]]であるから、{{math|''a''{{sub|0}}}} が決まれば {{math|''a''{{sub|1}}}} が決まり、以下順番に {{mvar|a{{sub|k}}}} まで求めることができる。

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

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

== 関連項目==
* [[ネヴィルのアルゴリズム]]
* [[多項式補間]]
* [[ラグランジュ補間]]
* [[バーンスタイン多項式]]
* {{ill2|エルミート補間|en|Hermite interpolation}}
* {{ill2|カールソンの定理|en|Carlson's theorem}}
* {{ill2|ニュートン級数の一覧|en|Table of Newtonian series}}

== 外部リンク ==
* {{MathWorld|urlname=NewtonsDividedDifferenceInterpolationFormula|title=Newton's Divided Difference Interpolation Formula}}
* {{SpringerEOM|urlname=Newton_interpolation_formula|title=Newton interpolation formula}}

*[http://www.math-linux.com/spip.php?article46 Interpolation polynômiale (sic) de type Newton et différences divisées] sur math-linux.com
<!--{{Traduction/Référence|en|Newton polynomial|13859858|type=n}}-->

{{portal|数学}}
{{DEFAULTSORT:にゆうとんほかん}}
[[Category:補間]]
[[Category:有限差分]]
[[Category:多項式]]
[[Category:アイザック・ニュートン]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]