Metoda Monte Carlo

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
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

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[edytuj | edytuj kod]

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

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

  1. Losuje się punktów z opisanego na tym kole kwadratu – dla koła o 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 wszystkich prób było trafionych, zatem pole koła wynosi:

gdzie jest polem kwadratu opisanego na tym kole (dla  : ).

Dokładność i poprawność metody Monte Carlo[edytuj | edytuj kod]

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.

Przykład obliczania liczby π metodą Monte Carlo w języku C++11[edytuj | edytuj kod]

#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;    // 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;
}

Bibliografia[edytuj | edytuj kod]