fbpx

Metoda Monte Carlo to temat dla mnie ważny, ponieważ prace nad nim były jednym z przełomów w mojej karierze zawodowej. Rozwiązywanie zadań z metod numerycznych są dla mnie fascynujące i utwierdzają mnie w przekonaniu, że matematyka w programowaniu ma sens (nie samym CRUD-em programista żyje). Jednym z takich zagadnień dotyczących całkowania się zajmiemy. Chodzi oczywiście o tytułową metodę Monte Carlo. Postaram się wyjaśnić następujące kwestie:

  • Czym w ogóle jest metoda MC?
  • Jakie może mieć zastosowania?
  • Jak ją zaimplementować?
  • Co ma wspólnego liczba PI z metodą MC?
  • Czym jest igła Buffona?

Chcę zaznaczyć, że temat jest poważny i ciężki. Wiele osób ma awersję słysząc magiczne słowo matematyka. Uważam, że dziedzina ta ma swoje piękne strony i postaram się ją trochę pokazać w tym wpisie. 🙂

Słowem wstępu

Metoda Monte Carlo to zagadnienie, nad którym pracował jednocześnie zespół węgierskiego matematyka Johna von Neumanna oraz polski matematyk Stanisław Ulam. W różnych definicjach spotkać się można raz z jednym, raz z drugim matematykiem i ciężko stwierdzić, kto w pierwszej kolejności opracował i wykorzystał do obliczeń metodę MC. Pierwsze oficjalne wzmianki pojawiły się w roku 1949 w artykule zatytułowanym „The Monte Carlo method”.

Wciąż jest dla mnie źródłem nieustającego zdziwienia, że kilka znaków nagryzmolonych na tablicy lub na kartce papieru może zmienić bieg ludzkich spraw.

Stanisław ulam

Metoda Monte Carlo swoją nazwę zawdzięcza nazwie miasta w księstwie Monako. Miasto to słynie z gier hazardowych, które cechują się losowym charakterem. Główną ideą metody jest rozwiązywanie pewnych problemów matematycznych za pomocą losowych wyborów. Podstawy teoretyczne były znane od dawna jednak możliwości stosowania metody MC nabrały sensu wraz z rozwojem komputerów (dlatego też postanowiłem zmierzyć się z tematem).

Przykład ogólny

Aby zobrazować sposób, w jaki działa metoda MC posłużę się rysunkiem. Zadaniem będzie obliczenie pola figury S, która to figura znajduje się wewnątrz kwadratu o boku 1. Warto wspomnieć, że figura może przybrać dowolny kształt, ważne by była wewnątrz kwadratu o boku a. Mając taką konstrukcję geometryczną kolejnym krokiem będzie wylosowanie N punktów, dowolnie rozmieszczonych wewnątrz kwadratu. Na przykład rysunek poniżej zawiera 41 takich punktów (czerwone kropki). Mając informację o ilości kropek znajdujących się wewnątrz figury S (kropek tych jest dokładnie 25) mamy możliwość oszacować z pewnym prawdopodobieństwem pole figury S. Pole takie wyliczamy mnożąc pole powierzchni kwadratu przez ilość punktów wewnątrz figury S i dzieląc otrzymany wynik przez ilość wszystkich kropek. Daje nam to 1 * 25 / 41 = 0,6097. Wiedząc, że dokładne pole figury S wynosi dokładnie 0,65 możemy zauważyć, że wynik bardzo nie odbiega od rzeczywistości i w wielu przypadkach wynik taki będzie zadowalający.

Metoda Monte Carlo - figura S wpisana w kwadrat
Rysunek 1. Figura S wpisana w kwadrat.

Przykład tarczy

Oczywistym jest fakt, że im więcej takich „punktów” umieścimy w kwadracie, tym nasze szacowanie będzie dokładniejsze. Do tego typu obliczeń idealnie nadają się współczesne komputery. Podam jeszcze jeden przykład z błędnym podejściem do szacowania. Wyobrazić można sobie taki eksperyment na podstawie tarczy do gry w popularną barową grę dart. Mając koło wewnątrz kwadratu, po oddaniu dużej ilości rzutów i policzeniu ilości rzutek, które trafiły w koło możemy oszacować jego pole powierzchni. Podejście wydaje się słuszne jednak jest jeszcze jeden aspekt. Chodzi mianowicie o „równomiernie rozmieszczone” punktów. Podczas gry w dart, trafiając na dobrego gracza możemy mieć problem z obliczeniami, ponieważ osoba taka może rzucać w tarczę wszystkie swoje rzutki. Pomiar wtedy będzie błędny, bo zasugeruje, że okrąg ma takie samo pole jak kwadrat. Patrz rysunek poniżej.

