Monte-Carlo-integrálás

A Wikipédiából, a szabad enciklopédiából
Egy illusztráció a Monte-Carlo-integrálásról A példában D a belső kör, és E a négyzet. A négyzet területe könnyen kiszámítható, így a körlap területe (π*12) megbecsülhető a körön belüli (40) és az összes pont (50) számának arányából. A körlap területe így 4*0.8 = 3.2 ≈ π*12.


A matematikában a Monte-Carlo-integrálás egy olyan numerikus integrálási módszer, mely véletlenszámokat használva számol. A többi integrálási algoritmus általában egy szabályos rácson értékelik ki az integrandust, míg a Monte-Carlo-módszerrel véletlen pontokban végez függvénykiértékelést. Ez a módszer különösen hasznos többdimenziós integrálok számításakor.

Áttekintés[szerkesztés | forrásszöveg szerkesztése]

Numerikus integrálás esetén egyes módszerek, például a trapézszabály a feladatot determinisztikus módon közelítik meg. Ezzel ellentétben a Monte-Carlo integrálás egy nem determinisztikus (sztochasztikus) módszer: minden végrehajtás után különböző eredményt kapunk, ami a pontos érték egy megközelítése.

A determinisztikus numerikus integrálási módszerek kevés dimenzióban jól működnek, viszont sokváltozós függvények esetében két probléma lép fel. A szükséges függvénykiértékelések száma gyorsan nő a dimenziók számával (hogyha 10 kiértékelés nyújt megfelelő pontosságot egy dimenzióban, akkor 100 dimenzióban 10100 pontban kell értéket kiszámolnunk). A második nehézséget a többdimenziós integrálási tartomány határa jelenti, a feladat legtöbbször nem vezethető vissza egymásba ágyazott egydimenziós integrálok kiszámítására.

A számítási idő exponenciális növekedése áthidalható a Monte-Carlo-módszerek alkalmazásával. Ha a függvény "jól viselkedik", az integrált megbecsülhetjük a 100 dimenziós térben véletlenszerűen felvett pontokban számolt függvényértékek súlyozott átlagával. A centrális határeloszlás-tétel alapján a módszer konvergenciája 1/ \sqrt{N} (pl.: a mintapontok számát négyszeresére növelve a hiba feleződik, a dimenziók számától függetlenül).

Az algoritmus javítására egy lehetőség a statisztikában fontossági mintavételként ismert módszer, aminek lényege, hogy a mintapontokat véletlenszerűen választjuk ki, de ott, ahol az integrandus értéke nagyobb, sűrűbben veszünk mintát. Ennek pontos végrehajtásához előre ismernünk kéne az integrált, viszont megközelíthetjük azt egy hasonló függvény integráljával. Adaptív módszerek alkalmazása is hatékonyabbá teszi az algoritmust, ilyenek a rétegzett mintavétel, a rekurzív rétegzett mintavétel, az adaptív esernyő-mintavételi technika vagy a VEGAS algoritmus.

A kvázi Monte-Carlo-módszerek alacsony diszkrepanciájú sorozatokat használnak, melyek egyenletesebben "kitöltik" a tartományt. Egy tartományban véletlen bolyongás módszereivel (Markov-lánc Monte-Carlo MCMC) is generálhatunk véletlenszám-sorozatot. Erre példa a Metropolis-Hastings algoritmus, Gibbs-mintavétel valamint a Wang és Landau algoritmus.


Többszörös integrálok értékének meghatározása[szerkesztés | forrásszöveg szerkesztése]

A többszörös integrál transzformálása[szerkesztés | forrásszöveg szerkesztése]

Az I integrál geometriai jelentése egy m+1 dimenziójú térfogat, vagyis egy Ox1x2...xmy térben S alapú egyenes hiperhenger, melyet felülről az y=f(x1,x2,...,xm) felület határol.

Legyen az  y=f( x_{1},x_{2},...,x_{m} ) függvény folytonos egy zárt S tartományon.

A feladat az  I = \iint\dots \int_S \;f( x_{1},x_{2},...,x_{m} )  \mathrm{d}x_{1}\mathrm{d}x_{2}\dots\mathrm{d}x_{m}  integrál értékének meghatározása.

Az I integrált olyan alakra hozzuk, hogy az új integrálási tartomány egy m dimenziós egységélű hiperkockán belülre kerüljön.

Ha az S tartomány a következő m dimenziós paralelepipedonon belül helyezkedett el  a_{i}\leq x_{i}\leq A_{i} \quad (i=1,2,\dots,m) változócserét végzünk a következőképpen: x_{i} = a_{i}+ (A_{i}-a_{i})\xi_{i}

