Linux Music 3.0

Hola, en general un trazador o función spline en un intervalo [a,b], en matemáticas, son polinomios que están definidos en subintervalos de [a,b] que cumplen ciertas condiciones de regularidad; normalmente cumplen lo que se llama ser función de clase , es decir, que son continuas tanto la función como sus derivadas hasta orden n en [a,b], lo cual es bastante obvio en polinomios.

Los trazadores se utilizan cuando por ejemplo tenemos un conjunto de puntos y queremos encontrar la función que pasa por todos esos puntos y que mejor se aproxima, dicha función a calcular es lo que llamamos trazador o función spline. Esta técnica de los trazadores es muy útil en informática para dibujar figuras no regulares. Por ejemplo, se puede utilizar para dibujar un perro o un edificio con tan sólo dar unos cuantos puntos representativos de dichas figuras y buscando su trazador.

El uso de trazadores en informática es muy útil ya que nos permite encontrar funciones que pasan por una cantidad finita de puntos mediante funciones a trozos, todas ellas polinómicas de grado pequeño, con lo cual el cómputo de operaciones de los algoritmos se reduce drásticamente, además de que dichas funciones a trozos (los trazadores) son funciones “suaves”.

Otro campo matemático parecido a los splines son los NURBS, los cuales nos permiten representar figuras complicadas y libres mediante interacción con el usuario mediante el movimiento de los nodos. Son muy utilizados en campos como la animación, y también se les conoce como B-splines, por ser un caso particular de los que veremos aquí. Si habéis programado con OpenGL sabréis de lo que estoy hablando.

Pero dejemos de lado estas profundas disquisiciones y profundicemos un poco en los trazadores cúbicos, los cuales son un buen comienzo para adentrarse en este apasionante mundo de la aproximación de figuras libres utilizando las matemáticas. Empecemos definiendo que es una función spline en general.

