polinomio de Lagrange

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

Dado un conjunto de datos de pares de coordenadas${\displaystyle \textstyle (x_ {j}, y_ {j})}$⁠ , el ⁠${\displaystyle \textstyle x_ {j}}$⁠ se llaman nodos y el ⁠${\displaystyle \textstyle y_ {j}}$Se denominan valores . El polinomio de Lagrange${\displaystyle L(x)}$que interpola los datos y asume cada valor en el nodo correspondiente ,${\displaystyle \textstyle L(x_{j})=y_{j}}$⁠ . Si hay ⁠${\displaystyle k+1}$⁠ pares de datos, el polinomio de Lagrange tiene grado ⁠${\displaystyle \leq k}$.​

Aunque recibió su nombre de Joseph-Louis Lagrange , quien lo publicó en 1795, ^{[ 1 ]} el método fue descubierto por primera vez en 1779 por Edward Waring . ^{[ 2 ]} También es una consecuencia sencilla de una fórmula publicada en 1783 por Leonhard Euler . ^{[ 3 ]}

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

Para nodos equidistantes, la interpolación de Lagrange es susceptible al fenómeno de grandes oscilaciones de Runge.

Dado un conjunto de ⁠${\displaystyle k+1}$nodos​${\displaystyle \{x_{0},x_{1},\ldots ,x_{k}\}}$, que deben ser todos distintos ,${\displaystyle \textstyle x_ {j}\neq x_ {m}}$para índices​${\displaystyle j\neq m}$⁠ , la base de Lagrange para polinomios de grado ⁠${\displaystyle \leq k}$Para esos nodos es el conjunto de polinomios${\displaystyle \textstyle \{\ell _{0}(x),\ell _{1}(x),\ldots ,\ell _{k}(x)\}}$cada uno de grado${\displaystyle k}$que toman valores${\displaystyle \textstyle \ell _ {j} (x_ {m}) = 0}$si​​${\displaystyle m\neq j}$y​​${\displaystyle \textstyle \ell _ {j} (x_ {j}) = 1}$⁠ . Usando la delta de Kronecker, esto se puede escribir ⁠${\displaystyle \textstyle \ell _ {j}(x_ {m}) = \ delta _ {jm}}$Cada polinomio base puede describirse explícitamente mediante 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})}}\\[8mu]&=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\frac {x-x_{m}}{x_{j}-x_{m}}}{\vphantom {\Bigg |}}.\end{aligned}}}$$

Observe que el numerador${\displaystyle \textstyle \prod _{m\neq j}(x-x_{m})}$tiene​​${\displaystyle k}$raíces en los nodos${\displaystyle \textstyle \{x_{m}\}_{m\neq j}}$mientras que el denominador${\displaystyle \textstyle \prod _{m\neq j}(x_{j}-x_{m})}$escala el polinomio resultante de modo que${\displaystyle \textstyle \ell _{j}(x_{j})=1}$.​

El polinomio de interpolación de Lagrange para esos nodos a través de los valores correspondientes${\displaystyle \{y_{0},y_{1},\ldots ,y_{k}\}}$es la combinación lineal :

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

Cada polinomio base tiene grado ⁠${\displaystyle k}$⁠ , por lo tanto la suma ⁠${\displaystyle L(x)}$tiene título​${\displaystyle \leq k}$⁠ , e interpola los datos porque ⁠${\displaystyle \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. Demostración: supongamos algún polinomio .${\displaystyle M(x)}$grado​​${\displaystyle \leq k}$⁠ interpola los datos. Luego la diferencia ⁠${\displaystyle M(x)-L(x)}$es cero en${\displaystyle k+1}$nodos distintos${\textstyle \{x_{0},x_{1},\ldots ,x_{k}\}}$. Pero el único polinomio de grado ⁠${\displaystyle \leq k}$con más de${\displaystyle k}$⁠ roots es la función cero constante, por lo tanto ⁠${\displaystyle M(x)-L(x)=0}$, o​${\displaystyle M(x)=L(x)}$.​

Cada polinomio base de Lagrange${\displaystyle \textstyle \ell _{j}(x)}$⁠ se puede reescribir como el producto de tres partes, una función ⁠${\displaystyle \textstyle \ell (x)=\prod _{m}(x-x_{m})}$⁠ común a todos los polinomios base, una constante específica del nodo ⁠${\displaystyle \textstyle w_{j}=\prod _{m\neq j}(x_{j}-x_{m})^{-1}}$( llamado peso baricéntrico ) y una parte que representa el desplazamiento desde${\displaystyle \textstyle x_{j}}$a​​${\displaystyle x}$: ^{[ 4 ]}​

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

Mediante factorización${\displaystyle \ell (x)}$A partir de la suma, podemos escribir el polinomio de Lagrange en la llamada primera forma baricéntrica :

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

Si los pesos${\displaystyle \textstyle w_{j}}$⁠ han sido precalculados, esto solo requiere ⁠${\displaystyle {\mathcal {O}}(k)}$operaciones en comparación con${\displaystyle \textstyle {\mathcal {O}}(k^{2})}$para evaluar cada polinomio base de Lagrange${\displaystyle \textstyle \ell _{j}(x)}$individualmente . (Véase la notación Big O ).

La fórmula de interpolación baricéntrica también se puede actualizar fácilmente para incorporar un nuevo nodo .${\displaystyle \textstyle x_{k+1}}$⁠ dividiendo cada uno de los ⁠${\displaystyle \textstyle w_{j}}$,​​${\displaystyle j=0\dots k}$por​​${\displaystyle \textstyle (x_{j}-x_{k+1})}$y construyendo el nuevo${\displaystyle \textstyle w_{k+1}}$como se indicó anteriormente.

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

$${\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}}}$$

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

