aproximación mediante splines cúbicos recontrasuperarchimegarechuchatumareterminado

Splines Cbicos Mtodos Numricos

Pgina 1

Aproximacin mediante splines cbicos

El origen del concepto spline proviene del uso de una lmina de plstico delgada

llamada curvgrafo ("spline") en el trazado de curvas suaves a travs de un

conjunto de puntos (Sheid 1991).Las funciones "spline" son ecuaciones cbicas

que modelan el comportamiento de las curvas realizadas por dicho instrumento,

permitiendo unir en forma suave y continua una serie de puntos.

Esta interpolacin se llama interpolacin segmentaria o interpolacin por splines.

La idea central es que en vez de usar un solo polinomio para interpolar los datos,

podemos usar segmentos de polinomios y unirlos adecuadamente para formar

nuestra interpolacin , esta interpolacin posee una gran finura, y que inclusive

es usado para el diseo por computadora, por ejemplo, de tipos de letra.

La ms populares son los polinomios cbicos por tramos y en especial los splines

cbicos (naturales), por las siguientes razones:

Son fciles de calcular y evaluar.

Son fciles de derivar y sus derivadas aproximan a las derivadas de fx.

Son fciles de integrar y se usan para aproximar la integral de fx.

Modelan con suavidad la tendencia de un conjunto de datos.

1, Breve historia

Tomado de NA. Digest.v.98,#s6. 19 de julio de 1998.Mait to na.digest@na-

net.oml.gov Information about NA-NET:Mail to [email protected] URL :

http://www.netlib.org/na-net/na_home.html

Hace dos semanas puse aqu una pregunta acerca de las conexiones entre el

desarrollo de aproximaciones de splines y el diseo de cuerpos automotores, y

recib cerca de 30 respuestas, todas ellas muy informativas. Dado que muchos de

ellos me pidieron que mostrara lo que haba aprendido, decid escribir un breve

resumen y subirlo al compendio. Esta es la razn de estas notas.

Se acepta comnmente que la primera referencia matemtica de los splines es el

trabajo de Schoenberg [s], donde probablemente fue el primer lugar donde el

trmino spline se us en conexin con la aproximacin polinomial tenue por

piezas. Sin embargo, estas ideas tienen sus races en las industrias de aviacin y

Construccin de barcos. En el reenvio a [BBB], Robin Forrest describe el

localizar, una tcnica en la industria britnica de aviacin usada durante la

Segunda Guerra Mundial, para construir plantillas para aviones, pasando tablones

de madera delgadas a travs de puntos en el suelo de un local de diseo grande.


Pgina 2

Las plantillas estaran puestas en puntos discretos (llamados patos por Forrest;

Schoenberg usa perros o ratas) y entre estos puntos asumira formas de un

mnimo de energa de tensin. De acuerdo a Forrest, una motivacin posible para

un modelo matemtico de este proceso fue la pedida potencial de los

componentes del diseo crticos en toda una nave si el local fuera bombardeado

por el enemigo. Esto promovi el localizamiento cnico, el cual usaba secciones

cnicas para modelar la posicin de la curva entre los patos. El localizamiento

cnico fue reemplazado por lo que llamaramos splines a principios de los 60s

basados en el trabajo de J.C.Ferguson de Boeing y (tiempo despus) por

M.A.Sabin de British Aircraft. Lo que considero muy interesante es que Forrest

dice que la palabra spline viene de un dialecto Anglicano del Este.

El uso de splines para modelar cuerpos automotores parece tener un sinfn de

comienzos independientes. El crdito lo piden a nombre de De Castelau de

Citroen, Bezler de Renault, and Birkhoff, Garabedian, y de Boor de General Mortos

(GM), todos ellos por sus trabajos realizados a finales de la dcada de 1950s o

principios de los aos 1960s. Al menos uno de los trabajos de De Casteljau fue

publicado, pero no ampliamente, en 1959. La obra de D Boor de GM result en un

conjunto de escritos siendo publicados a principios de los 60s, incluyendo algo del

trabajo fundamental sobre los B-splines. El trabajo tambin fue hecho en Pratt

yThitney Aircfraft, donde dos de los autores de [ANw] (el primer libro en s acerca

de splines) fueron contratados, y el Modelo Basin de David Taylor, hecho por

Feodor Theilheimer

Referencias

