Super metody numeryczne: 2012

W punkcie II rozpatrywaliśmy zmienne losowe, które zależały tylko od przypadku czyli od $\omega \in \Omega$ , w praktyce spotyka się na ogół bardziej skomplikowane wielkości losowe , które zmieniają się wraz ze zmianą pewnego parametru $t \in T$ , są one zatem zależne zarówno od przypadku, jak i od wartości tego parametru. Inaczej mówiąc dla opisu wyniku doświadczenia nie wystarcza już punkt przestrzeni , a niezbędna jest funkcja wspomnianego parametru. Jednym z historycznie pierwszych przykładów takich wielkości jest każda współrzędna cząsteczki w tzw. ruchu Browna, która nie tylko jest zmienną losową, ale także zależy od czasu. Innym przykładem są szumy zniekształcające sygnały radiowe, które są zmiennymi losowymi (np. z powodu z wyładowań atmosferycznych), a także zależą od czasu. Także liczba zadań (procesów) w systemie komputerowym, czy liczba pojazdów przejeżdżające przez dane skrzyżowanie są zmiennymi losowymi zależnymi również od czasu. Podkreślmy, że parametrem od którego zależą wymienione (i inne wielkości losowe) zmienne losowe nie musi być czas np. w ruchu turbulentnym prędkość cząsteczki cieczy jest zmienną losową (trójwymiarową) zależną do punktu przestrzeni. W ogólności parametr, o którym mówimy nie musi mieć w ogóle żadnej interpretacji fizycznej. Rozszerzenie teorii prawdopodobieństwa pozwalające badać zmienne losowe zależne od danego parametru nazywa się teorią procesów losowych (przypadkowych,stochastycznych).

Uwaga: Niektórzy autorzy rezerwują pojęcie proces dla sytuacji, gdy omawiany parametr jest czasem, w pozostałych sytuacjach mówiąc o funkcjach losowych. Nie będziemy czynić tego rozróżnienia, które nie ma żadnego znaczenia matematycznego tymbardziej, że w rozpatrywanych przez nas sytuacjach praktycznych t będzie zawsze czasem.

Powyższe rozważania prowadzą do następujących definicji.

Definicja 1: Procesem losowym nazywamy rodzinę zmiennych losowych
$\{X_t(\omega), t \in T\}$
zależnych od parametru $t$ i określonych na danej przestrzeni probabilistycznej $(Ω, A, P)$ .

Innymi słowy proces losowy to losowa funkcja parametru

t

, czyli taka funkcja, która $\forall{t \in T}$ jest zmienną losowa.
Zmienną losową

X t

, którą proces losowy jest w ustalonej chwili $t \in T$ nazywamy wartością tego procesu.
Zbiór wartości wszystkich zmiennych losowych $X_t(\omega), t \in T$ , nazywamy przestrzenią stanu procesu losowego lub przestrzenią stanu.
Jeśli zbiór jest skończony lub przeliczalny, to mówimy o procesach losowych z czasem dyskretnym. W pierwszym wypadku mamy do czynienia z n-wymiarową zmienną losową, a w drugim z odpowiednim ciągiem zmiennych losowych.

Choć niektóre klasy procesów losowych z czasem dyskretnym (np. łańcuchy Markowa) zasługują na uwagę, to jednak w dalszym ciagu skoncentrujemy się na procesach losowych z czasem ciągłym czyli takich, dla których T jest nieprzeliczalne.
Dla głębszego zrozumienia natury procesu losowego spójrzmy nań jeszcze z innej strony. Jak pamiętamy zmienna losowa przyporządkowywała zdarzeniu losowemu punkt w przestrzeni

R n

. W przypadku procesu losowego mamy do czynienia z sytuacją gdy do opisu wyniku doświadczenia niezbędna jest funkcja ciągła, zwana realizacją procesu losowego.
W dalszym ciągu zakładamy, że mamy do czynienia ze skończonymi funkcjami losowymi, a zbiór wszystkich takich funkcji (realizacji) będziemy nazywali przestrzenią realizacji procesu losowego. Prowadzi to do drugiej definicji:

