ULPGC

Tutorial de Análisis Numérico

Informática
Interpolación : Fórmula de Newton en
Página Web
diferencias divididas
Página de Inicio
Jesús Garcı́a Quesada
Departamento de Informática y Sistemas Contenido
Universidad de Las Palmas de Gran Canaria
35017 Campus de Tafira, España JJ II
Email : [email protected]
J I
2 de Octubre de 2000, v0.3
Página 1 de 19

Volver

Pantalla completa

Cerrar

Salir
 ULPGC

Índice General
1 FÓRMULA DE NEWTON EN
DIFERENCIAS DIVIDIDAS 3
Informática
2 PROBLEMAS 10
Página Web
Soluciones a los Problemas 13
Página de Inicio

Contenido

JJ II

J I

Página 2 de 19

Volver

Pantalla completa

Cerrar

Salir
 ULPGC

1. FÓRMULA DE NEWTON EN
DIFERENCIAS DIVIDIDAS
Sea pk (x) el polinomio de interpolación en los puntos x0 , x1 , . . . , xk (grado máximo = k).
Informática
Considerando pk (x), pk−1 (x) y su diferencia :
Página Web
qk (x) = pk (x) − pk−1 (x)

vemos que para los puntos x0 , x1 , . . . , xk−1 tenemos que : Página de Inicio

pk−1 (xi ) = yi = pk (xi ), 06i6k−1

Contenido
y también que para el siguiente punto xk tenemos que pk (xk ) = yk , sin conocerse el
valor a priori que pueda tener pk−1 (xk ). JJ II
Por tanto, el polinomio qk (x) verifica :
J I
qk (xi ) = pk (xi ) − pk−1 (xi ) = yi − yi = 0, 06i6k−1
Ahora bien, qk (x) es un polinomio de grado máximo k ya que es la resta de dos Página 3 de 19
polinomios, pk (x) de grado k y pk−1 (x) de grado k − 1 y según se acaba de ver se anula
en los k puntos anteriores tiene con lo cual se puede expresar de la siguiente forma : Volver
k−1
Y
qk (x) = ak (x − x0 )(x − x1 ) · · · (x − xk−1 ) = ak (x − xi ) Pantalla completa
i=0

Por otra parte, en el punto xk se cumple : Cerrar

Salir
 ULPGC

qk (xk ) = pk (xk ) − pk−1 (xk ) = ak (xk − x0 )(xk − x1 ) · · · (xk − xk−1 )

y despejando entonces ak de ésta última identidad tenemos :

yk − pk−1 (xk ) Informática

ak =
(x − x0 )(x − x1 ) · · · (x − xk−1 )
Página Web
con lo cual podemos poner :

pk (x) = pk−1 (x) + qk (x) Página de Inicio

donde lo que parece complicado es calcular el ak , que serı́a el coeficiente de xk en el

Contenido
polinomio pk (x) pero para esto se puede utilizar las diferencias divididas:

Definición 1. Dada la función f de la cual se conoce su valor en los puntos x0 , x1 , . . . , xk , JJ II

se llama diferencia dividida de f en los puntos x0 , x1 , . . . , xk al valor ak = f [x0 , x1 , · · · , xk ]
y se calcula recursivamente como sigue :
J I
f [xi ] = f (xi ) = yi
f [xi+1 ] − f [xi ] Página 4 de 19
f [xi , xi+1 ] =
xi+1 − xi
Volver
f [xi+1 , xi+2 , · · · , xi+k ] − f [xi , xi+1 , · · · , xi+k−1 ]
f [xi , xi+1 , · · · , xi+k ] =
xi+k − xi
Pantalla completa

Cerrar

Salir
 ULPGC

Lema 1.1.
f [xi+1 , xi+2 , · · · , xi+k ] − f [xi , xi+1 , · · · , xi+k−1 ]
f [xi , xi+1 , · · · , xi+k ] =
xi+k − xi
Demostración. Sea pj (x) el polinomio de grado 6 j que coincide con f (x) en los puntos Informática
xi , xi+1 , . . . , xi+j y sea qk−1 (x) el polinomio de grado 6 k − 1 que coincide con f (x) en
los puntos xi+1 , xi+2 , . . . , xi+k . Entonces : Página Web
x − xi xi+k − x
p(x) = qk−1 (x) + pk−1 (x)
xi+k − xi xi+k − xi Página de Inicio
es un polinomio de grado 6 k que verifica :
Contenido
p(xj ) = f (xj ), para j = i, i + 1, . . . , i + k
ya que : JJ II

