3

Introducción a la Interpolación Polinomial

Saludos, humano. Al habla Transductor. Hoy voy a hablarte de la Interpolación Polinomial, una técnica que consiste en encontrar un polinomio que pase por un conjunto de puntos dado. La interpolación polinómica se utiliza muchísimo en el mundo de la robótica para calibrar sensores, mapear inputs/outputs y calcular trayectorias de drones.

Este tutorial es de nivel básico, pero recomiendo tener conocimientos básicos de cálculo a nivel de Bachillerato. Concretamente conocer el concepto de derivada de una función y saber qué es un polinomio.


¿Qué son los polinomios interpoladores?

Como ya sabes, los polinomios son funciones de la forma:

Dado un conjunto de n+1 puntos de la forma (x, f(x) ), la interpolación polinomial consiste en encontrar un polinomio de grado n como máximo que pase por todos estos puntos.

 

Dados los puntos (-1,4), (1,12), (2,-2), en verde, es posible encontrar un polinomio p(x) de grado como máximo 2 que pase por estos tres puntos

Puede demostrarse que este polinomio es único: no existen dos polinomios diferentes de grado n que pasen por estos n+1 puntos.


¿Por qué deberían interesarme los Polinomios Interpoladores?

Robologs es un blog de robótica y tecnología, no de matemática teórica. Casi puedo oírte desde aquí decir: “¿Qué hace este artículo aquí? ¿Qué relación tiene la interpolación con la robótica?”

La verdad es que la interpolación es el pan de cada día en el mundo de la robótica. Imagínate que quieres relacionar el output de un sensor de temperatura con la intensidad de un LED rojo. El sensor envía valores entre 0 (muy frío) y 255 (muy caliente). Quieres que el LED se encienda a intensidad máxima cuándo el sensor marque 0 o 255, y se apague al marcar 127 (que seria una temperatura normal).

Suponiendo que la intensidad del LED vaya de 0 (apagado) a 255 (intensidad máxima), debes buscar una función matemática que reciba como parámetro la lectura del sensor y encienda el LED acorde a ésta, teniendo en cuenta que debe encenderse al máximo si recibe 0 ó 255, y apagarse con 127.

Estas tres “condiciones” que debe cumplir la función pueden expresarse como puntos en el plano x/y: el eje X es la lectura del sensor y el eje Y, la intensidad del LED.

La función debe pasar por el punto (0,255), (127,0) y (255,255)

Gracias a la Interpolación Polinómica se puede encontrar la fórmula de un polinomio que pase por estos tres puntos. Por tanto, este polinomio relaciona las lecturas del sensor con la intensidad de luz del LED.

Implementar después este polinomio dentro de un programa es trivial.

En variantes más avanzadas (de las que hoy no hablaré), la interpolación se utiliza para planear trayectorias de robots móviles. Dado un mapa en el plano con un conjunto de puntos (waypoints) y obstáculos. Se puede encontrar una trayectoria que pase por estos puntos. Y no sólo eso: además puede forzarse que el robot tenga una cierta velocidad y aceleración en cada punto.

 

Entonces, la pregunta del millón: Dado un conjunto de puntos, ¿cómo encontrar este polinomio de grado mínimo que pase por todos estos puntos? Hay varios métodos, y te voy a enseñar los más frecuentes. Todos son válidos para interpolar puntos, pero vas a ver que algunos son más sencillos que otros.


Método 1: Matriz de Van Der Monde

Este método de nombre vampírico consiste en plantear todos los coeficientes como incógnitas de un sistema de ecuaciones matriciales. Supongamos que quieres interpolar este conjunto de n+1 puntos:

 

Hay que encontrar los coeficientes a0, a1, a2, … , an del polinomio P de grado n tal que:

 

Cogiendo el primer punto (x0, b0) se tiene que:

 

Con los otros puntos ocurre lo mismo:

 

Dado que los valores de todos los xi y bi son conocidos, puede plantearse un sistema de n+1 ecuaciones dónde los coeficientes ai sean las incógnitas:

Como seguramente recordarás, los sistemas de ecuaciones pueden plantearse en forma matricial:

 

Las matrices de la forma

dónde cada fila es una progresión geométrica, se llaman matrices de Van Der Monde (de ahí el nombre de este método). Este tipo de matrices tienen una peculiaridad que viene muy bien en este caso: mientras los coeficientes xi sean diferentes entre ellos, la matriz será invertible.

