Metoda Monte Carlo

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Monte Carlo je třída algoritmů pro simulaci systémů. Jde o stochastické metody používající pseudonáhodná čísla. Typicky využívány pro výpočet integrálů, zejména vícerozměrných, kde běžné metody nejsou efektivní. Metoda Monte Carlo má široké využití od simulaci experimentů přes počítání určitých integrálů až třeba řešení diferenciálních rovnic. Základní myšlenka této metody je velice jednoduchá, chceme určit střední hodnotu veličiny, která je výsledkem náhodného děje. Vytvoří se počítačový model toho děje a po proběhnutí dostatečného množství simulací se mohou data zpracovat klasickými statistickými metodami, třeba určit průměr a směrodatnou odchylku.

Historie[editovat | editovat zdroj]

Metoda Monte Carlo byla formulována již ve 40. letech 20. století a svého využití se dočkala ještě v průběhu druhé světové války. Jejím zakladatelem byl Stanislaw Marcin Ulam a John von Neumann, kteří v té době pracovali v americké Národní laboratoři Los Alamos, kde zkoumali chování neutronů, především je zajímalo, jaké množství neutronů projde různými materiály (např. nádrží vody).[1]

Přes velké množství informací nebylo možné tento problém vyřešit teoreticky ani prakticky. K výsledku dopomohla až metoda Monte Carlo, kdy se autoři nechali inspirovat kolem rulety (odtud také název Monte Carlo). Bylo jim známo, že k pohlcení neutronu jiným atomem dojde v přibližně jednom případu ze sta. Každé roztočení rulety by simulovalo pohyb neutronu, pokud by se zastavila na dílku, který znázorňuje pohlcení neutronu, neutron by cestu neprošel. To by se opakovalo vždy tak dlouho, dokud by neutron nebyl pohlcen nebo dokud by úspěšně prošel celou cestu.[2]

Ač je tento příklad velmi zjednodušený, podstatu metody Monte Carlo vystihuje. Simulace by byla pochopitelně velmi časově náročná, pokud by se skutečně pokaždé točilo ruletou. Autoři ale pracovali v době, kdy vývoj výpočetní techniky byl již v plném proudu, a proto pro tyto simulace mohli používat na dnešní dobu jednoduché počítače, které dobu simulace výrazně zkrátily.

Vzdáleným předchůdcem metody Monte Carlo je tzv. Buffonova jehla. Je to úloha z roku 1777, jejímž autorem je francouzský matematik Georges Louis Lecrerc de Buffon. Velmi zjednodušeně jde o pokus, kdy se na arch papíru, který je rozdělen rovnoběžnými linkami hází jehlou, která má stejnou velikost, jako je vzdálenost mezi čárami. Výsledkem je, že pravděpodobnost, že jehla některou čáru protne, je 2/π. Z toho se dá odvodit hodnota π.

Výpočet hodnoty π[editovat | editovat zdroj]

Typickou úlohou metody Monte Carlo je zjištění hodnoty Ludolfova čísla π. Základem je čtverec, kterému je vepsaná čtvrtkružnice. Analogicky jako u Buffonovy jehly je možné jeho hodnotu zjistit náhodným házením jehlou, popřípadě jakýmkoliv jinými drobnými předměty do prostoru čtverce, a výsledný poměr počtu všech hodů a hodů do kruhu dá hodnotu čísla π.[3]

výpočet pí

obsah čtvrtkružnice: S_1 = \frac{\pi r^2}{4}

obsah čtverce: S_2 = r^2

jejich poměr je pak :\frac{S_1}{S_2} = \frac{\pi r^2}{4 r^2} = \frac{\pi}{4}

pak \pi = 4 \frac{S_1}{S_2}

Aplikace[editovat | editovat zdroj]

Přesnost a efektivnost celého výpočtu metodou Monte Carlo pomocí výpočetní techniky je dána těmito faktory:[4]

Metoda MC zahrnuje:

  • vytvoření modelu skutečného systému, se stejnými pravděpodobnostními charakteristikami jako má reálný systém (vliv náhody - náhodná čísla)
  • model musí zahrnovat veškeré relevantní skutečnosti, podstatně ovlivňující reálný systém
  • experimentování s modelem, mnohanásobné zkoumání chování modelu
    • s pevným časovým krokem – sledujeme chování systému po určitých konstantních časových intervalech a zjišťujeme, zda došlo ke změnám)
    • s proměnným časovým krokem – generujeme interval, po který v systému nedojde k žádným změnám