[anw] Ahlberg, Nielson and Wash, The Theory of splines and Theri applications,

1967

[B] Birkhoff. Fluid dynamics, reactor computations and surface representation. In

a History of Scientific Computation (Steve Nash, editor), 1990

[BBB] Bartelsm Beatty and Barsky, an introduction to Splines for use in Computer

Graphics and Geometric Modeling 1987

[BdB] Birkhof and de Boor, Piecewise polynomial interpolation and approximation

Proc. General Motors Symposium of 1964

[D] Davis . B-splines and Geometric design . SIAM news vol.29 no, 5

[S] Schoenberg. contributions to the problem of approximation of equidistant data

by analytic functions Quart appl math. Vol. 4

[Y] Young. Garrtett Dirkhoff and applled mathematics. Notices of the AMS, vol.44


Pgina 3

2. Teora Matemtica

Los polinomios de grado mayor tienen naturaleza oscilatoria y fluctuaciones sobre

una porcin pequea del intervalo estudiado puede inducir cambios muy grandes

sobre un rango considerable, restringen el uso cuando se aproximan muchas

delas funciones en situaciones fsicas reales.

La tcnica llamada aproximacin polinmica segmentaria busca resolver este

problema dividiendo el intervalo de la funcin f

en una coleccin de subintervalos y construir polinomios aproximadamente

diferentes en cada uno.

La aproximacin de este tipo ms empleada es la interpolacin cbica de spline

Esta tcnica requiere que en el intervalo el polinomio sea diferenciable

continuamente y que adems tenga segunda derivada. Pero a pesar de esta

condicin, el trazador cbico no supone que las derivadas del interpolante

coinciden con las de la funcin.

A esta forma de aproximar se le conoce como aproximacin polinomial

fragmentaria.

Aproximacin polinomial fragmentaria.

La Aproximacin polinomial fragmentaria es la interpolacin lineal fragmentaria

que consiste en unir una serie de puntos.

Mediante una serie de segmentos de recta, como se aprecia en la figura 3.7

La aproximacin por funciones lineales muestra una desventaja; no se tiene la

seguridad de que haya derivabilidad en los extremos de los subintervalos, lo cual

dentro de un contexto geomtrico significa que la funcin de interpolacin o

interpolante no es suave en dichos puntos. A menudo las condiciones fsicas

indican claramente que se requiere la suavidad y que la funcin aproximante debe

ser continuamente derivable.

Otro procedimiento consiste en emplear un polinomio fragmentario del tipo

Hermite. Por ejemplo, si los valores de y de se conocen en los puntos

podemos emplear un polinomio de Hermite de grado tres en

cada uno de los subintervalos [ ] [ ] [ ] para obtener una

funcin continuamente derivable con el intervalo [ ].


Pgina 4

Si queremos determinar el polinomio cbico de Hermite apropiado en determinado

intervalo, hasta calcular ( ) para ese intervalo. Puesto que los polinomios

interpolantes de Lagrange necesarios para calcular son de primer grado,

podemos hacer el clculo sin gran dificultad, Sin embargo, para utilizar los

polinomios fragmentarios de Hermite en la interpolacin general, necesitamos

conocer la derivada de la funcin que va ser aproximada, lo cual muchas veces no

es posible.

El tipo ms simple de funcin de polinomio fragmentario diferenciable en un

intervalo entre [ ] es la funcin obtenida al ajustar un polinomio cuadrtico

entre cada par consecutivo de nodos. Esto se hace construyendo una cuadrtica

en [ ] que concuerde con la funcin en y en ; y as sucesivamente. Un

polinomio cuadrtico general tiene tres constantes arbitrarias: el trmino

constante, el coeficiente de x y el coeficiente de y nicamente se requieren dos

condiciones para ajustar los datos en los extremos de cada intervalo, por ellos,

existe flexibilidad que permite seleccionar la cuadrtica de modo que la

interpolante tenga una derivada continua en [ ]. El problema de este

procedimiento se presenta cuando hay que especificar las condiciones referentes

a la derivada de la interpolante en los extremos y .No hay constantes

suficientes para cerciorarse de que se satisfagan las condiciones.


Pgina 5

Splines cbicos

La aproximacin polinmica fragmentaria ms comn utiliza polinomios entre cada

par consecutivo de nodos y recibe el nombre de interpolacin de trazadores

