ネヴィルのアルゴリズム

ネヴィルのアルゴリズム (テンプレート:Lang-en-short) はラグランジュ補間の計算アルゴリズムのひとつである。テンプレート:仮リンクと近い関係にあり、エリック・ハロルド・ネヴィルによって考案された。

アルゴリズム

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

1. ゼロ次多項式 $P_{i,0}$ ($i=0,1,\cdots ,N$) を
   $P_{i,0}=y_i$
   により定める。
2. 多項式 $P_{i,k}$ を $P_{i,k-1}$ と $P_{i-1,k-1}$ から漸化式
   $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}$ から上記漸化式を通じて定まる「娘」である。 テンプレート:Indent

特徴

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

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

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book

関連項目

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