Metoda Monte Carlo

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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) 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[edytuj | edytuj kod]

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

,

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:

,

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

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 1
    // wynosi dokladnie pi/4. Stosunek pola tego kola do kwadratu to
    // tez 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]