Criterios Para Interpolar

CRITERIOS PARA INTERPOLAR Prof. Andr´es L. Granados M. Abril, 2015. Versi´ on Julio, 2017. INTRODUCCION Se ha desarrollado un algoritmo de interpolaci´ on usando los polinomios de Newton en diferencias divididas, de tal forma que, en principio, es libre del orden o grado del polinomio. Para hacer eficientemente la interpolaci´ on se han usado dos criterios que hacen de ´esta la m´as consistente posible con los puntos discretos dados. Estos criterios son el de Simetr´ıa y el de Monoton´ıa. Estos criterios, aplicados en conjunto, permiten determinar el grado del polinomio o´ptimo a utilizar durante una interpolaci´ on. POLINOMIOS DE INTERPOLACION Sean (x0 , f (x0 )), (x1 , f (x1 )), (x2 , f (x2 )) hasta (xn , f (xn )) los n + 1 puntos discretos que representan a una funci´ on y = f (x). Como se sabe, existe un u ´ nico polinomio y = Pn (x) de grado n que pasa por los n + 1 puntos mencionados. Estos polinomios son adecuados para realizar estimaciones de la funci´ on y = f (x) para un valor x cualquiera perteneciente al intervalo [x0 , x1 , x2 , x3 , . . . , xn ] que contiene a todos los puntos, estando los valores xi no necesariamente ordenados, ni habiendo valores repetidos. A este proceso se le denomina “Interpolaci´ on”. Si el valor x est´a fuera del intervalo de los puntos entonces el proceso se denomina “Extrapolaci´on”. Diferencia Divididas Las diferencias divididas [Carnahan et al.,1969] simbolizadas por f [ · ] se definen de manera recurrente de la siguiente forma f [x0 ] = f (x0 ) f [x1 , x0 ] =

f [x2 , x1 , x0 ] =

f [x3 , x2 , x1 , x0 ] =

f [xn , xn−1 , . . . , x1 , x0 ] =

(1.a)

f [x1 ] − f [x0 ] x1 − x0

(1.b)

f [x2 , x1 ] − f [x1 , x0 ] x2 − x0

(1.c)

f [x3 , x2 , x1 ] − f [x2 , x1 , x0 ] x3 − x0

f [xn , xn−1 , . . . , x2 , x1 ] − f [xn−1 , xn−2 , . . . , x1 , x0 ] xn − x0

(1.d)

(1.e)

Las diferencias divididas cumplen con la propiedad (conmutatividad) f [xn , xn−1 , . . . , x1 , x0 ] = f [x0 , x1 , . . . , xn−1 , xn ]

∀n ∈ N

(2)