A transzformáció Jacobi-determinánsát felhasználva

 \frac{D( x_{1},x_{2},...,x_{m} )}{D( \xi_{1},\xi_{2},...,\xi_{m})}= 
\begin{vmatrix}
A_{1}-a_{1} & 0 & \cdots & 0 \\
0 & A_{2}-a_{2} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & A_{m}-a_{m} \\
\end{vmatrix}
I = \iint\dots \int_\sigma \;F( \xi_{1},\xi_{2},...,\xi_{m} )  \mathrm{d}\xi_{1}\mathrm{d}\xi_{2}\dots\mathrm{d}\xi_{m}

ahol  F(\xi_{1},\xi_{2},...,\xi_{m})= (A_{1}-a_{1})(A_{2}-a_{2})\dots (A_{m}-a_{m}) f(a_{1}+ (A_{1}-a_{1})\xi_{1},a_{2}+ (A_{2}-a_{2})\xi_{2}, \dots, a_{m}+ (A_{m}-a_{m})\xi_{m})

az alábbi jelöléseket bevezetve:

\boldsymbol{\xi} = (\xi_{1},\xi_{2},\dots,\xi_{m})
\mathrm{d} \boldsymbol{\sigma} = \mathrm{d}\xi_{1}\mathrm{d}\xi_{2}\dots\mathrm{d}\xi_{m}
 I = \iint\dots \int_\sigma \;F(\boldsymbol{\xi})\mathrm{d}\boldsymbol{\sigma}

A fenti integrált két véletlen mintavételen alapuló módszerrel számolhatjuk ki:

Az integrál kiszámolása Mote-Carlo-módszerrel[szerkesztés | forrásszöveg szerkesztése]

Első módszer[szerkesztés | forrásszöveg szerkesztése]

Generáljunk a [0,1] intervallumon m darab, N elemből álló véletlen számsorozatot egyenletes eloszlással. A számsorokból az m dimenziós hiperkockán belül N pontot kapunk:

M_{i}(\xi_{i}^{(1)},\xi_{i}^{(2)}, \dots, \xi_{i}^{(m)}) \quad (i=1,2,\dots,N)

Elegendő mintapont felvétele után megszámoljuk azokat a pontokat, melyek a σ tartományon belül találhatók. Ha a tartomány határa bonyolult, különösen fontos feltételeket szabni arra, mikor tekintjük a pontot tartományon belülinek. Ha n pont esett a tartományon belülre, y átlagértéke:  <y> = \frac{1}{n} \sum_{i=1}^{n} F(M_{i})

A kiszámolandó integrál értéke:  I = <y>\sigma= \frac{\sigma}{n} \sum_{i=1}^{n} F(M_{i})

\sigma \approx \frac{n}{N}\quad \text{ahonnan} \quad I \approx \frac{1}{N} \sum_{i=1}^{n} F(M_{i})H(M_{i})

H(M_{i}) = \begin{cases} 0, & M_{i} \not\in \sigma \\ 1, & M_{i} \in \sigma \end{cases}

y=F(M_{i}) behelyettesítési értéket csak abban az esetben számolunk, ha a pont az integrálási tartományon belül található.


Második módszer[szerkesztés | forrásszöveg szerkesztése]

Ha az F függvény nemnegatív, az integrál felírható I = \iint\dots \int_V \mathrm{d}\xi_{1}\mathrm{d}\xi_{2}\dots\mathrm{d}\xi_{m}\mathrm{d}y alakban, aminek geometriai jelentése egy m+1 dimenziós térfogat.

\eta = frac{1}{B}y változócserével, ahol 0 \leq F(\xi) \leq B
I = B\iint\dots \int_\nu \mathrm{d}\xi_{1}\mathrm{d}\xi_{2}\dots\mathrm{d}\xi_{m}\mathrm{d}\eta

a ν tartomány az m+1 dimenziós egységoldalú hiperkockán belül helyezkedik el. Ezúttal az Oξ1ξ2...ξmη térben vesszük fel a mintapontokat. Ha N pontból n tartozik a ν térfogathoz, elegendően nagy N értékre az integrál:

I \approx B frac{n}{N} \qquad  I = B P(M \in \nu)

Források[szerkesztés | forrásszöveg szerkesztése]

  • Computational Mathematics B.P. Demidovich, I. A. Maron, Mir Publishers, Moscow, 1981