PDF de programación - Programación: Construcción del polinomio interpolante con la fórmula de Newton

Programación:

Construcción del polinomio interpolante

con la fórmula de Newton

Se recomienda resolver estos ejercicios antes de la clase de programación.

Objetivos. Programar la construcción del polinomio interpolante con la fórmula de New-
ton, usando la tabla de diferencias divididas.

Requisitos. Cálculo de los valores del polinomio en una lista de puntos, multiplicación
de un polinomio por un binonio.

1. Funciones que trabajan con polinomios. Suponemos que los polinomios se guardan
como listas de coeficientes, empezando con el coeficiente de x0. Vamos a usar las funciones
PolValues y MulPolBinom de las clases anteriores:

PolValues de dos argumentos fcoefs, points calcula los valores del polinomio con
coeficientes fcoefs en los puntos de la lista points;

MulPolBinom de dos argumentos fcoefs, b calcula los coeficientes del producto del
polinomio con coeficientes fcoefs por el binomio (x + b). Atención: el binomio
(x + b) está dado no por la lista de sus coeficientes, sino por un número b.

Cálculo de la tabla de las diferencias divididas

2. Definición de las diferencias divididas. Supongamos que x1, . . . , xn son algunos
números diferentes a pares y pertenecientes al dominio de definición de una función f,
y denotemos por y1, . . . , yn a los valores de la función f en estos puntos. Entonces las
diferencias divididas de la función f en estos puntos se definen de manera recursiva:

f[xi, xi+1, . . . , xj−1, xj] :=

f[xi+1, . . . , xj−1, xj] − f[xi, xi+1, . . . , xj−1]

xj − xi

,

(1)

con las condiciones iniciales f[xi] = yi. Suponemos que los números x1, . . . , xn (diferentes
a pares) y los números y1, . . . , yn son nuestros datos iniciales; el problema es calcular las
siguientes diferencias divididas:

f[x1],

f[x1, x2],

f[x1, x2, x3],

f[x1, x2, x3, . . . , xn].

Programación: Polinomio interpolante en forma de Newton, página 1 de 6

3. Escriba las fórmulas recursivas (1) para los siguientes casos particulares (n = 3):

f[x1] = y1

f[x2] = y2

f[x1, x2] =

f[x3] = y3

f[x1, x2] =

f[x1, x2, x3] =

4. Idea recomendada: guardar las diferencias divididas en un arreglo unidimen-
sional borrando los valores que ya no se necesitan. Dados los puntos x1, . . . , xn y
los valores y1, . . . , yn tenemos que calcular sus diferencias divididas. Vamos a guardarlas
en un arreglo dd de longitud n, como se muestra en el siguiente esquema para n = 4.
Están escritos con color gris los contenidos que ya no se cambian, sino se heredan de los
pasos anteriores.

contenido de dd[1] :
contenido de dd[2] :
contenido de dd[3] :
contenido de dd[4] :

Paso 0 Paso 1
f[x1]
f[x1]
f[x2]
f[x3]
f[x4]

f[x1, x2]
f[x2, x3]
f[x3, x4]

Paso 2
f[x1]

f[x1, x2]

Paso 3
f[x1]

f[x1, x2]

f[x1, x2, x3]
f[x2, x3, x4]

f[x1, x2, x3]

f[x1, x2, x3, x4]

En el p-ésimo paso se calculan las diferencias divididas del p-ésimo orden. En casa paso
(es decir, en cada columna) tenemos que empezar desde las últimas entradas. Por ejemplo,
sería un error empezar en el Paso 1 con

dd[2] :=

dd[2] − dd[1]

x[2] − x[1]

porque de esta manera se perdería el valor anterior dd[2] = f[x2], el cual todavía necesi-
tamos para calcular f[x2, x3]. Mencione en el orden correcto los valores que calculamos en
cada paso.

Paso 0 (inicialización): dd es una copia del arreglo y = [y1, . . . , yn].

Paso 1: dd[4] := f[x3, x4], dd[

] := f[

], dd[

] := f[

].

Paso 2: dd[4] := f[x2, x3, x4], dd[

] := f[

].

Paso 3: dd[4] := f[

].

Programación: Polinomio interpolante en forma de Newton, página 2 de 6

5. Tabla de las diferencias divididas, seguimiento por pasos, n = 4.

Paso p = 0.

dd := una copia del arreglo y[1], y[2], y[3], y[4].

Paso p = 1.

dd[4] := (dd[4] − dd[3]) / (x[4] − x[3])

dd[3] := (dd[3] − dd[2]) / (x[3] − x[2])

dd[

] := (dd[

] − dd[

]) / (x[

] − x[

])

Paso p = 2.

dd[

] := (dd[

] − dd[

]) / (x[

] − x[

])

dd[3] := (dd[3] − dd[2]) / (x[3] − x[1])

Paso p = 3.

dd[

] := (dd[

] − dd[

]) / (x[

] − x[

])

6. Tabla de las diferencias divididas, estructura de los ciclos, n = 4.

dd := una copia del arreglo y.

Paso p = 1. Para j := ,

,

:

dd[j] :=

Paso p = 2. Para j := ,

:

dd[j] :=

Paso p = 3. Para j := :

dd[j] :=

