Algoritmo de Neville

En matemáticas, el algoritmo de Neville es un procedimiento utilizado para interpolación polinómica ideado por el matemático Eric Harold Neville.[1]​ Dados n+1 puntos, hay un polinomio único de grado ≤ n que pasa por los puntos dados. El algoritmo de Neville evalúa este polinomio.

El algoritmo de Neville se basa en la forma de Newton del polinomio interpolador y en una relación recursiva para obtener las diferencias divididas. Es similar al algoritmo de Aitken (llamado así por Alexander Aitken), que actualmente no se utiliza.

El algoritmo

Dado un conjunto de datos formado por n+1 puntos (x_i, y_i) en donde no hay dos x_i iguales, el polinomio de interpolación es el polinomio p de grado n como máximo, con la propiedad

p(x_i) = y_i para todo i = 0, …, n

Este polinomio existe y es único. El algoritmo de Neville evalúa el polinomio para un valor dado cualquiera x.

Supóngase que p_i,j denota el polinomio de grado j−i que pasa por los puntos (x_k, y_k) para k = i, i+1, …, j. El p_i,j satisface la relación de recurrencia

${\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_{j}-x_{i}}},\,}$	${\displaystyle 0\leq i<j\leq n.\,}$

Esta recurrencia permite calcular p_0,n(x), que es el valor que se busca. Este es el algoritmo de Neville.

Por ejemplo, para n = 4, se puede usar la recurrencia para llenar el cuadro triangular que figura a continuación de izquierda a derecha.

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

Este proceso permite calcular p_0,4(x), el valor del polinomio que pasa por los n+1 puntos de datos (x_i, y_i) en el punto x.

El algoritmo requiere operaciones de punto flotante O(n^2).

La derivada del polinomio se puede obtener de la misma manera, es decir:

${\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 i<j\leq n.\,}$

Aplicación a la diferenciación numérica

Lyness y Moler demostraron en 1966 que usando coeficientes indeterminados para los polinomios en el algoritmo de Neville, se puede calcular la expansión de Maclaurin del polinomio de interpolación final, que produce aproximaciones numéricas para las derivadas de la función en el origen. Si bien "este proceso requiere más operaciones aritméticas de las que se requieren en los métodos de diferencias finitas", "la elección de puntos para la evaluación de funciones no está restringida de ninguna manera". También muestran que su método puede aplicarse directamente a la solución de sistemas lineales del tipo Vandermonde.

Referencias

1. Didier H. Besset (2001). Object-Oriented Implementation of Numerical Methods: An Introduction with Java & Smalltalk. Morgan Kaufmann. pp. 93 de 766. ISBN 9781558606791. Consultado el 29 de junio de 2020. 

BIbliografía

• Press, William; Saul Teukolsky; William Vetterling; Brian Flannery (1992). «§3.1 Polynomial Interpolation and Extrapolation (encrypted)». Numerical Recipes in C. The Art of Scientific Computing (2nd edición). Cambridge University Press. ISBN 978-0-521-43108-8. doi:10.2277/0521431085.  (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). Press, William; Saul Teukolsky; William Vetterling; Brian Flannery (1992). «§3.1 Polynomial Interpolation and Extrapolation (encrypted)». Numerical Recipes in C. The Art of Scientific Computing (2nd edición). Cambridge University Press. ISBN 978-0-521-43108-8. doi:10.2277/0521431085.  (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). Press, William; Saul Teukolsky; William Vetterling; Brian Flannery (1992). «§3.1 Polynomial Interpolation and Extrapolation (encrypted)». Numerical Recipes in C. The Art of Scientific Computing (2nd edición). Cambridge University Press. ISBN 978-0-521-43108-8. doi:10.2277/0521431085.  (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
• JN Lyness y CB Moler, Sistemas Van Der Monde y diferenciación numérica, Numerische Mathematik 8 (1966) 458-464 (doi: 10.1007 / BF02166671 )

Enlaces externos

• Weisstein, Eric W. «Neville's Algorithm». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Java Code by Behzad Torkian Archivado el 4 de marzo de 2016 en Wayback Machine.

• Datos: Q7884545