algorytm.org

Cał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
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Całkowanie numeryczne - metoda Monte Carlo I
Ocena użytkowników:***** / 21
SłabyŚwietny 
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:
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.
Metoda Monte-Carlo

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:
Funkcja f(x):
Początek przedziału całkowania:
Koniec przedziału całkowania:
Wartość minimalna (lub mniejsza) funkcji w przedziale:
Wartość maksymalna (lub większa) funkcji w przedziale:
Dokładność całkowania:

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 1
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 8
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 3
Tomasz LubińskiJavaScript
.js
.js
***** / 0
 
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: 04 października 2012 15:52
Dodaj komentarz