ネヴィルのアルゴリズムのソースを表示

'''ネヴィルのアルゴリズム'''<ref name="朝倉">{{Cite book |和書 |title=朝倉　数学辞典 |publisher=朝倉書店 |date=2016 |editor=川又雄二郎、坪井俊、楠岡成雄、新井仁之 |isbn=9784254111255 |page=575}}</ref> ({{Lang-en-short|Neville's algorithm}}) は[[ラグランジュ補間]]の計算[[アルゴリズム]]のひとつである。{{仮リンク|エイトケン補間|en|Aitken interpolation}}と近い関係にあり<ref>Press et al., p. 108.</ref>、[[エリック・ハロルド・ネヴィル]]によって考案された<ref>{{Cite journal |last=Neville |first=E. H. |title=Iterative interpolation |journal=J. Indian Math. Soc. |volume=20 |pages=87–120 |date=1934}}</ref>。

== アルゴリズム ==
与えられた <math>N + 1</math> 点 <math>\{ ( x_n, y_n ) \}_{n = 0}^{N}</math> の[[ラグランジュ補間]]多項式 <math>L ( x )</math>、すなわちこれらの点を通る <math>N</math> 次[[多項式]]を求めることを考える。ただし <math>x_n \neq x_m</math> (<math>n \neq m</math>) とする。ネヴィルのアルゴリズムは、 <math>k + 1</math> 個の点 <math>\{ ( x_n, y_n ) \}_{n = i-k}^{i}</math> を通る <math>k</math> 次多項式 <math>P_{i, k}</math> を以下のように[[再帰]]的に定めるものである<ref>Press et al., pp. 108-109.</ref><ref>Deuflhard & Hofmann, pp. 184-185.</ref><ref>Stoer & Bulirsch, pp. 40-42.</ref><ref group="注釈">ここでの表記法は Stoer & Bulirsch および Dieflhard & Hofmann に沿うものである。</ref>。

# ゼロ次多項式 <math>P_{i, 0}</math> (<math>i = 0, 1, \cdots, N</math>) を<br/><math>\qquad P_{i, 0} = y_i</math><br/>により定める。
# 多項式 <math>P_{i, k}</math> を <math>P_{i, k-1}</math> と <math>P_{i-1, k-1}</math> から漸化式<br/><math>\qquad P_{i, k} ( x ) = \frac{ ( x - x_{i-k} ) P_{i, k-1} - ( x - x_i ) P_{i-1, k-1} }{ x_i - x_{i-k} } = P_{i, k-1} + \frac{ x - x_i }{ x_i - x_{i-k} } ( P_{i, k-1} - P_{i-1, k-1} )</math><br/>によって定める。
# <math>P_{N, N} = L</math> が求めるラグランジュ多項式を与える。

ここで2番目のステップにおいて、漸化式の右辺に現れる多項式 <math>P_{i, k-1}</math>, <math>P_{i-1, k-1}</math> はともに <math>k - 1</math> 個の点 <math>\{ ( x_n, y_n ) \}_{n = i - k + 1}^{i-1}</math> を通ることに注意する。その結果として上記漸化式により <math>P_{i, k}</math> は2点 <math>( x_{i-k}, y_{i-k} )</math>, <math>( x_i, y_i )</math> をも通る多項式 <math>P_{i, k}</math> が構成できる<ref>Stoer & Bulirsch, p. 40.</ref>。

例えば <math>N = 3</math> の場合, このアルゴリズムは次の表を左から埋めていくことに対応する<ref name="Press109">Press et al., p. 109.</ref><ref>Stoer & Bulirsch, p. 41.</ref>。多項式 <math>P_{i, k}</math> は自身の左側にあるふたつの多項式 <math>P_{i, k-1}</math>, <math>P_{i-1, k-1}</math> から上記漸化式を通じて定まる「娘」である<ref name="Press109"/>。
{{Indent|<math>\begin{matrix}
y_0 = P_{0, 0} & \\
& P_{1, 1} \\
y_1 = P_{1, 0} & & P_{2, 2} \\
& P_{2, 1} & & P_{3, 3} = L \\
y_2 = P_{2, 0} & & P_{3, 2} \\
& P_{3, 1} \\
y_3 = P_{3, 0} & 
\end{matrix}</math>}}

== 特徴 ==
ネヴィルのアルゴリズムはラグランジュ補間多項式のある一点 <math>x</math> での値 <math>L ( x )</math> を評価する目的に適している<ref name="朝倉"/><ref>Stoer & Bulirsch, pp. 40-41.</ref>。多項式それ自体を求める場合、あるいは複数の点の補間値が必要な場合、[[ニュートン補間]]の方が好ましい<ref>Stoer & Bulirsch, pp. 43-44.</ref>。補間値を得るためには必ずしもネヴィルのアルゴリズムを最後まで実行する必要はなく、途中で止めることも可能である<ref>{{Cite web |url=http://www.physics.utah.edu/~detar/phys6720/handouts/interpolation/interpolation/node4.html |title=Neville algorithm |accessdate=2021-01-11}}</ref>。

ネヴィルのアルゴリズムは[[定積分]]を数値的に求める[[ロンバーグ積分]]に用いられる<ref>Press et al., pp. 140-141.</ref>。

== 脚注 ==
=== 注釈 ===
{{Reflist |group="注釈"}}

=== 出典 ===
{{Reflist |2}}

== 参考文献 ==
* {{Cite book |last1=Press |first1=William H. |first2=Saul A. |last2=Teukolsky |first3=William T. |last3=Vetterling |first4=Brian P. |last4=Flannery |date=1992 |title=Numerical Recipes in C: The Art of Scientific Computing |edition=2nd |publisher=Cambridge University Press |doi=10.2277/0521431085 |isbn=978-0-521-43108-8}}
* {{Cite book |last1=Deuflhard |first1=Peter |last2=Hohmann |first2=Andreas |title=Numerical Analysis in Modern Scientific Computing: An Introduction |publisher=Springer |date=1993 |isbn=978-0-387-21584-6 |doi=10.1007/978-0-387-21584-6}}
* {{Cite book |last1=Stoer |first1=Josef |last2=Bulirsch |first2=R. |title=Introduction to Numerical Analysis |publisher=Springer |date=2002 |isbn=978-0-387-21738-3 |doi=10.1007/978-0-387-21738-3}}

== 関連項目 ==
* [[ラグランジュ補間]]
* [[リチャードソンの補外]]

{{DEFAULTSORT:ねういるのあるこりすむ}}
[[Category:補間]]
[[Category:多項式]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]