El algoritmo de Neville

En matemáticas , el algoritmo de Neville es un algoritmo de interpolación polinómica desarrollado por el matemático Eric Harold Neville en 1934. Dados n + 1 puntos, existe un polinomio único de grado ≤ n que pasa por dichos puntos. El algoritmo de Neville evalúa este polinomio.

El algoritmo de Neville se basa en la formulación newtoniana del polinomio interpolador y en la relación de recurrencia para las diferencias divididas . Es similar al algoritmo de Aitken (llamado así en honor a Alexander Aitken ), que actualmente 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 interpolador es el polinomio p de grado como máximo n 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 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

Esta recurrencia 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 rellenar el cuadro triangular que aparece a continuación de izquierda a derecha.

Este proceso produce 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 .

Este algoritmo necesita O ( n ² ) operaciones de punto flotante para interpolar un solo punto, y O ( n ³ ) operaciones de punto flotante para interpolar un polinomio de grado n.

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

En las fórmulas anteriores, si tomamos el grado de los polinomios interpoladores sucesivos d = j − i y cambiamos la notación a p _{d , i} ,

El valor final p _{n ,0} (en esta notación) es el valor interpolado requerido.

Dado que el número de elementos calculados, es decir, el rango de i, disminuye con cada d sucesivo , se puede utilizar una matriz lineal para optimizar la memoria, sobrescribiendo p _i e ignorando d . (Por ejemplo:)

La derivada (utilizando la regla del producto ) se puede calcular de la siguiente manera:

Como antes, p ′ _{n ,0} (en esta notación) es la derivada.

Como esto depende de los valores sucesivos calculados de p también para cada d , puede calcularse dentro del mismo bucle. Si se utilizan matrices lineales para p y p′ por motivos de eficiencia, los valores de p ′ deben calcularse antes de que se sobrescriban los valores de p .

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

• Press, William; Saul Teukolsky; William Vetterling; Brian Flannery (1992). "§3.1 Interpolación y extrapolación polinomial (encriptado)" (PDF) . Numerical Recipes in C. The Art of Scientific Computing (2.ª  ed.). Cambridge University Press. ISBN 978-0-521-43108-8.{{cite book}}: CS1 mantenimiento: estado de la URL ( enlace ) (el enlace no funciona)
• JN Lyness y CB Moler, Sistemas Van Der Monde y diferenciación numérica, Numerische Mathematik 8 (1966) 458-464 ( doi:10.1007/BF02166671 )
• Neville, EH: Interpolación iterativa. J. Indian Math. Soc. 20, 87–120 (1934)

• Weisstein, Eric W. "El algoritmo de Neville" . MathWorld .