¿Alguna vez has necesitado encontrar un polinomio que pase por varios puntos? ¡No te preocupes, Lagrange está aquí para salvarte! Aqui te cuento todo lo que necesitas saber sobre interpolación y polinomios.
Es importante entender que un campo finito es un conjunto de elementos que cumplen con propiedades específicas. Estas propiedades permiten la realización de operaciones como suma, multiplicación, cálculo de inversos, entre otras. Para una discusión más detallada sobre campos finitos, te invito a consultar mi artículo anterior:
Son los estados de evaluación del programa, posteriormente se guardan en una estructura de datos como el 'array'. Esta huella se utiliza en combinación con el campo finito para hacer una interpolación.
Un ejemplo de la huella para la funcion de Fibonacci seria:
[1, 1, 2, 3, 5, 8, 13]
La interpolación de Lagrange es un método utilizado para encontrar un polinomio que pase por un conjunto de puntos. Este método se utiliza para encontrar un polinomio que represente la salida del programa. Pero, ¿Cómo funciona? - Usando polinomios de base.
Los polinomios de base forman los bloques de construcción del espacio polinómico. Son análogos a los vectores de base en un espacio vectorial. Usando combinaciones lineales de polinomios de base, podemos crear cualquier polinomio.
El espacio polinómico es un conjunto de todos los posibles polinomios de un grado dado. El espacio polinómico se construye utilizando polinomios de base "linealmente independientes". Al combinar estos polinomios de base, podemos crear cualquier polinomio.
Los polinomios de base se consideran linealmente independientes si ningún polinomio se puede expresar como una combinación lineal de otros polinomios en el conjunto.
Usando una combinación lineal de polinomios de base, podemos construir cualquier polinomio en el espacio polinómico. Este concepto es similar a cómo usamos combinaciones lineales de vectores de base para crear cualquier vector en un espacio vectorial.
Un ejemplo de combinación lineal es:
Dado los vectores u = (1, 2) y v = (3, 4), su combinación lineal 2u + 3v es igual a:
(2*1 + 3*3, 2*2 + 3*4) = (11, 16).
Sirve porque vamos a interpolar la huella con los elementos del campo finito. ¿Cual es la finalidad de esto? - tener una representacion polinomica de la secuencia a lo largo de campo finito.
Para mas detalles sobre la interpolacion de Lagrange te sugiero el siguiente video:
Hemos interpolado el campo finito con la huella del programa y obtuvimos un polinomio. Este polinomio es unico, y explicaremos como a continuación:
La matriz invertible en la interpolación de Lagrange garantiza la unicidad y la existencia del polinomio interpolante. Para que la matriz sea invertible el determinante debe ser diferente de cero.
Un determinante diferente de cero garantiza que la matriz tiene una inversa, siendo esta matriz inversa la unica que puede resultar en la identidad multiplicativa o matriz identidad cuando es multiplicada por la matriz original, es decir: A * A^-1 = I
Para mas detalles ver:
Para aclarar, existen diversos metodos para interpolar, pero Lagrange es preferido sobre otros métodos como el de Newton porque requiere "menos cálculos", especialmente para conjuntos de datos que se evaluan en el mismo domino (nuestro campo finito)
Deciamos "menos cálculos", pero el metodo de newton es x1.17 mejor que Langrange
(descargar el articulo: 'Comparison of Lagrange’s and Newton’s interpolating polynomials').
Entonces, ¿Pór que decimos que hacemos menos calculos? Porque las bases polinomicas solo dependen del dominio.En nuestro caso el dominio es el campo finito (que siempre sera el mismo), por lo que podemos precalcular todas las bases polinomicas y reusarlas.
Los polinomios tienen propiedades especiales como:
Se puede expandir el dominio de evaluacion (Reed-Solomon error correcting codes).
Identidad multiplicativa.
En algunos casos tienen inversas.
mas...
En conclusión, los campos finitos, la traza del programa, la interpolación de Lagrange, los polinomios base y el espacio de polinomios son conceptos que permiten cálculos seguros y eficientes en una variedad de aplicaciones.
Para la proxima publicacion venimos con: Evaluación de polinomica, Corrección de errores de Reed-Solomon y Cosets.