cbicos. Un polinomio cbico general contiene cuatro constantes; as pues, el

procedimiento del trazador cbico ofrece suficiente flexibilidad para garantizar que

el interpolante no slo sea continuamente diferenciable en el intervalo, sino que

adems tenga una segunda derivada continua en el intervalo. Sin embargo, en la

construccin del trazador cbico no se supone que las derivadas del interpolante

concuerdan con las de la funcin, ni siquiera en los nodos.

Definicin.

Dada una funcin definida en [ ] y un conjunto de nodos

un interpolante de spline cbico S para es una funcin que cumple con

las condiciones siguientes:

a. ( )es un polinomio cbico, denotado ( ),el subintervalo [ ] para

cada ;

b. ( ) ( ) para cada ;

c. ( ) ( ) para cada ;

d. ( )

( ) para cada

e. ( )

( ) para cada

f. Una de las siguientes condiciones de frontera se satisface:

(i) ( ) ( ) (frontera libre o natural);

(ii) ( ) ( ) y

( ) ( ) (frontera sujeta).


Pgina 6

Aunque los splines cbicos se definen con otras condiciones de frontera, las

condiciones dadas en ( ) son suficientes en este caso. Cuando se presentan las

condiciones de frontera libre, el trazador recibe el nombre de spline natural y su

grfica se aproxima a la forma que adoptara una varilla larga y flexible si la

hiciramos pasar por los puntos {( ( )) ( ( )) ( ( ))}

En trminos generales, en las condiciones de frontera sujeta se logran

aproximaciones ms exactas, ya que abarcan ms informacin acerca de la

funcin. Pero para que se cumpla este tipo de condicin de frontera, se requiere

tener los valores de la derivada en los extremos o bien una aproximacin precisa

de ellos.

Construccin de un spline cbico

Para construir la interpolante de spline cbico de determinada funcin ,

aplicamos las condiciones de la definicin a los polinomios cbicos:

( ) ( ) ( ) ( )

,

Para cada . Como ( ) ( ) puede aplicarse la

condicin (c) para obtener

Para cada

Los trminos se utilizaran varias veces en este desarrollo, por eso

conviene introducir la notacin ms simple

Para cada . Si tambin definimos ( ) entonces la

ecuacin

(I)

Ser vlida para cada

De manera anloga, defina ( ) y observe que


Pgina 7

Significa que ( ) para cada . Al aplicar la condicin (d)

obtenemos

(II)

Para cada

Al definir ( ) y aplicar la condicin (e) se obtiene otra relacin entre los

coeficientes de , En este caso para

(III)

Al despejar en la ecuacin (III) y sustituir este valor en las ecuaciones (I) y (II)

para cada se obtienen las ecuaciones.

(IV)

Y

(V)

La relacin final que incluye los coeficientes se obtiene resolviendo la ecuacin

correspondiente en la forma de la ecuacin (IV) , primero para

(VI)

Y luego, con una reduccin del ndice, para . Esto da como resultado

Cuando sustituimos estos valores en la ecuacin obtenida de la ecuacin (V) con

el ndice reducido en 1, obtenemos el sistema de ecuaciones lineales

(VII)

Para cada .


Pgina 8

Splines naturales

Si est definida en , entonces tendr una

interpolante nica de spline natural S en los nodos es decir, una

interpolante de spline que cumple con las condiciones de frontera ( ) y

( )

Demostracin. En este caso las condiciones de frontera significan que

( ) y que

( ) ( ),

as que . Las dos ecuaciones y junto a las ecuaciones de (VII)

Producen un sistema lineal descrito por la ecuacin vectorial , donde A es

la matriz de ( ) ( )

La matriz A es estrictamente dominante en sentido diagonal.

Y donde b y x son los vectores


Pgina 9

Spline cbicos sujetos

SI f est definida en a = <


Pgina 10

Las ecuaciones

Y

Determinan el sistema lnea Ax = b, donde:

La matriz A es estrictamente dominante en sentido diagonal, en consecuencia el

sistema tiene una solucin nica para , ,. ..,


Pgina 11

3. Solucin de problemas

1) Construya un spline natural cbico que pase por los puntos (1,2) ;(2,3) y

(3,5)

Solucin.

Este spline consiste de dos cbicas. La primera para el intervalo [ ], denotada

por:

