Quadratura adaptativa

En càlcul, la quadratura adaptativa és un procés en el qual es troba una aproximació de la integral definida d'una funció ${\displaystyle f(x)}$ emprant un mètode estàtic d'integració numèrica sobre uns subintervals d'integració que es divideixen de forma adaptativa. En general, els algorismes adaptatius són tan eficients i efectius com els algorismes tradicionals pel cas de funcions amb "bon comportament", però també són efectius per a funcions amb "mal comportament" per a les quals els algorismes tradicionals fallen.

Esquema general

La quadratura adaptativa segueix el següent esquema general

1. procediment integrar (f, a, b, tau)
2. ${\displaystyle Q\approx \int _{a}^{b}f(x)\,{\mbox{d}}x}$
3. ${\displaystyle \varepsilon \approx \left|Q-\int _{a}^{b}f(x)\,{\mbox{d}}x\right|}$
4. si ${\displaystyle \varepsilon >\tau }$ llavors
5. m = (a + b) / 2
6. Q = integrar(f,a,m,tau) + integrar(f,m,b,tau)
7. fi si
8. retorna Q

Es calcula una aproximació ${\displaystyle Q}$ a la integral de ${\displaystyle f(x)}$ sobre l'interval ${\displaystyle [a,b]}$ (línia 2), així com una estimació de l'error ${\displaystyle \varepsilon }$ (línia 3). Si l'error estimat és més gran que la tolerància requerida ${\displaystyle \tau }$ (línia 4), llavors, l'interval se subdivideix (línia 5) i s'aplica la quadratura a totes dues meitats per separat (línia 6). Ja sigui l'estimació inicial o la suma de les dues meitats calculades de forma recursiva és el resultat que es retorna (línia 7).

Els components importants són:

el mètode de quadratura

${\displaystyle Q\approx \int _{a}^{b}f(x)\,{\mbox{d}}x,}$

la forma de fer l'estimació de l'error

${\displaystyle \varepsilon \approx \left|Q-\int _{a}^{b}f(x)\,{\mbox{d}}x\right|,}$

i la lògica per decidir quin interval s'ha de subdividir i quan s'ha d'acabar.

Mètode bàsic de quadratura

Els mètodes de quadratura, generalment tenen la forma

${\displaystyle Q_{n}\quad =\quad \sum _{i=0}^{n}w_{i}f(x_{i})\quad \approx \quad \int _{a}^{b}f(x)\,{\mbox{d}}x}$

On els nodes ${\displaystyle x_{i}}$ i els pesos ${\displaystyle w_{i}}$ en general es tenen precalculats.

En el cas més simple, es fan servir les fórmules de Newton-Cotes de grau parell, on els nodes ${\displaystyle x_{i}}$ estan uniformement espaiats dins l'interval:

${\displaystyle x_{i}=a+{\frac {i}{n}}(b-a)}$.

Quan es fan servir aquest tipus de mètodes, els punts als quals ${\displaystyle f(x)}$ ha estat avaluada es poden reutilitzar al subdividir l'interval:

Una estratègia similar es fa servir amb la quadratura de Clenshaw-Curtis, on els nodes es trien com

${\displaystyle x_{i}=\cos \left({\frac {2i}{n}}\pi \right)}$

O quant es fa servir la quadratura de Fejér,

${\displaystyle x_{i}=\cos \left({\frac {2(i+0.5)}{n+1}}\pi \right)}$.

• Quadratura de Gauss
• Mètode de Gauss–Kronrod

Un algorisme pot decidir fer servir diferents mètodes de quadratura sobre diferents subintervals, per exemple emprant un mètode d'ordre elevat només quan l'integrand és suau.

Estimació de l'error

Alguns algorismes de quadratura generen una successió de resultats que haurien d'aproximar el valor correcte. Altrament es pot fer servir un "mètode nul" que té la forma del mètode de quadratura de més amunt però que el seu valor hauria de ser zero per a un integrand simple (per exemple, si l'integrand fos un polinomi del grau adequat).

Vegeu:

• extrapolació de Richardson
• mètode de Romberg

Lògica de subdivisió

Un mètode de quadratura "Local" fa que l'error acceptable per a un interval donat sigui proporcional a la longitud de l'interval. Aquest criteri pot ser difícil de satisfer si l'integrand té un mal comportament només en uns quants punts, per exemple unes quantes discontinuïtats de salt. Alternativament, es podria requerir només que la suma dels errors de tots els subintervals sigui més petita que els requeriments de l'usuari. Això seria una quadratura adaptativa "global". Les quadratures adaptatives globals poden ser més eficients (emprant menys avaluacions de l'integrand) però en general són més complexes de programar i poden requerir més espai de treball per emmagatzemar la informació del conjunt d'intervals a cada moment.

Vegeu també

• Mètode de Simpson adaptatiu per veure un exemple de quadratura adaptativa

Referències

• William M. McKeeman: Algorithm 145: Adaptive numerical integration by Simpson's rule. Commun. ACM 5(12): 604 (1962).
• John R. Rice. A Metalgorithm for Adaptive Quadrature. Journal of the ACM 22(1) pp 61-82 ((January 1975).