Metoda Monte Carlo - tarcza z trafionymi rzutami przez profesjonalnego gracza.
Rysunek 2. Tarcza z trafionymi rzutami przez profesjonalnego gracza.

Metoda Monte Carlo i liczba π

Jednym z ciekawszych zastosowań metody Monte Carlo jest próba oszacowania przybliżonej wartości liczby Pi, czyli policzenia ilość punktów, które trafiły w okrąg wpisany w kwadrat. Wydaje się to prostym zadaniem jednak aby to zrobić potrzebujemy pewnych informacji na temat pola powierzchni koła. Po pierwsze zobacz rysunek poniżej. Widać tam kwadrat o boku długości a = 2 oraz koło, które posiada taką samą średnicę. Wynika z tego, że jego promień r = 1. Teraz wystarczy przypomnieć sobie jak wygląda wzór na pole koła:

Pole koła = π * r2

Gdy pod r podstawione zostanie 1, to pole koła wyniesie π. Logicznie rzecz ujmując, im więcej pomiarów (punktów) zostanie wykorzystanych do oszacowania pola powierzchni koła tym dokładniejszy otrzymamy wynik. Wystarczy zgodnie z regułą opisywaną na początku artykułu zebrać wszystkie punkty, które trafiły w okrąg, przemnożyć te punkty przez pole kwadratu i na końcu podzielić wynik przez ilość wszystkich pomiarów, które zostały użyte.

Metoda Monte Carlo - Okrąg o promieniu 1 wpisany w kwadrat o boku 2
Rysunek 3. Okrąg o promieniu 1 wpisany w kwadrat o boku 2.

Implementacja

Poniższy kod pozwoli nam w przybliżeniu przedstawić wartość π. Na wejście programu prosimy użytkownika o wprowadzenie ilości losowych punktów (linie 9-10). W kolejnej linii deklarujemy zmienną int, która przechowa sumę punktów, które trafiły w okrąg. Wartości valX oraz valY przechowywać będą wylosowane liczby z zakresu od 0 do 2 i reprezentować odpowiednio pozycję na osi X, oraz osi Y w układzie kartezjańskim. Dwie następne linie również dotyczą deklaracji. Linia 13 to obiekt Random, który dalej będzie używany do wywołania metody NextDouble. Metoda będzie odpowiedzialna za wylosowanie randomowej wartości. ReturnVal przechowa natomiast wynik.

Główne ciało metody rozpoczyna się instrukcją warunkową, która sprawdza, czy liczba losowych punktów nie jest mniejsza od 3. Gdyby była to oznacza, że szacunek byłby zbyt niedokładny i prezentowany komunikat, że nie jest możliwe wyznaczenie przybliżonej wartości PI (linie 16-17). Gdy program przejdzie dalej natrafi na pętle, której zadaniem jest wyznaczenie wartości valX oraz valY z przedziału od 0 do 2 (funkcja rand.NextDouble() zwraca wartości od 0 do 1, dlatego dodatkowo następuje mnożenie razy 2). Czas na gościa głównego programu — jest nim równanie okręgu. Jeżeli pamiętasz ze szkoły średniej równanie okręgu ma następujący wzór:

(𝑥 – 𝑎 )2 + (𝑦 − 𝑏)2 = 𝑟2

We wzorze a oraz b to 1. Promień tego koła również wynosi 1. X oraz Y to odpowiednio wartości valX oraz valY. Już teraz wzór nabiera sensu i można go przedstawić w następującej postaci:

Odwzorowany wzór pod pierwiastkiem jest widoczny w linii 24. Sprawdzamy jeszcze zgodnie z równaniem, czy wyznaczona wartość jest mniejsza bądź równa 1. Jeżeli tak, to wiadome jest, że punkt leży wewnątrz okręgu.

Podsumowując