Esta segunda forma tiene ventajas en cuanto a coste computacional y precisión: evita la evaluación de${\displaystyle \ell (x)}$; el trabajo para calcular cada término en el denominador${\displaystyle w_{j}/(x-x_{j})}$ya se ha hecho en informática${\displaystyle {\bigl (}w_{j}/(x-x_{j}){\bigr )}y_{j}}$y por lo tanto, calcular la suma en el denominador cuesta solo${\textstyle k}$operaciones de suma; para 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 el numerador como en el denominador y ambos se cancelan, lo que deja una buena precisión relativa en el resultado final.

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

Cada polinomio base de Lagrange también puede escribirse 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}}}.}$$

Resolver un problema de interpolación conduce a un problema de álgebra lineal equivalente a la inversión de una matriz. Usando 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}}$resolver${\displaystyle L(x_{i})=y_{i}}$para los coeficientes${\displaystyle m_{j}}$de${\displaystyle L(x)}$. Al elegir una base mejor, la base de Lagrange,${\textstyle L(x)=\sum _{j=0}^{k}l_{j}(x)y_{j}}$, simplemente obtenemos la matriz identidad ,${\displaystyle \delta _{ij}}$, que es su propia inversa: la base de Lagrange invierte automáticamente el análogo de la matriz de Vandermonde.

Esta construcción es análoga al teorema chino del resto . En lugar de comprobar los restos de números enteros módulo números primos, comprobamos los restos de polinomios al dividirlos por números lineales.

Además, cuando el orden es grande, se puede utilizar la transformada rápida de Fourier para calcular los coeficientes del polinomio interpolado.

Deseamos interpolar${\displaystyle f(x)=x^{2}}$sobre el dominio${\displaystyle 1\leq x\leq 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 polinomio de nodos${\displaystyle \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 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)&=y_{0}\cdot \ell _{0}(x)+y_{1}\cdot \ell _{1}(x)+y_{2}\cdot \ell _{2}(x)=x^{2}.\end{aligned}}}$$

En forma baricéntrica (segunda),

$${\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}}}}.}$$

La forma lagrangiana del polinomio de interpolación muestra el carácter lineal de la interpolación polinómica y la unicidad del polinomio de interpolación. Por lo tanto, se prefiere en demostraciones y argumentos teóricos. La unicidad también se puede apreciar en la invertibilidad de la matriz de Vandermonde, debido a que el determinante de Vandermonde no se anula .

Pero, como se puede observar en la construcción, cada vez que cambia un nodo x _k , es necesario recalcular todos los polinomios de la base de Lagrange. Una forma más adecuada del polinomio de interpolación para fines prácticos (o computacionales) es la forma baricéntrica de la interpolación de Lagrange (véase más abajo) o los polinomios de Newton .

La interpolación de Lagrange y otras interpolaciones en puntos igualmente espaciados, como en el ejemplo anterior, producen un polinomio que oscila por encima y por debajo de la función verdadera. Este comportamiento tiende a aumentar con el número de puntos, lo que da lugar a una divergencia conocida como el fenómeno de Runge ; el problema puede eliminarse eligiendo puntos de interpolación en los nodos de Chebyshev . ^{[ 5 ]}

Los polinomios de la base de Lagrange se pueden utilizar en la integración numérica para derivar las fórmulas de Newton-Cotes .

Al interpolar una función dada f mediante un polinomio de grado k en los nodos${\displaystyle x_{0},\dots ,x_{k}}$obtenemos el resto${\displaystyle R(x)=f(x)-L(x)}$que se puede expresar como ^{[ 6 ]}

