Metoda Monte Carlo

Metoda Monte Carlo została opracowana przez Stanisława UlamaStanisław UlamStanisława Ulama. Wykorzystano ją podczas pracy nad bombą atomową do procesu symulowania rozpadu cząsteczek. Naukowcy nie potrafili zastosować do tych obliczeń klasycznych modeli matematycznych, postanowili więc wykorzystać losową symulację przeprowadzoną za pomocą komputerów.

Terminem Monte Carlo określamy wszystkie metody numeryczne, które wykorzystują wybór przypadkowy (losowanie) wielkości charakteryzujących modelowany proces, przy czym losowanie przeprowadzane jest zgodnie ze znanym rozkładem.

Wyznaczanie powierzchni koła metodą Monte Carlo

Przeprowadźmy eksperyment myślowy. Załóżmy, że nie znamy wzoru na pole koła ani tym bardziej przybliżonej wartości liczby $\pi$. Wyobraźmy sobie, że mamy kwadratową kartkę. Rysujemy na niej koło, które jest styczne do każdego boku kwadratu lub wpisujemy koło w kwadrat. Następnie zaczynamy rzucać ołówkiem w losowe miejsca na kartce. Notujemy, ile rzutów oddaliśmy. W momencie, gdy ołówek narysuje punkt wewnątrz koła, zapisujemy zdarzenie jako trafienie.

Podejście to przedstawiono na poniższym rysunku. Trafione w koło rzuty ołówkiem zaznaczono kolorem ciemnozielonym, a nietrafione – ciemnoczerwonym.

RPly2T8C21h4b

Ilustracja przedstawia różowy kwadrat, w który wpisane jest koło. Na zielonkawym tle koła jest osiem zielonych kropek. Na tle kwadratu w pobliżu koła, po przeciwnych stronach, jest po jednej czerwonej kropce.

Po pewnym czasie stosunek liczby trafień do liczby rzutów powinien zbliżać się do stosunku pola koła do pola kartki, wówczas:

Dalsze oszacowanie pola koła jest bardzo proste. Pozostało nam obliczyć powierzchnię kartki. Użyjemy do tego wzoru na pole kwadratu i podstawimy do obliczeń. Niech długość boku kwadratu wynosi $a$:

Wyznaczanie liczby πpi metodą Monte Carlo

W poprzednim eksperymencie wyznaczyliśmy pole koła, zakładając, że nie znamy wzoru. Teraz przyszła pora na założenie, że znamy wzór na pole koła, ale nie dysponujemy przybliżeniem liczby $\pi$. Przypomnijmy wzór na pole koła:

Ponieważ koło jest wpisane w kwadrat o boku $a$:

RxesWr4EyeBKv

lustracja przedstawia różowy kwadrat, w który wpisane jest jasnozielone koło. Bok kwadratu oznaczono pionową strzałką i literą a. Promień koła oznaczono jako a/2.

korzystamy z równania:

by wyznaczyć wartość liczby $\pi$:

W tym momencie możemy zauważyć, że wartość liczby $\pi$ nie zależy od długości boku kwadratu ani od promienia koła.

Pojawia się pytanie, w jaki sposób przeprowadzić symulację za pomocą komputera. Skorzystajmy z nierówności opisującej koło o środku w punkcie $(a,b)$ i promieniu $r$:

W celu wyznaczenia liczby $\pi$ wystarczy przyjąć dowolny kwadrat, losować na nim dowolny punkt oraz w odpowiedni sposób – za pomocą nierówności opisującej koło – sprawdzać, czy trafiliśmy do wnętrza koła.

W dalszej części materiału symulację przeprowadzamy w kartezjańskim układzie współrzędnych. Wybieramy kwadrat o boku 2 ze środkiem w punkcie $(0,0)$. Rozwiązanie zapisane za pomocą pseudokodu może przedstawiać się następująco:

liczbaRzutow ← 10000
liczbaTrafien ← 0

dla i = 1, 2, ..., liczbaRzutow wykonuj:
	x ← 2 * losuj() - 1
    y ← 2 * losuj() - 1
    
    jeżeli x * x + y * y <= 1:
    	liczbaTrafien ← liczbaTrafien + 1

przyblizona_liczba_pi ← 4 * (liczbaTrafien / liczbaRzutow)

wyświetl przyblizona_liczba_pi

Zakładamy, że funkcja losuj() losuje jednakowo prawdopodobne liczby z zakresu $⟨0,1⟩$.

Dokładność wyniku

