Quadratura de Clenshaw-Curtis

La quadratura de Clenshaw-Curtis i la quadratura de Fejér són métodos d'integració numèrica o quadratura, que es basen en una expansió del integrant en térmens de polinomis de Chebyshov. De forma equivalent, ampren un canvi de variable $x=\cos \theta$ i utilisen com a aproximació la transformada de coseno discreta (TCD) per a una série de cosenos. Ademés de tindre una precisió de convergència ràpida comparable a les regles de quadratura de Gauss, la quadratura de Clenshaw-Curtis conduïx naturalment a l'integració numèrica de funcions aniuades (a on diferents órdens de precisió compartixen punts), lo que és important tant per a la quadratura adaptativa com per a la quadratura multidimensional (integració numèrica).

En resum, la funció $f(x)$ que es va a integrar s'evalua en els $N$ extrems o raïls d'un polinomi de Chebyshov, i estos valors s'utilisen per a construir una aproximació polinòmica de la funció. Este polinomi s'integra de forma exacta. En la pràctica, els pesos d'integració per al valor de la funció en cada nodo es precalculan, i este càlcul pot realisar-se en temps $O(N\log N)$ per mig d'algoritmes relacionats en la transformada ràpida de Fourier per a la TCD.

Método general

Una forma senzilla de comprendre l'algoritme és donar-se conte de que la quadratura de Clenshaw-Curtis (proposta per estos autors en 1960) equival a integrar per mig d'un canvi de variable x= cos(θ). L'algoritme s'expressa normalment per a l'integració d'una funció f(x) en l'interval [-1,1] (qualsevol atre interval pot obtindre's per mig d'un reescalamiento adequat). Per a esta integral, es pot escriure:

$\underset{-1}{\overset{1}{\int }}f(x)dx=\underset{0}{\overset{\pi }{\int }}f(\cos \theta )\sin (\theta )d\theta .$

És dir, s'ha transformat el problema d'integrar $f(x)$ a integrar $f(\cos \theta )\sin \theta$. Açò es pot realisar si es coneix les série de cosenos para $f(\cos \theta )$:

$f(\cos \theta )=\frac{a_0}{2}+\sum _{k=1}^{\mathrm{\infty }}{a}_k\cos (k\theta )$

En el cas del qual, l'integral es convertix en:

$\underset{0}{\overset{\pi }{\int }}f(\cos \theta )\sin (\theta )d\theta =a_0+\sum _{k=1}^{\mathrm{\infty }}\frac{2a_{2k}}{1-(2k{)}^2}.$

Per supost, per a calcular els coeficients de la série de cosenos

$a_k=\frac{2}{\pi }\underset{0}{\overset{\pi }{\int }}f(\cos \theta )\cos (k\theta )d\theta ,k=0,1,2,\dots ,$

és necessari realisar novament una integració numèrica, per lo que, en un principi, açò podria no semblar que simplifica el problema. No obstant, a diferència del càlcul d'integrals arbitràries, les integració de séries de Fourier per a funcions periòdiques (com $f(\cos \theta )$, per construcció), fins a la freqüència de Nyquist $k=N$, es calculen en precisió per mig dels $N+1$ punts igualment espayats i igualment ponderats ${\theta }_n=n\pi /N$ per a $n=0,\dots ,N$ (excepto que els extrems es ponderen per 1/2, per a evitar la doble contabilisació, equivalent a regla del trapezi o fòrmula de Euler-Maclaurin). És dir, s'aproxima l'integral de la série de cosenos per mig de la transformada discreta de Fourier (TCD) de tipo I (transformada de coseno discreta:

$a_k\approx \frac{2}{N}[\frac{f(1)}{2}+\frac{f(-1)}{2}(-1{)}^k+\sum _{n=1}^{N-1}f(\cos [n\pi /N])\cos (nk\pi /N)]$

per a $k=0,\dots ,N$ i després s'usa la fòrmula anterior per a l'integral en térmens d'estos $a_k$. Ya que solament es necessita $a_{2k}$, la fòrmula se simplifica encara més en una TCD de tipo I d'orde N/2, suponent que N és un número par:

$a_{2k}\approx \frac{2}{N}[\frac{f(1)+f(-1)}{2}+f(0)(-1{)}^k+\sum _{n=1}^{N/2-1}\{f(\cos [n\pi /N])+f(-\cos [n\pi /N])\}\cos \left(\frac{nk\pi }{N/2}\right)]$

A partir d'esta fòrmula, queda clar que la regla de quadratura de Clenshaw-Curtis és simètrica, ya que pondera f(x) i f(-x) per igual.

Per la distorsió, solament es calculen els coeficients $a_{2k}$ fins a k= N/2, ya que el mostreig discret de la funció fa que la freqüència de 2k siga indistinguible de la de N–2k. De forma equivalent, els $a_{2k}$ són les amplitut dels amples de banda llimitats i de l'interpolació trigonométrica únics que passen pels N+1 punts a on s'evalua f(cos θ), i s'aproxima l'integral per mig de l'integral d'este polinomi d'interpolació. Existix certa subtilea en el tractament del coeficient $a_N$ en l'integral; no obstant, per a evitar la doble contabilisació en el seu àlies, s'inclou en pes 1/2 en l'integral aproximada final (com també es pot observar en examinar el polinomi d'interpolació):

$\underset{0}{\overset{\pi }{\int }}f(\cos \theta )\sin (\theta )d\theta \approx a_0+\sum _{k=1}^{N/2-1}\frac{2a_{2k}}{1-(2k{)}^2}+\frac{a_N}{1-N^2}.$

Conexió en els polinomis de Chebyshov

La raó per la que açò està conectat en els polinomis de Chebyshov $T_k(x)$ és que, per definició, $T_k(\cos \theta )=\cos (k\theta )$, i per lo tant la série de cosenos anterior, és en realitat una aproximació de $f(x)$ per mig de polinomis de Chebyshov:

$f(x)=\frac{a_0}{2}{T}_0(x)+\sum _{k=1}^{\mathrm{\infty }}{a}_k{T}_k(x),$

i, per lo tant, s'està integrant realment $f(x)$ integrant la seua expansió aproximada en térmens de polinomis de Chebyshov. Els punts d'evaluació $x_n=\cos (n\pi /N)$ corresponen als extrems del polinomi de Chebyshov $T_N(x)$.

El fet de que l'aproximació siga simplement una série de cosenos baix un canvi de variables explica la ràpida convergència de l'aproximació a mida que s'inclouen més térmens $T_k(x)$. Una série de cosenos convergix molt ràpidament per a funcions pares, periòdiques i suficientment suaus. Açò es complix en este cas, ya que $f(\cos \theta )$ és parell i periòdica en $\theta$ per construcció, i és diferenciable k voltes en tot el seu domini si $f(x)$ és diferenciable k voltes en $[-1,1]$. En contrast, aplicar directament un desenroll en série de cosenos a $f(x)$ en lloc de a $f(\cos \theta )$ generalment no convergix ràpidament, ya que la pendent de l'extensió parell-periòdica sol ser discontínua.

Vore també

• Fòrmula de Euler-Maclaurin
• Fòrmula de quadratura de Gauss-Kronrod