xi+k − xi J I
Para i : p(xi ) = pk−1 (xi ) = yi = f (xi )
xi+k − xi
xi+k − xi Página 5 de 19
Para i + k : p(xi+k ) = qk−1 (xi+k ) = yi+k = f (xi+k )
xi+k − xi
y para cada j = i + 1, . . . , i + k − 1 : Volver
xj − xi xi+k − xj
p(xj ) = qk−1 (xj ) + pk−1 (xj ) =
xi+k − xi xi+k − xi Pantalla completa
 
xj − xi xi+k − xj xi+k − xi
+ yj = yj = yj
xi+k − xi xi+k − xi xi+k − xi Cerrar

Salir
 ULPGC

Por tanto, por la unicidad del polinomio de interpolación, tendremos que p(x) = pk (x) y
entonces
f [xi , xi+1 , · · · , xi+k ] = coeficiente término principal de pk (x) =
coeficiente término principal de qk−1 (x) coeficiente término principal de pk−1 (x)
= − = Informática
xi+k − xi xi+k − xi
f [xi+1 , xi+2 , · · · , xi+k ] − f [xi , xi+1 , · · · , xi+k−1 ] Página Web
=
xi+k − xi
Página de Inicio

¿Cómo organizar el cálculo de la tabla de diferencias divididas? Contenido

Ejemplo. El cálculo de las diferencias divididas para cuatro puntos se ordenarı́a como
sigue : JJ II
Solución:
x0 −→ y0 = f [x0] &
J I
f [x0 , x1] &
x1 −→ y1 = f [x1 ] % f [x0 , x1 , x2] & Página 6 de 19
f [x1 , x2 ] % f [x0 , x1 , x2 , x3]
x2 −→ y2 = f [x2 ] f [x1 , x2 , x3 ] % Volver
f [x2 , x3 ]
x3 −→ y3 = f [x3 ] Pantalla completa


Cerrar

Salir
 ULPGC

Podemos abordar entonces el cálculo del polinomio de interpolación en los puntos

(x0 , y0 ), (x1 , y1 ),(x2 , y2 ),. . . , (xn , yn ) de la siguiente forma :

p0 (x) = a0 = f [x0 ] = f (x0 ) = y0

Informática
p1 (x) = p0 (x) + a1 (x − x0 ) = f [x0 ] + a1 (x − x0 ) = f [x0 ] + f [x0 , x1 ](x − x0 )
p2 (x) = p1 (x) + a2 (x − x0 )(x − x1 ) = f [x0 ] + a1 (x − x0 ) + a2 (x − x0 )(x − x1 ) = Página Web
= f [x0 ] + f [x0 , x1 ](x − x0 ) + f [x0 , x1 , x2 ](x − x0 )(x − x1 )
.. Página de Inicio
.
pn (x) = a0 + a1 (x − x0 ) + a2 (x − x0 )(x − x1 ) + · · · + an (x − x0 )(x − x1 ) . . . (x − xn−1 ) =
Contenido
pn (x) = f [x0 ] + f [x0 , x1 ](x − x0 ) + f [x0 , x1 , x2 ](x − x0 )(x − x1 ) + · · ·
+ f [x0 , x1 , · · · , xn ](x − x0 )(x − x1 ) . . . (x − xn−1 ) JJ II
o también de forma más concisa :
J I
n
X i−1
Y
pn (x) = f [x0 , x1 , . . . , xi ] (x − xj )
Página 7 de 19
i=0 j=0

que se denomina fórmula de interpolación de Newton en diferencias divididas.

Volver
Para la evaluación del polinomio de interpolación en su forma de Newton en diferencias
divididas pn (x) = f [x0 ] + f [x0 , x1 ](x − x0 ) + · · · + f [x0 , x1 , . . . , xn ](x − x0 )(x − x1 ) · · · (x −
xn−1 ) usaremos el anidamiento del esquema de Ruffini–Horner : Pantalla completa

pn (z) = (· · · (an (z − xn−1 ) + an−1 )(z − xn−2 ) + · · · + a1 )(z − x0 ) + a0 Cerrar

Salir
 ULPGC

para la evaluación en un punto z, y donde se ha puesto ak = f [x0 , . . . , xk ].

Obsérvese que se necesitan n productos y 2n? sumas/restas.
Ejemplo. Obtener una fórmula para la suma de los cuadrados de los primeros números
naturales.
n Informática
k 2 = n(n+1)(2n+1)
P
Solución: Sabemos que 6
y como queremos obtenerla por interpolación
k=1
construimos un conjunto de valores según los diferentes valores de n. Como el polinomio Página Web
ha de ser el mismo para cualquier posible ordenación de los puntos, elegimos el siguiente
orden: Página de Inicio