Po tym, jak w pętli przeanalizowana zostanie podana na wejściu ilość punktów następuje obliczenie wartości końcowej za pomocą wzoru prezentowanego wyżej. Pole kwadratu, na którym oparte jest koło (wynosi w tym przypadku 4) zostaje przemnożone przez sumę ilości punktów w środku koła, a następnie podzielone przez ilość wszystkich wylosowanych punktów.

Przy odpowiednio dużej ilości punktów, podanych na wejściu program pokaże bardzo dokładne przybliżenie liczbę PI do kilku cyfr po przecinku. Na przykład szacunki dla 100000 punktów są następujące:

  • 3.15476
  • 3.13836
  • 3.13904

Jak widać, przybliżenie może nie jest mega dokładne jednak pokazuje możliwości, jakie ma metoda Monte Carlo.

using System;

namespace MC
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Podaj liczbę losowych punktów: ");
            int counter = int.Parse(Console.ReadLine());
            int inTheMiddle = 0;
            double valX, valY;
            Random rand = new Random();
            string returnVal;

            if (counter < 2)
                returnVal = "Nie można wyznaczyć przybliżonej wartości PI";
            else
            {
                for (int i = 0; i < counter; i++)
                {
                    valX = rand.NextDouble() * 2;
                    valY = rand.NextDouble() * 2; 
                    if (Math.Sqrt((valX - 1) * (valX - 1) + (valY - 1) * (valY - 1)) <= 1)
                        inTheMiddle++;
                }

                float returnValFloat = 4 * float.Parse(inTheMiddle.ToString()) / float.Parse(counter.ToString());
                returnVal = returnValFloat .ToString();
            }

            Console.WriteLine("Liczba PI w przybliżeniu wynosi: " + returnVal);

            Console.ReadLine();

        }
    }
}

Czy wiesz, że…

Sama metoda Monte Carlo nie byłaby tak popularna, gdyby nie fakt jej przydatności. Poniżej kilka przykładów zastosowania jej w połączeniu z komputerami:

  • obliczanie całek oznaczonych
  • sprawdzanie jakości i niezawodności produktów, czyli na przykład do oszacowania długości życia żarówki wolframowej
  • systemy obsługi klientów, czyli przepustowość kas w sklepie lub długość oczekiwania na połączenie z infolinią
  • zastosowania w fizyce, czyli rozszczepianie cząstek
  • analiza danych w takich dziedzinach jak finanse

Jednym z ciekawszych zagadnień powiązanych z metodą Monte Carlo jest tak zwany problem igły Buffona, czyli problem polegający na tym, że na pewnej planszy narysowane są linie oddalone od siebie o odległość S. Na planszę upuszczane są igły o długości L (przy założeniu, że długość igły jest mniejsza niż odległość między równoległymi liniami). Eksperyment wykonywany jest poprzez rzut igłą N razy. Następnie liczone jest ile razy igła przecięła równoległą linię. Korzystając ze wzoru (2 * długość igły * ilość wszystkich rzutów) / (odległość między równoległymi liniami * stosunek ilości rzutów przecinających równoległe linie do wszystkich rzutów) pozwala nam oszacować przybliżoną wartość liczby Pi.

Metoda Monte Carlo - losowo rozrzucone igły
Rysunek 3. Losowo rozrzucone igły o długości L na planszy z równoległymi liniami oddalonymi od siebie o S.

Doświadczenie tego typu przedstawiane jest również na filmie poniżej!

 

Metoda Monte Carlo – Podsumowanie

I to już koniec. Temat nie jest łatwy, jednak opracowywanie go sprawiło wiele frajdy. Spędziłem nad nim wiele godzin, kilka wieczorów zarwałem w bibliotece lub na uczelni, jednak uważam, że było warto!

Aktualnie wiem jedno, niektóre tematy są bardzo ubogie w materiały i trzeba głęboko szukać, by wydobyć to, co najlepsze. Tak było właśnie w przypadku tematu związanego z metodą Monte Carlo.

Mam jednak nadzieję, że analiza Ci się spodobała i będziesz pogłębiał wiedzę z tych i podobnych tematów! W kolejnym, czwartym już wpisie coś luźnego, opiszę swoje pomysły na temat zarządzania czasem, czyli dylatacja czasu.

PS. Będę wdzięczny za komentarze pod tym postem!

PS2. Czeka też na Ciebie prezent. Wystarczy, że zapiszesz się na Newsletter poniżej!

PS3. Dołącz do naszej grupy na Facebook!


