Algoritmo de cómputo para la interpolación del polinomio de newton

18.1.5 Algoritmo de cómputo para la interpolación del polinomio de newton

Tres propiedades hacen que la interpolación del polinomio de newton sea muy atractiva para las aplicaciones en la computadora:

1. como en la ecuación (18.7), se puede desarrollar de manera secuencial versiones de orden mayor con la adición de un solo termino a la siguiente ecuación de orden inferior. Esto facilita la evaluación de algunas de las versiones de diferente orden en el mismo programa. Tal capacidad es en especial valiosa cuando el orden del polinomio no es conocido a priori. Al agregar nuevos términos en forma secuencial, podemos determinar cuando se alcanza un punto de disminución de regreso (es decir, cuando la adición de términos de orden superior ya no mejora de manera significativa la estimación, o en ciertas situaciones de hecho la aleja). Las ecuaciones para estimar el error que se analizan en el punto 3 son útiles para visualizar un criterio objetivo para identificar este punto en términos disminuidos.

2. las diferencias divididas finitas que constituyen los coeficientes del polinomio [ecuaciones (18.8) hasta (18.11)] se pueden calcular de manera eficaz. Es decir, como en la ecuación (18.14) y la figura 18.5, se usa diferencias del orden inferior para calcular las de alto orden. Por medio de la información determinada antes, los coeficientes se pueden calcular de manera eficiente. El algoritmo en la figura 18.7 contiene un esquema semejante.

3. el error estimado [véase la ecuación (18.8)] puede ser muy simple de incorporar en un algoritmo de computo debido a la manera secuencial en la cual se construye la predicción.

Figura 18.7

Un algoritmo para el polinomio de interpolación de newton escrito en pseudocódigo.

SUBROUTINE newtint (x, y, n, xi, yint, ea)

LOCAL fdd n,n

DO i= O, y

Fdd i,o= Yi

END DO

DO j= 1, n

DO i= 0, n-j

Fdd ij= (fdd i+1,j-1 –fdd ij-1)/(xi+j-xi)

END DO

END DO

xterm = 1

yint 0= fdd 0, 0

DO order = 1, n

xterm = xterm * (xi-x order-1)

yint2 = yint order-1 + fdd 0,order * xterm

Ea order-1= yint 2-yint order-1

Yint order=yint 2

END order

END newtint

Todas las características anteriores pueden aprovecharse y ser incorporadas en un algoritmo general para implementar el polinomio de newton (véase en la figura 18.7). observe que el algoritmo consiste en dos partes: l primero determina los coeficientes a partir de la ecuación (18.7); el segundo establece las predicciones y su error asociado. La utilidad de este algoritmo se demuestra en el siguiente ejemplo.

Ejemplo 18.5

Estimación del error para determinar el orden adecuado de interpolación

Enunciado del problema. Después de incorporar el error[véase la ecuación (18.18)], utilice el algoritmo de computo que se muestra en la figura 18.7 y la siguiente información para evaluar f(x) = ln x en x = 2:

x f(x) = ln x

0 1

...