Monte Carlo meetodid

Monte Carlo meetodid on rühm arvutialgoritme, mis kasutavad tulemuste arvutamiseks korduvat juhuslikku valimit. Kõige enam kasutatakse Monte Carlo meetodeid arvutisimulatsioonides matemaatiliste ja füüsikaliste süsteemide jaoks. Need meetodid on eelkõige mõeldud arvutiga arvutamiseks ja neid kasutatakse siis, kui deterministliku algoritmiga (sama sisend annab alati sama väljundi) täpse vastuse saamine on teostamatu.

Monte Carlo meetodi defineerimisel puudub konsensus.

Monte Carlo meetodid on eriti kasulikud paardunud vabadusastmetega süsteemide, näiteks vedelike ja rakustruktuuride simuleerimiseks. Neid kasutatakse suure sisendmääramatusega nähtuste modelleerimiseks, näiteks ärinduses riski arvutamiseks. Samuti kasutatakse neid rohkesti matemaatikas, näiteks paljumõõtmeliste (mitmekordsete) ja keeruliste ääretingimustega määratud integraali lahendamiseks ja füüsikas näiteks termodünaamilise tasakaalu simuleerimiseks kineetilise Monte Carlo meetodiga.

Nimetuse „Monte Carlo meetod“ võtsid kasutusele John von Neumann, Stanislaw Ulam ja Nicholas Metropolis 1940. aastatel, kui nad tegelesid Manhattani projektiga. Nimetus tuli Monte Carlo kasiino järgi, kus Ulami onu tihti oma raha maha mängis.

Monte Carlo meetodeid on mitmesuguseid, kuid nad kipuvad järgima teatud raamistikku:

1. defineerida sisendite määramispiirkond
2. genereerida juhusliku jaotusega sisendväärtusi üle määramispiirkonna
3. arvutada sisendid deterministlikult
4. koondada tulemused.

π arvutamise näide

Olgu vaja arvutada π väärtus. Selleks võib lähtuda pildist, millel on kujutatud ruudu sisse kujundatud ring.

Lihtsuse mõttes võib sellest pildist kasutada ainult veerandit, sest ülejäänud veerandid on samasugused.

Kui nüüd joonist pimesi nooltega loopida, siis nende noolte arv, mis tabasid ruutu, ja nende noolte arv, mis tabasid värvitud veerandringi, on vastavate pindaladega proportsionaalsed ehk

${\frac {\text{noolte arv värvitud alas}}{\text{noolte arv kogu ruudus}}}={\frac {\text{värvitud ala pindala}}{\text{kogu ruudu pindala}}}$.

Pindala valemeid mäletades saame:

${\frac {\text{noolte arv värvitud alas}}{\text{noolte arv kogu ruudus}}}={\frac {1/4\pi r^{2}}{r^{2}}}={\frac {1}{4}}\pi$, millest $\pi =4{\frac {\text{noolte arv värvitud alas}}{\text{noolte arv kogu ruudus}}}$.

Värvitud ala tabamuste suhe möödavisetega on ¼ π väärtusest. Et saada π väärtusele mõistlik tulemus, peaks noolte arv olema suur.

Ise seda teha on raske ja selleks kasutatakse lihtsaid arvutialgoritme, nagu näiteks:

Olgu ringi raadius 1 ühik. Iga viske jaoks saab genereerida kaks juhuarvu, mida kasutatakse x- ja y-koordinaadina. Seejärel saab Pythagorase teoreemi abil leida kauguse koordinaatide alguspunktist $(0,0)$. Kui see on $\leqslant 1$, on see värvitud ala sees ja loeb. Tehes seda tuhandeid või rohkem kordi, saame π jaoks päris mõistliku väärtuse.

Ajalugu

Monte Carlo meetodi algset varianti võib näha Buffoni nõela eksperimendis, kus saab leida π ligikaudse väärtuse, pillates nõelu paralleelsete puitplaatidega põrandale. 1930-ndatel eksperimenteeris Enrico Fermi Monte Carlo meetodiga, esimest korda neutronite difusiooniga katsetades, kuid ei avaldanud midagi sellekohast.