Definicja 2: Procesem losowym nazywamy mierzalną względem P transformację przestrzeni zdarzeń elementarnych $Ω$ w przestrzeni realizacji, przy czym realizacją procesu losowego nazywamy każdą skończoną funkcją rzeczywistą zmiennej $t \in T$ .

Definicja powyższa wynika ze spojrzenia na proces losowy jako na funkcję dwóch zmiennych $t \in T$ i $\omega \in \Omega$ , ustalając

t

otrzymujemy zmienną losową , a ustalając

ω

otrzymujemy realizację .
Na ogół na przestrzeń realizacji procesu losowego narzuca się pewne ograniczenia np. żeby to była przestrzeń Banacha (niezerowa i zwyczajna).
Reasumując: graficznie można przedstawić te dwa punkty widzenia w następujacy sposób.
Pełne oznaczenie procesu losowego ma zatem postać
$\{X_t(\omega) : t \in T\}$ , lub $X(\omega, t), t \in T, \omega \in \Omega$
przy czym w obu wypadkach zakłada się, że jest określona przestrzeń probabilistyczna $(\Omega, \mathcal{A}, P)$ .

Ponieważ jednak zależność od

ω

jako naturalną zwykle się pomija, otrzymujemy:
$\{X_t : t \in T\}$ , lub $X(t) : t \in T$ .
Ponadto, jeśli zbiór

T

jest zdefiniowany na początku rozważań to pomija się także zapis $t \in T$ i w rezultacie otrzymujemy :

X t

, lub

X (t)

.
Oznaczenie

X (t)

może zatem dotyczyć całego procesu losowego, jego jednej realizacji (dla ustalonego

ω

) lub jego jednej wartości, czyli zmiennej losowej (dla ustalonego

t

). Z kontekstu jednoznacznie wynika, o co w danym zapisie chodzi.
Przejdźmy do zapisu procesu losowego X(t). Będziemy rozpatrywać wyłącznie procesy losowe rzeczywiste (proces losowy zespolony ma postać:

X (t) = X 1 (t) + i X 2 (t)

, gdzie

X 1 (t)

X 2 (t)

są procesami losowymi rzeczywistymi).
Ponieważ $\forall{t \in T}$ proces losowy

X t

jest zmienną, więc jego pełny opis w chwili

t

stanowi pełny rozkład prawdopodobieństwa tej zmiennej losowej. Rozkład taki nazywamy jednowymiarowym rozkładem prawdopodobieństwa procesu losowego. Jest on scharakteryzowany przez jednowymiarową dystrybuantę procesu losowego, w postaci :

F (x, t) = P [X (t) < x]

Oczywiście rozkład jednowymiarowy procesu losowego nie charakteryzuje wzajemnej zależności między wartościami procesu (zmiennymi losowymi) w różnych chwilach. Jest on zatem ogólny tylko wtedy gdy dla dowolnych układow $t_1, t_2, \cdots$ wartości procesu losowego,są ciągami zmiennych losowych niezależnych, co na ogół nie zachodzi. W ogólności musimy zatem rozpatrywać łączny rozkład wartości procesu w różnych chwilach.

Definicja: n-wymiarowym rozkładem prawdopodobieństwa procesu losowego nazywamy łączny rozkład prawdopodobieństwa i jego wartości dla dowolnego układu chwili $t 1, t 2,..., t n$ , czyli łączny rozkład prawdopodobieństwa wektora losowego $[X (t 1), X (t 2),..., X (t n)]$ opisany n - wymiarową dystrybuantą procesu losowego :
$F (x 1, t 1; x 2, t 2;...; x n, t n) = P (X (t 1) < x 1, X (t 2) < x 2,..., X (t n) < x n)$

[edytuj] Momenty procesu losowego

Podobnie jak dla zmiennych losowych również dla procesów losowych definiuje się pewne proste charakterystyki rozkładu, w szczególności momenty. Mając jednowymiarowy rozkład procesu możemy określić jego jednowymiarowe momenty np. zdefiniowane poniżej.

