Algoritmo de Neville
# 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. 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

    $p_{i,i}(x)=y_{i},\,$$0\leq i\leq 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\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.

    $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 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:

    $p'_{i,i}(x)=0,\,$$0\leq i\leq n,\,$ $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}}},\,$$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.