schéma monte carlo Schéma postupu metody Monte Carlo

Řešení problému metodou Monte Carlo můžeme rozdělit do tří kroků:[5]

  • Rozbor problému a návrh modelu - z hlediska řešení problému se jedná o nejdůležitější krok. I když je MMC použitelná prakticky u všech problémů a její formulace není složitá, nalezení vhodného postupu může nezkušenému řešiteli dělat problémy.
  • Generování náhodných veličin, jejich transformace na veličiny s daným pravděpodobnostním rozdělením. Rychlost konvergence chyby výsledku k nulové hodnotě je u MMC rovna přibližně převrácené hodnotě odmocniny z počtu realizovaných pokusů N, z čehož plyne, že nepatří mezi metody nejefektivnější.
  • Statistické zpracování výsledků - hledaná hodnota je zpravidla dána některým z momentů statistických veličin, nejčastěji střední hodnotou.

Oblasti použití[editovat | editovat zdroj]

Metoda Monte Carlo má širokou možnost využití. Obecně se dá říci, že je možné ji použít všude tam, kde je řešení možné nalézt pomocí mnohokrát opakovaných náhodných pokusů. Jelikož se jedná o metodu stochastickou, je nutné znát pravděpodobnostní rozdělení sledovaných veličin. Tyto problémy lze nalézt ve všech oborech, nejen v matematice, ale také v oblasti financí a obchodu, fyzice a fyzikální chemii, ve výpočetní technice a hrách apod.

Matematika[editovat | editovat zdroj]

Metoda Monte Carlo je použitelná nejen k řešení jednoduchých určitých i vícerozměrných integrálů, parciálních diferenciálních rovnic, ale třeba také řešení systémů lineárních rovnic, či hledání kořenů rovnic.[4]

Numerická matematika[editovat | editovat zdroj]

Příkladem použití metody Monte Carlo je Rabinův-Millerův test prvočíselnosti. Používá se k rychlému rozhodnutí, zda je dané celé kladné číslo N prvočíslem nebo zda je složené. Počítá několik mocnin čísla b modulo N, první exponent je číslo N-1, každý další exponent je polovina předcházejícího, pokud je předcházející exponent sudý. Test končí ve chvíli, kdy je odpovídající mocnina různá od jedné i od minus jedné modulo N a číslo je správně klasifikováno jako složené, nebo v okamžiku, kdy buď už exponent nelze dělit dvěma, nebo se mocnina rovná minus jedné modulo N a tehdy se číslo označuje jako silné pseudoprvočíslo při bázi b. Pravděpodobnost, že silné pseudoprvočíslo není prvočíslem, je menší, než jedna osmina. Opakujeme-li tedy test s jinými volbami báze, a vždy dostáváme odpověď, že se jedná o silné pseudoprvočíslo, pravděpodobnost, že se skutečně jedná o prvočíslo, prudce vzrůstá.[6]

Rozlišují se dvě varianty metody Monte Carlo, analogový a neanalogový model.

Analogový model[editovat | editovat zdroj]

Musíme umět modelovat celou situaci na počítači, to znamená například znát všechna pravděpodobnostní rozložení zkoumaných jevů a fyzikální zákonitosti, kterými se řídí. Provedením této simulace získáme výsledek, realizaci jakési náhodné veličiny \xi. Tuto simulaci spustíme n-krát a získáme soubor historií x1 ...xn . Odhad střední hodnoty \xi se určí :

\xi  \approx  \frac{1}{N}\sum_{i=1}^N x_i

a směrodatná odchylka se určí jednoduše jako

\sigma = \sqrt{ \frac{\sum_{i=1}^n (\bar{x} - x_i)^2}{n-1}}

Neanalogový model[editovat | editovat zdroj]

Tak se nazývá případ, kdy při výpočtu nepoužíváme model reálného děje. Například výpočet určitého integrálu, případně obsahu ohraničeného útvaru.

Integrace metodou Monte Carlo[editovat | editovat zdroj]

Metody typu Monte Carlo lze úspěšně využít také pro numerickou integraci. Hlavní článek o Monte Carlo integrování.

Přesnost metody Monte Carlo[editovat | editovat zdroj]