Definicja: Wartością średnią procesu losowego $X (t)$ nazywamy funkcję m(t), która $\forall{t \in T}$ jest wartością średnią zmiennej losowej $X (t)$ , którą jest proces w chwili t:
$m (t) = E [X (t)]$

Definicja: Wariancją procesu losowego $X (t)$ nazywamy funkcję $σ 2 (t)$ , która $\forall{t \in T}$ jest wariancją zmiennej losowej $X (t)$ , którą jest proces w chwili t:
$σ 2 (t) = D 2 [X (t)] = E [X (t) - m (t)] 2$

Oczywiście jednowymiarowe momenty procesu losowego nie charakteryzują jego zależności pomiędzy wartościami procesu w różnych chwilach. Żeby opisywać te zależności musimy rozpatrywać wyższe momenty, w szczególności rozpatrzymy 2 różne chwile

t 1

t 2

Definicja: Funkcję korelacyjną procesu losowego $X (t)$ definiujemy jako:
$R x (t 1, t 2) = E {[X (t 1) - m (t 1)][X (t 2) - m (t 2)]}$

Analogicznie można zdefiniować momenty procesu losowego dla ukladu chwil $t_1,t_2,\cdots,t_n)$ np.: funkcję korelacyjną rzędu n dana wzorem
$R_x(t_1,t_2,...,t_n) = E \{[X(t_1) - m(t_1)][X(t_2) - m(t_2)]\cdots[X(t_n) - m(t_n)]\}$

Jednak w większości sytuacji praktycznych wystarczy znajomość momentu rzędu 1 i 2 procesu losowego. Teoria procesów losowych oparta na znajomości tych momentów nazywa się teorią korelacyjną procesów losowych. Teoria ta jest ogólna dla procesów losowych normalnych (gaussowskich), tzn. takich, których wszystkie skończenie wymiarowe rozkłady są normalne.
W praktyce zachodzi często potrzeba rozpatrywania kilku procesów losowych (np. w układach sterowania wielowymiarowych z wieloma we i wy). Mówimy wówczas o wektorowych procesach losowych. Ograniczając się do

n = 2

, czyli do procesu dwuwymiarowego

[X (t), Y (t)]

rozpatrzmy go w dwóch różnych chwilach. Możemy zdefiniować tzw. funkcję korelacji wzajemnej określoną wzorem:

R X Y (t 1, t 2) = E {[X (t 1) - m X (t 1)][Y (t 2) - m Y (t 2)]}

Dla odróżnienia funkcje korelacyjne zdefiniowane uprzednio dotyczące pojedynczych procesów losowych nazywa się funkcjami korelacji własnej (autokorelacji) i oznacza przez

R X X (t 1, t 2)

R Y Y (t 1, t 2)

.
Macierz:
$\begin{bmatrix}R_{XX}(t_1,t_2) & R_{XY}(t_1,t_2) \\ R_{YX}(t_1,t_2) & R_{YY}(t_1,t_2) \end{bmatrix}$
nazywa się macierzą korelacyjną procesu wektorowego

[X (t), Y (t)]

[edytuj] Procesy stacjonarne

Ponieważ ogólna teoria procesów losowych jest dla celów praktycznych zbyt skomplikowana rozpatruje się pewne klasy tych procesów spełniających dodatkowe założenia i upraszczające analizę. W dalszych punktach rozpatrzmy kilka takich klas zaczynając od procesów stacjonarnych. Rozpatruje się procesy stacjonarne w sensie węższym i szerszym.

Definicja: Proces losowy X(t) nazywamy stacjonarnym w węższym sensie, jeśli dla dowolnego $n \in N$ , dla dowolnego układu chwil $t 1, t 2,..., t n$ dla dowolnego h takiego, że $\forall_{t_i, 1 \le i \le n}$ $(t_i+h \in T)$ zachodzi:
$F (x 1, t 1; x 2, t 2;...; x n, t n) = F (x 1, t 1 + h; x 2, t 2 + h;...; x n, t n + h)$

W szczególności dla

n = 1

mamy:

F (x, t) = F (x, t + h)

co oznacza, że

F (x, t) = F (x)

, zatem jednowymiarowe momenty takiego procesu nie zależą od

t

, w szczególności

