stringtranslate.com

Polinomio de Lagrange

Esta imagen muestra, para cuatro puntos ( (−9, 5) , (−4, 2) , (−1, −2) , (7, 9) ), el polinomio de interpolación (cúbico) L ( x ) (discontinuo, negro), que es la suma de los polinomios base escalados y 0 0 ( x ) , y 1 1 ( x ) , y 2 2 ( x ) y y 3 3 ( x ) . El polinomio de interpolación pasa por los cuatro puntos de control, y cada polinomio base escalado pasa por su respectivo punto de control y es 0, donde x corresponde a los otros tres puntos de control.

En el 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 con los que se denominan nodos y los que se denominan valores . El polinomio de Lagrange tiene grado y asume cada valor en el nodo correspondiente,

Aunque el nombre se debe a 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 fácil de una fórmula publicada en 1783 por Leonhard Euler . [3]

Los usos de los polinomios de Lagrange incluyen el método de integración numérica de Newton-Cotes , el esquema de intercambio de secretos de Shamir en criptografía y la corrección de errores de Reed-Solomon en la teoría de 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 nodos , que deben ser todos distintos, para los índices , la base de Lagrange para polinomios de grado para esos nodos es el conjunto de polinomios cada uno de grado que toman valores si y . Usando el delta de Kronecker esto puede escribirse Cada polinomio base puede describirse explícitamente por el producto:

Observe que el numerador tiene raíces en los nodos mientras que el denominador escala el polinomio resultante de modo que

El polinomio de interpolación de Lagrange para aquellos nodos a través de los valores correspondientes es la combinación lineal:

Cada polinomio base tiene grado , por lo que la suma tiene grado , e interpola los datos porque

El polinomio de interpolación es único. Demostración: supongamos que el polinomio de grado interpola los datos. Entonces la diferencia es cero en nodos distintos . Pero el único polinomio de grado con más de raíces es la función cero constante, por lo que o

Forma baricéntrica

Cada polinomio base de Lagrange se puede reescribir como el producto de tres partes: una función común a cada polinomio base, una constante específica del nodo (llamada peso baricéntrico ) y una parte que representa el desplazamiento de a : [4]

Al factorizar la suma, podemos escribir el polinomio de Lagrange en la llamada primera forma baricéntrica :

Si los pesos se han calculado previamente, esto solo requiere operaciones de comparación para evaluar cada polinomio base de Lagrange individualmente.

La fórmula de interpolación baricéntrica también se puede actualizar fácilmente para incorporar un nuevo nodo dividiendo cada uno de los , por y construyendo el nuevo como se indicó anteriormente.

Para cualquier porque la función constante es el único polinomio de grado interpolando los datos Podemos simplificar aún más la fórmula baricéntrica dividiendo

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

Esta segunda forma tiene ventajas en cuanto a costo y precisión de cálculo: evita la evaluación de ; el trabajo para calcular cada término en el denominador ya se ha hecho en el cálculo y, por lo tanto, calcular la suma en el denominador solo cuesta operaciones de suma; para los puntos de evaluación que están cerca de uno de los nodos , la cancelación catastrófica normalmente sería un problema para el valor , sin embargo, esta cantidad aparece tanto en el numerador como en el denominador y los dos se cancelan dejando una buena precisión relativa en el resultado final.

El uso de esta fórmula para evaluar en uno de los nodos dará como resultado un resultado indeterminado ; las implementaciones informáticas deben reemplazar dichos resultados por

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

Una perspectiva desde el álgebra lineal

La solución de un problema de interpolación conduce a un problema de álgebra lineal que equivale a la inversión de una matriz. Si utilizamos una base monomial estándar para nuestro polinomio de interpolación , debemos invertir la matriz de Vandermonde para obtener los coeficientes de . Si elegimos una base mejor, la base de Lagrange, , simplemente obtenemos la matriz identidad , , 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, estamos comprobando los restos de polinomios cuando se dividen por números lineales.

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

Ejemplo

Deseamos interpolar sobre el dominio en los tres nodos :

El polinomio del nodo es

Los pesos baricéntricos son

Los polinomios base de Lagrange son

El polinomio de interpolación de Lagrange es:

En (segunda) forma baricéntrica,

Notas

Ejemplo de divergencia de interpolación para un conjunto de polinomios de Lagrange.

La forma de Lagrange 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 ver a partir de la invertibilidad de la matriz de Vandermonde, debido a la no desaparición del determinante de Vandermonde .

