Polinomio de Lagrange

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Polynomials used for interpolation

Esta imagen muestra, por cuatro puntos ((9, 5), (4, 2), (1, - 2), (7, 9)), el polinomio de interpolación cúbica L()x) (dashed, black), que es la suma de escalada polinomios de base Sí.₀l₀()x), Sí.₁l₁()x), Sí.₂l₂()x) y Sí.₃l₃()x). El polinomio de interpolación pasa a través de los cuatro puntos de control, y cada uno escalada polinomio de base pasa a través de su punto de control respectivos y es 0 donde x corresponde a los otros tres puntos de control.

En análisis numérico, el polinomio de interpolación de Lagrange es el único polinomio de menor grado que interpola un conjunto dado de datos.

Dado un conjunto de datos de pares de coordenadas ${displaystyle (x_{j},y_{j})}$ con ${displaystyle 0leq jleq k,}$ el $x_{j}$ se llaman nodos y el $y_{j}$ se llaman valores. El polinomio Lagrange $L(x)$ grado ${textstyle leq k}$ y asume cada valor en el nodo correspondiente, ${displaystyle L(x_{j})=y_{j}.}$

Aunque lleva el nombre de Joseph-Louis Lagrange, quien lo publicó en 1795, el método fue descubierto por primera vez en 1779 por Edward Waring. También es una fácil consecuencia de una fórmula publicada en 1783 por Leonhard Euler.

Los usos de los polinomios de Lagrange incluyen el método de Newton-Cotes de integración numérica, el esquema secreto compartido de Shamir en criptografía y la corrección de errores de Reed-Solomon en la teoría de la codificación.

Para los nodos equiespaciados, la interpolación de Lagrange es susceptible al fenómeno de gran oscilación de Runge.

Definición

Dado un conjunto de ${textstyle k+1}$ nodos ${displaystyle {x_{0},x_{1},ldotsx_{k}}}$ , que todos deben ser distintos, ${displaystyle x_{j}neq x_{m}}$ para índices ${displaystyle jneq m}$ , el Base de referencia para polinomios de grado ${textstyle leq k}$ para esos nodos es el conjunto de polinomios ${textstyle {ell _{0}(x),ell _{1}(x),ldotsell _{k}(x)}}$ cada grado ${textstyle k}$ que toman valores ${textstyle ell _{j}(x_{m})=0}$ si ${textstyle mneq j}$ y ${textstyle ell _{j}(x_{j})=1}$ . Usando el delta Kronecker esto se puede escribir ${textstyle ell _{j}(x_{m})=delta _{jm}.}$ Cada base polinomio puede ser descrito explícitamente por el producto:

{displaystyle {begin{aligned}ell _{j}(x)&={frac {(x-x_{0})}{(x_{j}-x_{0})}}cdots {frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}cdots {frac {(x-x_{k})}{(x_{j}-x_{k})}}\[10mu]&=prod _{begin{smallmatrix}0leq mleq k\mneq jend{smallmatrix}}{frac {x-x_{m}}{x_{j}-x_{m}}}.end{aligned}}}

Note que el numerador ${textstyle prod _{mneq j}(x-x_{m})}$ tiene ${textstyle k}$ raíces en los nodos ${textstyle {x_{m}}_{mneq j}}$ mientras que el denominador ${textstyle prod _{mneq j}(x_{j}-x_{m})}$ escala el polinomio resultante para que ${textstyle ell _{j}(x_{j})=1.}$

El polinomio interpolador de Lagrange para esos nodos a través del correspondiente valores ${displaystyle {y_{0},y_{1},ldotsy_{k}}}$ es la combinación lineal:

{displaystyle L(x)=sum _{j=0}^{k}y_{j}ell _{j}(x).}

Cada base polinomio tiene grado ${textstyle k}$ , así que la suma ${textstyle L(x)}$ grado ${textstyle leq k}$ , e interpola los datos porque ${textstyle L(x_{m})=sum _{j=0}^{k}y_{j}ell _{j}(x_{m})=sum _{j=0}^{k}y_{j}delta _{mj}=y_{m}.}$

El polinomio interpolador es único. Prueba: asumir el polinomio ${textstyle M(x)}$ grado ${textstyle leq k}$ interpola los datos. Entonces la diferencia ${textstyle M(x)-L(x)}$ es cero a ${textstyle k+1}$ nodos distintos ${textstyle {x_{0},x_{1},ldotsx_{k}}.}$ Pero el único polinomio de grado ${textstyle leq k}$ con más que ${textstyle k}$ raíces es la función cero constante, así que ${textstyle M(x)-L(x)=0,}$ o ${textstyle M(x)=L(x).}$

