StartAlgorytmyProcedury numeryczneCałkowanie numeryczne - metoda Monte Carlo I
Baza Wiedzy
Wersja offline serwisu przeznaczona na urządzenia z systemem Android.

Darowizny
darowiznaWspomóż rozwój serwisu


Nagłówki RSS
Kanał artykuły
Kanał implementacje
Kanał komentarze
Kanał forum


Bookmarki









Sonda
Implementacji w jakim języku programowania poszukujesz?
 
Całkowanie numeryczne - metoda Monte Carlo I
Ocena użytkowników:+++++ / 5
SłabyŚwietny 
Wpisany przez Tomasz Lubiński
wtorek, 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: Pprostokata = |xk - xp| * |yk - yp|.

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.
Metoda Monte-Carlo

Jak już wspominaliśmy na podstawie wylosowanych punktów i przyporządkowania ich do odpowiedniej kategorii możemy wyznaczyć odpowiednie proporcje:
Pprostokata / Całka = n / c, zatem po przekształceniach wartość szukanej całki możemy wyrazić wzorem:
całka = Pprostokata * (c / n) = |xk - xp| * |yk - yp| * (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



Autor Język programowania Komentarz Otwórz Pobierz Ocena
Tomasz Lubiński C# MS Visual Studio .net
Implementacja w C#
Implementacja w C#
++++- / 1
Tomasz Lubiński C/C++
Implementacja w C/C++
Implementacja w C/C++
++++- / 1
Tomasz Lubiński Delphi/Pascal
Implementacja w Delphi/Pascal
Implementacja w Delphi/Pascal
++++- / 1
Tomasz Lubiński Java
Implementacja w Java
Implementacja w Java
++++- / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie



Poprawiony: środa, 26 maja 2010 19:04

Dodaj komentarz

Kod antysapmowy
Odśwież