Integració de Montecarlo

Representació del mètode d'integració de Montecarlo. En aquest exemple, el domini d és el cercle interior, i el domini D és el quadrat. Com que l'àrea del quadrat es pot calcular fàcilment (4), hom pot estimar l'àrea del cercle (π*1²) a partir de la proporció (0,8) de punts a l'interior del cercle (40) respecte al nombre total de punts (50), obtenint així un valor aproximat per a l'àrea del cercle donat per 4*0,8 = 3,2 ≈ π*1².

En matemàtiques, la integració de Montecarlo és un mètode de quadratura numèrica que fa servir nombres pseudo aleatoris. És a dir, els mètodes d'integració de Montecarlo són algorismes per trobar una avaluació aproximada de la integral definida, normalment d'integrals múltiples. Els algorismes deterministes d'integració numèrica, per aproximar la integral, avaluen la funció en un conjunt de punts corresponents a una graella regular o en un conjunt de punts predefinits. En canvi, els mètodes de Montecarlo trien de forma aleatòria els punts en els que s'avaluarà la funció. La integració de Montecarlo forma part d'una família d'algorismes anomenats genèricament mètodes de Montecarlo. Aquests algorismes utilitzen nombres aleatoris per a resoldre diferents tipus de problemes matemàtics i reben el seu nom a causa del casino de Montecarlo

Informalment, per estimar l'àrea d'un domini d, primer es tria un domini D tal que contingui d i que la seva àrea sigui fàcil de calcular (per exemple un rectangle). Llavors es tria un conjunt aleatori de punts que caiguin dins de D. Es calcula la fracció d'aquests punts que també queden dins de d. Llavors l'àrea de d s'aproxima com l'àrea de D multiplicada per aquesta fracció.

L'algorisme tradicional de Montecarlo distribueix els punts on s'avalua la funció uniformement dins l'intèrval d'integració. Els algorismes adaptatius com ara VEGAS i MISTER fan servir el mostreig per importància i el mostreig estratificat per tal d'obtenir un resultat millor.

L'algorisme tradicional

L'algorisme tradicional calcula una estimació d'una integral definida múltiple de la forma,

$I=\int _{x_{l}}^{x_{u}}\int _{y_{l}}^{y_{u}}f(x,y,\ldots )\,dx\,dy\ldots =\int _{V}f(x,y,\ldots )\,dx\,dy\ldots$

Sobre l'hipercub de volum $V$ definit per { (x, y, …) | x_l ≤ x ≤ x_u, y_l ≤ y ≤ y_u, … }.

L'algorisme mostreja punts uniformement distribuïts dins la regió d'integració per tal d'estimar la integral i el seu error. Suposeu que es té un conjunt de mostres de mida N i els punts del conjunt són x₁, …, x_N. Llavors l'estimació de la integral ve donada per

$E(f;N)=V\cdot \langle f\rangle =V{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i}),$

on $\langle f\rangle$ indica la mitjana aritmètica de l'integrand.

La variància de la funció es pot estimar emprant

$\sigma ^{2}(E;N)={\frac {1}{N}}\sum _{i=1}^{N}(f(x_{i})-\langle f\rangle )^{2}.$

La variància de l'estimació de la integral es pot estimar emprant

$\sigma ^{2}(E;N)={\frac {V^{2}}{N^{2}}}\sum _{i=1}^{N}(f(x_{i})-\langle f\rangle )^{2}.$

Per valors grans de N aquesta variància disminueix asimptòticament en proporció a V² var(f) / N, on var(f) és l'autèntica variància de la funció sobre la regió d'integració. L'error de l'estimació mateix disminueix en proporció a V σ(f) / √N. La llei familiar dels errors disminuint en proporció a 1 / √N s'aplica: per a reduir l'error en un factor de 10 cal augmentar 100 cops el nombre de punts de mostreig.

L'expressió anterior subministra una estimació estadística de l'error del resultat. Aquesta estimació no és estrictament una fita superior; pot ser que el mostreig aleatori de la funció no descobreixi totes les característiques rellevants de la funció i per tant potser infravalori l'error.

MISER Montecarlo

L'algorisme MISER de Press i Farrar es basa en un mostreig recursiu estratificat. Aquesta tècnica busca reduir l'error global d'integració a base de concentrar els punts d'integració en les regions on la variància és més gran.

La idea del mostreig estratificat sorgeix de l'observació de què per a dues regions disjuntes a i b amb estimacions de Montecarlo de la integral $E_{a}(f)$ i $E_{b}(f)$ i variàncies $\sigma _{a}^{2}(f)$ i $\sigma _{b}^{2}(f)$, la variància $Var(f)$ de l'estimació combinada $E(f)=(1/2)(E_{a}(f)+E_{b}(f))$ ve donada per,