Aastal 1946 uurisid füüsikud Los Alamose teaduslaboratooriumis radioaktiivse kiirguse varjestust ja distantsi, mida neutronid tõenäoliselt eri materjalides läbiksid. Kuigi oli olemas enamik vajalikke andmeid, nagu keskmine vaba tee pikkus, mida neutron tõenäoliselt aines läbiks enne aatomituumaga kokkupõrkamist, ja kui palju energiat neutron tõenäoliselt kokkupõrke järel välja annaks, ei suutnud füüsikud lahendada probleemi traditsiooniliste deterministlike matemaatiliste meetodite abil. Poola-ameerika matemaatikul Stanisław Ulamil tekkis idee kasutada juhuslikke eksperimente. Ta kirjeldas oma inspiratsiooni tekkimist järgmiselt:

„Esimesed ideed ja katsed Monte Carlo meetodi praktiseerimiseks ilmnesid mulle aastal 1946 haigusest toibudes ja pasjanssi mängides ühe küsimuse näol. See küsimus on järgmine: "Mis on tõenäosus 52 kaardi väljaladumisel Canfieldi pasjanss edukalt lõpetada?" Kui ma olin juba kulutanud tükk aega, proovides arvutada tõenäosust puhtalt kombinatoorsete kalkulatsioonide kaudu, murdsin ma pead, üritades otsustada, kas poleks näiteks kaartide 100-kordne väljaladumine ja tulemuste jälgimine praktilisem meetod kui puhas abstraktne mõtlemine. Katse ja eksituse meetodit oli kerge ette kujutada tänu kiirete arvutite ajastu algusele ning ma hakkasin kohe mõtlema probleemidest füüsika valdkonnas, näiteks neutronite hajumisele ja teistele küsimustele matemaatilises füüsikas, ning üldisemalt: kuidas muuta diferentsiaalvõrrandite kirjeldatud protsesse niisugusse vormi, mida saaks tõlgendada juhuslike operatsioonide järgnevusena. Hiljem [aastal 1946] kirjeldasin ma oma ideed John von Neumannile ja me hakkasime kavandama tegelikke arvutusi.“

– Stanisław Ulam

Kuna von Neumanni ja Ulami töö oli salajane, vajas see varjunime, milleks von Neumann valis Monte Carlo. Nimi viitab Monte Carlo kasiinole Monacos, kus Ulami onu laenas raha õnnemängude jaoks. Von Neumann arendas meetodi pseudojuhuslike arvude kalkuleerimiseks, kasutades ruutkeskmise meetodit, kuna tõeliselt juhuslike numbrite loendi kasutamine oli väga aeglane. Kuigi seda meetodit peeti algeliseks, oli von Neumann sellest teadlik. Ta õigustas selle kasutamist, kuna see oli kiirem kui kõik teised tema käsutuses olevad meetodid, ja väärtulemused olid ilmselged, erinevalt teistest meetoditest, mille tulemused võisid olla märkamatult väärad.

Monte Carlo meetodid olid Manhattani projekti simulatsioonide keskmeks, kuigi piiratud tollaste arvutusvahendite poolt. 1950. aastatel kasutati neid Los Alamosel vesinikupommi arenduse varastes arengustaadiumides ning need muutusid populaarseks füüsika, füüsikalise keemia ja tegevusanalüüsi valdkonnas. Sellel ajal vastutasid Monte Carlo meetodite rahastamise ja leviku eest ettevõte RAND ja Ameerika Ühendriikide Õhujõud ning nende rakendus hakkas levima järjest kiiremini ja järjest rohkematesse valdkondadesse.

Monte Carlo meetodite kasutamine vajab suurtes kogustes juhuarve ja nende kasutuselevõtt ergutas pseudojuhuslike arvude generaatorite arendust, mis omakorda olid mitu korda kiiremad kui juhuarvude tabelid, mida varem statistikas kasutati.

Rakendused

Monte Carlo meetodid on eriti kasulikud selleks, et simuleerida nähtusi, millel on suure määramatusega sisendid, ja süsteeme, millel on suur hulk paardunud vabadusastmeid. Peamised kasutusalad on

• tehnika
• arvutusbioloogia
• rakendusstatistika
• arvutimängud
• disain
• rahandus
• telekommunikatsioon

Rakendused matemaatikas

Monte Carlo meetodeid kasutatakse matemaatikas mitmesuguste ülesannete lahendamiseks. Genereeritakse sobilikke juhuslikke arve ja jälgitakse seda arvude osa, mis käitub mingile omadusele kohaselt. Meetod on kasulik arvuliste lahendite leidmiseks probleemidele, mida on liiga keeruline analüütiliselt lahendada. Kõige kasutatum Monte Carlo meetod on Monte Carlo integreerimine.