Zastanówmy się, od czego zależy dokładność osiągniętego wyniku przy użyciu metody Monte Carlo. Możemy dojść do wniosku, że im większa liczba losowanych punktów, tym dokładniejszy wynik. Jednak nie jest to jedyny czynnik, który ma na to wpływ. Liczby losowe w komputerze są bowiem wyznaczane za pomocą generatora liczb pseudolosowychgenerator liczb pseudolosowychgeneratora liczb pseudolosowych. Proces zupełnej losowości jest niemożliwy do zaimplementowania. Pamiętajmy jednak, że dysponując idealnym generatorem liczb losowych, można założyć, iż statystyczna dokładność metody Monte Carlo rośnie wraz ze wzrostem liczby losowań.

Sprawdźmy zatem, w jaki sposób może wyglądać wykres zależności błędu od liczby wykonanych losowań. Jako błąd przyjmujemy wartość bezwzględną różnicy pomiędzy przybliżeniem liczby $\pi$ wyznaczonej metodą Monte Carlo, a wartością, którą podaje najdokładniejsze przybliżenie możliwe do przechowania w zmiennej typu zmiennoprzecinkowego. W celu poprawnej wizualizacji wyniku oś x (liczbę losowań) przedstawiono w skali logarytmicznejskala logarytmicznaskali logarytmicznej. Intuicyjnie możemy przypuszczać, że na wykresie będą występowały liczne skoki z uwagi na losowania, które mogą odstawać od przewidywanych. W ostateczności jednak wartość błędu powinna być coraz mniejsza.

R1hfuu2TdZfYs

Ilustracja przedstawia wykres. Oś pozioma opisana jest jako: ilość losowań, a oś pionowa jako: Błąd. Linia na wykresie ma trend malejący - od wartości nieco powyżej 0,8 na osi błędów i 10 do potęgi zerowej na osi liczby losowań krzywa spada gwałtownie do wartości około 0,1 na osi błędów i 10 do potęgi 0,7 na osi losowań. Następnie nieco pnie się do góry, po czym znowu spada. Od wartości bliskiej zera na osi błędów i od liczby losowań dziesięć po potęgi drugiej krzywa stabilizuje się - ma liczne wahania, ale w obrębie podobnych współrzędnych. Przy liczbie losowań dziesięć do potęgi piątej i wartości zero na osi Y krzywa staje się niemal prostą linią, bez odchyleń.

Wykres potwierdza przypuszczenia intuicyjne. Łatwo zauważyć, że metoda nie jest stabilna – czasem następuje skok w górę lub w dół, jednak ostatecznie widać, że wartość błędu maleje.

Ukryte piękno liczby $\pi$

$62831853071796$ — to liczba cyfr po przecinku dziesiętnego rozwinięcia liczby $\pi$(znanych ludzkości na dzień powstania tego e‑materiału). Wynik ten został osiągnięty dzięki programowi y‑cruncher. Program pracował przez 108 dni. Niewykluczone, że w obecnym momencie jakiś śmiałek próbuje pobić ten rekord.

Zastanawiające może być, ile tak naprawdę powinniśmy znać cyfr rozwinięcia dziesiętnego liczby $\pi$. Nikt przecież nie będzie używał wymienionego wyżej rekordu, aby obliczyć liczbę cegieł potrzebnych do zbudowania okrągłej studni. Okazuje się, że do wyliczenia obwodu znanego nam wszechświata z dokładnością do wielkości 1 atomu, potrzeba tylko 39 cyfr dziesiętnych liczby $\pi$. Rozwinięcie to wygląda następująco:

Warto również spojrzeć na przybliżenia historyczne. Pierwsze wzmianki o liczbie $\pi$ sięgają czasów starożytnej Babilonii (1900‑1700 p.n.e.). Na odnalezionej z tego okresu kamiennej tablicy pojawia się opis obwodu koła o średnicy $1$, który wynosił $3.125$. Ponieważ wzór na obwód koła to liczba $\pi$ pomnożona przez długość średnicy, liczba $3.125$ to jedno z pierwszych odnalezionych na kartach historii przybliżeń liczby $\pi$.

Znacznie mniej dokładne przybliżenie możemy znaleźć w Biblii:

Sprawdźmy, ile według tego fragmentu wynosi liczba $\pi$. Oto wzór na obwód koła o średnicy $d$:

Dokonując przekształcenia, otrzymujemy wzór na $\pi$:

Zatem według przytoczonego fragmentu:

Ciekawym zbiegiem okoliczności jest występowanie w rozwinięciu dziesiętnym liczby $\pi$ po przecinku dwóch kolejnych liczb: 14 oraz 15. Fakt ten pozwolił na ustalenie adekwatnego na święto liczby $\pi$ miejsca w kalendarzu — jest to noc z 14 na 15 marca. Data ta może być zapisana w amerykańskim systemie jako 3.14‑15, co stanowi całkiem przyzwoite przybliżenie liczby $\pi$.

Słownik