Esta propiedad, expresada para cualquier n, lo que significa es que, sin importar el orden en que est´an los valores xi dentro de una diferencia dividida, el resultado es siempre el mismo. Dicho de otra forma concisa, la diferencia dividida es invariante a cualquier permutaci´ on de sus argumentos. Esta propiedad la hace adecuada para los c´ alculos, como veremos en adelante. Una forma de expresar todas las diferencias divididas posibles de generar mediante, por ejemplo, un conjunto de cuatro puntos (x0 , f (x0 )), (x1 , f (x1 ), (x2 , f (x2 )), (x3 , f (x3 )) y (x4 , f (x4 )), no necesariamente ordenados, es lo que se denomina el Diagrama Romboidal de diferencias divididas. Para el ejemplo propuesto 1

se tiene que el diagrama romboidal se representa como x0

f [x0 ]

x1

f [x1 ]

x2

f [x2 ]

x3

f [x3 ]

x4

f [x4 ]

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

f [x0 , x1 , x2 ]

f [x0 , x1 , x2 , x3 ]

f [x1 , x2 , x3 ]

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

f [x1 , x2 , x3 , x4 ]

f [x2 , x3 , x4 ]

(3)

Se puede observar que para obtener cualquier diferencia dividida en un v´ertice de un tri´angulo imaginario, basta con restar las diferencias divididas contiguas y dividirla entre la resta de los valores extremos de x de la base de dicho tri´ angulo. Manipulaci´ on algebra´ıca de la diferencias de o´rdenes crecientes conlleva, mediante inducci´ on, a una forma sim´etrica similar para la k-´esima diferencia dividida, en t´ermino de los argumentos xi y de los valores funcionales f (xi ). Esta forma sim´etrica puede ser escrita de manera compacta como f [x0 , x1 , x2 , . . . , xk−1 , xk ] =

k


k

f (xi )

j=0 (xi j
=i

i=0

− xj )

(4)

Para intervalos regulales en x, donde los xi est´an ordenados, se define la diferencia adelantada ∆k fi , tal que (5) ∆k fi = k! hk f [xi , xi+1 , xi+2 , . . . , xi+k−1 , xi+k ] donde h es el tama˜ no del intervalo en x consecutivos (h = xi+1 − xi ). Se ordenan de forma romboidal al igual que antes, s´ olo que no son divididas, por ello el factor k! hk . Polinomios de Newton Los polinomios de Newton Pn (x) de grado n en diferencias divididas [Carnahan et al.,1969], como se dijo antes, permiten hacer estimaciones de la funcion y = f (x) de puntos intermedios en la forma f (x) = Pn (x) + Rn (x)

(6)

donde Pn (x) es el polinomio de grado n Pn (x) =f [x0 ] + (x − x0 ) f [x0 , x1 ] + (x − x0 )(x − x1 ) f [x0 , x1 , x2 ] + · · · + (x − x0 )(x − x1 )(x − x2 ) · · · (x − xn−1 ) f [x0 , x1 , x2 , . . . , xn−1 , xn ] =

n k−1


(x − xj ) f [x0 , x1 , x2 , . . . , xk−1 , xk ]

(7)

k=0 j=0

on y la funci´ on Rn (x) es el error cometido en la interpolaci´ Rn (x) =

n 

(x − xj ) f [x0 , x1 , x2 , . . . , xn−1 , xn , x]

j=0

=

n 

(x − xj )

j=0

f (n+1) (ξ) (n + 1)!

ξ ∈ [x0 , x1 , . . . , xn−1 , xn ]

(8)

siendo ξ el valor comprendido entre el menor y mayor de los valores {x0 , x1 , . . . , xn−1 , xn }. Naturalmente Rn (xi ) = 0 para i = 1, 2, 3, . . . , n, ya que el polinomio pasa por cada uno de los puntos (xi , f (xi )). Cuando 2

el l´ımite superior de una productoria es menor que el l´ımite inferior, como ocurre con el primer t´ermino de (7), el resultado de dicha productoria es la unidad. Un ejemplo sencillo es la par´abola que pasa por los tres puntos (a, f (a)), (b, f (b)) y (c, f (c)) P2 (x) = f [a] + (x − a)f [a, b] + (x − a)(x − b)f [a, b, c]

(9)

donde f [a, b] es la pendiente de recta entre los puntos a y b y f [a, b, c] es la curvatura de la par´ abola, que si es positiva es abierta hacia arriba y si es negativa es abierta hacia abajo. Para intervalos regulares, el polinomio de Newton en diferencias divididas (7) se convierte en Pn (x) =

n  
s

k

k=0

∆k f0

(10)

denominado polinomio de Newton-Gregory progresivo y donde el n´ umero combinatorio significa   x − x0 Γ(s + 1) s s= = k Γ(s − k + 1) Γ(k + 1) h

(11)

Particularmente, Γ(k + 1) = k! por ser k un entero positivo y, aunque la funci´ on Γ(s) no es un factorial siempre, se satisface Γ(s + 1)/Γ(s − k + 1) = s(s − 1)(s − 2) . . . (s − k + 1) [Gerald,1970]. La expresi´on (10) se ha obtenido de substituir k−1 

Γ(s + 1) = k! hk (x − xj ) = h Γ(s − k + 1) j=0 k

y (5), despejada en f [ · ] para i = 0, en (7). Para intervalos regulares, el error (8) se convierte en   s Rn (x) = hn+1 f (n+1) (ξ) n+1

  s k

ξ ∈ [x0 , x1 , . . . , xn−1 , xn ]

(12)

(13)

teniendo ξ el mismo significado que antes. Los polinomios para intervalos regulares se muestran aqu´ı s´olo como referencia. En general, los datos utilizados en interpoleci´ on no estar´ an ordenados, ni ser´an regulares. Al final se usan los polinomios en diferencias divididas por la raz´ on adicional justificada a continuaci´ on. Polinomios de Lagrange Los polinomios de Lagrange [Hildebrand,1956] son otra forma de expresar los mismos polinomios Pn (x) de la ecuaci´on (7), pero a trav´es de (4). De manera que se tiene [Carnahan et al.,1969] Pn (x) =

n


Li (x) f (xi )

(14)

i=0

donde Li (x) =

n  (x − xj ) (x i − xj ) j=0

(15)

j
=i

El error Rn (x) contin´ ua siendo el mismo que la expresi´on (8). Cada valor funcional f (xi ) incluido en la expresi´on (14) es multiplicado por Li (x), que son todos polinomios de grado n. Por ello reciben el nombre de multiplicadores de Lagrange. Un incoveniente que tienen los polinomios de Lagrange es que, para aumentar el grado del polinomio en una unidad, implica el proceso engorroso de agregar un factor adicional a cada multiplicador (productos), y hay que calcular todo de nuevo. Este inconveniente no lo presenta los polinomios de Newton, donde para aumentar un grado al polinomio, s´ olo hay que agregar un punto y calcular un t´ermino adicional (sumas), y todos los c´alculos anteriores siguen sirviendo. 3

CRITERIOS PARA INTERPOLAR A continuaci´ on se describen los dos criterios utilizados en el algoritmo: simetr´ıa y monoton´ıa. Luego se formula como se acoplan en el algoritmo. Simetr´ıa El criterio de la simetr´ıa consiste en escoger la distribuci´on de puntos lo m´ as sim´etricamente posible, alrededor de donde se desee interpolar. Esto se puede hacer de dos maneras: mediante el n´ umero de puntos o mediante la distancia de influencia, a uno y otro lado del punto donde se vaya a interpolar. En el caso de intervalos irregulares, la segunda opci´ on se convierte en un criterio de Proximidad, que no requiere necesariamente que los puntos est´en ordenados. En el caso de intervalos regulares una de las formas implica a la otra. En cualquier caso, el n´ umero de puntos pr´ oximos lo determina el criterio de monoton´ıa descrito abajo. En los extremos del intervalo que contiene a los puntos, a veces es imposible seguir el criterio de simetr´ıa de forma estricta, y entonces se hace necesario en su lugar seguir el criterio de proximidad, si se desea alcanzar un mayor orden de monoton´ıa como se explica abajo. El criterio de simetr´ıa tiene otra ventaja. Por ejemplo, en los esquemas de diferencias finitas centradas, las formulaciones presentan un menor error, que cuando no lo son, usando inclusive el mismo n´ umero de puntos. Monoton´ıa El criterio de la monoton´ıa se basa en la definici´ on de monoton´ıa de una funci´ on: Una funci´ on se dice que es mon´otona hasta el orden m, en un determinado intervalo, si todas sus derivadas de hasta dicho orden conservan siempre su signo en dicho intervalo. En otras palabras, una funci´ on continua f (x) es mon´otona de orden m en un intervalo [a, b], si f  (x) = 0

f  (x) = 0

f  (x) = 0

···

f (m) (x) = 0 f (m+1) (x) = 0

para todo

x ∈ [a, b]

para alg´ un x ∈ [a, b]

(16)

En el ejemplo mostrado en (9), la par´ abola tiene monoton´ıa de orden 2 en los intervalos (−∞, v) y (v, ∞), separadamente, donde v = 12 { a + b − f [a, b]/f [a, b, c] } es la localizaci´on del v´ertice de dicha par´abola. Las diferencias divididas son proporcionales a las derivadas en su entorno, tal como lo indica la siguiente relaci´on reflejada en (8) f [x0 , x1 , x2 , . . . , xn−1 , xn , x] =

f (n+1) (ξ) (n + 1)!

ξ ∈ [x0 , x1 , . . . , xn−1 , xn , x]

(17)

Por ello, el criterio de monoton´ıa implica escoger hasta el mayor orden en las diferencias divididas que tengan igual signo, por columna, en el diagrama romboidal. La u ´ltima diferencia dividida a evitar a partir de aqu´ı, junto con el u ´ltimo punto que la origin´ o, deber´ a tener signo opuesto a todas las dem´as diferencias divididas vecinas del mismo orden (en la misma columna). Recordemos que cada punto agregado al esquema de interpolaci´ on tambi´en agrega una diagonal descendiente-ascendiente al digrama romboidal, si el punto agregado est´a por arriba-debajo. Esto significa que el criterio de la monoton´ıa acepta polinomios de interpolaci´on hasta el grado m = n. La falta de monoton´ıa en las interpolaciones implica que pueden producirse oscilaciones indeseables de la funci´on alrededor o entre los puntos dados. Como el u ´ltimo punto agregado es el m´ as lejano, por el criterio de la simetr´ıa, no existe inconveniente en dejarlo (no recomendado), ya que los c´alculos est´an hechos y son del u ´ ltimo orden en el error (esto u ´ ltimo, sobre todo cuando el rompimiento de la monoton´ıa ocurre en la parte final del diagrama de romoboidal de diferencias divididas y no al principio). Entre m´ as parecidas sean las monoton´ıas de la funci´ on discreta y el polinomio de interpolaci´ on, en esa misma medida la interpolaci´ on ser´ a m´as consistente.

4

Algoritmo Los criterios de simetr´ıa y monoton´ıa se complementan para indicar cuales puntos y el n´ umero de ellos se deben usar en la interpolaci´ on. En cualquier caso, el grado del polinomio ser´ a siempre una unidad menor que el n´ umero de puntos usados. El algoritmo se resume de la siguiente manera: se escogen los puntos m´as cercanos al punto donde se desee interpolar, en un n´ umero (distancia) sim´etrico (pr´ oxima), uno a uno (calculando cada vez las diferencias divididas de la diagonal incluido el v´ertice), hasta que dicho n´ umero de puntos, reflejado en las diferencias divididas, conserve el m´ aximo orden posible de monoton´ıa del polinomio de interpolaci´ on igual que el de la funci´ on discreta. El algoritmo antes explicado puede usarse para hacer interpolaciones en una o en varias dimensiones. Tambi´en permite la interpolaci´ on sin necesidad de pre-ordenar los puntos usados o pre escoger su n´ umero. En varias dimensiones lo u ´ nico que se exige es que los valores de las funciones sean siempre para los mismos y todos los puntos discretos en cada dimensi´on. El algoritmo tampoco necesita escoger un grado del polinomio anticipadamente, durante el proceso de la interpolaci´ on. El algoritmo decide el grado del polinomio o´ptimo que garantice satisfacer los criterios de simetr´ıa y monoton´ıa. REFERENCIAS • Carnahan, B.; Luther, H. A.; Wilkes, J. O. Applied Numerical Methods. John Wiley & Sons (New York), 1969. • Gerald, C. F. Applied Numerical Analysis, 2nd Edition. Addison-Wesley (New York), 1970. • Hildebrand, F. B. Introduction to Numerical Analysis. McGraw-Hill (New York),1956.

5