$${\displaystyle {\begin{aligned}R(x)&=f[x_{0},\ldots ,x_{k},x]\ell (x)\\[1ex]&=\ell (x){\frac {f^{(k+1)}(\xi )}{(k+1)!}},&x_{0}<\xi <x_{k},\end{aligned}}}$$

dónde${\displaystyle f[x_{0},\ldots ,x_{k},x]}$es la notación para diferencias divididas . Alternativamente, el resto puede expresarse como una integral de contorno en el dominio complejo como

$${\displaystyle {\begin{aligned}R(x)&={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)(t-x_{0})\cdots (t-x_{k})}}dt\\[1ex]&={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)\ell (t)}}dt.\end{aligned}}}$$

El resto puede ser vinculado como

$${\displaystyle |R(x)|\leq {\frac {(x_{k}-x_{0})^{k+1}}{(k+1)!}}\max _{x_{0}\leq \xi \leq x_{k}}|f^{(k+1)}(\xi )|.}$$

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

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

Recordemos (véase la sección  Definición anterior) que cada polinomio base de Lagrange es

$${\displaystyle {\begin{aligned}\ell _{j}(x)&=\prod _{\begin{smallmatrix}m=0\\m\neq j\end{smallmatrix}}^{k}{\frac {x-x_{m}}{x_{j}-x_{m}}}.\end{aligned}}}$$

La primera derivada se puede encontrar utilizando la regla del producto :

$${\displaystyle {\begin{aligned}\ell _{j}'(x)&=\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\Biggl [}{\frac {1}{x_{j}-x_{i}}}\prod _{\begin{smallmatrix}m=0\\m\not =(i,j)\end{smallmatrix}}^{k}{\frac {x-x_{m}}{x_{j}-x_{m}}}{\Biggr ]}\\[5mu]&=\ell _{j}(x)\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{x-x_{i}}}.\end{aligned}}}$$

La segunda derivada es

$${\displaystyle {\begin{aligned}\ell _{j}''(x)&=\sum _{\begin{smallmatrix}i=0\\i\neq j\end{smallmatrix}}^{k}{\frac {1}{x_{j}-x_{i}}}{\Biggl [}\sum _{\begin{smallmatrix}m=0\\m\neq (i,j)\end{smallmatrix}}^{k}{\Biggl (}{\frac {1}{x_{j}-x_{m}}}\prod _{\begin{smallmatrix}n=0\\n\neq (i,j,m)\end{smallmatrix}}^{k}{\frac {x-x_{n}}{x_{j}-x_{n}}}{\Biggr )}{\Biggr ]}\\[10mu]&=\ell _{j}(x)\sum _{0\leq i<m\leq k}{\frac {2}{(x-x_{i})(x-x_{m})}}\\[10mu]&=\ell _{j}(x){\Biggl [}{\Biggl (}\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{x-x_{i}}}{\Biggr )}^{2}-\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{(x-x_{i})^{2}}}{\Biggr ]}.\end{aligned}}}$$

La tercera derivada es

$${\displaystyle {\begin{aligned}\ell _{j}'''(x)&=\ell _{j}(x)\sum _{0\leq i<m<n\leq k}{\frac {3!}{(x-x_{i})(x-x_{m})(x-x_{n})}}\end{aligned}}}$$

y lo mismo ocurre con las derivadas de orden superior.

Cabe señalar que todas estas fórmulas para derivadas no son válidas en un nodo o cerca de él. Un método para evaluar eficientemente todos los órdenes de derivadas de un polinomio de Lagrange en todos los puntos del dominio, incluidos los nodos, consiste en convertir el polinomio de Lagrange a su forma de base de potencias y, a continuación, evaluar las derivadas.

El polinomio de Lagrange también se puede calcular en cuerpos finitos . Esto tiene aplicaciones en criptografía , como en el esquema de compartición de secretos de Shamir .

• "Fórmula de interpolación de Lagrange" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• ALGLIB tiene implementaciones en C++ / C# / VBA / Pascal.
• GSL tiene un código de interpolación polinómica en C.
• SO tiene un ejemplo en MATLAB que demuestra el algoritmo y recrea la primera imagen de este artículo.
• Método de interpolación de Lagrange : notas, PPT, Mathcad, Mathematica, MATLAB, Maple
• Polinomio de interpolación de Lagrange en www.math-linux.com
• Weisstein, Eric W. "Polinomio de interpolación de Lagrange" . MathWorld .
• Función de hoja de cálculo de Excel para interpolación de Lagrange bicúbica
• Polinomios de Lagrange en Python