Interpolacion

Teoría Básica de Interpolación
Curso PDI

Interpolación
n

La interpolación consiste en generar a partir de un conjunto N de puntos, un polinomio P que represente el comportamiento de los puntos

X Y

x0 y0

x1 L xn y1 L yn

P ( x) = b0 + b1 ( x − x0 ) + b2 ( x − x0 )( x − x1 ) + L bn ( x − x0 ) L ( x − xn−1 )

1

Interpolación
n

Condiciones para la interpolación

P( xi )= yi , ∀i = 0,..., n
X Y x0 y0 x1 L xn y1 L yn
P ( x0 ) = y 0 P ( x1 ) = y1 P ( xn ) = y n

Interpolación Lineal
n

Cantidad de puntos requeridos: 2
X Y x0 y0 x1 y1

Estructura General Polinomio Lineal:

P ( x) = b0 + b1 ( x − x0 )
Dado que P(x0) = y0, entonces:

P( x1 ) = y0 + b1 ( x1 − x0 ) = y1 y −y ∴ b1 = 1 0 x1 − x0

P ( x0 ) = b0 + b1 ( x0 − x0 ) = b0 = y0

2Interpolación Cuadrática

X Y

x0 y0

x1 x 2 y 1 y2

P( x ) = b0 + b1 ( x − x0 ) + b2 ( x − x0 )( x − x1 )
P( x2 ) = b0 + b1 ( x2 − x 0 ) + b2 (x 2 − x0 )(x2 − x1 ) = y2
b0 = y0 y −y b1 = 1 0 x1 − x 0

y 2 − y1 y1 − y 0 − x − x x1 − x0 ∴b2 = 2 1 x2 − x 0

Diferencias Divididas de Newton
n

Con la finalidad de simplificar las operaciones, se utilizan las Diferencias Divididas de Newtonf [ xi , x j ] =

f [ xi ] − f [ x j ] xi − x j

3

Diferencias Divididas de Newton Caso Lineal
b0 b1

x0 → f [ xo ] = yo x1 → f [ x1 ] = y1

f [ x1 , x0 ] =

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

f ( x) = b0 + b1 ( x − x0 ) = f [ x0 ] + f [ x1 , x0 ]( x − x0 )

Diferencias Divididas de Newton Caso Cuadrático
x0 → f [ xo ] = yo x1 → f [ x1 ] = y1 x2 → f [ x2 ] = y2
b0
f [ x1] − f [ x0 ]f [ x1, x0 ] = x1 − x0 f [ x2 ] − f [ x1 ] f [ x2 , x1 ] = x2 − x1

b1

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

b2

f ( x) = b0 + b1 ( x − x0 ) + b2 ( x − x0 )( x − x1 ) = f [ x0 ] + f [ x1 , x0 ]( x − x0 ) + f [ x2 , x1 , x0 ]( x − x0 )( x − x1 )

4

Lagrange
n

Enfoque alternativo para calcular un polinomio de interpolación
X Y x0 y0 x1 L xn y1 L y n

P (x) = y0l0 ( x ) + y1l1 ( x) + L + yn ln ( x)
P( x0 ) = y0 ⇒ l0 ( x0 ) = 1, P( x1 ) = y1 ⇒ l1 ( x1 ) = 1, M P( xn ) = yn ⇒ ln ( xn ) = 1, l 0 ( xi ) = 0 ∀i ≠ 0 l1 ( xi ) = 0 ∀i ≠ 1 ln ( xi ) = 0 ∀i ≠ n

Lagrange
n

Despejando l0(x0) = 1 y l0(xi) = 0, i ≠ 0, entonces se propone:
l0 ( x ) = c( x − x1 )( x − x2 ) L ( x − xn )
Como l 0(x0) = 1, entonces:

1 = l0 ( x0 ) = c ( x 0 − x1 )( x0 −x2 ) L ( x0 − xn )
⇒c= 1 ( x0 − x1)( x0 − x1 ) L( x0 − xn )

∴ l0 ( x) =

( x − x1 )( x − x 2 ) L ( x − x n ) ( x0 − x1)( x 0 − x 2 ) L ( x 0 − x n )

5

Lagrange
n

Generalizando:

l j ( x) =

∀i ≠ j ,i =0 ,...,n j ∀i ≠ j ,i =0 ,...,n

∏ (x − x ) , (x − x ) ∏
i i

j = 0,..., n

Lagrange
n

Por ejemplo, calcular el polinomio de Lagrange para los siguientes puntos:

X Y1 3 5 7 − 2 1 2 −3

6

Splines
n

n

Técnica ampliamente utilizada en el procesamiento digital de imágenes En lugar de representar a todos los puntos con un polinomio de alto grado, se dividen por segmentos a los puntos, donde cada segmento será representado por un polinomio

Splines
n

Una función spline s(x) esta formada por varios polinomios, cada uno definido en unintervalo, los cuales se unen bajo ciertas condiciones de continuidad
x0 < x1 < … < xn

X Y

x0 y0

x1 L xn y1 L y n

a) s(xi) = yi , ∀ i = 0, …, n b) s(x) es un polinomio de grado ≤ k en cada subintervalo [xi-1, xi ] c) s(x) tiene derivada continua hasta de orden k-1

7

Splines Lineales
n

Unir a los puntos con segmentos de recta
 s1 ( x), x ∈ [ x0 , x1 ]  s ( x ), x ∈[ x , x ]  2 12 s( x ) =  M   sn ( x ), x ∈[ x n−1, x n ] 

 y 0 + f [ x1 , x0 ]( x − x0 ), x ∈ [ x0 , x1 ]  y + f [ x , x ]( x − x ), x ∈ [ x , x ]  1 2 1 1 1 2 ⇒ s( x ) =  M   y n −1 + f [x n , x n−1 ]( x − x n−1 ), x ∈ [ x n −1 , x n ] 

Splines Cuadráticos
n

Consiste en unir cada uno de los puntos a través de segmentos de curvas cuadráticas:
 s1 ( x), x ∈ [ x0 , x1 ]  s ( x ), x ∈[ x...