Forma baricéntrica

Cada polinomio base de Lagrange ${textstyle ell _{j}(x)}$ puede ser reescrito como el producto de tres partes, una función ${textstyle ell (x)=prod _{m}(x-x_{m})}$ común a cada base polinomial, una constante de nodo específico ${textstyle w_{j}=prod _{mneq j}(x_{j}-x_{m})^{-1}}$ (llamado el peso barícéntrico), y una parte que representa el desplazamiento de ${textstyle x_{j}}$ a ${textstyle x}$ :

{displaystyle ell _{j}(x)=ell (x){dfrac {w_{j}}{x-x_{j}}}}

Por factoring ${textstyle ell (x)}$ de la suma, podemos escribir el polinomio Lagrange en el llamado primera forma barícentrica:

{displaystyle L(x)=ell (x)sum _{j=0}^{k}{frac {w_{j}}{x-x_{j}}}y_{j}.}

Si los pesos $w_{j}$ han sido pre-computados, esto requiere sólo ${mathcal O}(k)$ operaciones en comparación con ${displaystyle {mathcal {O}}(k^{2})}$ para evaluar cada polinomio base de Lagrange $ell _{j}(x)$ individualmente.

La fórmula de interpolación barícena también se puede actualizar fácilmente para incorporar un nuevo nodo $x_{k+1}$ dividiendo cada uno de los $w_{j}$ , $j=0dots k$ por $(x_{j}-x_{k+1})$ y construir el nuevo $w_{k+1}$ como arriba.

Para cualquier ${textstyle x,}$ ${textstyle sum _{j=0}^{k}ell _{j}(x)=1}$ porque la función constante ${textstyle g(x)=1}$ es el único polinomio de grado $leq k$ interpolar los datos ${textstyle {(x_{0},1),(x_{1},1),ldots(x_{k},1)}.}$ Así podemos simplificar aún más la fórmula baricéntrica dividiendo ${displaystyle L(x)=L(x)/g(x)colon }$

{displaystyle {begin{aligned}L(x)&=ell (x)sum _{j=0}^{k}{frac {w_{j}}{x-x_{j}}}y_{j}{Bigg /}ell (x)sum _{j=0}^{k}{frac {w_{j}}{x-x_{j}}}\[10mu]&=sum _{j=0}^{k}{frac {w_{j}}{x-x_{j}}}y_{j}{Bigg /}sum _{j=0}^{k}{frac {w_{j}}{x-x_{j}}}.end{aligned}}}

Esto se llama la segunda forma o forma verdadera de la fórmula de interpolación baricéntrica.

Esta segunda forma tiene ventajas en el costo y la precisión de la computación: evita la evaluación de $ell (x)$ ; el trabajo para calcular cada término en el denominador $w_{j}/(x-x_{j})$ ya se ha hecho en la informática ${displaystyle {bigl (}w_{j}/(x-x_{j}){bigr)}y_{j}}$ y así computar la suma en el denominador cuesta sólo ${textstyle k-1}$ operaciones adicionales; para los puntos de evaluación ${textstyle x}$ que están cerca de uno de los nodos ${textstyle x_{j}}$ , la cancelación catastrófica normalmente sería un problema para el valor ${textstyle (x-x_{j})}$ , sin embargo esta cantidad aparece tanto en numerador y denominador y los dos cancelan dejando buena precisión relativa en el resultado final.

Usar esta fórmula para evaluar $L(x)$ a uno de los nodos $x_{j}$ resultará en el indeterminado ${displaystyle infty y_{j}/infty }$ ; las implementaciones informáticas deben reemplazar esos resultados por ${displaystyle L(x_{j})=y_{j}.}$

Cada polinomio de base de Lagrange también se puede escribir en forma baricéntrica:

{displaystyle ell _{j}(x)={frac {w_{j}}{x-x_{j}}}{Bigg /}sum _{m=0}^{k}{frac {w_{m}}{x-x_{m}}}.}

Una perspectiva desde el álgebra lineal

