Metóda Monte Carlo

Náhoda hrá vo vede významnú úlohu. Mnohé dôležité objavy boli objavené na základe náhodných okolností. Niektoré sú možno iba mytologizáciou skutočnosti napríklad objav Archimedovho zákona a údajný beh nahého Archimeda Syrakúzami vykrikujúceho Heuréka! alebo Pád jablka na hlavu Newtona. Mnohé iné sa určite stali napríklad Flemingov objav penicilínu. Vo všetkých týchto prípadoch však popri náhode bolo dôležité, že príslušný vedec mal adekvátne vedomosti a tvorivú myseľ a tak hoci predtým tisíckam ľudí padli jablká či hrušky na hlavu, až Newton si dal veci do súvisu a prišiel na to, že rovnaká sila udržiava planéty okolo Slnka a Mesiac okolo Zeme, aká pôsobí na padajúce jablko, stovky vedcov mali neumyté misky a iba ich umyli, pričom si nevšimli žiadnu anomáliu až Fleming aj pri umývaní misiek premýšľal. Keď môže byť náhoda alebo omyl čas od času príčinou pokroku, stojí za úvahu, či neskúmať niektoré prírodné javy pomocou využitia náhody.

Už ste sa stretli s tým, že programovacie jazyky zvyknú mať funkciu, ktorá generuje pseudonáhodné čísla.  Dali by sa takto generované čísla využiť pri skúmaní prírodných javov? Podobnú otázku si položili  Stanisław Marcin Ulam a John von Neumann, ktorí sa podieľali na konštrukcii americkej atómovej bomby. V Los Alamos skúmali správanie sa neutrónov, napríklad skúmali koľko neutrónov prejde rôznymi druhmi materiálov. V tom čase vedci nevedeli navrhnúť adekvátnu teóriu. Využitím metódy Monte Carlo,  pomocou vtedajších z dnešného pohľadu primitívnych a pomalých počítačov problém vyriešili.

Predchodcom metódy Monte Carlo bola Buffonova ihla – pomocou hádzania ihly na linajkovaný papier sa experimentálne dalo odhadnúť číslo \pi. Keď vzdialenosť medzi riadkami je rovnako veľká ako dĺžka ihly, dá sa matematicky dokázať, že pravdepodobnosť toho, že ihla pretne linajku je \cfrac{2}{\pi}. Ak ihlu hodíme tisíckrát a zaznamenáme, koľkokrát pretla linajku, môžeme približne odhadnúť hodnotu čísla \pi.

Odhad čísla \pi metódou Monnte Carlo

Nakreslime kruh s priemerom r. Generujme náhodné čísla x a y tak, aby boli z intervalu -r a r. Nakreslime modrý bod, ak súradnice vygenerovaného bodu budú mimo kruh a červený bod, ak budú v kruhu. Keďže obsah kruhu je S_1=\pi\cdot r^2 a obsah štvorca je S_2=(2\cdot r)^2, pravdepodobnosť toho, že vygenerovaný bod padol do kruhu bude p=\cfrac{S_1}{S_2}, potom p=\cfrac{\pi \cdot r^2}{4\cdot r^2} a teda

p=\cfrac{\pi}{4}

\pi=4\cdot p

Ak urobíme dostatočne veľký počet pokusov, to čo nameriame sa veľmi blíži pravdepodobnosti, takže možno číslo \pi odhadnúť ako pomer počtu bodov, ktoré boli v kruhu, ku celkovému vygenerovanému počtu bodov.

\pi\approx\cfrac{4k}{n}, kde k – je počet bodov v kruhu a n – je počet všetkých vygenerovaných bodov.

Chyba výsledku z n pokusov je úmerná \cfrac{1}{\sqrt{n}}.

Úloha: Naprogramujte odhad čísla \pi pomocou vyššie uvedených vzťahov. Pomôcka: Kruh nakreslite inou farbou ako štvorec, potom stačí testovať, akej farby je bod, ktorý ste náhodne vygenerovali. Pokiaľ vygenerované body budete aj kresliť, tak musíte ošetriť prípad, keď bude znova vygenerovaný bod, ktorý už vygenerovaný bol.

Poznámka: Keď som to am naprogramoval tak, ako som napísal v zadaní, odhadnutá hodnota pí bola takmer vždy menšia, než skutočná hodnota. Vždy keď k čomusi podobnému dôjde, treba predpokladať, že v algoritme je nejaká systematická chyba. V našom prípade je chyba spôsobená tým, že nemáme k dispozícii nekonečne veľa bodov, ale obrázok je rastrovaný. Ak by sme ho mnohonásobne zväčšili, zistili by sme, že na obvode kruhu sú „zuby“, chýbajúce zuby sú tou chýbajúcou plochou, takže odhad čísla pí vyjde menší než skutočnosť.

Ošetril som to tak, že testujem, či vzdialenosť vygenerovaného bodu je menšia alebo rovná polomeru kruhu, ak je, bod patrí do kruhu, ak nie je, bod do kruhu nepatrí. Ešte aj v takom prípade dochádza k istej systematickej chybe, lebo generátor Imaginu generuje celé čísla a mali by to byť reálne čísla, ale chyba je výrazne menšia než v predchádzajúcom prípade.

print

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *