Metoda Monte Carlo

Całkowanie metodą Monte-Carlo działa na zasadzie porównywania losowych próbek z wartością funkcji

Błędy całkowania maleją odwrotnie proporcjonalnie do pierwiastka z liczby próbek czyli $1/\sqrt{N}$

Metoda Monte Carlo (MC) jest stosowana do modelowania matematycznego procesów zbyt złożonych (obliczania całek, łańcuchów procesów statystycznych), aby można było przewidzieć ich wyniki za pomocą podejścia analitycznego. Istotną rolę w metodzie MC odgrywa losowanie (wybór przypadkowy) wielkości charakteryzujących proces, przy czym losowanie dokonywane jest zgodnie z rozkładem, który musi być znany.

Typowym przykładem może być modelowanie wyniku zderzenia cząstki o wysokiej energii z jądrem złożonym, gdzie każdy akt zderzenia elementarnego (z pojedynczym nukleonem jądra) modelowany jest oddzielnie poprzez losowanie liczby, rodzaju, kąta emisji, energii itp. cząstek wtórnych emitowanych w wyniku takiego zderzenia. Następnym etapem jest modelowanie losu każdej z cząstek wtórnych (w wyniku kolejnego losowania prawdopodobieństwa oddziaływania lub wyjścia z jądra). Kontynuując taką procedurę można otrzymać pełny opis "sztucznie generowanego" procesu złożonego. Po zebraniu dostatecznie dużej liczby takich informacji można zestawić ich charakterystyki z obserwowanymi wynikami doświadczalnymi, potwierdzając lub negując słuszność poczynionych w całej procedurze założeń.

Metoda została opracowana i pierwszy raz zastosowana przez Stanisława Ulama.

Przykład całkowania metodą Monte Carlo

Metodą Monte Carlo można obliczyć pole figury zdefiniowanej nierównością:

$x^2 +y^2 \le R^2$

czyli koła o promieniu R i środku w punkcie (0,0).

1. Losuje się n punktów z opisanego na tym kole kwadratu - dla koła o R = 1 współrzędne wierzchołków (-1,-1), (-1,1), (1,1), (1,-1).
2. Po wylosowaniu każdego z tych punktów trzeba sprawdzić, czy jego współrzędne spełniają powyższą nierówność (tj. czy punkt należy do koła).

Wynikiem losowania jest informacja, że z n wszystkich prób k było trafionych, zatem pole koła wynosi

$P_k=P\ \frac {k}{n}$

gdzie P jest polem kwadratu opisanego na kole (Dla R = 1 : P = 4).

Dokładność i poprawność metody Monte Carlo

Dokładność wyniku uzyskanego tą metodą jest zależna od liczby sprawdzeń i jakości użytego generatora liczb pseudolosowych. Zwiększanie liczby prób nie zawsze zwiększa dokładność wyniku, ponieważ generator liczb pseudolosowych ma skończenie wiele liczb losowych w cyklu.

Ta metoda całkowania jest używana w przypadkach, kiedy szybkość otrzymania wyniku jest ważniejsza od jego dokładności (np. obliczenia inżynierskie).

Poprawność metody Monte Carlo w przypadku liczenia pól lub całek można udowodnić stosując twierdzenie Picka (lub jego wielowymiarowe uogólnienia) do najlepszego wielokąta wpisanego w figurę, której pole chcemy obliczyć w przybliżeniu tzw. kryształu wirtualnego, tzn. regularnej siatki punktów o stałej sieci równej średniej odległości między wylosowanymi punktami. W nieskończonej granicy tych wielokątów i siatek metoda jest dokładna dla dowolnego kształtu.

Przykład obliczania liczby pi metodą Monte Carlo w języku C++

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>
 
using namespace std;
 
int main()
{
     srand(time(NULL)); //zainicjalizowanie maszyny generujacej liczby losowe
     int n;
     int nk = 0;
     double x,y;
     float s;
 
     cout << "Podaj liczbe losowanych pkt:" << endl;
     cin >> n;
 
     for(int i = 1; i <= n; i++)
     {           
         x = ((double)rand() / (RAND_MAX))*2 - 1;
         y = ((double)rand() / (RAND_MAX))*2 - 1;
         if(x*x + y*y <= 1)
         {
             nk++;
         }
     }
 
     cout << "Liczba pkt. w kole wynosi: " << nk << endl;
     cout << "Liczba pkt. w kwadracie wynosi: " << n << endl;
     s = 4 * (double)nk / n;
     cout << "Liczba pi wynosi: " << s;
}