Fields (Campos), Interpolación de Lagrange y Polinomios 🤯⬇️: STARKS II
April 1st, 2023

¿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.

Intro a los campos finitos:

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:

¿Qué es la huella o 'trace'?

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]

Interpolación de Lagrange

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.

fn(x) es el polinomio interpolado y Li(x) es el polinomio base
fn(x) es el polinomio interpolado y Li(x) es el polinomio base

Espacio Polinómico?

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.

Polinomios Linealmente Independientes?

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.

¿Combinación Lineal?

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).

Ok, me hablaste de la huella y la interpolación. ¿De qué sirve saber esto?

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:

Ok, ¿Qué hemos hecho hasta ahora?

Hemos interpolado el campo finito con la huella del programa y obtuvimos un polinomio. Este polinomio es unico, y explicaremos como a continuación:

Matriz Invertible, Unicidad e Identidad Multiplicativa

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:

¿Por qué el método de interpolación de Lagrange en lugar del método de Newton?

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.

¿Por qué interpolamos para obtener polinomios?

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...

Conclusión

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.

Subscribe to 0xFenrir
Receive the latest updates directly to your inbox.
Nft graphic
Mint this entry as an NFT to add it to your collection.
Verification
This entry has been permanently stored onchain and signed by its creator.
More from 0xFenrir

Skeleton

Skeleton

Skeleton