Integreerimine

Monte Carlo integreerimine on meetod, millega arvutatakse määratud integraalidele arvulisi lahendeid, kasutades juhuslikke arve. Monte Carlo algoritmid valivad suvalise punkti, kus integraali arvutatakse. See meetod on eriti kasulik kordsete integraalide lahendamiseks.

Ülevaade

Deterministlikud arvulised integreerimisalgoritmid töötavad hästi väheste mõõtmete korral, aga esineb kaks probleemi, kui funktsioonidel on mitu muutujat. Esiteks mõõtmete arvu kasvuga suureneb järsult funktsiooni hinnangute arv. Näiteks kui 10 hinnangut tagavad piisava täpsuse ühes mõõtmes, siis 100 mõõtmes on vaja 10¹⁰⁰ punkti arvutada, mis nõuab ilmselgelt liiga palju arvutusvõimsust. Teiseks, mitmemõõtelise piirkonna ääretingimus võib olla väga keeruline, seega ei pruugi olla mõistlik lihtsustada probleemi mitmele ühekordsele integraalile. 100 mõõdet ei ole mitte mingil määral ebaharilik, kuna paljudes füüsikalistes probleemides mõõde võrdub vabadusastmega. Monte Carlo meetodid võimaldavad väljapääsu arvutusaja eksponentsiaalsest kasvust.

Olgu hulk $\Omega$ $\mathbb {R} ^{D}$ osahulk, millel kordne määratud integraal

$I=\int _{\Omega }f({\bar {\mathbf {x} }})\,d{\bar {\mathbf {x} }}$

arvutatakse ruumipiirkonnas $\Omega$:

$V=\int _{\Omega }d{\bar {\mathbf {x} }}$.

Kõige labasem viis $I$ arvutamiseks on piirkonnas $\Omega$ valimeid võttes : andes $N$-ile palju kordi valimeid ${\bar {\mathbf {x} }}_{1},\dots ,{\bar {\mathbf {x} }}_{N}\in \Omega$. $I$-le saab hea lähendi kujul:

$I\approx Q_{N}\equiv V{\frac {1}{N}}\sum _{i=1}^{N}f({\bar {\mathbf {x} }}_{i})=V\langle f\rangle$.

Mida suurem hulk valimeid võtta, seda väiksem on kõrvalekalle tegelikust väärtusest:

$\lim _{N\to \infty }Q_{N}=I$.

Funktsiooni lähendi saab leida, valides suvaliselt punkte 100-mõõtmelises ruumis ja leides nende funktsioonide keskmise väärtuse. Keskse piirteoreemi põhjal näitab see meetod $\scriptstyle 1/{\sqrt {N}}$ koonduvust: kui neljakordistada valimit, väheneb viga kaks korda, olenemata mõõtmete arvust.

Kui võrrelda Monte Carlo ja Las Vegase algoritmi, siis esimene on mõeldud eelkõige lähendi leidmiseks tegelikule väärtusele ja seda kasutatakse siis, kui ühest funktsiooni ei ole defineeritud. Las Vegase algoritm annab alati õige vastuse või jätab selle andmata. Lisaks võib Las Vegase algoritmi katkestamine anda Monte Carlo meetodiga sarnase tulemuse, kuna tulem ei ole enam 100% korrektne.

Kirjandus

• Hubbard, Douglas (2007). How to Measure Anything: Finding the Value of Intangibles in Business. John Wiley & Sons. Lk 46.
• Metropolis, N. (1987). "The beginning of the Monte Carlo method" (PDF). Los Alamos Science (1987 Special Issue dedicated to Stanisław Ulam): 125–130.
• Eckhardt, Roger (1987). "Stan Ulam, John von Neumann, and the Monte Carlo method". Los Alamos Science, Special Issue (15): 131–137.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Newman, MEJ; Barkema, GT (1999). Monte Carlo Methods in Statistical Physics. Clarendon Press.
• Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1996) [1986]. Numerical Recipes in Fortran 77: The Art of Scientific Computing. Fortran Numerical Recipes. Kd 1 (Second ed.). Cambridge University Press. ISBN 0-521-43064-X.

Välislingid

• π arvutamise näide
• Café math: Monte Carlo integreerimine Blogipostitus Monte Carlo integreerimisest
• Feynmani-Kaci mudelid ja Monte Carlo algoritmid osakeste jaoks
• Monte Carlo meetodi Exceli näide