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:
 defineerida sisendite määramispiirkond
 genereerida juhusliku jaotusega sisendväärtusi üle määramispiirkonna
 arvutada sisendid deterministlikult
 koondada tulemused.

π arvutamise näide
Olgu vaja arvutada π väärtus. Selleks võib lähtuda pildist, millel on kujutatud ruudu sisse kujundatud ring.
200px|right

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

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
.

Pindala valemeid mäletades saame:
, millest .

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 . Kui see on , 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. aastatel 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:

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.Press et al, 2007, Chap. 7. 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 10100 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   osahulk, millel kordne määratud integraal

arvutatakse ruumipiirkonnas :

.

Kõige labasem viis  arvutamiseks on piirkonnas  valimeid võttes Newman, 1999, Chap. 1.: andes -ile palju kordi valimeid . -le saab hea lähendi kujul:
.

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

.

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  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.

Viited

 Kirjandus 

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

Kategooria:Matemaatika