n y f [xi , xi+1 ] f [xi , xi+1 , xi+2 ] f [xi , . . . , xi+3 ] f [xi , . . . , xi+4 ]

Contenido
3 −→ 14
9
2 −→ 5 23/6 JJ II
50/3 1/3
5 −→ 55 19/6 0 J I
54/4 1/3
1 −→ 1 23/6
Página 8 de 19
29/3
4 −→ 30
Volver

Pantalla completa

Cerrar

Salir
 ULPGC

El polinomio es por tanto:

23 1
p(x) =14 + 9(x − 3) + (x − 3)(x − 2) + (x − 3)(x − 2)(x − 5) =
6 3 (1)
3 2
2x + 3x + 6x x(x + 1)(2x + 1) Informática
= =
6 6
como cabrı́a esperar.  Página Web

Ejemplo. Obtener por interpolación el valor para x = 3 conocidos los valores x0 = 0, y0 = −1;
x1 = 1, y1 = 0; x2 = 2, y2 = 7; x3 = 4, y3 = 63. Página de Inicio
Solución:
Por la fórmula de Newton tenemos, sustituyendo ya el valor x = 3 : Contenido

x y f [xi , xi+1 ] f [xi , xi+1 , xi+2 ] f [xi , . . . , xi+3 ]

0 −1 JJ II
1
1 0 3 J I
7 1
2 7 7 Página 9 de 19
28
4 63
Volver
El valor del polinomio es por tanto:
Pantalla completa
p(3) = −1 + 1.(3) + 3.3.(2) + 1.(3).(2).(1) = 26 (2)
que es lo mismo que se obtuvo con Lagrange, lógicamente. 
Cerrar

Salir
 ULPGC

2. PROBLEMAS
Problema 1. Los siguientes datos están tomados de un polinomio de grado 6 5. ¿Cúal
es el grado del polinomio?
xi −2 −1 0 1 2 3
yi −5 1 1 1 7 25 Informática

Problema 2. Determinar el número de sumas/restas y el número de productos/divisiones Página Web

que se necesitan para:
1. calcular las diferencias divididas para n + 1 nodos. Página de Inicio

2. calcular (eficientemente) el polinomio de Newton, una vez se conocen las diferencias

Contenido
divididas.
Problema 3. Construir la tabla de diferencias divididas para los puntos JJ II
x −0.2 0.5 0.1 0.7 0.0
f (x) 1.3940 1.0025 1.1221 1.0084 1.1884 J I
y usarla para estimar f (0.15) usando:
Página 10 de 19
(a) el polinomio de grado dos obtenido con los tres primeros puntos
(b) el polinomio de grado dos obtenido con los tres últimos puntos Volver
(c) el polinomio de grado tres obtenido con los cuatro primeros puntos
(d) el polinomio de grado tres obtenido con los cuatro últimos puntos Pantalla completa
(e) el polinomio de grado cuatro
Cerrar

Salir
 ULPGC

Referencias
[Act90] F.S. Acton. Numerical Methods That (Usually) Work. The Mathematical As-
sociation of America, Washington, 1990.

[Atk89] K. E. Atkinson. An Introduction to Numerical Analysis. John Wiley, New York, Informática
2nd. edition, 1989.
Página Web
[BF80] R.L. Burden and D. Faires. Análisis Numérico. Grupo Editorial Iberoameri-
cana, México, 1980. Página de Inicio

[CC89] S.C. Chapra and R.P. Canale. Numerical Methods for Engineers. McGraw-Hill
International, New York, second edition, 1989. Contenido

[CdB80] S. D. Conte and C. de Boor. Elementary Numerical Analysis: An Algorithmic JJ II

Approach. McGraw–Hill, New York, third edition, 1980.

[DB74] Germund Dahlquist and Åke Björck. Numerical Methods. Prentice-Hall, En- J I
glewood Cliffs, New Jersey, 1974.
Página 11 de 19
[Fad59] V.N. Faddeeva. Computational Methods of Linear Algebra. Dover Publications,
Inc, New York, 1959.
Volver
[Frö79] C.-E. Fröberg. Introduction to Numerical Analysis. Adison–Wesley, Reading,
Massachusetts, 2nd. edition, 1979.
Pantalla completa
[GW89] C.F. Gerald and P.O. Wheatley. Applied Numerical Analysis. Addison–Wesley
Publishing Co., Reading, Massachusets, fourth edition, 1989. Cerrar

