Predavanje 8 METODA MONTE-CARLO

1 MA INSKI FAKULTET NI - LOGISTI KE SIMULACIJE 2010/2011 - dr Miomir Jovanovi 1 Predavanje 8 METODA MONTE-CARLO Von Neumann i Ulam, s kraja etrdesetih godina, su re avaju i probleme velike kompleksnosti, ustanovili da se rezultati ne mogu dobiti analiti kim putem, a sprovo enje eksperimenata bi bilo veoma skupo, pa su pristupili kori enju Monte Karlo tehnike. Tako su do li do matemati kih re enja deterministi kih problema simulacijom stohasti kih procesa, koji su imali verovatnosnu raspodelu koja zadovoljava matemati ke relacije datog deterministi kog problema.

2 Monte Carlo simulacija odslikava stohasti ke procese kod kojih vreme ne igra ulogu. Ona se ozna ava i kao METODA ponovljenih poku aja. Numeri ke metode, poznate kao Monte Carlo metode, mogu se slobodno definisati kao statisti ki simulacioni metodi, kod kojih se upotrebljavaju nizovi slu ajnih brojeva za izvr enje simulacije. Monte Carlo metode poslednjih nekoliko decenija dobija status potpuno zaokru ene numeri ke metode sposobne za re avanje najkompleksnijih zahteva. Monte Carlo metodi su prvobitno poznati kao statisti ka upro avanja.

3 Naziv Monte Carlo , popularizovan od strane prvih istra iva a u ovoj oblasti (Stanislaw Marcin Ulam, Enrico Fermi, John von Neumann i Nicholas Metropolis), je proistekao iz naziva uvenog kazina u Monaku. Kori enje slu ajnosti i procesa ponavljanja u metodi je analogno aktivnostima koji se doga aju u kazinu. Kako su za dobijanje dovoljno ta ne ocene tra ene veli ine, potrebna izra unavanja za veoma veliki broj posebnih slu ajeva i odgovaraju a statisti ka obrada ogromnog numeri kog materijala to je efektivna primena metode Monte Carlo omogu ena tek pojavom elektronskih ra unara.

4 Monte Carlo METODA zahteva da se fizi ki sistem opi e funkcijama gustine verovatno e. Kada su poznate ove funkcije, Monte Carlo simulacija se nastavlja slu ajnim izborom vrednosti iz funkcija. Potom se izvr e mnoge simulacije (eksperimenti, probe), a za re enje se uzima prose an rezultat svih simulacija (mo e biti jedno ispitivanje, a mo da i milion ispitivanja). Pri re avanju razli itih problema kod kojih je te ko do i do analiti kih izraza koriste se ra unski metodi, modeliranjem slu ajnih promenljivih.

5 Slede i primer ilustruje ideju tih METODA , kojima pripada i METODA Monte Carlo. Primer 1: Potrebno je izra unati povr inu ravne figure S. To mo e biti potpuno proizvoljna figura koja je ograni ena krivom linijom; mo e biti definisana grafi ki ili analiti ki, mo e biti cela figura ili figura sa injena od nekoliko delova. Pretpostavimo da je S prostor, , sadr an u jedini nom kvadratu. N slu ajnih ta aka u jedini nom kvadratu S x y 0 1 1 MA INSKI FAKULTET NI - LOGISTI KE SIMULACIJE 2010/2011 - dr Miomir Jovanovi 2 N slu ajnih ta aka nalazi se u kvadratu.

6 Ozna imo broj ta aka koje su sadr ane u figuri S sa N', a sa m(S) povr inu figure S. Geometrijski je o igledno da odnos povr ina figure S i jedini nog kvadrata pribli no jednak odnosu N'/N, odnosno m(S) je pribli no jednak N'/N. to je ve e N, ve a je i ta nost ove procene. Ovaj primer ima vi e ilustrativan nego prakti an zna aj. Za izra unavanje povr ina ravnih figura koriste se ta niji metodi (kvadratne formule) koji su i komplikovanije. Me utim, kada je u pitanju izra unavanje zapremina figura u prostoru sa vi e dimenzija metod Monte Carlo predstavlja jedini na in za re avanje takvih problema.

7 Izbor ta aka u kvadratu na slu ajan na in se mo e realizovati pomo u tehni kih ure aja koji formiraju (generi u) slu ajne brojeve. Ti ure aji se nazivaju generatori slu ajnih brojeva. Najprostiji ure aj te vrste je drveni ili metalni disk (to ak) koji se okre e oko svoje osovine. Ovaj ure aj se jo naziva i rulet i defini e princip rada na kome se izgra eni i savr eniji elektronski ure aji koji se danas koriste kao generatori slu ajnih brojeva. Na prikazan je generator slu ajnih brojeva. Rulet generator slu ajnih brojeva Osnovna ideja METODA Monte Carlo sastoji se u slede em: Da bi pribli no izra unali neku skalarnu veli inu a (povr ina figure u ravni, zapremina tela u prostoru, vrednost odre enog integrala i dr.)

8 Treba po i od slu ajne promenljive X ije je matemati ko o ekivanje EH jednako a. Odrediv i N nezavisnih vrednosti (realizacija) x1,x2,..,xN slu ajne promenljive H, za pribli nu vrednost veli ine a mo e se uzeti aritmeti ka sredina vrednosti x1,x2,..,xN: Oblast primene metode Monte Carlo Monte Carlo METODA se primenjuje u raznim simulacijama koje koriste slu ajne brojeve. Naj e e se METODA koristi samo za stati ke tipove simulacija kod kojih se u re avanju problema koristi stvaranje uzoraka iz raspodela slu ajnih promenljivih.

9 Pri tome, problemi mogu biti bilo deterministi kog, bilo stohasti kog karaktera. Razlikujemo slede e primene Monte Carlo simulacije: 1. Deterministi ki problemi koje je te ko ili skupo re avati. Tipi an primer je kori enje ovog METODA za izra unavanje odre enih integrala koji se ne mogu re iti analiti ki. Monte Carlo METODA se u ovom slu aju koristi za generisanje niza slu ajnih 0 5 7 2 9 4 8 1 6 3 MA INSKI FAKULTET NI - LOGISTI KE SIMULACIJE 2010/2011 - dr Miomir Jovanovi 3 ta aka (xj,yj) sa jednakim verovatno ama unutar odre enog pravougaonika.

10 Zatim ispituje koliko je generisanih ta aka sadr ano u povr ini koja odgovara integralu. 2. Slo eni fenomeni koji nisu dovoljno poznati. Ovo je druga klasa problema koje se re avaju uz pomo Monte Carlo METODA . Ove probleme karakteri e to da nije poznat na in uzajamnog delovanja izme u elemenata, ve su poznate samo verovatno e njihovog ishoda. Verovatno e se koriste za izvo enje niza eksperimenata koji daju uzorke mogu ih stanja zavisnih promenljivih. Statisti kom obradom rezultata dobija se raspodela verovatno a zavisnih promenljivih koje su od interesa.