$\mathrm {Var} (f)=(\sigma _{a}^{2}(f)/4N_{a})+(\sigma _{b}^{2}(f)/4N_{b})$

Es pot demostrar que aquesta variància queda minimitzada a base de distribuir els punts de forma tal que,

$N_{a}/(N_{a}+N_{b})=\sigma _{a}/(\sigma _{a}+\sigma _{b})$

D'aquí en resulta que l'estimació més petita de l'eror s'aconsegueix a base de col·locar un nombre de punts a cada sub-regió proporcional a la desviació típica de la funció en la sub-regió.

L'algorisme MISTER treballa bisecant la regió d'integració al llarg d'un eix coordenat per obtenir dues sub-regions a cada pas. La direcció es tria a base d'examinar totes les direccions possibles i elegint la que minimitzarà la variància combinada de les dues sub-regions. La variància en les sub-regions s'estima amb la fracció del nombre total de punts que està disponible a cada pas. Llavors es repeteix recursivament el procés per a cada un dels dos semiespais obtinguts amb la millor bisecció. Els punts de mostreig que queden es col·loquen en les sub-regions emprant la fórmula per N_a i N_b. Aquesta recursió continua fins a una profunditat especificada per l'usuari, llavors s'integra cada subr-regió amb l'algorisme tradicional de Montecarlo. Llavors es combinen aquestes estimacions individuals i les seves estimacions de l'error per obtenir el resultat global i la seva estimació de l'error.

VEGAS Montcarlo

L'algorisme VEGAS de G.P.Lepage es basa en el mostreig per importància. Mostreja els punts a partir de la distribució de probabilitat descrita per la funció $|f|$, de forma que els punts es concentren el les regions que fan l'aportació més gran a la integral.

En general, si la integral de Montecarlo de $f$ es mostreja amb punts distribuïts d'acord amb la distribució de probabilitat que descriu la funció $g$, s'obté una estimació $E_{g}(f;N)$,

$E_{g}(f;N)=E(f/g;N)$

Amb una variància corresponent,

$Var_{g}(f;N)=Var(f/g;N)$

Si la distribució de probabilitat es tria com $g=|f|/I(|f|)$ llavors es pot demostrar que la variància $V_{g}(f;N)$ s'esvaeix, i l'error de l'estimació esdevé zero. A la pràctica no és possible mostrejar a partir d'una distribució exacta $g$ que a qualsevol funció arbitrària, per tant els algorismes basats en el mostreig per importància pretenen produir aproximacions eficients a la distribució desitjada.

L'algorisme VEGAS aproxima la distribució exacta a base de diverses passades sobre la regió d'integració i trobant l'histograma de la funció $f$. Cada histograma es fa servir per a definir la distribució del mostreig de la següent passada. Aquest procediment convergeix assimptòticament acap a la distribució desitjada. Per tal d'evitar que el nombre de piles de l'hitograma creixi en proporció de $K^{d}$ la distribució d probabilitat s'aproxima amb una funció separable: $g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\ldots$ així el nombre de piles que calen és només proporcional a $Kd$. Això és equivalent a localitzar elspics de la funció a partir de les projeccions de l'integrand sobre els eixos de coordenades. L'eficiència de VEGAS depèn d'aquesta suposició. És més eficient quan els pics de l'integrand estan ben localitzats. Si un integrand es pot reescriure de manera que sigui aproximadament separable, això augmentarà l'eficiència de la integració amb VEGAS.

Referències

La següent referència en anglès dels mètodes de Montecarlo i quasi-Montcarlo (amb una descripció de les tècniques de reducció de la variància) és un excel·lent començament:

• R. E. Caflisch, Monte Carlo and quasi-Monte Carlo methods, Acta Numerica vol. 7, Cambridge University Press, 1998, pp. 1-49.

Curs en anglès per a estudiants de física d'altes energies que fa una introducció als mètodes d'integració numèrica incloent-hi el mètode de Montecarlo:

• S. Weinzierl, Introduction to Monte Carlo methods,

L'algorisme MISER es descriu en el següent article,

• W.H. Press, G.R. Farrar, Recursive Stratified Sampling for Multidimensional Monte Carlo Integration, Computers in Physics, v4 (1990), pp190-195.

L'algorisme VEGAS es descriu en els següents articles,

• G.P. Lepage, A New Algorithm for Adaptive Multidimensional Integration, Journal of Computational Physics 27, 192-203, (1978)
• G.P. Lepage, VEGAS: An Adaptive Multi-dimensional Integration Program, Cornell preprint CLNS 80-447, March 1980

Enllaços externs

• Module for Monte Carlo Integration