Porque la interpolación no fue una buena idea

Mientras que estamos interpolando la cosa va bien y la operacion es bastante precisa, pero en nuestro problema en general no necesitamos interpolar nada sino extrapolar, es decir que tenemos que averiguar que pasara en el futuro.

Esto es bastante mas dificil de lo que parece por muchas razones, la primera y mas antiintuitiva es que no se puede interpolar directamente y en funcion de x ya que tampoco tenemos estimacion de como crece x asi que nos quedan dos opciones:

interpolar x e y en funcion de t (por ejemplo el numero del frame en que estamos).
interpolar x en funcion de t e y en funcion de x.

Esto no es demasiado problema pero vamos perdiendo precision. El verdadero problema es que el polinomio se ajusta muy bien entre los n puntos que le damos, sin embargo predecir lo que hara la funcion a partir de ahi no es facil.

Algunos ejemplos:


En la zona en que se interpola las funciones coinciden, pero luego el polinomio crece mucho mas rápido por lo que la estimación es cada vez peor.


Para esta línea la estimación es casi perfecta, pero para conseguir esto fue necesario probar diferentes separaciones entre puntos y grados del polinomio, este en concreto tiene grado 4 y los puntos han sido tomados cada 5t.


Este es un caso extremadamente malo en que la funcion de estimacion crece de forma exponencial a diferencia de la original que es lineal.

Otro ejemplo de funciones que crecen a diferente velocidad.

Lo importante a darse cuenta es que dependemos de los puntos tomados, la separación entre ellos, la función original y el grado del polinomio usado y los parámetros que son buenos para una función original no lo son para otra, de modo que tendríamos que dejar al programa que decida, esto es un montón de trabajo y computo.

La idea ahora es usar algún tipo de componente derivativa dentro de la dinámica inercial para suplir esto que nos ayude a seguir objetos en trayectoria curva y no complique excesivamente las cosas para aquellos que siguen una recta.

Interpolación (3)

La idea que proponen en numerical recipes para la interpolación de Lagrange es bastante mejor, la idea es definir:

como el valor x del unico polinomio de grado 0 (una constante) que pasa por , entonces , definimos de la misma forma y de forma analoga diremos que como el valor en x del unico polinomio de grado 1 (una recta) que pasa a la vez por y , seguimos definiendo de esta forma todos los polinomios hasta el grado del polinomio de interpolacion que queramos, ya que el polinomio es el unico polinomio de grado N que pasa por todos los puntos que queremos!

Si ponemos los valores de P en una tabla en forma de "arbol" obtenemos lo siguiente:

El algoritmo para obtener hijos a partir de los ancestros de este arbol de llama algoritmo de Neville:



Esto funciona porque los "padres" ya están de acuerdo en .

La siguiente mejora para la recursión es guardar un registro de las diferencias entre padres e hijos, esto es:

Para


Y juntando esto con la ecuacion de Neville obtenemos:


Para cada nivel m en nuestro arbol las Ces y las Des son las correcciones que hay que aplicar para convertir el polinomio en un orden mayor.

Finalmente obtenemos , que es el resultado de mas los Ces y Des que haya en el camino en el árbol tomando siempre el hijo de la derecha.


Las ideas fueron sacadas de Numerical Recipes in C, que como siempre esta mucho mejor explicado que aquí y mucho mas en ingles.

Interpolación (2)

Entre dos puntos (diferentes) pasa una única línea, entre tres puntos (diferentes) pasa una única función cuadrática etc. etc.

El polinomio de Lagrange de grado N-1 nos da exactamente eso para N puntos tales que , esto es:



La idea es que en los puntos que nos dan todos los polinomios excepto uno serán 0, y el que no es cero nos dará justo el valor esperado.


Programar esto tal como viene no es una idea demasiado buena ya que tenemos una complejidad O(N²) por cada punto nuevo que queramos calcular.

Interpolación (1)

A veces conocemos el valor de una función f(x) en unos puntos dados siendo pero no tenemos una expresión que nos permita calcular f(x) en otro punto cualquiera.

La misión es obtener una estimación de f(x) para un x cualquiera de modo que la curva que dibujemos sea "suave" entre los puntos y en su alrededor. La forma en que aproximemos las funciones tiene que ser general porque no sabemos en principio con que función nos estamos enfrentando. Las aproximaciones mas comunes o al menos las que aprendí en mis clases de calculo son (1)Polinomios (2)Cocientes de polinomios y (3)Funciones trigonométricas.

Hay funciones que tienen un "mal comportamiento" con la interpolación, para saber si el comportamiento ha sido bueno o malo es útil tener una estimación del error, hay que notar que estamos presumiendo que las funciones son suaves y continuas, lo que es perfecto para el movimiento real.

La idea básica es encontrar una función que encaje en los puntos dados y luego evaluarla para otro punto deseado, la mayoría de las aproximaciones empiezan con un punto y van haciendo correcciones al ir agregando otros nuevos puntos, esto nos da una complejidad de

La misión es obtener una estimación de f(x) para un x cualquiera de modo que la curva que dibujemos sea "suave" entre los puntos y en su alrededor. La forma en que aproximemos las funciones tiene que ser general porque no sabemos en principio con que función nos estamos enfrentando. Las aproximaciones mas comunes o al menos las que aprendí en mis clases de calculo son (1)Polinomios (2)Cocientes de polinomios y (3)Funciones trigonometricas.

Hay funciones que tienen un "mal comportamiento" con la interpolación, para saber si el comportamiento ha sido bueno o malo es útil tener una estimación del error, hay que notar que estamos presumiendo que las funciones son suaves y continuas, lo que es perfecto para el movimiento real.

La interpolación local con un numero finito de vecinos no es continua en las derivadas, si necesitamos que sea continua en las derivadas tenemos que usas la no localidad, por ejemplo con splines, es decir entre dos puntos dados definimos un polinomio que los interpola.