En el análisis numérico , los polinomios de Lagrange se utilizan para la interpolación de polinomios . Para un conjunto de puntos dado sin dos valores iguales, el polinomio de Lagrange es el polinomio de menor grado que asume en cada valor el valor correspondiente , de modo que las funciones coincidan en cada punto.
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 . [1] También es una consecuencia fácil de una fórmula publicada en 1783 por Leonhard Euler . [2]
Los usos de los polinomios de Lagrange incluyen el método Newton-Cotes de integración numérica y el esquema de intercambio secreto de Shamir en criptografía .
La interpolación de Lagrange es susceptible al fenómeno de gran oscilación de Runge . Como cambiando los puntosrequiere recalcular todo el interpolante, a menudo es más fácil usar polinomios de Newton en su lugar.
Definición
Dado un conjunto de k + 1 puntos de datos
donde no hay dos son iguales, el polinomio de interpolación en la forma de Lagrange es una combinación lineal
de polinomios de base de Lagrange
dónde . Observe cómo, dada la suposición inicial de que no hay dos son iguales, entonces (cuando ) , por lo que esta expresión siempre está bien definida. Los pares de razones con no están permitidos es que no hay función de interpolación tal que existiría; una función solo puede obtener un valor para cada argumento. Por otro lado, si también, entonces esos dos puntos serían en realidad un solo punto.
Para todos , incluye el término en el numerador, por lo que todo el producto será cero en :
Por otro lado,
En otras palabras, todos los polinomios base son cero en , excepto , por lo que sostiene que , porque carece de término.
Resulta que , entonces en cada punto , , mostrando que interpola la función exactamente.
Prueba
La función L ( x ) que se busca es un polinomio en x del menor grado que interpola el conjunto de datos dado; es decir, asume el valor y j en el correspondiente x j para todos los puntos de datos j :
Observa eso:
- En hay k factores en el producto y cada factor contiene una x , por lo que L ( x ) (que es una suma de estos k polinomios de grado) debe ser un polinomio de grado k como máximo .
Expanda este producto. Dado que el producto omite el término donde m = j , si i = j entonces todos los términos que aparecen son. Además, si i ≠ j entonces un término en el producto será (para m = i ),, poniendo a cero todo el producto. Entonces,
dónde es el delta de Kronecker . Entonces:
Por tanto, la función L ( x ) es un polinomio con grado como máximo k y donde L ( x i ) = y i .
Además, el polinomio de interpolación es único, como lo muestra el teorema de unisolvencia en el artículo de interpolación del polinomio .
También es cierto que:
ya que debe ser un polinomio de grado, como máximo, ky pasa por todos estos k + 1 puntos de datos:
resultando en una línea horizontal, ya que una línea recta es el único polinomio de grado menor que k + 1 que pasa por k + 1 puntos alineados.
Una perspectiva del álgebra lineal
Resolver un problema de interpolación conduce a un problema de álgebra lineal que equivale a la inversión de una matriz. Usando una base monomial estándar para nuestro polinomio de interpolación, debemos invertir la matriz de Vandermonde resolver para los coeficientes de . Al elegir una base mejor, la base de Lagrange,, simplemente obtenemos la matriz de 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 buscar restos de números enteros modulo primos, buscamos restos de 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.
Ejemplos de
Ejemplo 1
Deseamos interpolar ƒ ( x ) = x 2 en el rango 1 ≤ x ≤ 3, dados estos tres puntos:
El polinomio de interpolación es:
Ejemplo 2
Deseamos interpolar ƒ ( x ) = x 3 en el rango 1 ≤ x ≤ 4, dados estos cuatro puntos:
El polinomio de interpolación es:
Notas
La forma de Lagrange del polinomio de interpolación muestra el carácter lineal de la interpolación polinomial y la unicidad del polinomio de interpolación. Por tanto, se prefiere en pruebas y argumentos teóricos. La singularidad también se puede ver en la invertibilidad de la matriz de Vandermonde, debido a la no desaparición del determinante de Vandermonde .
Pero, como puede verse en la construcción, cada vez que un nodo x k cambia, todos los polinomios de base de Lagrange deben recalcularse. Una mejor forma del polinomio de interpolación para propósitos prácticos (o computacionales) es la forma baricéntrica de la interpolación de Lagrange (ver más abajo) o polinomios de Newton .
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 crecer con el número de puntos, dando lugar a una divergencia conocida como fenómeno de Runge ; el problema puede eliminarse eligiendo puntos de interpolación en los nodos de Chebyshev . [3]
Los polinomios de base de Lagrange se pueden utilizar en la integración numérica para derivar las fórmulas de Newton-Cotes .
Forma baricéntrica
Utilizando
podemos reescribir los polinomios de base de Lagrange como
o, definiendo los pesos baricéntricos [4]
simplemente podemos escribir
que se conoce comúnmente como la primera forma de la fórmula de interpolación baricéntrica.
La ventaja de esta representación es que el polinomio de interpolación ahora se puede evaluar como
que, si los pesos se han calculado previamente, solo requiere operaciones (evaluando y los pesos ) Opuesto a para evaluar los polinomios de 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 anteriormente.
Podemos simplificar aún más la primera forma considerando primero la interpolación baricéntrica de la función constante :
Divisor por no modifica la interpolación, pero produce
que se conoce como la segunda forma o forma verdadera de la fórmula de interpolación baricéntrica. Esta segunda forma tiene la ventaja de que no necesita ser evaluado para cada evaluación de .
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 se puede expresar como [5]
dónde es la notación para diferencias divididas . Alternativamente, el resto se puede expresar como una integral de contorno en un dominio complejo como
El resto se puede vincular como
Derivación [6]
Claramente, es cero en los nodos. Encontrar en un punto , define una nueva función y elige (Esto asegura en los nodos) donde es la constante que estamos obligados a determinar para un determinado . Ahora posee ceros (en todos los nodos y ) Entre y (incluidos los puntos finales). Asumiendo que es -veces diferenciables, y son polinomios y, por tanto, infinitamente diferenciables. Por el teorema de Rolle , posee ceros posee ceros ... tiene 1 cero, digamos . Escritura explícita:
- (Porque el mayor poder de en es )
La ecuación se puede reorganizar como
Derivados
La Las derivadas del polinomio de Lagrange se pueden escribir como
- .
Para la primera derivada, los coeficientes están dados por
y para la segunda derivada
- .
A través de la recursividad, se pueden calcular fórmulas para derivadas más altas.
Campos finitos
El polinomio de Lagrange también se puede calcular en campos finitos . Esto tiene aplicaciones en criptografía , como en el esquema de intercambio secreto de Shamir .
Ver también
- El algoritmo de Neville
- Forma de Newton del polinomio de interpolación
- Polinomio de Bernstein
- Teorema de carlson
- Constante de Lebesgue (interpolación)
- El sistema Chebfun
- Tabla de series newtonianas
- Covariante de Frobenius
- Fórmula de Sylvester
- Coeficiente de diferencia finita
Referencias
- ^ Waring, Edward (9 de enero de 1779). "Problemas de interpolaciones" . Transacciones filosóficas de la Royal Society . 69 : 59–67. doi : 10.1098 / rstl.1779.0008 .
- ^ Meijering, Erik (2002). "Una cronología de interpolación: de la astronomía antigua al procesamiento moderno de señales e imágenes" (PDF) . Actas del IEEE . 90 (3): 319–342. doi : 10.1109 / 5.993400 .
- ^ Quarteroni, Alfio; Saleri, Fausto (2003). Computación científica con MATLAB . Textos en ciencia e ingeniería computacional. 2 . Saltador. pag. 66. ISBN 978-3-540-44363-6..
- ^ Berrut, Jean-Paul ; Trefethen, Lloyd N. (2004). "Interpolación baricéntrica de Lagrange" (PDF) . Revisión SIAM . 46 (3): 501–517. doi : 10.1137 / S0036144502417715 .
- ^ 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. 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. pag. 878. ISBN 978-0-486-61272-0. LCCN 64-60036 . Señor 0167642 . LCCN 65-12253 .
- ^ "Interpolación" (PDF) .
enlaces externos
- "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 polinomial en C
- SO tiene un ejemplo de 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 en el Instituto de métodos numéricos holísticos
- Polinomio de interpolación de Lagrange en www.math-linux.com
- Weisstein, Eric W. "Polinomio de interpolación de Lagrange" . MathWorld .
- Polinomio de Lagrange en ProofWiki
- Interpolación dinámica de Lagrange con JSXGraph
- Computación numérica con funciones: el proyecto Chebfun
- Función de hoja de cálculo de Excel para la interpolación bicúbica de Lagrange
- Polinomios de Lagrange en Python