Własny silnik graficzny. Część IV: krwawienie kolorów i miękkie cienie.

30.11.2010 - Robert Kraus
TrudnośćTrudnośćTrudnośćTrudność

Pod niewielkimi zmianami w kodzie kryje się trochę matematyki. Dowiemy się teraz dlaczego to, co zrobiliśmy, działa.

Całkowanie

Niespodzianka, a teraz nauczymy się całkować. Interesować nas będzie geometryczna interpretacja całki, która mówi, że $ \int \limits_{x \in [a,b]} f(x) dx $ (czyt. całka z funkcji $ f(x) $ na odcinku $ [a,b] $) jest równa polu pod wykresem funkcji $ f(x) $, jeśli przyjmuje ona wartości wyłącznie nieujemne. Przyjrzyjmy się kilku przykładom.

Przykład 1

Niech $ f(x) = 2 $. Zauważmy, że na odcinku $ [a, b] $ pole pod wykresem funkcji $ f(x) $ jest równe polu prostokąta, którego jeden bok ma długość $ 2 $, a drugi ma długość $ |b-a| $. A więc:

$$ \int \limits_{x \in [a,b]} f(x) dx = 2 \cdot |b-a| $$

Przykład 2

Niech $ f(x) = x $. Zauważmy, że na odcinku $ [0, 4] $ pole pod wykresem funkcji $ f(x) $ jest równe połowie pola kwadratu o boku $ 4 $. A więc:

$$ \int \limits_{x \in [0,4]} f(x) dx = \frac{4 \cdot 4}{2} = 8 $$

Przykład 3

Niech teraz funkcja $ f(x) $, będzie taka jak na poniższej ilustracji. W przypadku takiej funkcji pojawia się problem ("gołym okiem" niezbyt widać ile wynosi pole pod wykresem takiej funkcji). Teraz poradzimy sobie całkowaniem stochastycznym.

Całkowanie stochastyczne

Całkowanie stochastyczne polega na oszacowaniu (przybliżeniu) wartości całki w sposób losowy. Konstruujemy coś, co będzie przybliżało wartość interesującej nas całki (będzięmy to nazywać estymatorem).

Estymator zdefiniowany jest następująco:

$$X_f(x) = \frac{f(x)}{p(x)}$$
gdzie $ p(x) $ jest gęstością rozkładu z jaką wylosowano próbkę $ x $ z dziedziny funkcji $ f(x) $.

Na początek oswoimy się z pojęciem rozkładu. Intuicyjnie rozkład warunkuje to, w których miejscach dziedziny funkcji punkty będą losowane z większym prawdopodobieństwem, a w których z mniejszym (co skutkuje tym, że jak wylosujemy przykładowo 100 punktów, to w jednych obszarach dziedziny mogą powstawać gęstsze skupiska punktów, a w innych punkty będą występować sporadycznie).

Na powyższej ilustracji widać przykład dwóch rozkładów. Wylosowano 16 punktów na odcinku. W rozkładzie jednostajnym punkty rozkładają się na odcinku równomiernie (tj. nie mają wyraźnej tendencji do grupowania się tylko w pewnych miejscach). Natomiast w rozkładzie niejednostajnym punkty mogą sie grupować tak jak na ilustracji na końcach odcinka oraz rzadko występować w okolicy jego środka.

Skupimy sie teraz na rozkładzie jednostajnym. Z rozkładem związane jest pojęcie gęstości. Detale teoretyczne takie jak wyprowadzanie gęstości dla konkretnego rozkładu oraz czym dokładnie jest gęstość wybiegają nieco poza poziom trudności tego artykułu, więc funkcje gęstości dla rozkładów bedą podawane jako fakty, w które należy uwierzyć bez dowodu. Dla rozkładu jednostajnego funkcja gęstości jest równa odwrotności długości odcinka, bądź polu lub objętości zbioru, z którego losujemy punkty. Przykładowo dla odcinka długości 10 funkcja gęstości to $ p(x) = \frac{1}{10} $, a dla prostokąta o polu 25 funkcja gęstości to $ p(x) = \frac{1}{25} $.

$$----------$$

Przekonajmy się, że to wszystko rzeczywiście działa. Wrócmy do przykładu nr 1 całkowania. Mamy funkcję $ f(x) = 2 $ na pewnym przedziale $ [a,b] $. Z przykładu nr 1 pamiętamy, że:

