Metóda Monte Carlo

Metóda Monte Carlo je trieda algoritmov na simuláciu systémov. Ide o stochastické metódy používajúce náhodné alebo pseudonáhodné čísla. Typicky sú využívané na výpočet integrálov, najmä viacrozmerných, kde bežné metódy nie sú efektívne.

Metóda Monte Carlo má široké využitie od simulácie experimentov, cez počítanie určitých integrálov, až po riešenie diferenciálnych rovníc. Základná myšlienka metódy je veľmi jednoduchá: chceme určiť strednú hodnotu veličiny, ktorá je výsledkom náhodného deja. Vytvorí sa počítačový model tohto deja a po prebehnutí dostatočného množstva simulácií sa môžu dáta spracovať klasickými štatistickými metódami, napríklad určiť priemer a smerodajnú odchýlku.

Metóda je nazvaná podľa Monte Carla známeho svojimi kasínami a najmä ruletou. Termín prvýkrát použili fyzici v roku 1940 pracujúci na zostrojení americkej atómovej bomby.

Rozlišujú sa dva varianty metódy Monte Carlo, analógový a neanalógový model.

Analógový model

Musíme vedieť modelovať celú situáciu na počítači, to znamená napríklad poznať všetky pravdepodobnostné rozloženia skúmaných javov a fyzikálne zákonitosti, ktorými sa riadia. Prevedením tejto simulácie získame výsledok, realizáciu akejsi náhodnej veličiny $\xi$. Túto simuláciu spustíme n-krát a získame súbor histórií x₁…x_n. Odhad strednej hodnoty $\xi$ sa určí takto

$\xi \approx {\frac {1}{N}}\sum _{i=1}^{N}x_{i}$

a smerodajná odchýlka sa určí jednoducho ako

$\sigma ={\sqrt {\frac {\sum _{i=1}^{n}({\bar {x}}-x_{i})^{2}}{n-1}}}$.

Neanalógový model

Tak sa nazýva prípad, keď pri výpočte nepoužívame model reálneho deja. Napríklad výpočet určitého integrálu, prípadne obsahu ohraničeného útvaru.

Integrácia metódou Monte Carlo

Hlavnou výhodou integrácie touto metódou je jej jednoduchosť. Na druhej strane, presnost výpočtu je veľmi malá, obzvlášť ak má integrovaná funkcia úzke maximá. Ak potrebujeme presný výsledok, je výhodnejšie použiť iné metódy.

Ak určíme hodnotu funkcie f v N náhodných bodoch ležiacich v integračnej oblasti V, potom platí vzťah

$\int _{V}f(\mathbf {x} )dV\approx Vf(\mathbf {x} )\pm {\frac {\sigma V}{\sqrt {n}}}$

$\sigma ={\sqrt {\frac {\sum _{i=1}^{n}({\overline {y}}-y_{i})^{2}}{n}}}$

kde x označuje náhodný bod v oblasti V, ${\bar {y}}$ označuje priemer funkčných hodnôt a $y_{i}$ jednotlivé výsledky.

Integrovanie oblasti V v oblasti V'

Ak budeme tento integrál počítať metódou Monte Carlo, musíme oblasť V uzavrieť do čo najmenšej oblasti V'. Prípadne oblasť V rozdeliť na viac častí a integrovať ich samostatne. Teraz zavedieme funkcie${\tilde {f}}$ takto

${\tilde {f}}(\mathbf {x} )={\begin{cases}0&\mathbf {x} \notin V\\f(\mathbf {x} )&\mathbf {x} \in V\end{cases}}$

potom vygenerujeme N náhodných bodov ležiacich v oblasti V' a približnú hodnotu integrálu určíme ako

$I\approx {\frac {V'}{N}}\sum _{i=1}^{N}f'(\mathbf {x} )$

a smerodajná odchýlka sa určí analogicky ako v predchádzajúcom prípade.

Presnosť metódy Monte Carlo

Na odhad chyby výsledku získaného metódou Monte Carlo sa väčšinou používa stredná kvadratická chyba aritmetického priemeru. Chyba výsledku získaného pomocou n histórií je úmerná $1/{\sqrt {n}}$. Takže, aby sa zlepšil výsledok o jeden rád, musí sa počet histórií zvýšiť aspoň o dva rády. Aby sme získali výsledok s presnosťou na 6 desatinných miest, musíme získať 10¹² histórií.

Ďalšie použitia metódy

• Buffonova úloha
• projekt Manhattan
• Rabin-Millerov algoritmus – test prvočíselnosti

Pozri aj

• Genetické algoritmy – ďalšia skupina numerických metód používajucich náhodné čísla.

Externé odkazy

• Tento článok je čiastočný alebo úplný preklad článku metoda Monte Carlo na českej Wikipédii (číslo revízie nebolo určené).
• O metóde Monte Carlo a možnostiach jej aplikácií