La solución de un problema de interpolación conduce a un problema en el álgebra lineal que equivale a la inversión de una matriz. Utilizando una base monomial estándar para nuestro polinomio de interpolación ${textstyle L(x)=sum _{j=0}^{k}x^{j}m_{j}}$ , debemos invertir la matriz de Vandermonde ${displaystyle (x_{i})^{j}}$ para resolver $L(x_{i})=y_{i}$ para los coeficientes $m_{j}$ de $L(x)$ . Al elegir una mejor base, la base Lagrange, ${textstyle L(x)=sum _{j=0}^{k}l_{j}(x)y_{j}}$ , simplemente tenemos la matriz de identidad, $delta _{ij}$ , que es su propio inverso: la base de Lagrange automáticamente invertidos el análogo de la matriz de Vandermonde.

Esta construcción es análoga al teorema chino del resto. En lugar de verificar los restos de los números primos del módulo entero, estamos verificando los residuos de los polinomios cuando se dividen por lineales.

Además, cuando el orden es grande, se puede usar la transformación rápida de Fourier para resolver los coeficientes del polinomio interpolado.

Ejemplo

Deseamos interponernos $f(x)=x^{2}$ sobre el dominio ${displaystyle 1leq xleq 3}$ en los tres nodos ${displaystyle {1,,2,,3}}$ :

{displaystyle {begin{aligned}x_{0}&=1,&&&y_{0}=f(x_{0})&=1,\[3mu]x_{1}&=2,&&&y_{1}=f(x_{1})&=4,\[3mu]x_{2}&=3,&&&y_{2}=f(x_{2})&=9.end{aligned}}}

El nodo polinomio $ell$ es

{displaystyle ell (x)=(x-1)(x-2)(x-3)=x^{3}-6x^{2}+11x-6.}

Los pesos baricéntricos son

{displaystyle {begin{aligned}w_{0}&=(1-2)^{-1}(1-3)^{-1}={tfrac {1}{2}},\[3mu]w_{1}&=(2-1)^{-1}(2-3)^{-1}=-1,\[3mu]w_{2}&=(3-1)^{-1}(3-2)^{-1}={tfrac {1}{2}}.end{aligned}}}

Los polinomios de la base de Lagrange son

{displaystyle {begin{aligned}ell _{0}(x)&={frac {x-2}{1-2}}cdot {frac {x-3}{1-3}}={tfrac {1}{2}}x^{2}-{tfrac {5}{2}}x+3,\[5mu]ell _{1}(x)&={frac {x-1}{2-1}}cdot {frac {x-3}{2-3}}=-x^{2}+4x-3,\[5mu]ell _{2}(x)&={frac {x-1}{3-1}}cdot {frac {x-2}{3-2}}={tfrac {1}{2}}x^{2}-{tfrac {3}{2}}x+1.end{aligned}}}

El polinomio de interpolación de Lagrange es:

{displaystyle {begin{aligned}L(x)&=1cdot {frac {x-2}{1-2}}cdot {frac {x-3}{1-3}}+4cdot {frac {x-1}{2-1}}cdot {frac {x-3}{2-3}}+9cdot {frac {x-1}{3-1}}cdot {frac {x-2}{3-2}}\[6mu]&=x^{2}.end{aligned}}}

En (segunda) forma baricéntrica,

{displaystyle L(x)={frac {displaystyle sum _{j=0}^{2}{frac {w_{j}}{x-x_{j}}}y_{j}}{displaystyle sum _{j=0}^{2}{frac {w_{j}}{x-x_{j}}}}}={frac {displaystyle {frac {tfrac {1}{2}}{x-1}}+{frac {-4}{x-2}}+{frac {tfrac {9}{2}}{x-3}}}{displaystyle {frac {tfrac {1}{2}}{x-1}}+{frac {-1}{x-2}}+{frac {tfrac {1}{2}}{x-3}}}}.}

Resto en la fórmula de interpolación de Lagrange

Cuando interpolar una función determinada f por un polinomio de grado $k$ en los nodos ${displaystyle x_{0},...,x_{k}}$ tenemos el resto $R(x)=f(x)-L(x)$ que pueden expresarse

Derivados

La $d$ ésima derivada de un polinomio de interpolación de Lagrange se puede escribir en términos de las derivadas de los polinomios base,

Campos finitos

El polinomio de Lagrange también se puede calcular en campos finitos. Esto tiene aplicaciones en criptografía, como en el esquema Secret Sharing de Shamir.

Contenido relacionado

Más resultados...