Monte Carlo metoda

Monte Carlo metoda
Metodu je osmislio Stanislaw Ulam, poljski matematičar, koji je radio u SAD-u s John von Neumannom na Manhattan projektu tokom II. svjetskog rata. Kako je došao do te metode najbolje opisuje sam:

Prve misli i pokušaji ostvarivanja metode nastale su 1946. kad sam se oporavljao od prehlade i igrao pasianz. Postavio sam si pitanje kolika je vjerojatnost ja se igra završi uspješno? Nakon dugo vremena provedenog u pokušaju procjene jednostavnom kombinatorikom, pomislio sam nije li jednostavnije primjenit praktičnu metodu od apstraktnog razmišljanja. Primjerice odigrat partiju stotinu puta i jednostavno zbrojiti uspješno odigrane partije. Ta mogučnost je postojala s početkom nove ere brzih računala.

Odmah sam počeo razmišljati o primjeni metode na difuziju neutrona i ostala pitanja fizike, općenito kako problem opisan diferencijalnom jednadžbom prikazati nizom slučajnih operacija. Svoju ideju sam opisao Johnu von Neumannu i počeli smo raditi na problemu.
Danas Monte Carlo metodu poznajemo kao metodu kojom riješavamo matematičke probleme upotrebom (pseudo)slušajnih brojeva. Drugim riječima statičnim uzorcima aproksimiramo riješenje kvantitativnog prolema. Ulam nije prvi u tom području, ideju je prvi prikazo W. S. Gossett poznatiji pod pseudonimom Student. Ulamov doprinos bio je u primjeni metode na novonastala računala.

Zajedno s John von Neumannom i Nicholasom Metropolisom razvio je algoritam za računalnu implementaciju, metoda je dobila ime po kasinima Monte Carla.

Sam princim metode nastao je puno prije Studenta, točnije 1777. kad se Comte de Buffon zapitao kolika je vjerojatnost da drvce dužine l bačeno na rešetku razmaka d (d>l) padne na jednu od linija rešetke.

Rješenje problema proizlazi iz zadanog integrala:

Kroz ovo rješnje matematičar Laplace je došao do jedinstvenog načina određivanja vrijednosti broja . Pretpostavimo da je Buffonov eksperiment izveden bacanjem drvca n puta, neka M označava koliko puta je drvce palo na liniju:

Pošto je ovoj i prethodnoj jednadžbi jednaka lijeva strana nužno im je jednaka i desna tj:

ili:

Koristeći taj princip Kapetan O.C.Fox je 1864 izveo eksperiment u tri serije i došao do sljedećih rezultata:

Prvi put je došao do nedovoljno dobrog rezultata, nezodovoljan činjenicom da bi morao višestruko povećati broj bacanja zarotirao je rešetku. Dalje nezadovoljan rezultatom a ne želeći znatno povećati broj bacanja promjenio je dimenzijski odnos. Taj pokus je dokazao da nije potrebno izvesti 2000 bacanja ili više već je dovoljno promjeniti druge parametre u pokusu što danas ima implementaciju u odabiru (pseudo)slučajnih brojeva. Pseudo zato što su sve samo ne slučajni što nam govori da kvaliteta odabira (pseudo)slučajnih brojeva određuje i točnost primjene Monte Carlo metde.

Primjer izračunavanja određenog integrala
Izračunavanje određenih integrala se svodi na izračunavanje površine ispod podintegralne funkcije. Površina ovakvih likova se može ocjeniti ako se uniformno razbacaju točke po nekoj većoj površini poznate površine koja je sadrži (obično kvadratu ili pravokutniku),a zatim se prebroje točke koje su pale unutar lika. Kao konkretan primer razmotrit ćemo četvrtinu jediničnog kruga. Ako po jediničnom kvadratu u kojem se nalazi uniformno razbacamo 10 točaka, a zatim utvrdimo da je unutar kruga palo 8, dobit ćemo da je

Greška je izračunata pomoću izraza iz statistike:

jer je rijeć o promjenjivoj varijabli x koja može poprimiti vrijednosti: 1(pogodak u figuru) i 0(promašaj). Ova metoda se u praksi zovi Hit-or-mis Monte Carlo metoda.

Također, kako je i naznačeno preko slike osim površine ispod integrala možemo izračunati i vrijednost pošto funkcija u sebi sadrži parametar .

Dva usporedna programa u Fortranu i C-u koji preko ovog integrala izračunavaju vrijednost

Prednosti i nedostaci algoritma:

-prednosti

a) Jednostavnost algoritma;

b) Laka ocjena greške;

c) Jednostavno tretiranje domena integracije kompleksnih oblika;

d) Ocjena integrala može po potrebi biti naknadno profinjena daljim ulaganjem kompjuterskog vremena.

-mane

a) Mogućnost sistematskih grešaka (pristrasnost ocjene);

b) Potrebni su "dovoljno dobri" slučajni brojevi (potrebno je testiranje).

Stoga je pri primjeni Monte Carlo metoda potrebna izvjesna doza opreznosti.

Razvoj simulacijskih metoda:

Problem odabira pseudo brojeva otvorio je put razvoju drugim metodama, tako Vegas algoritam služi za smanjivanje pogreške Monte Carlo simulacije.

U osnovi Vegas testira pravilnost distribucije točaka na površinu (primjer određivanja integrala pomoću Monte Carlo metode), prolazeći poljem radi histogram.

Postoji niz algoritama koji se bave odabirom pseudo brojeva:

Metropolis-Hastings, Gipsov uzorak, Markovov lanac...

Sama Monte Carlo metoda zbog širokog spektra uporabe odjeljena je na metode:

Direktna simulacija M.C., Dinamična M.C. metoda, Kvantna M.C. metoda te Kvazi M.C: metoda