Nevillův algoritmus - Nevilles algorithm - Wikipedia

V matematice Nevillův algoritmus je algoritmus používaný pro polynomiální interpolace který odvodil matematik Eric Harold Neville^{[Citace je zapotřebí ]}. Dáno n + 1 bod, existuje jedinečný polynom stupně ≤ n který prochází danými body. Nevilleův algoritmus vyhodnocuje tento polynom.

Nevilův algoritmus je založen na Newtonova forma interpolačního polynomu a relace rekurze pro rozdělené rozdíly. Je to podobné jako Aitkenův algoritmus (pojmenoval podle Alexander Aitken ), který se dnes nepoužívá.

Algoritmus

Vzhledem k souboru n+1 datové body (X_i, y_i) kde žádné dva X_i jsou stejné, interpolační polynom je polynom p stupně nanejvýš n s majetkem

p(X_i) = y_i pro všechny i = 0,…,n

Tento polynom existuje a je jedinečný. Nevilův algoritmus v určitém okamžiku vyhodnotí polynom X.

Nechat p_i,j označit polynom stupně j − i který prochází body (X_k, y_k) pro k = i, i + 1, …, j. The p_i,j uspokojit relaci opakování

${ displaystyle p_ {i, i} (x) = y_ {i}, ,}$	${ displaystyle 0 leq i leq n, ,}$
${ displaystyle p_ {i, j} (x) = { frac {(x-x_ {j}) p_ {i, j-1} (x) - (x-x_ {i}) p_ {i + 1 , j} (x)} {x_ {i} -x_ {j}}}, ,}$	${ displaystyle 0 leq já$

Toto opakování lze vypočítatp_0,n(X), což je hledaná hodnota. Toto je Nevillův algoritmus.

Například pro n = 4, lze použít opakování k vyplnění trojúhelníkového tabla níže zleva doprava.

${ displaystyle p_ {0,0} (x) = y_ {0} ,}$
	${ displaystyle p_ {0,1} (x) ,}$
${ displaystyle p_ {1,1} (x) = y_ {1} ,}$		${ displaystyle p_ {0,2} (x) ,}$
	${ displaystyle p_ {1,2} (x) ,}$		${ displaystyle p_ {0,3} (x) ,}$
${ displaystyle p_ {2,2} (x) = y_ {2} ,}$		${ displaystyle p_ {1,3} (x) ,}$		${ displaystyle p_ {0,4} (x) ,}$
	${ displaystyle p_ {2,3} (x) ,}$		${ displaystyle p_ {1,4} (x) ,}$
${ displaystyle p_ {3,3} (x) = y_ {3} ,}$		${ displaystyle p_ {2,4} (x) ,}$
	${ displaystyle p_ {3,4} (x) ,}$
${ displaystyle p_ {4,4} (x) = y_ {4} ,}$

Tento proces se získá p_0,4(X), hodnota polynomu procházejícího n + 1 datové body (X_i, y_i) na místě X.

Tento algoritmus potřebuje Ó (n²) operace s plovoucí desetinnou čárkou.

Derivaci polynomu lze získat stejným způsobem, tj.:

${ displaystyle p '_ {i, i} (x) = 0, ,}$	${ displaystyle 0 leq i leq n, ,}$
${ displaystyle p '_ {i, j} (x) = { frac {(x_ {j} -x) p' _ {i, j-1} (x) -p_ {i, j-1} ( x) + (x-x_ {i}) p '_ {i + 1, j} (x) + p_ {i + 1, j} (x)} {x_ {j} -x_ {i}}}, ,}$	${ displaystyle 0 leq já$

Aplikace na numerickou diferenciaci

Lyness a Moler v roce 1966 ukázali, že pomocí neurčitých koeficientů pro polynomy v Nevillově algoritmu lze vypočítat Maclaurinovu expanzi konečného interpolačního polynomu, která poskytuje numerické aproximace pro derivace funkce na počátku. I když „tento proces vyžaduje více aritmetických operací, než je požadováno v metodách konečných rozdílů“, „výběr bodů pro vyhodnocení funkce není nijak omezen“. Ukazují také, že jejich metoda může být aplikována přímo na řešení lineárních systémů typu Vandermonde.

Reference

• Press, William; Saul Teukolsky; William Vetterling; Brian Flannery (1992). „§3.1 Polynomiální interpolace a extrapolace (šifrovaná)“ (PDF). Numerické recepty v C. The Art of Scientific Computing (2. vyd.). Cambridge University Press. doi:10.2277/0521431085. ISBN  978-0-521-43108-8. (odkaz je špatný)
• J. N. Lyness a C. B. Moler, Van Der Monde Systems and Numerical Differential, Numerische Mathematik 8 (1966) 458-464 (doi: 10.1007 / BF02166671 )
• Neville, E.H .: Iterativní interpolace. J. Indian Math. Soc.20, 87–120 (1934)

externí odkazy

• Weisstein, Eric W. „Nevillův algoritmus“. MathWorld.
• Kód Java Behzad Torkian