m (t) = m = c o n s t

.

Dla

n = 2

mamy:

F (x 1, t 1; x 2, t 2) = F (x 1, t 1 + h; x 2, t 2 + h)

czyli

F (x 1, t 1; x 2, t 2) = F (x 1, x 2,τ)

gdzie

τ = t 2 - t 1

.
Widzimy zatem, że dla procesu stacjonarnego w węższym sensie wartość średnia m(t), jeśli istnieje jest stała, a funkcja korelacji własnej

R X X

, jeśli istnieje zależy tylko od

τ = t 2 - t 1

Definicja: Proces losowy $X (t)$ , dla którego istnieją $m (t)$ i $R x (t 1, t 2)$ nazywamy stacjonarnym w szerszym sensie, jeśli $m (t) = m = c o n s t$
$R X (t 1, t 2) = R X (τ)$ , $τ = t 2 - t 1$ .

Łatwo wykazać twierdzenie:

Twierdzenie: Proces stacjonarny $X (t)$ w węższym sensie, dla którego $E[X^2(t)]<\infty$ jest stacjonarny w szerszym sensie.

Dla procesów normalnych (gaussowskich) słuszne jest również twierdzenie odwrotne.
Z pojęciem stacjonarności wiąże się pojęcie procesu losowego o przyrostach stacjonarnych.

Definicja: Proces losowy $X (t)$ nazywamy procesem o przyrostach stacjonarnych, jeśli dla dowolnego $δ$ takiego, że $\forall_{t \in T}{t+\delta \in T}$ proces losowy $Y (t) = X (t + δ) - X (t)$ jest stacjonarny węższym sensie.

[edytuj] Procesy o przyrostach niezależnych i procesy Markowa

Definicja: Proces losowy X(t) nazywamy procesem o przyrostach niezależnych jeżeli dla dowolnego ukladu $t_1 < t_2 < \cdots < t_n \in T$ (uporządkowany układ chwil) zmienne losowe $X(t_1),X(t_2)-X(t_1),\cdots ,X(t_n) - X(t_{n-1})$ są niezależne.

Ważną klasą procesów niezależnych stanowią procesy Poissona.

Definicja: Proces losowy X(t) nazywamy procesem Markowa jeśli dla każdego $t_1 < t_2 < \cdots < t_n \in T$ oraz dla dowolnych liczb rzeczywistych $x_1,x_2,\cdots,x_n$ zachodzi
$P[X(t_n) < x_n | X(t_{n-1}) = x_{n-1},X(t_{n-2}) = x_{n-2}, \cdots , X(t_1) = x_1] = P[X(t_n) < x_n | X(t_{n-1}) = x_{n-1}]$

Jak widać dla procesu Markowa rozkład warunkowy jego wartości w chwili

X (t n)

przy danych wartościach $X(t_1), X(t_2), \cdots , X(t_{n-1})$ zalezy tylko od

X (t n - 1)

. Oznacza to, że własności procesu Markowa w dowolnej chwili

t n

zależą tylko od jego wartości w tej chwili oraz w chwili

t n - 1

, a nie zależą od jego wartości w chwilach poprzedzających chwilę

t n - 1

. Własność ta nazywa się własnością Markowa lub własnością braku pamieci.
Zauważmy, że oznacza to, iż proces Markowa jest w pełni opisany przez dystrybuantę warunkową

F (x, y, s, t) = P [X (t) < x | X (s) = y], s < t

lub przez łączna dystrybuantę wektora losowego

[X (t), X (s)]

wraz z dystrybuantą tzw. początkową

F (s, y) = P [X (s) < y]

. Widzimy zatem, że proces Markowa jest w pełni opisany przez rozkład dwuwymiarowy.

Twierdzenie: Proces losowy X(t) o przyrostach niezależnych, dla którego $P [X (t 1) = c] = 1$ (gdzie c to dowolna stała) jest procesem Markowa (ale nie odwrotnie).

Zobacz też listę procesów stochastycznych na angielskiej wikipedii.

[edytuj] Ergodyczność procesów losowych

