Quadratura de Clenshaw-Curtis

La quadratura de Clenshaw–Curtis i les quadratures de Fejer són mètodes d'integració numèrica basats en l'expansió de l'integrant en termes dels polinomis de Txebixev. Un resum breu de l'algoritme és el següent: la funció $f(x)$ que s'ha d'integrar és avaluada als extrems o arrels dels polinomis de Txebixev i aquests valors es fan servir per construir una aproximació polinòmica de la funció; aquesta és integrada exactament per donar una aproximació de la integral exacta que busquem. El càlcul dels pesos d'integració es pot fer mitjançant una DCT, que a través de la FFT es poden obtenir amb $O(n\log n)$ operacions.

Introducció general

Article principal: Integració numèrica

El mètode consisteix a avaluar la funció en $n+1$ nodes determinats, que anomenarem $x_{j}$, amb $j=0,\ldots ,n$. Llavors, el mètode es pot resumir en la següent equació:

$\int _{-1}^{1}f(x)\mathrm {d} x\approx I_{N}[f]=\sum _{i=0}^{n}w_{i}f(x_{i})$

on els coeficients $w_{i}$ cal determinar-los en funció de la distribució dels nodes $x_{i}$.

Fórmules explícites

Es poden obtenir fórmules explícites de la quadrature de Clenshaw-Curtis i de Fejer I i II. Tot i que són poc útils a nivell computacional, ja que fan falta $O(n^{2})$ operacions per calcular-los, tenen la seva importància teòrica i a nivell didàctic.

Quadratura de Clenshaw-Curtis

Pel cas de la quadratura de Clenshaw-Curtis, els nodes on s'avaluarà la funció són:

$x_{k}=\cos \theta _{k}\equiv \cos \left({\frac {k\pi }{n}}\right),\quad k=0,\ldots ,n$

Per altra banda, els pesos d'integració són:

$w_{k}={\frac {c_{k}}{n}}\left(1-\sum _{j=1}^{\lfloor n/2\rfloor }{\frac {b_{j}}{4j^{2}-1}}\cos(2j\theta _{k})\right),\quad k=0,\ldots ,n$

On els coeficients $b_{j}$ i $c_{j}$ tenen la següent expressió:

$b_{j}=\left\{{\begin{array}{l l}1,&j=n/2\\2,&j<n/2\end{array}}\right.\qquad c_{k}=\left\{{\begin{array}{l l}1,&k=0,n\\2,&\mathrm {altrament} \end{array}}\right.$