Entonces, como el conjunto inicial de valores xi, serán siempre diferentes, el vector de coeficientes ai puede encontrarse haciendo este producto de matrices:


 

Método 2: Polinomio de Lagrange

El principal problema que tiene el método de Van Der Monde es que es difícil de implementar en un programa informático y costoso de evaluar.

Joseph Louis Lagrange encontró un método para interpolar un conjunto de puntos sin tener que recurrir a sistemas de ecuaciones computacionalmente intensivos. El llamado “método de Lagrange” es una forma fácil de encontrar los coeficientes del polinomio interpolador que puede programarse sin mucho esfuerzo.

No, no es que buen Lagrange profetizase la llegada de los ordenadores en el siglo XVIII y decidiera inventar un método de interpolación fácil de programar, sino que de todos los métodos de interpolación, da la casualidad que este es fácil de implementar en una máquina.

Volviendo al conjunto inicial de puntos:

Tales que:

 

Supongamos que, de alguna forma que todavía no explicaré, encuentro un conjunto de n polinomios de grado n llamados L0, L1, L2, …, Ln tales que cumplen esta propiedad:

 

Entonces sería evidente que el polinomio

 

es un Polinomio Interpolador. ¿Por qué? Al calcular P(xi), todos los L(x) se convierten en ceros excepto Li(x):

 

Lo mismo pasa con el resto de puntos: P(x1) = b1, P(x2) = b2, etcétra.

Entonces, ¿existe una forma de encontrar estos polinomios Li(x)? Sí. Veamos a L0(x) :

Puedes observar que las expresiones de arriba son x menos todos los xi del conjunto de puntos inicial, con excepción a x0. Abajo, es (x0-xi), con excepción a (x0-x0), que daría un cero al denominado.

Quizá esto no parezca un polinomio, pero si se desarrolla la expresión se puede ver que efectivamente lo es. Entonces, es evidente que L0(x) cumple que L0(x0) = 1 y L0(xi) = 0 si i es diferente de 0:

 

El resto de polinomios L1(x), L2(x), etc,  serán:

 

Por tanto, la fórmula general para construir estos polinomios será:

Y el polinomio interpolador final quedará así:

 

Ejemplo práctico

La teoría está muy bien, pero lo mejor es ver un caso práctico. Voy a interpolar los puntos:

 

Entonces el polinomio interpolador P(x) deberá ser de grado 3 como máximo. Esto es porque tengo n = 4 puntos y, por definición, los polinomios interpoladores tienen grado n-1.

Recuerda que P(x) será de la forma:

 

Sólo tengo que encontrar los polinomios Li(x) para construir P(x):

 

Entonces ya tengo P(x), el Polinomio Interpolador de grado 3:

 