Zauważmy, że w celu wyznaczenia momentu procesu losowego musielibyśmy dysponować jednocześnie wszystkimi jego realizacjami, co w praktyce jest na ogół niemożliwe. W naturalny sposób powstaje więc pytanie, przy jakich założeniach można na podstawie pojedynczej realizacji procesu wyznaczyć jego momenty.
Odpowiedź na to pytanie jest przedmiotem tzw. twierdzeń ergodycznych, a procesy losowe dla których średnie po czasie (z pojedynczej realizacji) mogą być utożsamiane z odpowiednimi średnimi po zbiorze nazywają się procesami ergodycznymi względem odpowiedniego momentu (np. wartości średniej czy f. korelacyjnej).
Można wykazać, że dla obszernej klasy procesów stacjonarnych warunek wystarczający ergodyczności względem wartości średniej i funkcji korelacyjnej ma postać:
$\lim_{\tau \rightarrow \infty} R_x(\tau) = 0$
Zatem dla procesów stacjonarnych spełniajacych powyższy warunek mamy
$E[X(t)] = m \approx {1 \over T} \int_0^T X(t)dt$
oraz
$E \{ [X(t)-m][X(t+\tau)-m]\} = R_x(\tau) \approx {1 \over T} \int_0^T[X(t)-m][X(t+\tau)-m]dt$

Materiał pobrany z http://putwiki.informatyka.org/wiki/Procesy_losowe

Aproksymacja jest dziełem analizy numerycznej zajmującym się najbardziej ogólnymi zagadnieniami przybliżania funkcji, polegającymi na wyznaczaniu dla danej funkcji f(x) takich funkcji F(x),które w określonym sensie najlepiej przybliżają funkcję f(x).

Potrzeba przybliżenia danej funkcji inną funkcją pojawia się w wielu zadaniach. Może mieć np. zastosowanie przy obliczaniu funkcji standardowych lub wtedy, gdy funkcja f(x) jest zdefiniowana bardzo skomplikowanym wzorem. Jednym ze sposobów rozwiązania tego zadania jest przybliżanie funkcji f(x) sumami częściowymi ich rozwinięć w szeregi Taylora.

Zadania aproksymacyjne mogą być formułowane bardzo różnie, w zależności od przyjętego sposobu oszacowania błędów aproksymacji. Wyróżnia się trzy rodzaje aproksymacji:

aproksymację interpolacyjną

aproksymację jednostajną

aproksymację średniokwadratową

rysunek 5.6

W przypadku aproksymacji interpolacyjnej, podobnie jak w zagadnieniu interpolacji, żądamy spełnienia warunku, aby funkcja dana f(x) i funkcja szukana F(x) przyjmowały dokładnie te same wartości na zbiorze z góry ustalonych punktów węzłowych (rys. 5.6). Warunek ten może być uzupełniony warunkami wyrażającymi równość pochodnych w węzłach, jeżeli wartości pochodnych zostaną zadane.

rysunek 5.7

W przypadku aproksymacji jednostajnej funkcję przybliżamy taką funkcją w całym przedziale [a,b]- (rys.5.7)

(5.61)

Twierdzenie Weierstrassa gwarantuje że zawsze można znaleźć wielomian o dowolnie małym odchyleniu od funkcji f(x) na przedziale [a,b]. Nie ma jednak ogólnej metody umożliwiającej znajdowanie wielomianu najlepszego przybliżenia jednostajnego stopnia n dla dowolnej funkcji ciągłej na [a,b].

W przypadku aproksymacji średniokwadratowej jako miarę odchylenia funkcji od danej funkcji przyjmujemy wielkość

(5.62)

zwaną odchyleniem kwadratowym. Funkcja aproksymująca wyznaczana jest z warunku, aby wartość wyrażenia (5.62) była możliwie najmniejsza. Geometrycznie warunek ten wyraża żądanie, aby pole powierzchni między liniami reprezentującymi funkcję było minimalne. Jest to pole zakreskowane na rysunku 5.8.

rysunek 5.8

