En matemáticas, el algoritmo de Neville es un algoritmo utilizado para la interpolación polinomial que fue derivado por el matemático Eric Harold Neville en 1934. Dado n + 1 puntos, existe 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 de interpolación y la relación de recursividad para las diferencias divididas . Es similar al algoritmo de Aitken (llamado así por Alexander Aitken ), que hoy en día no se utiliza.
Dado un conjunto de n +1 puntos de datos ( x i , y i ) donde no hay dos x i iguales, el polinomio de interpolación es el polinomio p de grado como máximo n con la propiedad
Este polinomio existe y es único. El algoritmo de Neville evalúa el polinomio en algún punto x .
Sea p i , j el polinomio de grado j − i que pasa por los puntos ( x k , y k ) para k = i , i + 1, ..., j . Los p i , j satisfacen la relación de recurrencia
Con esta recurrencia se puede 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 utilizar la recurrencia para llenar el cuadro triangular siguiente de izquierda a derecha.
Este proceso produce p 0,4 ( x ), el valor del polinomio que pasa por los n + 1 puntos de datos ( xi , yi ) en el punto x .
Este algoritmo necesita O ( n 2 ) operaciones de punto flotante para interpolar un solo punto y O ( n 3 ) operaciones de punto flotante para interpolar un polinomio de grado n.
La derivada del polinomio se puede obtener de la misma manera, es decir:
Lyness y Moler demostraron en 1966 que utilizando 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 que las requeridas 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 se puede aplicar directamente a la solución de sistemas lineales del tipo Vandermonde.