K odhadu chyby výsledku získaného metodou Monte Carlo se většinou používá střední kvadratická chyba aritmetického průměru. Chyba výsledku získaného pomocí n historií je úměrná 1/\sqrt{n}. Takže aby se zlepšil výsledek o jeden řád musí se počet historií zvýšit alespoň o dva řády. Abychom získali výsledek s přesností na 6 desetinných míst, což odpovídá přesnosti jiných metod musíme získat 1012 historií.

Další použití metody

Fyzika[editovat | editovat zdroj]

Kromě již zmíněné fyzikální chemii se metoda Monte Carlo používá ke složitým výpočtům v kvantové chromodynamice, aerodynamice, dále ve fyzice polymerů, statistické fyzice, fyzice částic. Monte Carlo najde uplatnění i při předpovědi počasí.

Počítačová grafika[editovat | editovat zdroj]

Zejména metoda Quasi Monte Carlo se využívá při renderování ve 3D modelech. Grafické programy mají funkci, která vytváří odrazy světla od různých ploch, Monte Carlo je generuje náhodně v rámci polokulové distribuce, Quasi Monte Carlo je vytváří pravidelně. Využití – počítačové hry, grafika, animace, filmové efekty, architektura apod. Jedna z metod renderování je radiozita, vychází ze zákona zachování energie a definuje se jako:

 B_i = E_i + R_i \int_j B_j F_ij

kde: Bi je radiozita plošky i. Ei je vyzařovaná energie této plošky. Ri je odrazivost plošky. integrál reprezentuje součet energií přicházejících na plošku i ze všech ostatních plošek. Fij je konfigurační faktor mezi ploškami i a j (vliv plošky j na plošku i).

Hazardní hry[editovat | editovat zdroj]

Hazardní hry jsou založeny na náhodě, tak jako u jiných her je popsána systémem pravidel a je posloupností tahů. Právě výsledky tahů jsou u hazardních her zcela náhodné – náhodné tahy, u jiných her, kde jsou tahy ovlivněny vůlí hráče, je označujeme jako osobní tahy. Monte Carlo je ukázkou procesů, kdy systém osobních tahů bude simulovat systém náhodných tahů. Právě hazardní hry byly východiskem pro vznik a rozvoj teorie pravděpodobnosti. Monte Carlo resp. generátory náhodných a pseudonáhodných čísel umožňují mechanizovat hazardní hry, protože umožňují nastavit všem alternativám stejnou pravděpodobnost.[7]

Finance a pojišťovnictví[editovat | editovat zdroj]

V oblasti ekonomiky je možné metodu Monte Carlo využít pro oceňování opcí, investic a jiných finančních derivátů, analýzu rizika, pro zjištění optimální hodnoty portfolia, pro rozhodování či zajišťování.

Analýza rizika[editovat | editovat zdroj]

Metoda Monte Carlo dává nejpřesnější pravděpodobnosti ve srovnání s jinými metodami. I přes značné výhody naráží na řadu překážek:[8]

  • vysoká citlivost výsledků metody Monte Carlo k zákonům pravděpodobnostního rozdělení a typu závislostí vstupních proměnných;
  • i když současné programy umožňují vzít v úvahu zákony rozdělení pravděpodobnosti, provést korelaci mezi vstupními proměnnými a zhodnotit jejich spolehlivost, v praxi to obvykle není možné, protože ve většině případů analytici stanoví změny základních proměnných makro a mikro prostředí, vybírají zákony rozdělení pravděpodobnosti a statistické vztahy mezi proměnnými subjektivně.
  • V důsledku výše uvedených důvodů je přesnost výsledných odhadů do značné míry závislá na kvalitě základních předpokladů a vzájemných souvislostech vstupních proměnných, což může vést k významným chybám ve výsledcích.

Z praktického hlediska je použitelnost metody Monte Carlo kvůli velkému množství zjednodušených předpokladů modelů značně omezená.

Další možnosti využití[editovat | editovat zdroj]

Využití metody Monte Carlo je opravdu velmi široké, musí pouze splňovat výše uvedené předpoklady. Kromě již zmíněného se Monte Carlo používá také:

Optimalizace[editovat | editovat zdroj]

