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) – metoda 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 tej metodzie 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}\leqslant 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 tym 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. Przykładowo całkowanie tą metodą jest używane w przypadkach, kiedy szybkość otrzymania wyniku jest ważniejsza od jego dokładności (np. obliczenia inżynierskie).

Poprawność metody Monte Carlo w przypadku obliczania 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.

Zastosowanie w biznesie

Metoda bywa stosowana również w biznesie, a szczególnie w zarządzaniu projektami do zarządzania ryzykiem. Pozwala ocenić przy jakim czasie trwania projektu lub wysokości budżetu, osiągnie się określony poziom ryzykowności.

Przykład obliczania liczby π metodą Monte Carlo w języku C++ (standard: C++11)

#include <iostream>
#include <random>

using std::cout;
using std::cin;
using std::endl;

int main()
{
    // Generator liczb losowych
    std::mt19937 gen{std::random_device{}()};
    // Rozklad jednorodny na przedziale -1.0 do 1.0
    std::uniform_real_distribution<double> losuj{-1., 1.};

    int punktow_w_kwadracie = 0;// Liczba punktow w kwadracie
    int punktow_w_kole = 0;     // Liczba punktow w kole

    // Liczby punktow mozemy przyjac jako dyskretna forme pola powierzchni,
    // stad, im wiecej punktow zalozymy, tym lepsza dokladnosc liczby pi

    cout << "Podaj liczbe losowanych punktow: ";
    cin >> punktow_w_kwadracie;

    double x, y;
    for(int i{0}; i < punktow_w_kwadracie; ++i)
    {
        x = losuj(gen);
        y = losuj(gen);

        // Sprawdzamy czy wylosowany punkt o wspolrzednych (x, y)
        // znajduje sie w kole o wzorze x^2 + y^2 <= 1
        // Wzor ten okresla kolo wpisane w kwadrat na przedziale
        // x i y = <-1, 1>

        if(x*x + y*y <= 1)
        {
            // Akceptujemy punkty w kole
            ++punktow_w_kole;
        }
    }

    // Wiemy, ze pole powierzchni kola wpisanego w kwadrat o boku 2
    // wynosi dokladnie pi. Stosunek pola tego kola do kwadratu to
    // pi/4. A wiec aby uzyskac przyblizenie liczby pi wystarczy
    // policzyc stosunek punktow_w_kole do punktow_w_kwadracie razy 4

    cout << "Liczba punktow w kole = " << punktow_w_kole << endl;
    cout << "Liczba punktow w kwadracie = " << punktow_w_kwadracie << endl;
    double _PI_ = 4. * punktow_w_kole / punktow_w_kwadracie;
    cout << "Szukana liczba pi = " << _PI_ << endl;
}

Zobacz też

• sekwencyjna metoda Monte Carlo

Bibliografia

• Metropolis, N. (1987). „The beginning of the Monte Carlo method”. Los Alamos Science (1987 Wydanie specjalne dedykowane Stanisławowi Ulamowi): s. 125–130.