Regresar dd.

;

;

;

Programación: Polinomio interpolante en forma de Newton, página 3 de 6

7. Tabla de las diferencias divididas. Escriba una función DivDifTable de dos argu-
mentos points y values que para los puntos points = (x1, . . . , xn) y los valores corres-
pondientes values = (y1, . . . , yn) calcule y regrese la lista de las siguientes diferencias
divididas:

[y1],

[y1, y2],

[y1, y2, y3],

. . . ,

[y1, y2, y3, . . . , yn].

Entrada: points, values.
n := longitud de la lista points;
dd := copia de la lista values;
Para p := ???, ..., ???:

Para j := ???, ..., ???:

dd[j] := (dd[???] - dd[???]) / (points[???] - points[???]);

Regresar dd.

8. Traduzca el pseudocódigo escrito en el ejercicio anterior a algún lenguaje de progra-
mación en el cual va a realizarlo.

9. Prueba de la función DivDifTable. Aplique la función a los puntos 2, 3, −1, 5 y
los valores 3, 11, −9, 69. La respuesta correcta es la lista 3, 8, 1, 1.

10. Número de operaciones. Calcule el número de operaciones de división en el algo-
ritmo DivDifTable. Por tener dos ciclos encajados, obtendremos un polinomio de segundo
grado:

???

???

??? =

p=???

j=???

=

n2 +

n1 +

n0.

?

?

?

Programación: Polinomio interpolante en forma de Newton, página 4 de 6

Construcción del polinomio interpolante

11. Fórmula de Newton para el polinomio interpolante.
Para los puntos x1, . . . , xn y los valores y1, . . . , yn, el polinomio interpolante se puede
construir mediante la siguiente fórmula:

n

k−1

P(x) =

f[x1, . . . , xk]

(x − xj).

k=1

j=1

(2)

Por ejemplo, para n = 3,

P(x) = f[x1] + f[x1, x2](x − x1) + f[x1, x2, x3](x − x1)(x − x2).

12. Ejemplo (n = 4). Escriba la fórmula (2) para n = 4:

P(x) =

13. Truco de Horner. La expresión (2) se puede calcular de manera eficiente, usando el
siguiente truco que se encuentra en trabajos de varios matemáticos, incluso Qin Jiushao,
Paolo Ruffini y William George Horner. Para cualesquiera números a, b, c, u1, u2, u3, u4,

u1 + u2a + u3ab + u4abc = (((u4)c + u3)b + u2)a + u1.

Haga la misma transformación para n = 5:

u1 + u2a + u3ab + u4abc + u5abcd =



P(x) =



14. Representación eficiente de la fórmula de Newton para n = 4.

f[x1, x2, x3, x4](x − x3) + f[x1, x2, x3]

(x − x2) + f[x1, x2]

(x − x1) + f[x1].

Escriba los cálculos por pasos. Invente una numeración conveniente de los pasos.

P(x) := f[x1, x2, x3, x4];

Paso ???:

P(x) := P(x) · (x − x3);

Paso ???:

P(x) := P(x) · (x −

Paso ???:

P(x) := P(x) · (x −

);

);

P(x) := P(x) + f[x1, x2, x3];

P(x) := P(x) +

;

P(x) := P(x) +

.

Programación: Polinomio interpolante en forma de Newton, página 5 de 6

15. ¿Cómo realizar la multiplicación de un polinomio por un binomio? Dada la
lista pcoefs de los coeficientes de un polinomio P(x) y un número a, necesitamos calcular
los coeficientes del producto P(x)(x − a). Recuerde cuál función nos puede servir. ¿Con
qué argumentos tenemos que llamarla? Escriba la respuesta:

16. ¿Cómo realizar la adición de una constante a un polinomio? Dada la lista
pcoefs de los coeficientes de un polinomio P(x) y un número c, necesitamos calcular los
coeficientes de la suma P(x) + c. ¿Cuál coeficiente de la lista pcoefs tenemos que cambiar
y de qué manera? Escriba la respuesta:

17. Construcción del polinomio interpolante con la fórmula de Newton. Esciba
una función NewtonInterpol con argumentos points y values que construya el polino-
mio interpolante correspondiente a los puntos points y valores values. Use las funciones
DivDifTable y MulPolBinom. Esquema del algoritmo:

Entrada: points, values;
dd := DivDifTable(points, values);
pcoefs := lista de un elemento ???;
Para k := ???, ..., ???:

pcoefs := MulPolBinom(pcoefs, ???);
pcoefs[???] += ???;

Regresar pcoefs.

18. Prueba. Usando la función NewtonInterpol calcule los coeficientes del polinomio
interpolante para los puntos 2, 3, −1, 5 y los valores 3, 11, −9, 69. Haga la comprobación
usando la función PolValues.

19. Número de operaciones. Calcule el número de operaciones de multiplicación y
división en el algoritmo NewtonInterpol. Hay que tomar en cuenta el número de ope-
raciones de división que se realizan en DivDifTable y contar de manera correcta todas
las multiplicaciones que se realizan en MulPolBinom. La respuesta es un polinomio de la
variable n. ¿De qué grado es este polinomio?

Programación: Polinomio interpolante en forma de Newton, página 6 de 6