En el análisis numérico , la cuadratura de Gauss-Legendre es una forma de cuadratura de Gauss para aproximar la integral definida de una función . Para la integración sobre el intervalo [−1, 1] , la regla toma la forma:
dónde
- n es el número de puntos muestrales utilizados,
- w i son pesos en cuadratura, y
- x i son las raíces del n- ésimo polinomio de Legendre .
Esta elección de pesos de cuadratura w i y nodos de cuadratura x i es la opción única que permite que la regla de cuadratura integre exactamente polinomios de grado 2 n - 1 .
Se han desarrollado muchos algoritmos para calcular las reglas de cuadratura de Gauss-Legendre. El algoritmo de Golub-Welsch presentado en 1969 reduce el cálculo de los nodos y pesos a un problema de valor propio que se resuelve mediante el algoritmo QR . [1] Este algoritmo fue popular, pero existen algoritmos significativamente más eficientes. Los algoritmos basados en el método de Newton-Raphson pueden calcular reglas de cuadratura para problemas de tamaño significativamente mayor. En 2014, Ignace Bogaert presentó fórmulas asintóticas explícitas para los pesos y nodos en cuadratura de Gauss-Legendre, que tienen una precisión dentro de la épsilon de máquina de doble precisión para cualquier elección de n ≥ 21. [2] Esto permite el cálculo de nodos y pesos para los valores de n superior a mil millones. [3]
Historia
Carl Friedrich Gauss fue el primero en derivar la regla de cuadratura de Gauss-Legendre, y lo hizo mediante un cálculo con fracciones continuas en 1814. [4] Calculó los nodos y pesos a 16 dígitos hasta el orden n = 7 a mano. Carl Gustav Jacob Jacobi descubrió la conexión entre la regla de cuadratura y la familia ortogonal de polinomios de Legendre . Como no existe una fórmula de forma cerrada para los pesos y nodos de cuadratura, durante muchas décadas las personas solo pudieron usarlos a mano para n pequeños , y el cálculo de la cuadratura tuvo que hacerse haciendo referencia a tablas que contenían el peso y los valores de los nodos. En 1942, estos valores solo se conocían hasta n = 16.
Definición
Para integrar f sobrecon la cuadratura de Gauss-Legendre, los polinomios ortogonales asociados son polinomios de Legendre , denotados por P n ( x ) . Con el n -ésimo polinomio normalizado de modo que P n (1) = 1 , el i -ésimo nodo de Gauss, x i , es la i -ésima raíz de P n y los pesos están dados por la fórmula ( Abramowitz y Stegun 1972 , pág.887)
Algunas reglas de cuadratura de orden inferior se tabulan a continuación para integrar sobre .
Número de puntos, n | Puntos, x i | Pesos, w i | ||
---|---|---|---|---|
1 | 0 | 2 | ||
2 | ± 0,57735… | 1 | ||
3 | 0 | 0.888889… | ||
± 0,774597… | 0.555556… | |||
4 | ± 0,339981… | 0,652145… | ||
± 0,861136… | 0.347855… | |||
5 | 0 | 0,568889… | ||
± 0,538469… | 0.478629… | |||
± 0,90618… | 0,236927… |
Para integrar en un intervalo real general , se puede aplicar un cambio de intervalo para convertir el problema en uno de integración sobre.
Algoritmos
Métodos de Newton-Raphson
Varios investigadores han desarrollado algoritmos para calcular los nodos y pesos en cuadratura de Gauss-Legendre basados en el método de Newton-Raphson para encontrar raíces de funciones. Se utilizan varias optimizaciones para este problema específico. Por ejemplo, algunos métodos calculan para evitar problemas asociados con la agrupación de raíces cerca del final del intervalo y . [5] [6] Algunos métodos utilizan fórmulas para aproximar los pesos y luego usan algunas iteraciones de Newton-Raphson para reducir el error de aproximación a una precisión inferior a la de la máquina. [7] [5]
Golub – Welsch
En 1969, Golub y Welsch publicaron su método para calcular las reglas de cuadratura gaussiana dada la relación de recurrencia de tres términos que satisfacen los polinomios ortogonales subyacentes. [1] Reducen el problema de calcular los nodos de una regla de cuadratura gaussiana al problema de encontrar los valores propios de una matriz tridiagonal simétrica particular . El algoritmo QR se utiliza para encontrar los valores propios de esta matriz. Aprovechando la estructura tridiagonal simétrica, los valores propios se pueden calcular en tiempo, a diferencia del tiempo esperado para un problema genérico de valores propios.
Fórmulas asintóticas
Se han desarrollado varios métodos que utilizan expresiones aproximadas de forma cerrada para calcular los nodos. Como se mencionó anteriormente, en algunos métodos las fórmulas se utilizan como aproximaciones a los nodos, después de lo cual se realizan algunas iteraciones de Newton-Raphson para refinar la aproximación. En un artículo de 2014, Ignace Bogaert deriva fórmulas asintóticas para los nodos que son exactas hasta la precisión de la máquina para y para los pesos exactos hasta la precisión de la máquina para . [2] Este método no requiere iteraciones de Newton-Raphson o evaluaciones de funciones de Bessel como lo hacen otros métodos. Como se muestra en el documento, el método pudo calcular los nodos con un tamaño de problema de mil millones en 11 segundos. Dado que los nodos cerca de los puntos finales de se acercan mucho entre sí con este tamaño de problema, este método de calcular los nodos es suficiente para prácticamente cualquier aplicación práctica en coma flotante de doble precisión.
Mayor precisión
Johansson y Mezzarobba [8] describen una estrategia para calcular las reglas de cuadratura de Gauss-Legendre en aritmética de precisión arbitraria , permitiendo tanto las pequeñas como las grandes. Una regla de ordencon 1000 dígitos de precisión se puede calcular en alrededor de un segundo. Su método utiliza la iteración de Newton-Raphson junto con varias técnicas diferentes para evaluar polinomios de Legendre. El algoritmo también proporciona un límite de error certificado.
Comparación con otras reglas de cuadratura
La cuadratura de Gauss-Legendre es óptima en un sentido muy estrecho para calcular integrales de una función f sobre [−1, 1] , ya que ninguna otra regla de cuadratura integra todos los polinomios de grado 2 n - 1 exactamente cuando se usan n puntos muestrales. Sin embargo, esta medida de precisión no es generalmente muy útil --- los polinomios son muy simples de integrar y este argumento por sí mismo no garantiza una mejor precisión en la integración de otras funciones.
La cuadratura de Clenshaw-Curtis se basa en la aproximación de f mediante un interpolante polinomial en los nodos de Chebyshev e integra polinomios de grado hasta n exactamente cuando se dan n muestras. Aunque no integra polinomios u otras funciones que son analíticas en un gran vecindario de [−1, 1] , así como en la cuadratura de Gauss-Legendre, Clenshaw-Curtis converge aproximadamente a la misma velocidad que la cuadratura de Gauss-Legendre para la mayoría (no -analítico) integrandos. [9] Además, Clenshaw-Curtis comparte las propiedades que disfruta la cuadratura de Gauss-Legendre de convergencia para todos los integrandos continuos f y robustez a los errores de redondeo numérico. [10] Clenshaw-Curtis es sencillo de implementar entiempo por métodos basados en FFT .
La cuadratura de Newton-Cotes se basa en la aproximación de f mediante un interpolante polinomial en puntos igualmente espaciados en [−1, 1] y, como Clenshaw-Curtis, también integra polinomios de grado hasta n exactamente cuando se dan n muestras. Sin embargo, sufre el fenómeno de Runge a medida que n aumenta; Newton-Cotes no converge para algunos integrandos continuos f , y cuando converge puede sufrir errores de redondeo numérico. [10] Por lo tanto, tanto Clenshaw-Curtis como Gauss-Legendre disfrutan de beneficios sustanciales sobre Newton-Cotes para n de moderada a grande .
Referencias
- ^ a b GH Golub y JH Welsch, Cálculo de las reglas de cuadratura de Gauss , Matemáticas. Comp., 23 (1969), 221-230.
- ^ a b I. Bogaert, Cálculo sin iteraciones de pesos y nodos en cuadratura de Gauss-Legendre , SIAM J. Sci. Comput., 36 (2014), C1008 – C1026.
- ^ A. Townsend, La carrera por la cuadratura de alto orden Gauss-Legendre . SIAM News, 48 (2015), págs. 1-3.
- ^ CF Gauss, Methodus nova integralium valores por aproximationem inveniendi , comentario. Soc. Reg. Scient. Conseguir. Reciente., (1814).
- ^ a b N. Hale y A. Townsend, Cálculo rápido y preciso de pesos y nodos en cuadratura de Gauss-Legendre y Gauss-Jacobi , SIAM J. Sci. Comput., 35 (2013), págs. A652 – A674
- ^ PN Swarztrauber, sobre el cálculo de los puntos y pesos para la cuadratura de Gauss-Legendre , SIAM J. Sci. Comput., 24 (2003), págs. 945–954.
- ^ I. Bogaert, B. Michiels y J. Fostier, O (1) cálculo de polinomios de Legendre y nodos y pesos de Gauss-Legendre para cálculo paralelo , SIAM J. Sci. Comput., 34 (2012), págs. 83-101.
- ^ F. Johansson y M. Mezzarobba, Cálculo rápido y riguroso de precisión arbitraria de pesos y nodos en cuadratura de Gauss-Legendre , SIAM J. Sci. Comput., 40 (2018), págs. C726 – C747
- ^ Lloyd N. Trefethen. 2012. Teoría de la aproximación y práctica de la aproximación . Sociedad de Matemáticas Industriales y Aplicadas, EE. UU.
- ^ a b LN Trefethen, ¿Es la cuadratura de Gauss mejor que Clenshaw-Curtis? . SIAM Rev., 50 (1), 67-87