Algoritme de Neville

En matemàtiques, el algoritme de Neville és un procediment utilisat para interpolació polinòmica ideat pel matemàtic Eric Harold Neville. Donats n+1 punts, hi ha un polinomi únic de grau ≤ n que passa pels punts donats. L'algoritme de Neville evalua este polinomi.

L'algoritme de Neville es basa en la forma de Newton del polinomi interpolador i en una relació recursiva per a obtindre les diferències dividides. És similar al algoritme de Aitken (cridat aixina per Alexander Aitken), que actualment no s'utilisa.

L'algoritme

Donat un conjunt de senyes format per n+1 punts (x_i, i_i) en a on no hi ha dos x_i iguals, el polinomi d'interpolació és el polinomi p de grau n com a màxim, en la propietat

p(x_i) = i_i per a tot i = 0, …, n

Este polinomi existix i és únic. L'algoritme de Neville evalua el polinomi per a un valor donat qualsevol x.

Suponga's que p_i,j denota el polinomi de grau j−i que passa pels punts (x_k, i_k) per a k = i, i+1, …, j. El p_i,j satisfà la relació de recurrencia

$p_{i,i}(x)=y_i,$	$0\le i\le n,$
$p_{i,j}(x)=\frac{(x-x_j)p_{i,j-1}(x)-(x-x_i)p_{i+1,j}(x)}{x_j-x_i},$	$0\le i<j\le n.$

Esta recurrencia permet calcular p_0,n(x), que és el valor que es busca. Est és l'algoritme de Neville.

Per eixemple, per a n = 4, es pot usar la recurrencia per a omplir el quadro triangular que figura a continuació d'esquerra a dreta.

$p_{0,0}(x)=y_0$
	$p_{0,1}(x)$
$p_{1,1}(x)=y_1$		$p_{0,2}(x)$
	$p_{1,2}(x)$		$p_{0,3}(x)$
$p_{2,2}(x)=y_2$		$p_{1,3}(x)$		$p_{0,4}(x)$
	$p_{2,3}(x)$		$p_{1,4}(x)$
$p_{3,3}(x)=y_3$		$p_{2,4}(x)$
	$p_{3,4}(x)$
$p_{4,4}(x)=y_4$

Este procés permet calcular p_0,4(x), el valor del polinomi que passa pels n+1 punts de senyes (x_i, i_i) en el punt x.

L'algoritme requerix operacions de punt flotant O(n²).

La derivada del polinomi es pot obtindre de la mateixa manera, és dir:

$p{\text{'}}_{i,i}(x)=0,$	$0\le i\le n,$
$p{\text{'}}_{i,j}(x)=\frac{(x_j-x)p{\text{'}}_{i,j-1}(x)-p_{i,j-1}(x)+(x-x_i)p{\text{'}}_{i+1,j}(x)+p_{i+1,j}(x)}{x_j-x_i},$	$0\le i<j\le n.$

Aplicació a la diferenciació numèrica

Lyness i Moldre varen demostrar en 1966 que usant coeficients indeterminats per als polinomis en l'algoritme de Neville, es pot calcular l'expansió de Maclaurin del polinomi d'interpolació final, que produïx aproximacions numèriques per a les derivades de la funció en l'orige. Si ben "este procés requerix més operacions aritmètiques de les que es requerixen en els métodos de diferències finitas", "l'elecció de punts per a l'evaluació de funcions no està restringida de cap manera". També mostren que el seu método pot aplicar-se directament a la solució de sistemes llineals del tipo Vandermonde.

Bibliografia

• ^{[enllaç trencat] [enllaç trencat] [enllaç trencat]}
• JN Lyness i CB Moldre, Sistemes Van Der Monde i diferenciació numèrica, Numerische Mathematik 8 (1966) 458-464 (doi: 10.1007 / BF02166671 )