Y la otra para [ ], denotada por:

Existen 8 constantes que deben determinarse, lo que requiere de 8 condiciones.

Cuatro de ellas proceden del hecho de que los splines deben coincidir con los

datos en los nodos. Por tanto.

Y

Dos ms provienen del hecho de que ( )

( ) y ( )

( ) .Estas son:

( )

( ) y ( )

( )

Las ltimas dos surgen de las condiciones de frontera natural:

( ) y

( )


Pgina 12

Resolviendo este sistema de ecuaciones tenemos el spline.

2) Interpolar los siguientes datos mediante una spline cbica:

X 2 9 5

Y -1 2 -7

Solucin.

Definimos un polinomio cbico en cada uno de los intervalos que se forman:

A continuacin, hacemos que se cumpla la condicin de que la spline debe pasar por los puntos dados en la tabla. As, tenemos que:

5,3

3,2

22

2

2

3

2

11

2

1

3

1

xsidxcxbxa

xsidxcxbxaxs

124812 1111 dcbas

2392723 1111 dcbas

752512575 2222 dcbas


Pgina 13

Ahora calculamos la primera derivada de :

Al igual que en el caso de las splines cuadrticas, se presentan ecuaciones que

pueden presentar discontinuidad en los cambios de intervalo; las posibles

discontinuidades son los puntos donde se cambia de intervalo, en este caso

. Para evitar esta discontinuidad, evaluamos en los dos polinomios e

igualamos:

o lo que es lo mismo:

Anlogamente procedemos con la segunda derivada :

Para lograr que sea continua:

xs

5,323

3,223

22

2

2

11

2

1

xsicxbxa

xsicxbxaxs

3x

3x

222

211

2

1 32333233 cbacba

222111 627627 cbacba

5,326

3,226

22

11

xsibxa

xsibxaxs

xs

2211 236236 baba

2211 218218 baba


Pgina 14

En este punto contamos con 6 ecuaciones y 8 incgnitas, por lo tanto tenemos 2 grados de libertad; en general, se agregan las siguientes 2 condiciones:

De lo cual vamos a obtener:

Con lo cual, hemos completado un juego de 8 ecuaciones vs. 8 incgnitas, el cual es el siguiente:

0

00

nxs

xs

022602 11 bas

0212 11 ba

025605 22 bas

0230 22 ba

0230

0212

218218

627627

7525125

23927

23927

1248

22

11

2211

222111

2222

2222

1111

1111

ba

ba

baba

cbacba

dcba

dcba

dcba

dcba


Pgina 15

Cuya forma matricial es la siguiente:

Usando Mathematica, obtenemos la siguiente solucin:

Sustituyendo estos valores en nuestra funcin inicial, vemos que la spline cbica para la tabla de datos dada, queda definida como sigue:

0

0

0

0

7

2

2

1

002300000

000000212

0021800218

0162701627

15251250000

139270000

000013927

00001248

2

2

2

2

1

1

1

1

d

c

b

a

d

c

b

a

125.50

875.39

375.9

625.0

5.0

75.10

5.7

25.1

2

2

2

2

1

1

1

1

d

c

b

a

d

c

b

a

5,3125.50875.39375.9625.0

3,25.075.105.725.123

23

xsixxx

xsixxxxs


Pgina 16

Mostramos la grfica correspondiente a este ejercicio, creada tambin en

Mathematica.

Obsrvese la finura con la que se unen los polinomios cbicos que conforman a la spline. Prcticamente ni se nota que se trata de dos polinomios diferentes!. Esto es debido a las condiciones que se impusieron sobre las derivadas de la funcin. Esta finura casi artstica, es la que permite aplicar las splines cbicas, para cuestiones como el diseo de letras por computadoras, o bien a problemas de aplicacin donde la interpolacin que se necesita es de un carcter bastante delicado, como podra tratarse de datos mdicos sobre algn tipo de enfermedad.


Pgina 17

3) Interpolar los siguientes datos utilizando splines cbicas:

x -1 1 2 4

y -1 1 5 -2

Solucin.

Nuevamente, definimos un polinomio cbico en cada uno de los intervalos:

Despus, hacemos que la spline pase por los puntos dados en la tabla. As, tenemos que:

Implica que,

Implica que,

Implica que,

4,2

2,1

