Monte-Carlo-integrálás

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 (π*1²) 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 ≈ π*1².

A matematikában a Monte-Carlo-integrálás egy olyan numerikus integrálási módszer, mely véletlen számokat használva számol. A többi integrálási algoritmus általában egy szabályos rácson értékeli 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

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 10¹⁰⁰ 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).

Egy illusztráció a Monte-Carlo-integrálás hiba számolásárol

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örténete

A Monte-Carlo-módszer története az 1930-as évektől ismert, Enrico Fermi nevéhez fűződik, majd az 1940-es években Neumann János és Stanisław Ulam foglalkozott vele, a Manhattan projekt keretein belül.

A módszer kifejlesztése előtt a szimulációkat a már megértett folyamatok ellenőrzésére használták, véletlen mintákkal a determinisztikus modell bizonytalanságait becsülték fel. A második világháború után a Los Alamos-i kutatóintézetben a neutronok szabad úthosszának meghatározása különböző anyagokban, analitikus módszerekkel nem volt megoldható. Stanislaw Ulam javasolta a véletlen értékekkel végzett kísérleteket, melyekből következtetéseket lehetett levonni a jelenségre vonatkozóan.

Monte Carlo szimuláció

Valószínűség-eloszlás mintavételezése. A minták alapján lehetséges kimenetek meghatározása. A lehetséges kimenetek valószínűségének számítása.

Többszörös integrálok értékének meghatározása

A többszörös integrál transzformálása

Az I integrál geometriai jelentése egy m+1 dimenziójú térfogat, vagyis egy Ox₁x₂...x_my térben S alapú egyenes hiperhenger, melyet felülről az y=f(x₁,x₂,...,x_m) 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

Első módszer

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

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ξ₁ξ₂...ξ_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 Bfrac{n}{N}\qquad I=BP(M\in \nu )$

Források

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