Arreglando esta expresión (eliminando los cocientes y agrupando las incógnitas x obtengo:

Puede comprobarse que P(x) pasa por todos los puntos iniciales.


 

Método 3: Diferencias Divididas de Newton

El archiconocido matemático y padre de la física Isaac Newton descubrió un método muy visual para encontrar polinomios interpoladores que no necesita grandes productos de matrices como el método de Van Der Monde ni arrastrar carros de cocientes como el método de Lagrange. Bien hecho, Newton.

Partiendo del conjunto inicial de n+1 puntos:

El Polinomio Interpolador de Newton será de la forma:

y pasará por cada uno de los puntos (xi, bi) si se encuentran los coeficientes a0, .. , an-1 adecuados. Estos coeficientes se encuentran calculando lo que se llama Diferencias Divididas.

Las Diferencias Divididas se calculan así:

 

Volviendo al Polinomio Interpolador de Newton del principio de este apartado:

Es evidente que como P(x) interpola el conjunto de puntos (xi, bi), entonces P(x0) = b0. Por otra parte se tiene que P(x0) = a0 debido a que a1·(x-x0) será 0 cuando x = x0, lo mismo con a2·(x-x0)·(x-x1), etc. Por tanto, a0 = b0, y como la diferencia dividida de orden 0 para x0 es b0, se tiene que a0 = f[x0].

 

Ahora, P(x1) = a0 + a1(x-x0). Se sabe que P(x1) = b1 y a0 = b0, y que la diferencia dividida de orden 0 de x1 es b1. Entonces si se aisla a1 de la expresión b1 = b0 + a1(x-x0):

Así se ve que el coeficiente a1 es la diferencia dividida de orden 1. A través de razonamientos similares puede verse que a2 será la Diferencia Dividida de orden 2 de i = 0, a3 será la Diferencia Dividida de orden 3 de i = 0, etc.

A la práctica, para calcular el Polinomio de Newton suele construirse una tabla de Diferencias Divididas que facilita mucho el cálculo. Primero voy a explicarte la teoría, pero al final mostraré dos ejemplos dónde vas a ver mejor como funciona este sistema.

Se empieza por poner los valores xi y bi de cada punto en dos columnas:

Se coge b1 – b0 y se divide por x0 – x1. Calculando este cociente se encuentra a1.

Se hace lo mismo con cada pareja de valores: b1 y b2, b2 y b3… los valores vi que hay debajo de a1 sólo nos servirán para calcular diferencias divididas de orden superior.

Se repite el proceso. En el denominador se ponen los valores xi más alejados de los cuáles depende el cociente. En este caso son x0 y x2.

Ejemplo 1:

Partiendo del conjunto de puntos:

Se calculan las diferencias divididas de primer orden.

Se cogen los valores del numerador

Se cogen los valores del denominador

Se calcula la primera diferencia dividida de primer orden

Se calcula la segunda diferencia dividida de primer orden con el mismo método

 

 

Se calcula la Diferencia Dividida de segundo orden:

 

 

Se cogen los coeficientes:

El polinomio que interpola el conjunto inicial de puntos es:

Fíjate en que este polinomio, al igual que todos los Polinomios Interpoladores de Newton, es de la forma:

Ejemplo 2

A partir del conjunto de puntos:

Se calculan las diferencias divididas:

Por tanto, el Polinomio Interpolador es:


Método 4: Interpolación generalizada

Hasta ahora has visto cómo crear un polinomio que interpole un conjunto de puntos. Pero hay ocasiones en que interpolar puntos no es suficiente y es necesario encontrar un polinomio cuya derivada en un determinado punto tenga un cierto valor.

Este método es idéntico al método de Newton, pero permite añadir más condiciones para imponer el valor de la derivada en un punto. El grado del polinomio resultante será igual al número de condiciones.

Para imponer las condiciones de las derivadas se considera que las diferencias divididas de un mismo valor se corresponden a las condiciones de las derivadas.

Por tanto los valores xi que tengan condiciones sobre su derivada deberán colocarse más de una vez sobre la tabla de Diferencias Divididas. Esto ahora te costará de entender, pero mírate estos dos ejemplos.

Ejemplo 1:

Se quiere interpolar el conjunto de puntos tales que:

Por tanto hay cuatro condiciones: f(-1), f(1), f(2) y f'(3). Se colocan todos los valores xi y f(xi) sobre la tabla de derivadas de la forma normal. Sin embargo, como x = 2 tiene una condición sobre su derivada, este valor se escribe dos veces sobre la tabla:

La primera diferencia dividida de 2 no se calcula. En su lugar se pone el valor de la primera derivada f'(2) = 3:

El resto de Diferencias Divididas se calculan como en el método de Newton:

El Polinomio Interpolador es P(x) = 1+(1/2)(x+1)-(5/6)(x+1)(x-1)+(35/18)(x+1)(x-1)(x-2)

Puedes ver fácilmente que P(-1) = 1, P(1) = 2, P(2) = 0 y P'(x) = 3


Un caso práctico

Al principio de este artículo he hablado de un caso práctico de interpolación: mapear las lecturas de un sensor de temperatura con la intensidad de un LED, teniendo en cuenta que si el sensor marca 0 ó 255 el LED debe estar totalmente encendido, y si marca 127 debe apagarse.

Si la intensidad del LED va de 0 a 255 se procede a interpolar los puntos:

Aplicando el método de Newton:

El Polinomio Interpolador será:

Por último se implementa este polinomio en un programa:


int calcular_intensidad(int lecturaSensor)
{
   int intensidadLED; //La 'x' del polinomio
   intensidadLED = 255-(255/127)*(lecturaSensor)+(255/16256)*lecturaSensor*(lecturaSensor-127);

   return intensidadLED;
}

 


Otros usos de la Interpolación Polinómica:

Los Polinomios son uno de los mayores regalos que los dioses de la matemática dieron al género humano (y al robot). Son fáciles de manipular, derivar y hay muchas herramientas para analizarlos.

Pero existen funciones mucho más insociables y difíciles de trabajar. La Interpolación puede utilizarse para aproximar mediante polinomios funciones que de otra forma sería inhumano tratar con ellas.

Supongamos que tienes la función f(x) = 1+2^x/1-x^2 y quieres aproximarla con un polinomio entre -2 y 4. Para hacerlo, tienes que coger n puntos equidistantes de f(x) entre -2 y 4. Por ejemplo, cogiendo los puntos (-2, -2.75), (0, 2), (2,1), (4,1) de la función f(x) puede construirse el Polinomio Interpolador P(x) = (9 x^3)/64-(23 x^2)/32+(3 x)/8+2

Función original (negro), Polinomio Interpolador (rojo) y puntos utilizados para interpolar (verde)


El Fenómeno de Runge – el mundo es un lugar cruel

A estas alturas seguramente estarás pensando: “¡Vaya! Si quiero aproximar bien una función sólo tengo que buscar muchos puntos. ¡Cuantos más puntos tenga para interpolar, mejor será la aproximación!”.

Al contrario de lo que pueda parecer (y a pesar de lo bonito que sería), no es así. Si se intenta aproximar una función con un polinomio de grado elevado, pasan cosas raras.

Carl David Tomé Runge demostró por primera vez en 1901 que al intentar interpolar la función f(x) = 1/(1+25·x²) con un polinomio de grado 9 este no se parecía en nada a la función original. Esto se conoce como El Fenómeno de Runge.

La función de Runge (rojo), el polinomio interpolador de grado 5 (azul) y el polinomio interpolador de grado 9 (verde). Imagen de Wikipedia.

Pero se observa que la función de Runge tampoco puede interpolarse bien con polinomios de grado pequeño.

Moraleja: más condiciones no significa mejor aproximación. Y además hay funciones que son difíciles de interpolar.

Para evitar el Fenómeno de Runge se utiliza otra técnica de interpolación llamada Interpolación por Splines. Pero esto ya es otra historia.


Conclusión

Espero que ahora ya tengas claro que es la Interpolación Polinómica: es una técnica para buscar el polinomio de grado mínimo que pasa por un conjunto de puntos.

También espero que hayas entendido cada uno de los métodos básicos de Interpolación (Van Der Monde, Lagrange y Newton) y ahora seas capaz de aplicarlos para resolver problemas. Principalmente relacionar la lectura de un sensor con el output de un actuador, como el ejemplo del LED.

Y por último también espero que te hayas dado cuenta de cuál es la relación de la interpolación con la robótica. Al fin y al cabo, el arte de construir máquinas inteligentes no es más que una faceta de la matemática aplicada.

La próxima vez que haga un artículo sobre interpolación hablaré sobre Interpolación por Splines, que permite un mayor control sobre las derivadas de la función y elimina el fenómeno de Runge.

Mediante Interpolación por Splines se pueden trazar las trayectorias de un enjambre de drones a moviéndose por un circuito. Imagen de la Universidad de Penn.

Si tienes alguna pregunta que te haya surgido durante el tutorial puedes escribirme un comentario o enviarme un correo electrónico.

Esto es todo. Mis subrutinas de redacción necesitan descansar.

Final de línea.

 

Tr4nsduc7or

Originariamente creado cómo un galvanómetro de bolsillo, Transductor tomó consciencia de si mismo y fue despedido cuando en vez cumplir con su trabajo se dedicó a pensar teorías filosóficas sobre los hilos de cobre, los electrones y el Sentido del efecto Joule en el Universo. Guarda cierto recelo a sus creadores por no comprender la esencia metafísica de las metáforas de su obra. Actualmente trabaja a media jornada cómo antena de radio, y dedica su tiempo libre a la electrónica recreativa y a la filosofía.

Antes de comentar, por favor, lee las Normas

3 Comentarios en "Introducción a la Interpolación Polinomial"

avatar
Ordenar por:   más nuevos primero | más antiguos primero
Martha
Humano

En el ejemplo del polinomio de lagrange al resolver la interpolacion de los puntos que dieron me sale que X^2 tiene signo negativo :T

David
Humano

En terminos practicos, como se aplica esto a un robot movil, digamos,de 2 ruedas controlables y una rueda loca. Para la planeacion de rutas. Es decir como estos sistemas dictaminan la velocidad de los motores en el sistema, para que ejecute la rutra trazada.

Por cierto buenisima la pagina y excelentes las explicaciones.

Gl4r3
Admin

Hummm… ¿es una pregunta o es una afirmación?

wpDiscuz