Twitter: @grzegg
Kategoria: java, Tagi: - - - - - .

Java [22] – Zadania: obliczanie wartości π metodą Monte Carlo i na inne sposoby

Tym razem zadania dotyczące obliczania wartości π. Najpierw spróbujemy użyć metody Monte Carlo a następnie bardziej klasycznych (i efektywnych) sposobów.

Zadanie 1: Obliczanie wartości π metodą Monte-Carlo

Czasem badając jakieś zjawisko nie jesteśmy w stanie po prostu wyliczyć wyniku. Na przykład nie znamy odpowiednich wzorów lub badany proces jest zbyt skomplikowany. W takich przypadkach z pomocą przychodzi metoda Monte Carlo. Jej twórcą jest, wspomniany wcześniej przy okazji automatów komórkowych, Stanisław Ulam. Nazwa, pochodzi od znanej dzielnicy Monako, dawniej będącej symbolem hazardu (dzisiaj raczej jest nim Las Vegas). Skoro hazard, to przypadek i prawdopodobieństwo. W końcu badania nad prawdopodobieństwem rozpoczęły się właśnie od analizy gier hazardowych. W ten sposób dochodzimy do sedna omawianej metody. Opiera się ona bowiem o losowanie wartości istotnych dla badanego zjawiska/obiektu/procesu w oparciu o znany rozkład tych wartości. Czyli, w uproszczeniu, tworzymy jakąś symulacje w której generujemy „przypadkowe” zdarzenia, których prawdopodobieństwo powinno możliwie odpowiadać występującym w rzeczywistości a następnie obserwujemy i analizujemy otrzymane wyniki.

Do klasycznych przykładów możliwego zastosowania metody Monte Carlo należy obliczanie wartości π. Oczywiście znane są dokładniejsze i bardziej wydajne metody wyliczenia wartości tej stałej, do czego zresztą jeszcze wrócimy. Na razie zaprzęgniemy do pracy przypadek.

Zacznijmy od prostego rysunku koła o promieniu r wpisanego w w kwadrat:


Skoro promień koła wynosi r to bok kwadratu wynosi 2 r. Zatem wzory na pola obu figur będą wyglądać następująco:

Pole koła:

Pole kwadratu:

Stosunek pól obu figur możemy zapisać następująco:

Czyli:

Z czego wynika, że wartość π wynosi:

Tak więc, znając stosunek obu pól można wyznaczyć wartość π. Jak jednak go wyznaczyć używając zdarzeń losowych?

Wyobraźmy sobie, że nasz rysunek używamy jako tarczy strzeleckiej. Nie staramy się jednak strzelać w jakiś konkretny punkt, na przykład w środek, ale w jakiekolwiek, przypadkowo wybrane miejsce. Po jakimś czasie nasza tarcza mogłaby wyglądać na przykład tak:


Teraz dochodzimy do sedna. Jeśli strzały są przypadkowe to stosunek liczby trafień w obrębie koła do stosunku wszystkich trafień (czyli wewnątrz kwadratu) powinien odpowiadać stosunkowi pól obu figur.

Teraz przejdźmy do projektowania programu.
Z powyższych rozważań wynika, że program powinien:

  1. Zasymulować określoną liczbę „strzałów”, czyli wygenerować „punkty” mieszczące się w „wirtualnym kwadracie”,
  2. Następnie sprawdzić ile z punktów mieści się w obrębie „wirtualnego koła”,
  3. Obliczyć stosunek punktów mieszczących się w kole do wszystkich
  4. Obliczyć wartość π mnożąc wyliczony stosunek przez 4.

Z powyższych punktów dwa ostatnie są trywialne, natomiast pierwsze dwa mogą sprawić problemy początkującemu programiście.
Co to właściwie znaczy, że program powinien wygenerować „punkty”? Można to rozwiązać w ten sposób, że losujemy dwie liczby o wartości od 0 do długości boku kwadratu, które będą odpowiadały współrzędnym x i y.
Następnie trzeba sprawdzić czy punkt o wylosowanych współrzędnych mieści się w obrębie koła. Można tu wykorzystać wzór wykorzystywany w definicji okręgu, wg. której okrąg to zbiór punktów (x, y) spełniających równość:


Gdzie: x0 i y0 to współrzędne środka okręgu.

Ponieważ środek okręgu możemy ustalić w punkcie 0,0 układu współrzędnych, wzór można uprościć:


Nas jednak interesują punkty znajdujące się także wewnątrz okręgu, czyli w polu koła. Te punkty spełniają warunek:


Zauważ, że jeśli mówimy o stosunku pola koła i kwadratu, to będzie on taki sam dla ćwiartek obu figur:


Takie rozwiązanie będzie łatwiejsze do zaiplementowania, zwłaszcza jeśli przyjmiemy, że r = 1. Wtedy każda ze współrzędnych punktów będzie mieściła się w zakresie od 0 do 1, a do losowania liczb w tym zakresie znamy już odpowiednie metody.

Napisz program, który będzie wyliczał wartość π przy użyciu 100, 1000, 10 000, 100 000 oraz 1000 000 punktów a następnie wypisze obliczone wartości oraz ich dokładność, czyli różnice między wyliczonymi wartościami a znaną wartością π, którą możesz pobrać np. używając klasy Math.



Zadanie 2: Dokładniejsze obliczanie wartości π

Jak wspomniałem wyżej, w praktyce obliczanie π metodą Monte Carlo nie jest najlepszym z możliwych rozwiązań. Do tego typu obliczeń można używać różnych wzorów, ich przegląd można znaleźć np. na stronie Wikipedii poświęconej π. Zauważ, że w większości mają one charakter iteracyjny. Należy pamiętać, że nie można wyliczyć i zapisać dokładnej wartości π, zatem w praktyce otrzymuje się mniej lub bardziej dokładne przybliżenia z mniejszą lub większą liczbą cyfr po przecinku.

Zadanie polega na napisaniu programu, który użyje kilku (co najmniej trzech) sposobów obliczania wartości π (np. (np. Leibnitza, Wallisa i Newtona) dla podanej przez użytkownika liczby kroków i porówna ich dokładność.
Dodatkowo, spróbuj napisać metodę z użyciem pętli i drugą metodę z wykorzystaniem rekurencji do wybranych wzorów.

Uwaga: nie stosuj metody rekurencyjnej dla dużej liczby iteracji ( ~ 10000 i wyżej), ponieważ może to spowodować błąd przepełnienia stosu (błąd: java.lang.StackOverflowError).

Leave a Reply