Algoritmo de Neville

procedimiento de interpolación polinómica

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

editar

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

p(xi) = yi 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 pi,j denota el polinomio de grado ji que pasa por los puntos (xk, yk) para k = i, i+1, …, j. El pi,j satisface la relación de recurrencia

   
   

Esta recurrencia permite calcular p0,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.

 
 
   
   
     
   
   
 
 

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

El algoritmo requiere operaciones de punto flotante O(n2).

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

   
   

Aplicación a la diferenciación numérica

editar

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

editar
  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

editar

Enlaces externos

editar