La cuadratura de Clenshaw-Curtis y la cuadratura de Fejér son métodos de integración numérica o cuadratura, que se basan en una expansión del integrando en términos de polinomios de Chebyshov. De forma equivalente, emplean un cambio de variable y utilizan como aproximación la transformada de coseno discreta (TCD) para una serie de cosenos. Además de tener una precisión de convergencia rápida comparable a las reglas de cuadratura de Gauss, la cuadratura de Clenshaw-Curtis conduce naturalmente a la integración numérica de funciones anidadas (donde diferentes órdenes de precisión comparten puntos), lo que es importante tanto para la cuadratura adaptativa como para la cuadratura multidimensional (integración numérica).
En resumen, la función que se va a integrar se evalúa en los extremos o raíces de un polinomio de Chebyshov, y estos valores se utilizan para construir una aproximación polinómica de la función. Este polinomio se integra de forma exacta. En la práctica, los pesos de integración para el valor de la función en cada nodo se precalculan, y este cálculo puede realizarse en tiempo mediante algoritmos relacionados con la transformada rápida de Fourier para la TCD.W. Morven Gentleman, "Implementing Clenshaw-Curtis quadrature I: Methodology and experience," Communications of the ACM 15(5), p. 337-342 (1972).Jörg Waldvogel, "Fast construction of the Fejér and Clenshaw-Curtis quadrature rules," BIT Numerical Mathematics 46 (1), p. 195-202 (2006).
Método general
Una forma sencilla de comprender el algoritmo es darse cuenta de que la cuadratura de Clenshaw-Curtis (propuesta por estos autores en 1960)C. W. Clenshaw and A. R. Curtis "A method for numerical integration on an automatic computer Numerische Mathematik 2, 197 (1960). equivale a integrar mediante un cambio de variable . El algoritmo se expresa normalmente para la integración de una función en el intervalo [-1,1] (cualquier otro intervalo puede obtenerse mediante un reescalamiento adecuado). Para esta integral, se puede escribir:
Es decir, se ha transformado el problema de integrar a integrar . Esto se puede realizar si se conoce las serie de cosenos para :
En cuyo caso, la integral se convierte en:
Por supuesto, para calcular los coeficientes de la serie de cosenos
es necesario realizar nuevamente una integración numérica, por lo que, en un principio, esto podría no parecer que simplifica el problema. Sin embargo, a diferencia del cálculo de integrales arbitrarias, las integraciones de series de Fourier para funciones periódicas (como , por construcción), hasta la frecuencia de Nyquist , se calculan con precisión mediante los puntos igualmente espaciados e igualmente ponderados para (excepto que los extremos se ponderan por 1/2, para evitar la doble contabilización, equivalente a regla del trapecio o fórmula de Euler-Maclaurin).J. P. Boyd, Chebychev and Fourier Spectral Methods, 2nd ed. (Dover, New York, 2001).See, for example, S. G. Johnson, "Notes on the convergence of trapezoidal-rule quadrature," online MIT course notes (2008). Es decir, se aproxima la integral de la serie de cosenos mediante la transformada discreta de Fourier (TCD) de tipo I (transformada de coseno discreta:
para y luego se usa la fórmula anterior para la integral en términos de estos . Dado que solo se necesita , la fórmula se simplifica aún más en una TCD de tipo I de orden , suponiendo que N es un número par:
A partir de esta fórmula, queda claro que la regla de cuadratura de Clenshaw-Curtis es simétrica, ya que pondera f(x) y f(-x) por igual.
Debido a la distorsión, solo se calculan los coeficientes hasta , ya que el muestreo discreto de la función hace que la frecuencia de sea indistinguible de la de N–2k. De forma equivalente, los son las amplitudes de los anchos de banda limitados y de la interpolación trigonométrica únicos que pasan por los puntos donde se evalúa , y se aproxima la integral mediante la integral de este polinomio de interpolación. Existe cierta sutileza en el tratamiento del coeficiente en la integral; sin embargo, para evitar la doble contabilización con su alias, se incluye con peso 1/2 en la integral aproximada final (como también se puede observar al examinar el polinomio de interpolación):
Conexión con los polinomios de Chebyshov
La razón por la que esto está conectado con los polinomios de Chebyshov es que, por definición, , y por lo tanto la serie de cosenos anterior, es en realidad una aproximación de mediante polinomios de Chebyshov:
y, por lo tanto, se está integrando realmente integrando su expansión aproximada en términos de polinomios de Chebyshov. Los puntos de evaluación corresponden a los extremos del polinomio de Chebyshov .
El hecho de que la aproximación sea simplemente una serie de cosenos bajo un cambio de variables explica la rápida convergencia de la aproximación a medida que se incluyen más términos . Una serie de cosenos converge muy rápidamente para funciones pares, periódicas y suficientemente suaves. Esto se cumple en este caso, ya que es par y periódica en por construcción, y es diferenciable k veces en todo su dominio si es diferenciable k veces en . En contraste, aplicar directamente un desarrollo en serie de cosenos a en lugar de a generalmente no converge rápidamente, ya que la pendiente de la extensión par-periódica suele ser discontinua.
Cuadratura de Fejér Lipót Fejér propuso dos reglas de cuadratura muy similares a la cuadratura de Clenshaw-Curtis, pero mucho antes (en 1933).Leopold Fejér, "On the infinite sequences arising in the theories of harmonic analysis, of interpolation, and of mechanical quadratures", Bulletin of the American Mathematical Society 39 (1933), pp. 521–534. Leopold Fejér, "Mechanische Quadraturen mit positiven Cotesschen Zahlen, Mathematische Zeitschrift 37, 287 (1933).
De estas dos, la segunda regla de cuadratura de Fejér es casi idéntica a la de Clenshaw-Curtis. La única diferencia radica en que los extremos y se establecen en cero. Es decir, Fejér solo utilizó los extremos interiores de los polinomios de Chebyshov, es decir, los verdaderos puntos estacionarios.
La primera regla de cuadratura de Fejér evalúa mediante el examen de en un conjunto diferente de puntos igualmente espaciados, a medio camino entre los extremos: para . Estas son las raíces de y se conocen como nodos de Chebyshov (estos puntos medios igualmente espaciados son la única otra opción de puntos de cuadratura que preserva tanto la simetría par de la transformada coseno como la simetría traslacional de la serie de Fourier periódica). Esto conduce a la siguiente fórmula:
que es precisamente la TCD de tipo II. Sin embargo, la primera regla de cuadratura de Fejér no está anidada: los puntos de evaluación de no coinciden con ninguno de los puntos de evaluación de , a diferencia de la cuadratura de Clenshaw-Curtis o la segunda regla de Fejér.
A pesar de que Fejér descubrió estas técnicas antes que Clenshaw y Curtis, el término cuadratura de Clenshaw-Curtis se ha convertido en estándar.
Comparación con la cuadratura gaussiana
El método clásico de cuadratura de Gauss evalúa el integrando en los puntos y está diseñado para integrar polinomios de forma exacta hasta el grado . En contraste, la cuadratura de Clenshaw-Curtis, descrita anteriormente, evalúa el integrando en puntos e integra polinomios de forma exacta solo hasta el grado (suponiendo que es un número par). Por lo tanto, podría parecer que la cuadratura de Clenshaw-Curtis es intrínsecamente peor que la cuadratura gaussiana, pero en realidad no parece ser así.
En la práctica, varios autores han observado que la cuadratura de Clenshaw-Curtis puede tener una precisión comparable a la de la cuadratura gaussiana para el mismo número de puntos. Esto es posible porque la mayoría de los integrandos numéricos no son polinomios (especialmente porque los polinomios se pueden integrar analíticamente), y la aproximación de muchas funciones en términos de polinomios de Chebyshov converge rápidamente (véase teoría de la aproximación). De hecho, resultados teóricos posteriores argumentan que tanto la cuadratura gaussiana como la de Clenshaw-Curtis tienen un error acotado por para un integrando diferenciable k veces.
Una ventaja frecuentemente citada de la cuadratura de Clenshaw-Curtis es que los pesos de cuadratura pueden evaluarse en tiempo mediante algoritmos de transformada rápida de Fourier (o sus análogos para la TCD), mientras que la mayoría de los algoritmos para pesos de cuadratura gaussianos requieren tiempo para su cálculo. Sin embargo, algoritmos recientes han alcanzado una complejidad para la cuadratura de Gauss-Legendre.Ignace Bogaert, Iteration-Free Computation of Gauss--Legendre Quadrature Nodes and Weights, SIAM Journal on Scientific Computing vol. 36, pp. A1008–A1026 (2014) En la práctica, la integración numérica de alto orden rara vez se realiza simplemente evaluando una fórmula de cuadratura para muy grandes. En cambio, se suele emplear un esquema de cuadratura adaptativa que primero evalúa la integral a un orden bajo y luego refina sucesivamente la precisión aumentando el número de puntos de muestreo, posiblemente solo en regiones donde la integral es imprecisa. Para evaluar la precisión de la cuadratura, se compara el resultado con el de una regla de cuadratura de orden aún menor. Idealmente, esta regla de cuadratura de orden inferior evalúa el integrando en un subconjunto de los N puntos originales, para minimizar las evaluaciones del integrando. Esto se denomina regla de cuadratura anidada, y aquí el método de Clenshaw-Curtis tiene la ventaja de que la regla para el orden N utiliza un subconjunto de los puntos del orden 2N. En contraste, las reglas de cuadratura gaussiana no están anidadas de forma natural, por lo que se deben emplear la fórmula de cuadratura de Gauss-Kronrod o métodos similares. Las reglas anidadas también son importantes para un retículo disperso en la cuadratura multidimensional, y la cuadratura de Clenshaw-Curtis es un método popular en este contexto.Erich Novak and Klaus Ritter, "High dimensional integration of smooth functions over cubes," Numerische Mathematik vol. 75, pp. 79–97 (1996).
Integración con funciones de ponderación
De forma más general, se puede plantear el problema de integrar una función arbitraria frente a una función de ponderación fija conocida de antemano:
El caso más común es , como se indicó anteriormente, pero en ciertas aplicaciones se prefiere un caso diferente, incorporando una función peso. La razón fundamental es que, dado que puede considerarse a priori, el error de integración puede depender únicamente de la precisión en la aproximación de , independientemente de la complejidad de la función de ponderación.
La cuadratura de Clenshaw-Curtis se puede generalizar a este caso de la siguiente manera. Como antes, se obtiene el desarrollo en serie de cosenos de mediante una transformada discreta del coseno (TCD) y, a continuación, se integra cada término de la serie. Ahora, sin embargo, estas integrales tienen la forma
Para la mayoría de los casos , esta integral no puede calcularse analíticamente, a diferencia de antes. Sin embargo, dado que generalmente se utiliza la misma función de ponderación para muchos integrandos , es posible calcular numéricamente con alta precisión de antemano los . Además, dado que generalmente se especifica analíticamente, a veces se pueden emplear métodos especializados para calcular .