Calculo Numerico

C´lculo Num´rico III: Pr´ctica 2 a e a
Parte 1: Interpolaci´n a polin´mica global. o o
Dados los nodos de interpolaci´n x1 , x2 , ..., xn , xn+1 distintos, y los valores y1 , y2 , ..., yn , yn+1 o hemos construido el unico polinomio p(x) ∈ Pn (x), de grado menor o igual n, tal que ´ p(xi ) = yi , i = 1, 2, ..., n, n + 1.

El polinomio de interpolaci´n, que es unico, se ha obtenido mediantetres algoritmos diferentes o ´ de construcci´n, usando bases distintas de Pn (x), que son: o 1. Algoritmo de Vandermonde: Se considera la base natural {1, x, x2 , ..., xn }, entonces el polinomio es pn (x) = an+1 + an x + an−1 x2 + ... + a2 xn−1 + a1 xn En este caso se obtiene  xn 1  xn 2   . .  .   xn n xn n+1 el siguiente sistema lineal para obtener los coeficientes      xn−1 . . . x1 1a1 y1 1   a2   y2  xn−1 . . . x2 1 2      . . .  ·  .  =  . . .. . . .   .   .  . . . .   .   .    a n   yn  xn−1 . . . xn 1 n an+1 yn+1 xn−1 . . . xn+1 1 n+1

Esto equivale a la inversi´n de la matriz de Vandermode y el problema con esta matriz es o que est´ mal condicionada y cuando el n´mero de puntos es grande no se puede resolver a u con garant´ de que seaprecisa la soluci´n. ıas o 2. Algoritmo de Lagrange: Se toma la base de los polinomios de Lagrange asociados a x1 , ..., xn , xn+1 , entonces el polinomio es pn (x) = y1 l1 (x) + ... + yn ln (x) + yn+1 ln+1 (x) en donde los polinomios de Lagrange asociados a los nodos x1 , ..., xn , xn+1 , tambi´n llae madas funciones cardinales, vienen dados por
n+1

li (x) =
j=1, j=i

x − xj , xi − xj

i =1, ..., n, n + 1

El problema de esta interpolaci´n reside en que hay que calcular otra vez todas las o funciones de base cada vez que se introduce un nuevo nodo de interpolaci´n. o 1

2 3. Algoritmo de Newton: Base de Newton asociada a los nodos x1 , ..., xn , xn+1 : son los
j

productos Nj (x) =
i=1

(x − xj ) para j = 1, ..., n: polinomio
2 n

pn (x) = c1 + c2 (x − x1 ) + c3

(x− xi ) + ... + cn+1
i=1

(x − xi ).
i=1

Gracias a esta ultima forma de interpolaci´n se observa que se puede extender el n´mero de ´ o u nodos de interpolaci´n aprovechando el trabajo realizado para los nodos previos. o Recordemos que el coeficiente ck de xk es la diferencia dividida de orden k, es decir, ck = f [x1 , ..., xk ].. Estos coeficientes se obtienen de la siguiente forma: Sabemosque f [x1 ] = y1 = c1 y definiendo f [xj ] = yj para j = 1, 2, ..., n, n + 1 podemos construir f [x2 ] − f [x1 ] y2 − y1 = . c2 = f [x1 , x2 ] = x2 − x1 x2 − x1 Esto se puede generalizar como sigue ck = f [x1 , ..., xk−1 , xk ] = f [x2 , ..., xk ] − f [x1 , ..., xk−1 ] xk − x1 (1)

Entonces, podemos usar la siguiente tabla para calcular los coeficientes que nos interesan x1 x2 x3 x4 . . . f [x1 ]f [x2 ] f [x1 , x2 ] f [x3 ] f [x2 , x3 ] f [x1 , x2 , x3 ] f [x4 ] f [x3 , x4 ] f [x2 , x3 , x4 ] f [x1 , x2 , x3 , x4 ] . . . . . . . . . . . .

..

.

que son los que aparecen al final de cada fila. Estos se pueden calcular v´ un algoritmo ıa recursivo, si definimos inicialmente ck = f [xk ] = yk .

Nodos de interpolaci´n y estimaciones del error de interpolaci´n: o o
Denotamos por Xn ={x1 , x2 , ..., xn , xn+1 } ⊂ [a, b] los nodos de interpolaci´n y recordemos que o se tiene la siguiente f´rmula para el error de interpolaci´n: o o f n+1) (ξx ) f (x) − pn (x) = (n + 1)! Tenemos entonces tres posibilidades: a) Nodos uniformemente espaciados en [a, b]: Consideramos xk = a + (k − 1) h, para k = 1, ..., n, n + 1, con h = (b − a)/n. En este caso, una estimaci´n del error viene dadapor: o |f (x) − pn (x)| ≤ hn+1 m´x |f (n+1 (ξ)|, a 4(n + 1) ξ∈[a,b] x ∈ [a, b]. (3)
n+1

(x − xi ).
i=1

(2)

C´lculo Num´rico III - Curso 2011/12 - D. Franco Coronil, F.J. Su´rez Grau, F. Rivero Garv´ a e a ıa.

3 La elecci´n ´ptima de los nodos de interpolaci´n no es la de los nodos espaciados o o o uniformemente, pues se verifica el fen´meno de Runge: c´lculos precisos y correctos...