1,1

)(

33

2

3

3

3

22

2

2

3

2

11

2

1

3

1

xsidcxbxa

xsidxcxbxa

xsidxcxbxa

xs

1)1( s

11111 dcba

1)1( s

11111 dcba

12222 dcba

5)2( s

5248 2222 dcba

5248 3333 dcba


Pgina 18

Y finalmente implica que,

Enseguida, calculamos la primera derivada:

Vemos entonces, que las posibles discontinuidades de son y .

Por lo tanto, para hacer que sea continua, igualamos las ecuaciones

correspondientes en ambos valores:

Ahora procedemos a calcular la segunda derivada:

2)4( s

241664 3333 dcba

4,223

2,123

1,123

)(

33

2

3

22

2

2

111

2

1

xsicxbxa

xsicxbxa

xsicxbxa

xs

)(xs 1x 2x

)(xs

222111 2323 cbacba

333222 412412 cbacba

4,226

2,126

1,126

)(

33

22

11

xsibxa

xsibxa

xsibxa

xs


Pgina 19

Nuevamente, las posibles discontinuidades son y . Por lo tanto, para

que sea continua, se igualan las ecuaciones en ambos valores:

Finalmente, se agregan las condiciones de que la doble derivada se anule en los puntos inicial y final de la tabla.

En este caso,

Con esto tenemos un juego de doce ecuaciones vs. Doce incgnitas:

1x 2x

)(xs

22112211 332626 babababa

33223322 66212212 babababa

030260)1( 1111 babas

01202240)4( 3333 babas

11111 dcba

11111 dcba

12222 dcba

5248 2222 dcba

5248 3333 dcba

241664 3333 dcba

222111 2323 cbacba

333222 412412 cbacba


Pgina 20

Este sistema tiene la siguiente forma matricial:

Usando Mathematica, obtenemos la solucin:

, ,

, ,

2211 33 baba

3322 66 baba

03 11 ba

012 33 ba

0

0

0

0

0

0

2

5

5

1

1

1

0011200000000

000000000013

001600160000

000000130013

01412014120000

000001230123

14166400000000

124800000000

000012480000

000011110000

000000001111

000000001111

3

3

3

3

2

2

2

2

1

1

1

1

d

c

b

a

d

c

b

a

d

c

b

a

140

511 a

10

212 a

35

243 a

140

1531 b

35

2972 b

35

2883 b


Pgina 21

, ,

, ,

Por lo tanto, la spline cbica es:

Finalmente, mostramos la grfica correspondiente (creada en Mathematica):

140

891 c

70

4732 c

70

18673 c

40

1531 d

35

482 d

35

7323 d

4,2

2,1

1,1

)(

35732

7018672

352883

3524

3548

704732

352973

1021

40153

140892

1401533

14051

xsixxx

xsixxx

xsixxx

xs

-1 1 2 4

-2

2

4

6

8


Pgina 22

4. Algoritmos

El spline cubico natural. Matlab, por defecto, calcula splines cbicos con la condicin not-a-knot, que es cierta relacin entre derivadas en los puntos extremos y los inmediatos. Solo se pueden calcular splines naturales con un

toolbox. El cdigo que sigue implementa el clculo del spline cubico natural de una

coleccin de puntos. La entrada es: x: la lista de las coordenadas x de los puntos y: la lista de las coordenadas y de los puntos Devuelve un objeto" de Matlab que se denomina polinomio a trozos, que describe exactamente un objeto polinomial definido a trozos: los intervalos en los que est definido vienen dados por el vector x y su valor en un t (que hay que computar utilizando la funcin ppval)

% spline cubico 'natural ': en ambos extremos , la % derivada segunda es 0. % la entrada es una nube de puntos con al menos % dos puntos function [f] = spline_cubico (x, y) n = length (x) -1; if(n 1& i < n) F(i ,[i -1 i i +1]) = [h(i -1) , 2*( h(i -1) + h(i)), h(i)] ; alpha (i) = 3*( y(i+1) -y(i))/h(i) - 3*( y(i) - y(i -1) )/h(i -1) ; else F(i,i) = 1; alpha (i) = 0; end i=i +1; end c = (F\ alpha ) '; 28 b = zeros (1,n); d = zeros (1,n); i = 1; while (i


Pgina 23

while (i

aproximación mediante splines cúbicos recontrasuperarchimegarechuchatumareterminado

Documents