$$ \int \limits_{x \in [a,b]} f(x) dx = 2 \cdot |b-a| $$
Zwróćmy uwagę na to, że skoro funkcja jest określona na przedziale $ [a,b] $, to dla rozkładu jednostajnego na tym odcinku funkcja gęstości wynosi $ p(x) = \frac{1}{|b-a|} $. Zgodnie z definicją estymator dla funkcji $ f(x) $ to
$$ X_f(x) = \frac{f(x)}{p(x)} = f(x) / \frac{1}{|b-a|} = f(x) \cdot |b-a|$$
Skoro wartością funkcji $ f $ jest zawsze $ 2 $, to:
$$ X_f(x) = 2 \cdot |b-a| = \int \limits_{x \in [a,b]} f(x) dx $$
Zatem wystarczy wylosować tylko jeden element z dziedziny fukncji, aby stochastycznie (losowo) obliczyć całkę z funkcji $ f $ na odcinku $ [a,b] $.

$$----------$$

Sprawdźmy teraz co się dzie w przypadku przykładu nr 2 całkowania. Mamy funkcję $ f(x) = x $ na przedziale $ [0,4] $. Pamiętamy, że:

$$ \int \limits_{x \in [0,4]} f(x) dx = 8 $$
Skoro funkcja jest określona na przedziale $ [0,4] $, to dla rozkładu jednostajnego na tym odcinku funkcja gęstości wynosi $ p(x) = \frac{1}{4} $. Zgodnie zdefinicją estymator dla funkcji $ f(x) $ to
$$ X_f(x) = \frac{f(x)}{p(x)} = f(x) / \frac{1}{4} = f(x) \cdot 4 $$
Zauważmy, że jesli wylosujemy $ x = 0 $, to $ X_f(0) = 0 $, a jeśli wylosujemy $ x = 4 $, to $ X_f(4) = 16 $. Widzimy zatem, że nasz prosty estymator bardzo słabo przybliża wartość naszej całki. Teraz zrobimy użytek naszego rozkładu i skonstruujemy lepszy estymator. Niech $ X_f^{(i)} $ oznacza wartość estymatora w $ i $-tej próbie (tj. wiele razy losujemy $ x $ i obliczamy $ X_f(x) $ dla każdego losowania), a $ X_f^{[n]} $ niech oznacza średnią arytmetyczną wartości $ X_f^{(i)} $, czyli:
$$ X_f^{[n]} = \frac{1}{n} \cdot \sum_{i=1}^n X_f^{(i)} = \frac{1}{n} \cdot ( X_f^{(1)} + X_f^{(2)} + ... + X_f^{(n)}) $$
Przy tak skonstruowanym estymatorze zachodzi:
$$ \lim_{n \rightarrow \infty} X_f^{[n]} = \int \limits_{x \in [0,4]} f(x) dx $$
Zróbmy mały eksperyment, wylosujmy $ 5 $ elementów z dziedziny funkcji $ f $. Skoro losujemy z rozkładem jednostajnym możliwa jest sytuacja, w ktorej wylosujemy punkty $ 0 $, $ 1 $, $ 2 $, $ 3 $, $ 4 $. Dla każdego wylosowanego punktu obliczamy $ X_f^{(i)} $:
$$ X_f^{(1)} = 0 \cdot 4 = 0 $$
$$ X_f^{(2)} = 1 \cdot 4 = 4 $$
$$ X_f^{(3)} = 2 \cdot 4 = 8 $$
$$ X_f^{(4)} = 3 \cdot 4 = 12 $$
$$ X_f^{(5)} = 4 \cdot 4 = 16 $$
Następnie obliczamy $ X_f^{[5]} $:
$$ X_f^{[5]} = \frac{X_f^{(1)}+X_f^{(2)}+X_f^{(3)}+X_f^{(4)}+X_f^{(5)}}{5} $$
$$ X_f^{[5]} = \frac{0+4+8+12+16}{5} = \frac{40}{5} = 8 = \int \limits_{x \in [0,4]} f(x) dx $$
A więc przy pięciu próbach możemy już otrzymać dokładny wynik.

4
Twoja ocena: Brak Ocena: 4 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com