Subskrybuj

Zapisz się na Newsletter, odbierz NAGRODĘ w postaci 10 omówionych algorytmów pojawiających się w pytaniach podczas REKRUTACJI.

Dodatkowo otrzymuj co niedzielę informacje na temat nowych wpisów, wiadomości ze świata IT i matematyki oraz ciekawych wydarzeniach. Nie przegap i dołącz już dziś do 406 osób!.

Źródła

http://home.agh.edu.pl/~pernach/wyklady/index.php?action=wyklad10_1
http://kft.umcs.lublin.pl/baran/epk/modelowanie/sobol.pdf
http://dotproject.net.pl/node/227
https://analizy.investio.pl/metoda-monte-carlo/
http://mst.mimuw.edu.pl/wyklady/sst/wyklad.pdf
http://zif.wzr.pl/pim/2012_4_1_2.pdf
http://keii.ue.wroc.pl/pracownicy/tb/Bart%C5%82omowicz%20T.%20[2011],%20Symulacja%20Monte%20Carlo%20jako%20narz%C4%99dzie%20prognozowania%20wybranych%20aspekt%C3%B3w%20rynku%20nieruchomo%C5%9Bci,%20W%20Pociecha%20J.%20(red.)%20Modelowanie%20i%20prognozowanie%20zjawisk...,%20UE%20Krak%C3%B3w.pdf
http://www.deltami.edu.pl/temat/matematyka/rachunek_prawdopodobienstwa/2011/02/01/Jak_matematyk_rzuca_igla/
http://coin.wne.uw.edu.pl/~tmostowski/pliki/matlab/matlab7.pdf
http://www.algorytm.org/procedury-numeryczne/calkowanie-numeryczne-metoda-monte-carlo-i.html
http://prac.im.pwr.edu.pl/~agniesz/rachunek_prawd_MAEW104/Monte_Carlo_pole_obszaru_prezentacja_1.pdf
https://eduinf.waw.pl/inf/alg/004_int/0005.php
http://www.if.pw.edu.pl/~agatka/numeryczne/wyklad_11.pdf
https://www.ue.katowice.pl/fileadmin/_migrated/content_uploads/10_02.pdf
https://mfiles.pl/pl/index.php/Metoda_Monte_Carlo 
http://home.agh.edu.pl/~chwiej/mn/mc_2015.pdf
Autor

👨‍💻 .NET and Python programming passionate 🏦 Digtial Banking Solutions 🎓 Student 📊 Psychology 📚 Bookworm 🏠 Warsaw

6 komentarzy

  1. Dla mnie nowość! Nie słyszam o tym wcześniej mimo, że skończyłam Politechnikę! Ciekawy blog, fajnie, że na niego trafiłam, będę odwiedzać Cię wcześniej 🙂

  2. Rysunek 3 wskazuje na to, że środek okręgu i kwadratu zawierają się w początku układu współrzędnych. W równaniu okręgu a,b to współrzędne środka, zatem nie ma mowy żeby a i b były równe 1. (chyba że czegoś nie doczytałem)

    „Wystarczy zgodnie z regułą opisywaną na początku artykułu zebrać wszystkie punkty, które trafiły w okrąg, przemnożyć te punkty przez pole kwadratu i na końcu podzielić wynik przez ilość wszystkich pomiarów, które zostały użyte.”
    Oczywiście rozumiem, że to pewien skrót myślowy, niemniej – jeśli już (potocznie) to punkty trafiły w KOŁO, nie okrąg. To takie upierdliwe uwagi.

    Prócz tego artykuł bardzo fajnie napisany, pisz dalej 😀

    • Dziękuję za uwagi, staram się nie stosować skrótów myślowych. 🙂 dziękuję za uwagi, wprowadzę stosowne sprostowania!

      Pozdrawiam, Mateusz Rus.

    • Świetny blog !!! Ciekawe z punktu widzenia matematyka tematy. Cieszę się że dowodzisz na każdym kroku, że matematyka ma także zastosowanie w praktyce a nie jest tylko suchą teorią. Bardzo dobrze czyta się kolejne wpisy mimo że materia nie jest trywialna.
      Aha i jeszcze jedno – materiały w cotygodniowym mailingu trzymają wysoki poziom. Pozdrawiam

Napisz komentarz

This site uses Akismet to reduce spam. Learn how your comment data is processed.