Interpolacion

Un problema de Aproximación ◆ Evolución de la temperatura diurna Hora Grados

Grados

2 2 10 81 16 41 12 08 6

4

6

6 7

8

8 9

1 0

10 12

12 18

1 1 Hora 2 4

14 21

16 19

18 15

20 10

1 6

1 8

2 0

2 2

Interpolacion ◆ Interpolación Polinomial ◆ Polinomios Osculadores: Interpolación de

Hermite ◆ Interpolación Racional: Aproximaciones de

Pade ◆ Interpolación segmentaria: Splines ◆ Otros

Ajuste ◆ Polinomios de Taylor ◆ Mínimos Cuadrados ◆ Minimización de normas ◆ Aproximación Racional ◆ Series de Fourier ◆ Curvas de Bezier ◆ B-Splines

Interpolación Polinómica Segmentaria ◆ Limitaciones de la interpolación polinómica ✔Grado del polinomio ✔Carácter de la función a interpolar ◆ Alternativa propuesta: Splines. ✔Numéricamente estable ✔Matrices dispersas ✔Agradable a la vista

Interpolación Polinomica Segmentaria: Splines ◆ Interpolación Segmentaria ◆ Interpolación Segmentaria Lineal ◆ Interpolación Segmentaria Cúbica ✔Condiciones Naturales ✔Condiciones sobre la derivada

Interpolación Segmentaria Lineal: Función de Runge Polinomio grado 4

Spline lineal

1

1 0.9

0.8

0.8 0.6

0.7 0.6

0.4

0.5 0.2

0.4 0.3

0

0.2 -0.2 -0.4

0.1 -1

0

1

0 -1

1 y= 1 + 25 x 2

0

1

Perfil para un diseño

Polinomio interpolador

Aplicaciones Ingeniería y Diseño (CAD/CAM, CNC’s) ◆ Geología ◆ Aeronáutica y automoción ◆ Economía ◆ Procesamiento de señales e imágenes (Reconocimiento de patrones, recuperación de imágenes) ◆ Robótica ◆ Medicina (Aparatos auditivos, mapas cerebrales) ◆ Meteorología (Mapas climáticos, detección de inundaciones,...) ◆ Mundo Virtual Distribuido Multiusuario ◆

Interpolación Polinómica Segmentaria Dados n+1 puntos (x0,y0), (x1,y1), ..., (xn,yn) con x0<x1…<xn, una función spline de orden k (k-Spline) sobre dichos puntos es una función S verificando: (i) S(x) = qk(x) polinomio de grado ≤k, x ∈ [xk,xk+1], k=0,1,...,n-1 (ii) S(xk) = yk, k=0,1,...,n (iii) S ∈ C k −1 [ x0 , x1 ]

Splines Lineales ◆ Polinomio de Lagrange

x − x k +1 x −xk q k ( x) = yk + y k +1 x k − x k +1 x k +1 − x k ◆ Polinomio de Newton

q k ( x) = f [ x k ] + f [ x k , x k +1 ]( x − x k ) = y k +1 − y k = yk + (x −xk ) x k +1 − x k

Splines Lineales

Interpolación Segmentaria Lineal: Función de Runge Polinomio grado 4

Spline lineal

1

1 0.9

0.8

0.8 0.6

0.7 0.6

0.4

0.5 0.2

0.4 0.3

0

0.2 -0.2 -0.4

0.1 -1

0

1

0 -1

1 y= 1 + 25 x 2

0

1

Splines Cúbicos ◆

Spline cúbico

q k ( x) = a k + b k ( x − x k ) + c k ( x − x k ) 2 + d k ( x − x k ) 3 ◆ ◆

4n incógnitas Condiciones de interpolación S ( xk ) = yk n+1 ecuaciones Condiciones de conexión

qk ( xk +1 ) = qk +1 ( xk +1 ) q k' ( xk +1 ) = qk' +1 ( xk +1 ) q k'' ( xk +1 ) = qk'' +1 ( xk +1 )

3(n-1) ecuaciones