Sea <   < .... < una partición del intervalo [a,b]. es una función spline de orden asociada a si ([a,b]) y si coincide en cada intervalo [ , , i=0,1,...,n-1, con un polinomio de grado .
Notemos que para k=1 se obtiene una función lineal a trozos, que todos llamamos poligonal.
En éste artículo me centraré sólo en el caso k=3, conocidos como trazadores cúbicos o splines cúbicas. Así pues nuestras splines serán de clase y de grado menor o igual que 3. Y en concreto a las de tipo I que definiré en breve.
Dado y = ( ,, …. ) denotaremos por a una función spline cúbica de interpolación que verifica para i = 0,1,…,n-1.
Hay que recalcar que estas condiciones no determinan de forma única la spline cúbica. Si os estáis preguntando qué pinta el y es muy sencillo, en nuestros problemas partiremos de una serie de puntos concretos, por ejemplo, consideremos que queremos interpolar los puntos (0,1), (1,2), (4,0); pues bien, cada abscisa de los puntos representan la partición y las ordenadas de cada punto representan la y, que lógicamente estos son los extremos de cada subintervalo de cada función a trozo de que se compone nuestra función spline.
Para determinar únivocamente las funciones spline se imponen, en general, 3 tipos de condiciones. Como en éste artículo sólo me voy a centrar en las de tipo I, su condición de unicidad va a ser:
(y,a) = (y,b) = 0. Se suelen denominar condiciones naturales.
Ya hablaré de los otros dos tipos en otra ocasión, a modo de información os diré que las de tipo III se utilizan para interpolar funciones periódicas de periodo (b-a).
Para calcular explícitamente los trazadores definiremos primero los momentos de mediante un vector M cuyas componentes vienen expresadas como para j=0,1,…,n-1.
Denotemos j=0,1,…,n-1 Para calcular los momentos utilizaremos loa siguiente expresión:

Donde los vectores vienen definidos por las expresiones:


( )
para
Para los extremos (j=0, j=n) imponemos las condiciones de tipo I y obtenemos :


Si reunimos todas las fórmulas obtenidas tenemos que llegamos a un sistema lineal AM = d donde A es una matriz tridiagonal en la que su diagonal principal esta formada todos su elementos por el 2, su diagonal superior lo forman el vector y su diagonal inferior esta formada por el vector .
Con todos estos datos ya podemos pasar a realizar un programa en Python sobre un caso concreto para ver cómo funciona. Las demostraciones de cómo se obtienen las fórmulas anteriores las podéis obtener en cualquier libro de texto universitario que se dedique a la rama matemática de Aproximación Numérica bajo el apartado de interpolación polinómica bajo splines o trazadores.
EJEMPLO
Vamos a determinar la función spline cúbica de tipo I que interpola los puntos:
(0,1), (1,2),(3,0)
Para ello he adaptado el método de trazadores cúbicos de tipo I a un sencillo programa escrito bajo lenguaje Python utilizando las librerías gráficas Matplotlib para poder dibujar la función spline. Su código es el siguiente:

from Numeric import *
from math import *
from numpy.linalg import *
from pylab import *

vectorx = array((0.,1.,3.), Float)
vectory = array((1.,2.,0.), Float)
h = array((0.,0.), Float)
lamda = array((0.0, 0.0),Float)
mu = array((0.0, 0.0),Float)
d = array((0.0, 0.0,0.0),Float)
A = array(([0.0, 0.0, 0.0],[0.0, 0.0, 0.0],[0.0, 0.0, 0.0]), Float)

i = 0
n = 0

while i<len(h) :
	h[i] = vectorx[i+1]-vectorx[i]
	i=i+1
i=1
while i<len(h) :
	lamda[i]=h[i]/(h[i-1]+h[i])
	i=i+1

i = 1
while i<len(h) :
	mu[i-1]=1.-lamda[i]
	i=i+1

i=1
while i<len(h) :
	d[i] = (6./(h[i-1]+h[i]))*((vectory[i+1]-vectory[i])/h[i]-(vectory[i]-vectory[i-1])/h[i-1])
	i=i+1

i=0
n=1
while i<len(mu) :
	A[i][n]=lamda[n-1]
	i=i+1
	n=n+1

i=1
n=0
while n<len(mu) :
	A[i][n]=mu[i-1]
	i=i+1
	n=n+1

i=0
while i<=len(mu) :
	A[i][i]=2.
	i=i+1

M = solve(A,d)

def funcionS1() :
	x = arange(0,3,0.1)
	m = len(x)
	s1 = array(([0.,0.]),Float)
	s2 = array(([0.0,0.]),Float)
	S = zeros(m, Float64)
	i = 0
	l = 0
	while i<=1 :
		while l<m :
			s1[i]=(vectory[i+1]-vectory[i])/(h[i+1])-(1./6.)*(2*M[i]+M[i+1])*h[i+1]
			s2[i]=(1./6.)*((M[i+1]-M[i])/h[i+1])
			S[l] = vectory[i]+s1[i]*(x[l]-vectorx[i])+0.5*M[i]*pow(x[l]-vectorx[i],2.)+s2[i]*pow(x[l]-vectorx[i],3.)
			l = l+1
		i = i+1
        plot(x, S, linewidth=1.0)
        xlabel('Abcisa')
        ylabel('Ordenada')
        title('Metodo I De Los Splines ')
        grid(True)
        axhline(linewidth=1, color='r')
        axvline(linewidth=1, color='r')
        show()

funcionS1()

El código del programa no tiene mayor misterio, a destacar la instrucción para resolver el sistema lineal AM=d, que es:

M = solve(A,d)

He utilizado la función solve de las librerías Numpy, en concreto, las específicas al álgebra lineal, y que para importarlas a nuestros programas se debe hacer de una forma especial al inicio de nuestro código mediante la instrucción:

from numpy.linalg import *

He decidido utilizar la función solve porque nuestro sistema lineal es muy pequeño, pero en casos grandes es aconsejable utilizar métodos de cálculo de sistemas lineales con matrices de coeficientes tridiagonales, para así disminuir drásticamente el número de operaciones que realice nuestro código.
De igual forma cuando calculamos los puntos interpoladores de nuestra función spline, si la cantidad de puntos a calcular es grande, es aconsejable utilizar el Algoritmo de Horner para su cálculo, lo cual es posible gracias a que nuestras funciones spline son funciones polinómicas definidas a trozos.
El resultado del programa lo podéis ver en la siguiente imagen:

Espero pronto poder escribir sobre los trazadores cúbicos de tipo II y III

Saludos :-h