Zagadnienia aproksymacji jednostajnej i aproksymacji średniokwadratowej są również formułowane dla funkcji określonych na dyskretnym zbiorze argumentów. Dla takich funkcji warunek (5.61) dotyczący aproksymacji jednostajnej zmienia się w ten sposób, że zamiast ciągłej zmiennej niezależnej x występuje w nim zmienna dyskretna X_i.

(5.63)

a w rachunku (5.62) na minimum odchylenia kwadratowego całka jest zastępowana sumą

(5.64)

Aproksymacja średniokwadratowa funkcji określonych na dyskretnym zbiorze argumentów jest najczęściej wykorzystywana w zastosowaniach praktycznych do wygładzania danych eksperymentalnych i wyników obliczeń ze względu na mniej skomplikowane algorytmy jej realizacji numerycznej w porównaniu z algorytmami aproksymacji jednostajnej i możliwość uzyskiwania dobrych przybliżeń funkcji f(x). W niektórych przypadkach istnieją przesłanki teoretyczne co do doboru postaci wzoru dla funkcji aproksymującej ( wskazując dostatecznie wąską klasę funkcji np. zbiór funkcji liniowych, potęgowych, wykładniczych itp. )- wtedy określamy tylko wartości liczbowe parametrów, przy których przybliżenie danej funkcji jest najlepsze.

Aproksymacja średniokwadratowa wielomianami

W zadaniach aproksymacji średniokwadratowej wielomianami funkcji aproksymującej F(x) wygodnie jest poszukiwać w postaci wielomianu uogólnionego

(5.65)

będącego kombinacją liniową liniowo-niezależnych funkcji. Rozważając aproksymację średniokwadratową funkcji y=f(x) określonej na dyskretnym zbiorze argumentów współczynniki a_i j=0,1...m funkcji (5.65) przyjmujemy tak , żeby funkcja

(5.66)

osiągnęła wartość minimalną. Zgodnie z ogólnymi metodami rachunku różniczkowego funkcja osiąga minimum wtedy i tylko wtedy ,gdy znikają pochodne cząstkowe względem wszystkich zmiennych a₀,a₁...a_i :

Stąd otrzymujemy układ m+1 równań z m+1 niewiadomymi współczynnikami , z układem normalnym :

(5.67)

w którym wprowadzono skrócone oznaczenie

(5.68)

Układ równań (5.67) ma dokładne jedno rozwiązanie dla liniowo - niezależnego układu funkcji:

Macierz współczynników (5.67) jest macierzą symetryczną i dodatnio określoną. Dla układu funkcji bazowych tworzących ciąg wielomianów

układ równań (5.67) przyjmie postać:

(5.69)

gdzie:

(5.70)

Wielomian aproksymujący daną funkcję f(x) w sensie najmniejszych kwadratów

(5.71)

powinien mieć stopień na tyle wysoki, aby dostatecznie przybliżał funkcję f(x), a jednocześnie mieć stopień wystarczająco niski, aby wielomian ten wygładzał błędy losowe np. z pomiarów. Jeśli m=n, to wielomian aproksymujący Q_m(x) pokrywa się z wielomianem Lagrange'a dla układu punktów: x<₀,x₁, ... x_m i S=0 wtedy . Wiadomo, że dla m=>6 układ (5.69) jest układem źle uwarunkowanym, wskutek czego otrzymane wyniki mogą być bardzo zaburzone i nie nadawać się do praktycznego wykorzystania. Podobnie więc jak w przypadku interpolacji aproksymację średniokwadratową wielomianami potęgowymi (5.71) można zastosować tylko dla małych wartości m. Trudności obliczeniowe związane z aproksymacją średniokwadratową za pomocą wielomianów wyższych stopni mogą być zmniejszone przy wykorzystaniu wielomianów ortogonalnych.

Średniokwadratowa aproksymacja trygonometryczna

W zagadnieniach , w których funkcja f(x) jest okresowa wygodnie jest taką funkcję aproksymować nie wielomianami algebraicznymi, a wielomianami trygonometrycznymi - tym bardziej, że ich odchylenia kwadratowe od funkcji f(x) jest najmniejsze w porównaniu z odchyleniami kwadratowymi dla innych wielomianów.
Jeżeli funkcja f(x) o okresie