q k ( x) = a k + b k ( x − x k ) + c k ( x − x k ) 2 + d k ( x − x k ) 3 h k = x k +1 − x k a k = f ( x k ), k = 0,1,..., n hk 1 bk = ( a k +1 − a k ) − ( 2c k + c k +1 ), k = 0,1,..., n − 1 hk 3

d k = (c k +1 − c k ) / ( 3h k ),

h

k −1

c

k −1

+ 2(h

k −1

k = 0,1, n − 1

+ h )c + h c k

k

k

k +1

=

3 3 = (a k +1 − a k ) − ( a k − a k −1 ) hk h k −1 n-1 ecuaciones y n+1 incógnitas

Condiciones Naturales Teorema 1 Sea f(x) una función definida en [x 0,x n]. Entonces existe un único s(x) spline interpolante cúbico para f(x) en [x 0,x n] tal que s’’(x 0) = 0

y

s’’(x n) = 0.

cn = s’’(xn)/2 = 0 s’’(x0) = 2c0 = 0 → c0 = 0.

Matriz del sistema h1 0  2( h 0 + h 1 )  h 2( h 1 + h 2 ) h2 1   0 h2 2( h 2 + h 3 )      M=      0 0 0   0 0 0  0 0 0 

       

 0 0 0    0 0 0    0 0 0              2( h n − 4 + h n − 3 ) h n− 3 0    h n− 3 2( h n − 3 + h n − 2 ) h n− 2   0 h n− 2 2( h n − 2 + h n − 1 ) 

Términos independientes 3 3   (a 2 − a 1 ) − (a 1 − a 0 )   h1 h0         p=         3  3  (a n − a n −1 ) − (a n −1 − a n − 2 )  h n−2  h n −1 

Ejemplo de la temperatura Polinomio interpolador

Spline cúbico 22

20

20

18

18

16

16

Grados

Grados

22

14

14

12

12

10

10

8 6

8 5

10

Hora

15

20

6

5

10

Hora

15

20

Condiciones sobre la derivada Teorema 2 Sea f(x) una función definida en [x 0,xn]. Entonces existe un único s(x) spline cúbico interpolante para f(x) en [x 0,xn].tal que s’(x 0) = f’(x 0) y s’(x n) = f’(x n). 3 2 h 0 c 0 + h 0 c1 = (a − a 0 ) − 3f ' ( x 0 ) h0 1

h n −1c n −1 + 2 h n −1c n = 3f ' ( x n ) −

3 h n −1

( a n − a n −1 ).

Matriz del sistema h0 0 0 2 h 0  h 2( h + h ) h1 0 0 1  0  0 h1 2 ( h1 + h 2 ) h2  0 0 h2 2( h 2 + h 3 )  M=       0 0 0  0  0 0 0 0  0 0 0  0

       

0  0 0 0   0 0 0   0 0 0       2( h n − 3 + h n − 2 ) h n− 2 0  h n− 2 2( h n − 2 + h n − 1 ) h n − 1   0 h n −1 2 h n −1  0

0

Términos independientes  3  h (a 1 − a 0 )  0  3 (a − a ) 1  h1 2 p=  3  (a n − a n −1 )  h n −1  3f ' ( x n )  

− −  − −

 3f ' ( x 0 )   3 (a1 − a 0 )   h0   3 ( a n −1 − a n −2 )  h n −2   3 (a n − a n −1 )  h n −1 

Splines Cúbicos

Interpolación segmentaria con MATLAB ◆ Interpolación segmentaria cúbica ➲ ps = spline(x,y) % Devuelve el Spline, no los coeficientes ➲ [x,s] = unmkpp(ps) % Devuelve los coeficientes ➲ ps = mkpp(x,s) ➲ syy = spline(x,y,xx) = ppval(ps,xx)

◆ Interpolación segmentaria lineal ➲ lyy = interp1(x,y,xx)

Spline de MATLAB

1

Interpolación Lineal

1

0.5 0.5 0 0 -1

0

1

Spline Natural

1

-1

1

Spline Derivada

1

0.5

0

0.5

0

0 -1

0

1

-1

0

1