ネヴィルのアルゴリズム

ネヴィルのアルゴリズム[1] (英: Neville's algorithm) はラグランジュ補間の計算アルゴリズムのひとつである。エイトケン補間（英語版）と近い関係にあり[2]、Eric Harold Nevilleによって考案された[3]。

アルゴリズム

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

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

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

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

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 {\displaystyle {\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 {\displaystyle x} での値 L ( x ) {\displaystyle L(x)} を評価する目的に適している[1][10]。多項式それ自体を求める場合、あるいは複数の点の補間値が必要な場合、ニュートン補間の方が好ましい[11]。補間値を得るためには必ずしもネヴィルのアルゴリズムを最後まで実行する必要はなく、途中で止めることも可能である[12]。

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

脚注

注釈

  1. ^ ここでの表記法は Stoer & Bulirsch および Dieflhard & Hofmann に沿うものである。

出典

  1. ^ a b 川又雄二郎、坪井俊、楠岡成雄、新井仁之 編『朝倉　数学辞典』朝倉書店、2016年、575頁。ISBN 9784254111255。 
  2. ^ Press et al., p. 108.
  3. ^ Neville, E. H. (1934). “Iterative interpolation”. J. Indian Math. Soc. 20: 87–120. 
  4. ^ Press et al., pp. 108-109.
  5. ^ Deuflhard & Hofmann, pp. 184-185.
  6. ^ Stoer & Bulirsch, pp. 40-42.
  7. ^ Stoer & Bulirsch, p. 40.
  8. ^ a b Press et al., p. 109.
  9. ^ Stoer & Bulirsch, p. 41.
  10. ^ Stoer & Bulirsch, pp. 40-41.
  11. ^ Stoer & Bulirsch, pp. 43-44.
  12. ^ “Neville algorithm”. 2021年1月11日閲覧。
  13. ^ Press et al., pp. 140-141.

参考文献

  • 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 

関連項目