ネヴィルのアルゴリズム

ネヴィルのアルゴリズム (英: Neville's algorithm) はラグランジュ補間の計算アルゴリズムのひとつである。エイトケン補間と近い関係にあり、エリック・ハロルド・ネヴィルによって考案された。

アルゴリズム

与えられた $N+1$ 点 $\{(x_{n},y_{n})\}_{n=0}^{N}$ のラグランジュ補間多項式 $L(x)$、すなわちこれらの点を通る $N$ 次多項式を求めることを考える。ただし $x_{n}\neq x_{m}$ ($n\neq m$) とする。ネヴィルのアルゴリズムは、 $k+1$ 個の点 $\{(x_{n},y_{n})\}_{n=i-k}^{i}$ を通る $k$ 次多項式 $P_{i,k}$ を以下のように再帰的に定めるものである。

1. ゼロ次多項式 $P_{i,0}$ ($i=0,1,\cdots ,N$) を
   $\qquad P_{i,0}=y_{i}$
   により定める。
2. 多項式 $P_{i,k}$ を $P_{i,k-1}$ と $P_{i-1,k-1}$ から漸化式
   $\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})$
   によって定める。
3. $P_{N,N}=L$ が求めるラグランジュ多項式を与える。

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

例えば $N=3$ の場合, このアルゴリズムは次の表を左から埋めていくことに対応する。多項式 $P_{i,k}$ は自身の左側にあるふたつの多項式 $P_{i,k-1}$, $P_{i-1,k-1}$ から上記漸化式を通じて定まる「娘」である。

${\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}}$

特徴

ネヴィルのアルゴリズムはラグランジュ補間多項式のある一点 $x$ での値 $L(x)$ を評価する目的に適している。多項式それ自体を求める場合、あるいは複数の点の補間値が必要な場合、ニュートン補間の方が好ましい。補間値を得るためには必ずしもネヴィルのアルゴリズムを最後まで実行する必要はなく、途中で止めることも可能である。

ネヴィルのアルゴリズムは定積分を数値的に求めるロンバーグ積分に用いられる。

参考文献

• Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1992). Numerical Recipes in C: The Art of Scientific Computing (2nd ed.). Cambridge University Press. doi:10.2277/0521431085. ISBN 978-0-521-43108-8 
• Deuflhard, Peter; Hohmann, Andreas (1993). Numerical Analysis in Modern Scientific Computing: An Introduction. Springer. doi:10.1007/978-0-387-21584-6. ISBN 978-0-387-21584-6 
• Stoer, Josef; Bulirsch, R. (2002). Introduction to Numerical Analysis. Springer. doi:10.1007/978-0-387-21738-3. ISBN 978-0-387-21738-3 

関連項目

• ラグランジュ補間
• リチャードソンの補外