Optimalizačních problémů je celá řada, ve všech oborech, např. ve fyzice hledání optimální tloušťky tlakové nádoby, či v umělé inteligenci hledání optimální trajektorie robota apod. Optimalizační problémy se dají řešit buď analyticky, nebo pokud to možné není, je možné je řešit optimalizačními algoritmy (jako např. uvedené příklady). Optimalizační algoritmy převedou daný problém na matematický, jehož optimalizace vede k nalezení argumentů tzv. účelové funkce, což je cílem optimalizace. Optimalizační algoritmy hledají minimum dané účelové funkce.[9]

Optimalizační metody je možné rozdělit do tří skupin:[9]

Generátory náhodných čísel[editovat | editovat zdroj]

Generátory náhodných čísel s definovaným stochastickým rozdělením jsou základem simulačních programů Monte Carlo. Generátory náhodných čísel fungují tak, že nejprve vygenerují posloupnost náhodných čísel s rovnoměrným rozdělením (primární generátor) a poté je z nich transformací vytvořena posloupnost s požadovaným rozdělením. Primární generátory jsou fyzikální nebo pseudonáhodné.[10]

Fyzikální generátory náhodných čísel[editovat | editovat zdroj]

Jako fyzikální generátor náhodných čísel se dá chápat vše, co má charakter náhodnosti, jako např. házení kostkou nebo mincí. Častěji se ale používají generátory založené na kombinaci radioaktivního zářiče a detektoru (vyzařuje částice v náhodném množství). Fyzikální generátory se ale málo používají, jelikož mohou být v závislosti na vnějších vlivech nestabilní, posloupnost čísel se nedá zopakovat a chování se může lišit v důsledku výrobních tolerancí.

Generátory pseudonáhodných čísel[editovat | editovat zdroj]

Nejpoužívanějším generátorem pseudonáhodných čísel je tzv. kongruentní generátor. Posloupnost lze vyjádřit vztahem:

X_{n+1}=(aX_n+c) mod\ m

kde mod m je celočíselný zbytek po dělení a, c, m jsou zvolené konstanty

Generovaná čísla jsou diskrétní z intervalu <0,m). Kvalita generovaných čísel závisí na zvolených konstantách, čím vyšší hodnoty, tím „kvalitnější“ generovaná čísla jsou, ale rychlost generování klesá.

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. FABIAN, František; KLUIBER, Zdeněk. Praha : PROSPEKTRUM s.r.o., 1998. ISBN 80-7175-058-1. Kapitola 1.2, s. 13. (česky) 
  2. FABIAN, František; KLUIBER, Zdeněk. Praha : PROSPEKTRUM s.r.o., 1998. ISBN 80-7175-058-1. Kapitola 1.2, s. 14. (česky) 
  3. Hradec Králové: Univerzita Hradec Králové, Pedagogická fakulta, Katedra fyziky a informatiky, [cit. 2010-01-20]. Dostupné online. (česky) 
  4. a b FABIAN, František; KLUIBER, Zdeněk. Metoda Monte Carlo a možnosti jejího uplatnění. Praha : PROSPEKTRUM s.r.o., 1998. ISBN 80-7175-058-1. Kapitola 1.3, s. 152. (česky) 
  5. TESAŘ, Jiří; BARTOŠ, Petr. České Budějovice: Pedagogická fakulta Jihočeské univerzity v Č. Budějovicích, Katedra fyziky, [cit. 2010-01-20]. Dostupné online. (česky) 
  6. KUČERA, Radan. Brno: Ústav matematiky a statistiky Přírodovědecké fakulty Masarykovy univerzity, 20.2.2006, [cit. 2010-01-20]. Dostupné online. (česky) 
  7. FABIAN, František; KLUIBER, Zdeněk. Praha : PROSPEKTRUM s.r.o., 1998. ISBN 80-7175-058-1. Kapitola 10, s. 116. (česky) 
  8. OSTROUŠKO, Viktorie. Ing. [online]. Ekonimika a management, [cit. 2010-01-20]. Dostupné online. (česky) 
  9. a b HABIBALLA, Hashim. Ostrava: Ostravská univerzita, Přírodovědecká fakulta, [cit. 2010-01-20]. Dostupné online. (česky) 
  10. GUŠTAR, Milan. Ostrava: I. ročník celostátní konference SPOLEHLIVOST KONSTRUKCÍ, rev. 15.3.2000, [cit. 2010-01-20]. Dostupné online. (česky) 

Literatura[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]