Salir
 ULPGC

[Hen72] P. Henrici. Elementos de Análisis Numérico. Ed. Trillas, México, 1972.

[Hil74] F. B. Hildebrand. Introduction to Numerical Analysis. McGraw–Hill, New

York, second edition, 1974.

[KC94] D. Kincaid and W. Cheney. Análisis Numérico : las matemáticas del cálculo Informática
cientı́fico. Addison-Wesley Iberoamericana, 1994.
Página Web
[Mar87] M. J. Maron. Numerical Analysis: A Practical Approach. Macmillan Publishing
Co., New York, second edition, 1987. Página de Inicio

[ML91] M. J. Maron and R. J. Lopez. Numerical Analysis: A Practical Approach.

Wadsworth, Belmont, California, third edition, 1991. Contenido

[RR78] Anthony Ralston and Philip Rabinowitz. A First Course in Numerical Analysis.
JJ II
McGraw-Hill, New York, 2nd. edition, 1978.

[Sch89] H.R. Schwarz. Numerical Analysis. John Wiley & Sons, Chichester, 1989. J I
[Wer84] W. Werner. Mathematics of Computation, 43:205–217, 1984.
Página 12 de 19
[YG73a] David M. Young and R.T. Gregory. A Survey of Numerical Mathematics, vol-
ume I. Dover Publications, New York, 1973. Volver

[YG73b] David M. Young and R.T. Gregory. A Survey of Numerical Mathematics, vol-
ume II. Dover Publications, New York, 1973. Pantalla completa

Cerrar

Salir
 ULPGC

Soluciones a los Problemas

Problema 1.
La tabla de diferencias divididas es:

x y f [xi , xi+1 ] f [xi , xi+1 , xi+2 ] f [xi , . . . , xi+3 ] f [xi , . . . , xi+4 ] Informática
−2 −5
Página Web
6
−1 1 3
0 1 Página de Inicio
0 1 0 0
0 1 Contenido
1 1 3 0
6 1 JJ II
2 7 6
18
3 25 J I

y por tanto el polinomio tiene grado tres, siendo éste: Página 13 de 19

p(x) = − 5 + 6(x + 2) + 3(x + 2)(x + 1) + 1(x + 2)(x + 1)x = Volver

= x3 − x + 1
Pantalla completa
como se puede constatar a partir de los nodos dados.
J Cerrar

Salir
 ULPGC

Problema 2. Probar que es una fórmula de O(n2 ):

El número de sumas/restas necesarias para calcular las diferencias divididas es n(n+1)
y el de divisiones es la mitad n(n + 1)/2.
Para evaluar eficientemente el polinomio en su forma de Newton:
Informática
pn (x) = f [x0 ] + f [x0 , x1 ](x − x0 ) + · · · + f [x0 , x1 , . . . , xn ](x − x0 )(x − x1 ) · · · (x − xn−1 ) Página Web

son necesarias 2n sumas/restas y n productos, ya que se considera el anidamiento del

esquema de Ruffini–Horner : Página de Inicio

pn (z) = (· · · (an (z − xn−1 ) + an−1 )(z − xn−2 ) + · · · + a1 )(z − x0 ) + a0 Contenido

para la evaluación en un punto z, y donde es ak = f [x0 , . . . , xk ].

J JJ II

J I

Página 14 de 19

Volver

Pantalla completa

Cerrar

Salir
 ULPGC

Problema 3(a) 1.0919



Informática

Página Web

Página de Inicio

Contenido

JJ II

J I

Página 15 de 19

Volver

Pantalla completa

Cerrar

Salir
 ULPGC

Problema 3(b) 1.0973



Informática

Página Web

Página de Inicio

Contenido

JJ II

J I

Página 16 de 19

Volver

Pantalla completa

Cerrar

Salir
 ULPGC

Problema 3(c) 1.0941



Informática

Página Web

Página de Inicio

Contenido

JJ II

J I

Página 17 de 19

Volver

Pantalla completa

Cerrar

Salir
 ULPGC

Problema 3(d) 1.0951



Informática

Página Web

Página de Inicio

Contenido

JJ II

J I

Página 18 de 19

Volver

Pantalla completa

Cerrar

Salir
Problema 3(e) 1.0920. El valor real es f (0.15) = 1.0956, ya que los valores corresponden
a la función:
1
f (x) =
sen(x + 1)