Pero, como se puede ver en la construcción, cada vez que cambia un nodo x k , todos los polinomios de base de Lagrange deben recalcularse. Una forma mejor del polinomio de interpolación para fines prácticos (o computacionales) es la forma baricéntrica de la interpolación de Lagrange (ver 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, produce un polinomio que oscila por encima y por debajo de la función verdadera. Este comportamiento tiende a crecer con el número de puntos, lo que conduce a una divergencia conocida como fenómeno de Runge ; el problema puede eliminarse eligiendo puntos de interpolación en los nodos de Chebyshev . [5]

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

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

Al interpolar una función dada f por un polinomio de grado k en los nodos obtenemos el resto que puede expresarse como [6]

donde es la notación para diferencias divididas . Alternativamente, el resto se puede expresar como una integral de contorno en el dominio complejo como

El resto se puede unir como

Derivación

Claramente, es cero en los nodos. Para encontrar en un punto , defina una nueva función y elija donde es la constante que se requiere determinar para un dado . Elegimos de modo que tenga ceros (en todos los nodos y ) entre y (incluidos los puntos finales). Suponiendo que es -veces diferenciable, ya que y son polinomios y, por lo tanto, son infinitamente diferenciables, será -veces diferenciable. Por el teorema de Rolle , tiene ceros, tiene ceros... tiene 1 cero, digamos . Escribiendo explícitamente :

(Porque el poder más alto de in es )

La ecuación se puede reorganizar como [7]

Ya que tenemos

Derivados

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

Recordemos (véase § Definición arriba) que cada polinomio base de Lagrange es

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

La segunda derivada es

La tercera derivada es

y lo mismo para las derivadas superiores.

Tenga en cuenta que todas estas fórmulas para derivadas no son válidas en un nodo o cerca de él. Un método para evaluar todos los órdenes de derivadas de un polinomio de Lagrange de manera eficiente en todos los puntos del dominio, incluidos los nodos, es convertir el polinomio de Lagrange a la forma de base de potencia y luego evaluar las derivadas.

Campos finitos

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

Véase también

Referencias

  1. ^ Lagrange, Joseph-Louis (1795). "Leçon Cinquième. Sur l'usage des courbes dans la solucion des problèmes". Leçons Elémentaires sur les Mathématiques (en francés). París.Republicado en Serret, Joseph-Alfred , ed. (1877). Obras de Lagrange . vol. 7. Gauthier-Villars. págs. 271–287.Traducido como "Conferencia V. Sobre el empleo de curvas en la solución de problemas". Lecciones de matemáticas elementales . Traducido por McCormack, Thomas J. (2.ª ed.). Open Court. 1901. págs. 127–149.
  2. ^ Waring, Edward (1779). "Problemas relacionados con las interpolaciones". Philosophical Transactions of the Royal Society . 69 : 59–67. doi :10.1098/rstl.1779.0008.
  3. ^ Meijering, Erik (2002). "Una cronología de la interpolación: desde la astronomía antigua hasta el procesamiento moderno de señales e imágenes" (PDF) . Actas del IEEE . 90 (3): 319–342. doi :10.1109/5.993400.
  4. ^ Berrut, Jean-Paul ; Trefethen, Lloyd N. (2004). "Interpolación de Lagrange baricéntrica" ​​(PDF) . SIAM Review . 46 (3): 501–517. Bibcode :2004SIAMR..46..501B. doi : 10.1137/S0036144502417715 .
  5. ^ Quarteroni, Alfio ; Saleri, Fausto (2003). Computación científica con MATLAB. Textos en ciencia computacional e ingeniería. Vol. 2. Springer. p. 66. ISBN 978-3-540-44363-6..
  6. ^ Abramowitz, Milton ; Stegun, Irene Ann , eds. (1983) [junio de 1964]. "Capítulo 25, ecuación 25.2.3". Manual de funciones matemáticas con fórmulas, gráficos y tablas matemáticas . Serie de Matemáticas Aplicadas. Vol. 55 (Novena reimpresión con correcciones adicionales de la décima impresión original con correcciones (diciembre de 1972); primera ed.). Washington DC; Nueva York: Departamento de Comercio de los Estados Unidos, Oficina Nacional de Normas; Publicaciones de Dover. pág. 878. ISBN 978-0-486-61272-0. LCCN  64-60036. MR  0167642. LCCN  65-12253.
  7. ^ "Interpolación" (PDF) . pp. 12–15. Archivado desde el original (PDF) el 15 de febrero de 2017.

Enlaces externos