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í x1…xn. 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. 

thumb|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ť 1012 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
* 
* O metóde Monte Carlo a možnostiach jej aplikácií 

Kategória:Numerická matematika
Kategória:Simulácia