Wpisany przez Tomasz Lubiński,
19 lutego 2008 19:26
Załóżmy, że chcemy obliczyć całkę z funkcji f(x) w przedziale <xp; xk>. Definicja całki oznaczonej Riemana, mówi nam, że wartość całki równa jest polu obszaru pod wykresem krzywej w zadanym przedziale całkowania.
Załóżmy na początek, iż wiemy z całą pewnością, że wartości funkcji w obszarze całkowania mieszczą się w przedziale <yp; yk>. Pole prostokąta wyznaczonego przez przedział całkowania: <xp; xk> oraz zakres wartości funkcji w tym przedziale: <yp; yk> jest prosty do wyznaczenia i wynosi:
Na poniższym schemacie, punkty spełniające warunek pierwszy oznaczono kolorem niebieskim. Punkty spełniające warunek drugi oznaczono kolorem czerwonym, pozostałe - spełniające warunek trzeci oznaczono kolorem czarnym.
Jak już wspominaliśmy na podstawie wylosowanych punktów i przyporządkowania ich do odpowiedniej kategorii możemy wyznaczyć odpowiednie proporcje:
xp = 3
xk = 7
yp = -2
yk = 5
Liczba wszystkich punktów pomiarowych n wynosi 36.
Liczba punktów niebieskich zwiększających zmienną c wynosi 8.
Liczba punktów czerwonych zmniejszających zmienną c wynosi 3.
Zatem ostateczna wartość zmiennej c wynosi 8 - 3 = 5.
Podstawiając wszystkie dane pod wyznaczony wzór otrzymujemy: |xk - xp| * |yk - yp| * (c/n) = |7 - 3| * |5 - -2| * (5/36) = 4 * 7 * 0.1388889 = 3.8888892
Zatem przybliżona wartość całki wynosi: 3.8888892
Załóżmy na początek, iż wiemy z całą pewnością, że wartości funkcji w obszarze całkowania mieszczą się w przedziale <yp; yk>. Pole prostokąta wyznaczonego przez przedział całkowania: <xp; xk> oraz zakres wartości funkcji w tym przedziale: <yp; yk> jest prosty do wyznaczenia i wynosi:
P{prostokata} = |x_k - x_p| * |y_k - y_p|
Metoda Monte Carlo polega na wylosowaniu n punktów znajdujących się w obrębie wspomnianego prostokąta i na tej podstawie obliczenia stosunku pola powierzchni pod krzywą czyli wartości całki do pola wyznaczonego prostokąta. W tym celu wprowadzimy zmienną pomocniczą c, którą modyfikować będziemy następująco:- jeżeli wylosowany punkt (xi, yi) leży nad osią OY i jednocześnie pod wykresem funkcji całkowanej, czyli spełnia nierówność: 0 < yi ≤ f(xi), wówczas zwiększamy zmienną c o jeden,
- jeżeli wylosowany punkt (xi, yi) leży pod osią OY i jednocześnie nad wykresem funkcji całkowanej, czyli spełnia nierówność: 0 > yi ≥ f(xi), wówczas zmniejszamy zmienną c o jeden,
- jeżeli wylosowany punkt (xi, yi) nie spełnia żadnego z powyższych warunków, wówczas pozostawiamy zmienną c bez zmian.
Na poniższym schemacie, punkty spełniające warunek pierwszy oznaczono kolorem niebieskim. Punkty spełniające warunek drugi oznaczono kolorem czerwonym, pozostałe - spełniające warunek trzeci oznaczono kolorem czarnym.
Jak już wspominaliśmy na podstawie wylosowanych punktów i przyporządkowania ich do odpowiedniej kategorii możemy wyznaczyć odpowiednie proporcje:
\frac{P_{prostokata}}{Calka} = \frac{n}{c}
zatem po przekształceniach wartość szukanej całki możemy wyrazić wzorem:
calka = P_{prostokata} * \frac{c}{n} = |x_k - x_p| * |y_k - y_p| * \frac{c}{n}
Wraz ze zwiększaniem się liczby punktów pomiarowych n, rozkładają się one coraz bardziej równomiernie w obrębie wyznaczonego prostokąta dając coraz dokładniejszy wynik. Podstawowym problemem w tej metodzie jest wyznaczenie zakresu wartości funkcji w przedziale całkowania. Dlatego też opracowano również inny algorytm całkowania oparty o Metodę Monte-Carlo, nie wymagający tej informacji.Przykład:
Obliczymy wartości całki, dla funkcji przedstawionej na schemacie powyżej zakładając, że:xp = 3
xk = 7
yp = -2
yk = 5
Liczba wszystkich punktów pomiarowych n wynosi 36.
Liczba punktów niebieskich zwiększających zmienną c wynosi 8.
Liczba punktów czerwonych zmniejszających zmienną c wynosi 3.
Zatem ostateczna wartość zmiennej c wynosi 8 - 3 = 5.
Podstawiając wszystkie dane pod wyznaczony wzór otrzymujemy: |xk - xp| * |yk - yp| * (c/n) = |7 - 3| * |5 - -2| * (5/36) = 4 * 7 * 0.1388889 = 3.8888892
Zatem przybliżona wartość całki wynosi: 3.8888892
Przykład w JavaScript:
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C# | MS Visual Studio .net | .cs | .cs | ***** / 2 |
Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 13 | |
Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 1 | |
Tomasz Lubiński | Java | .java | .java | ***** / 5 | |
Tomasz Lubiński | JavaScript | .js | .js | ***** / 0 |
Poprawiony: 04 października 2012 15:52