Metody stochastyczne  Metoda Monte Carlo
W tej metodzie, jako podstawowe zadanie, rozważane jest wyznaczenie całki
1
I =� f (�x)�dx
��
0
gdzie funkcja f(x) jest ograniczona i zachodzi 0 Ł� f (x) Ł� 1 dla
0 Ł� x Ł� 1
Przyjęte założenia nie stanowią żadnego ograniczenia, gdyż przedział całkowania
i wartości funkcji poprzez odpowiednie przekształcenie sprowadzić można do
takiego zadania
b
g(�u)�du
W przypadku ogólnym, przy obliczaniu zmianę przedziału całkowania
��
a
u -� a
x =�
uzyskujemy poprzez podstawienie
b -� a
Wówczas
f (x) =� (�b -� a)�g(�(�b -� a)�x +� a)�
f (x) -� f0
Zbiór wartości funkcji ograniczamy wprowadzając
f1 -� f0
f0 Ł� f (x) Ł� f1
gdzie f0 i f1 są takimi liczbami że dla zachodzi
0 Ł� x Ł� 1
Przy powyższych założeniach całkę można interpretować jako pole powierzchni
ograniczonej osią odciętych , wykresem funkcji i prostymi x = 0 oraz x = 1.
(odrzucamy przypadki trywialne f(x) �� 0, f(x) �� 1)
f(x)
1
x
1
Przeanalizujmy dwuwymiarową zmienną losową (X, Y) o rozkładzie
równomiernym na kwadracie 0 Ł� x Ł�1, 0 Ł� y Ł�1.
Z definicji takiej zmiennej losowej wynika, że prawdopodobieństwo zdarzenia
wystąpienia zmiennej w obszarze zaciemnionym jest równe polu tego obszaru czyli
szukanej wartości całki.
Metoda orzeł-reszka
(przedział całkowania i wartości funkcji ograniczone zgodnie z zasadami podanymi uprzednio)
Przyjmijmy, że N oznacza ilość losowań a M ilość trafionych
start
Oszacowana wartość całki
N=0 M=0
M
Q =�
N
generacja x i y
Wariancja
(kwadrat odchylenia
standardowego)
N=N+1
1 M M
ć�1-� ��
2
s� =�
�� ��
N N N
Ł� ł�
nie
tak
Oszacowanie błędu od
y Ł� f(x) M=M+1
góry
1
N
10
3
Przykład. Za pomocą metody orzeł-reszka wyznaczyć całkę
udu
��
0
u -� a u
Zmiana granic całkowania: Podstawiamy x =� =� gdyż a = 0 i b = 10
b -� a 10
f (x) =� (�b -� a)�g(�(�b -� a)�x +� a)� =� 103 10x
Uzyskana funkcja zmiennej x jest postaci
Funkcja ta jest w przedziale (0, 1) przyjmuje wartości od 0 do 21.554
f (x) -� f0
Utwórzmy nową funkcję przyjmując f0=0 oraz f1=30
h(x) =�
f1 -� f0
f (x) 1
3
W rezultacie całkowana będzie funkcja h(x) =� =� 10x
30 3
Uwaga! Po przeprowadzeniu obliczeń wyznaczoną wartości całki należy w
tym przypadku wymnożyć przez wartość f1 - f0 = 30 (dlaczego?)
Przybliżona wartość całki dla 1000 losowań
I = 16.8
Z oszacowanym błędem (po uwzględnieniu prawa propagacji błędu)
ą� 0.948
Metoda podstawowa
(przedział całkowania i wartości funkcji ograniczone zgodnie z zasadami podanymi uprzednio)
N - ilość losowań
1. Wygenerować N wartości losowych x1, x2,& , xN rozkładu równomiernego
z przedziału (0, 1)
2. Wyznaczyć wartości f(x1), f(x2) ,& , f(xN)
3. Obliczyć przybliżoną wartość całki jako średnią
N
1
I =� f (xi )
��
N
i=�1
Wariancja
Oszacowanie błędu od góry
(kwadrat odchylenia standardowego)
2s�
N
1
2
2
N
s� =�
�� (� f (x) -� I)�
N -�1
i=�1
10
3
Przykład. Za pomocą metody podstawowej wyznaczyć całkę
udu
��
0
Zmianę granic całkowania oraz normalizację wartości funkcji przeprowadzić
należy jak w przykładzie poprzednim
Przybliżona wartość całki dla 1000 losowań
I = 16.05
Z oszacowanym błędem (po uwzględnieniu prawa propagacji błędu)
ą� 0.26
Z pokazanych przykładów wynika, że metoda podstawowa daje mniejszy
błąd aniżeli metoda orzeł-reszka. Jest ona także bardziej efektywna jeśli
nie uwzględnimy nakładu obliczeń związanych z wyznaczaniem błędu.
Sytuacja zmienia się gdy konieczne staje się oszacowanie błędu
wyznaczania całki. W tym przypadku w metodzie podstawowej uwzględnić
należy nakład obliczeń związany z wyznaczanie wariancji.