Metody Numeryczne

POJĘCIE ZMIENNEJ LOSOWEJ
Natura zdarzeń elementarnych może być różnoraka. Żeby się od tego uwolnić przyporządkujmy każdemu zdarzeniu elementarnemu w przestrzeni

Ω

pewną liczbę rzeczywistą. Np. wyrzuceniu orła w rzucaniu monety można przyporządkować liczbę 1, a wyrzuceniu reszki liczbę 0; w rzucaniu sześcienną kostką do gry naturalne jest przyporządkowanie zdarzeniom elementarnym tych liczb, które one oznaczają. Oczywiście w rozpatrywanych przykładach prawdopodobieństwo pojawienia się odpowiedniego zdarzenia losowego jest równe prawdopodobieństwu pojawienia się przyporządkowanej mu liczby (wszystko sie zgadza tak długo jak

Ω

jest przeliczalna).
$\Omega \rightarrow R^1$
Chcielibyśmy jednak, żeby w ogólności (także dla

Ω

nieprzeliczalnych) było określone prawdopodobieństwo przyjmowania przez wyżej stworzoną funkcję wartości z dostatecznie obszernej klasy podzbiorów prostych. Wiemy, że klasę taką stanowi

σ

-algebra zbiorów borelowskich (w tym wypadku w

R 1

).
Żeby sobie to zapewnić zażądamy by przeciwobrazy zbiorów borelowskich w

R 1

otrzymane za pomocą tej funkcji były zdarzeniami losowymi czyli elementami

σ

-algebry $\mathcal{A}$ .
Prowadzi to do następujących definicji:

Definicja: Niech będzie dana przestrzeń probabilistyczna ( $\Omega, \mathcal{A}, P$ ). Zmienną losową (rzeczywistą) nazywamy funkcję rzeczywistą X określoną na przestrzeni zdarzeń elementarnych $Ω$ i taką, że przeciwobrazy zbiorów borelowskich w $R 1$ (na prostej) są zdarzeniami losowymi.

Wystarczy wymagać by przeciwobrazy przedziałów w postaci $(-\infty, x), x \in R^1$ były zdarzeniami losowymi (gdyż, jak łatwo wykazać, każdy zbiór borelowski na prostej można otrzymać za pomocą przeliczalnej liczby działań na takich przedziałach).
Inaczej mówiąc zmienna losowa to funkcja:
$X:\Omega \rightarrow R^1$ taka, że $\bigwedge_x X^{-1} [(-\infty, x)] = \left \{ \omega : X(\omega) < x \right \} \in \mathcal{A}$
Innymi słowy (porównaj def. funkcji mierzalnej) zmienna losowa to funkcja rzeczywista określona na przestrzeni zdarzeń elementarnych

Ω

mierzalna względem miary probabilistycznej P (czyli względem prawdopodobieństwa) lub krócej: to mierzalna względem P transformacja przestrzeni zdarzeń elementarnych w prostej.
Przechodząc do pojęcia rozkładu prawdopodobieństwa zauważmy, że zmienna losowa X w naturalny sposób generuje w

R 1 σ

-algebrę $\mathcal{A}_x$ zbiorów borelowskich

S

, dla których $X^{-1}(S) = \{ \omega : X(\omega) \in S \} \in \mathcal{A}$ . Generuje ona również prawdopodobieństwo określone na elementach tej

σ

-algebry $P_x(S), S \in \mathcal(A)_x$ , zwane prawdopodobieństwem indukowanym i dane wzorem:
$P_x(S)=P \{ \omega : X (\omega) \in S \}$ .
Otrzymujemy zatem definicję tego rozkładu.

Definicja: Rozkładem prawdopodobieństwa zmiennej losowej X nazywamy prawdopodobieństwo indukowane, czyli funkcję zbioru daną wzorem: $P_x (S) = P[X^{-1}(S)]=P\{\omega : X(\omega)\in S\}$ , gdzie S jest dowolnym zbiorem borelowskim w $R^1 (S\in\mathcal{A}_x)$ . Oczywiście $P x (R 1) = P (Ω) = 1$ .

Uwaga:

Często rozkład prawdopodobieństwa mógłby być zdefiniowany tylko na pewnym podbiorze $R 1$ , gdyż zmienna losowa X odwzorowuje $Ω$ w podzbiór $R 1$ . Tak jednak zwykle się nie robi, natomiast dla jednolitości uzupełnia się ten podzbiór do całej prostej traktując to uzupełnienie jako zdarzenie o prawdopodobieństwie równym 0.
Zmienne losowe będziemy oznaczali dużymi literami $X(\omega), Y(\omega), \dots$ lub krótko $X, Y, \dots$ a ich wartości (realizacje), o ile to możliwe, odpowiednio jako $x, y, \dots$ .

Jak widać rozkłady prawdopodobieństwa są funkcjami zbioru i jako takie nie mogą być badane za pomocą aparatu klasycznej analizy rozwiniętego jako funkcji punktu.
Powstaje zatem naturalne pytanie o istnienie funkcji punktu w sposób jedno-jednoznaczny odpowiadający rozkładom prawdopodobieństw. W ogólnej teorii miary jest to tzw. problem dystrybuanty miary. Odpowiedź na to pytanie jest pozytywna, a odpowiednie funkcje nazywają się dystrybuantami.

Zdefiniujmy następującą funkcję rzeczywistą: $F(x)=P_x[(-\infty,x)]=P[X^{-1}(-\infty,x)]=P\left\{\omega : X(\omega) \in (-\infty,x) \right \} = P(X < x)$

Łatwo wykazać, że funkcja

F (x)

ma następujące własnośći.

jest nieujemna, czyli $F(x) \ge 0$ i niemalejąca $\bigwedge_{x_1,x_2} (x_1 < x_2) \Rightarrow [ F(x_1) \le F(x_2) ]$
$F(-\infty)=0, \quad F(+\infty)=1$
jest co najmniej lewostronnie ciągła, czyli dla dowolnego ciągu $x_1 < x_2 < \dots < x$ zbieżnego do x $\lim_{k \to \infty} F(x_k) = F(x)$

Można wykazać następujące twierdzenie.

Tw.: Na to, by funkcja rzeczywista $F (x)$ była dystrybuantą zmiennej $X$ potrzeba i wystarcza by miała własności od 1 do 3.

Z twierdzenia tego wynika, że wzór

F (x) = P (X < x)

definiuje dystrybuantę zmiennej losowej

X

, a zatem funkcję punktu, która jedno-jednoznacznie odpowiada jej rozkładowi prawdopodobieństwa.
Z własności 3. dystrybuanty wynika, że zbiór punktów nieciągłości dystrybuanty jest co najwyżej przeliczalny.

TYPY ZMIENNYCH LOSOWYCH
Poniżej definiujemy dwa główne typy zmiennych losowych:

Definicja: Zmienną losową X nazywamy zmienną losową typu skokowego lub inaczej (zmienną losową dyskretną), jeśli może przyjmować co najwyżej przeliczalną liczbę wartości, które nazywamy punktami skokowymi.

Niech będą to wartości $x_i; i = 1,2,\dots$ przyjmowane z prawdopodobieństwami $p_i; i = 1,2,\dots$ . Oczywiście $p_i \ge 0; i = 1,2,\dots$ . Prawdopodobieństwa

p i

nazywamy skokami (lub masami), a wzór
$P(X = x_i) = p_i, i = 1,2,\dots$ definiuje funkcję prawdopodobieństwa zmiennej losowej X typu skokowego. Oczywiście funkcja ta w pelni charakteryzuje rozkład prawdopodobieństwa tej zmiennej losowej. Oczywisty jest fakt, że związek tej funkcji z dystrybuantą określa wzór:
$F(x) = \sum_{x_i<x}p_i$
Zadanie

Wykreślić dystrybuantę odpowiadającą rzutowi sześciennej kostki

Definicja: Zmienną losową X nazywamy typu ciągłego (ale nie ciągłą), jeśli istnieje taka funkcja rzeczywista $f (x)$ że dla każdego x zachodzi:

$F(x) = \int\limits_{-\infty}^{x}f(x)dx$
gdzie

F (x)

jest dystrybuantą zmiennej losowej X, a całkowanie odbywa się w sensie Lebesgue’a (Henri Lebesgue). Występującą w tym wzorze funkcję

f (x)

nazywamy funkcją gęstości prawdopodobieństwa (funkcją gęstości, gęstością) zmiennej losowej X typu ciągłego.
Uwagi:

Jeśli zmienna losowa X nie ma punktów skokowych, to jej dystrybuantą jest funkcja ciągła. To jednak nie wystarcza do tego by była ona zmienną losową typu ciągłego (według powyższej definicji). By tak było wymagana jest absolutna (lub bezwzględna) ciągłość dystrybuanty.
Wobec powyższego niektórzy autorzy definiują zmienne losowe ciągłe jako posiadające ciągłą dystrybuantę, a absolutnie (bezwzględnie) ciągłe jako posiadające bezwzględna (absolutnie) ciągłą dystrybuantę, czyli według naszej definicji zmienne losowe typu ciągłego.

Z definicji zmiennej losowej typu ciąglego oraz z definicji dystrybuanty wynika bezpośrednio poniższe twierdzenie.

Twierdzenie: Funkcja gęstości prawdopodobieństwa zmiennej losowej typu ciągłego X, to funkcja rzeczywista całkowalna w sensie Lebesgue'a na osi $(-\infty,\infty)$ i taka, że:

$f(x) \ge 0$
$\int\limits_{-\infty}^{\infty}f(x)dx = F(\infty) = 1$

Łatwo też wykazać, że słuszne jest twierdzenie odwrotne:

Twierdzenie: Każda nieujemna funkcja rzeczywista $f (x)$ , całkowalna w sensie Lebesgue'a na osi $(-\infty,\infty)$ oraz taka, że

$\int\limits_{-\infty}^{\infty}f(x)dx = 1$ jest funkcją gęstości prawdopodobieństwa pewnej zmiennej losowej typu ciągłego.
Z powyższych stwierdzeń wynika, że funkcja gęstości prawdopodobieństwa

f (x)

w pełni charakteryzuje rozkład prawdopodobieństwa zmiennej losowej typu ciągłego.
Z teorii całki Lebesgue'a wynika, że dla prawie wszystkich x (czyli z wyjątkiem zbioru miary Lebesque’a równej zero) zachodzi:
$f(x) = \frac{d(F(x))}{d(x)}$
W szczególności powyższy związek zachodzi dla każdego x, dla którego

f (x)

jest ciągła.
Zauważmy również, że dla zmiennej losowej X typu ciągłego
$\bigwedge_{a < b}P(a \le X \le b) = F(b)-F(a) = \int\limits_{a}^{b}f(x)dx$
Ponadto jeśli

x 0

jest wartością, dla której

f (x)

jest określona to
$P(X = x_0) = \int\limits_{x_0}^{x_0}f(x)dx = 0$ .
Zatem z tego, że prawdopodobieństwo zdarzenia związanego ze zmienną losową typu ciągłego jest równe 0 nie wynika, że jest to zdarzenie niemożliwe (pomimo, że odpowiednie zdarzenie elementarne jest możliwe). Zdarzenie takie po prostu uznajemy za bardzo mało prawdopodobne. Analogicznie, przy tym samym założeniu o zmiennej losowej X $P(X \ne x_o) = 1$ pomimo, że odpowiednie zdarzenie nie jest pewne. O takim zdarzeniu mówimy, że jest prawie pewne.

METODY ITERACYJNE - polegają na iteracyjnym ulepszaniu przybliżonego rozwiązania do momentu osiągnięcia zadowalającej dokładności.

METODA GAUSSA-SEIDLA
Minimalizacja funkcji f(x) wzdłuż ortogonalnej bazy x1, x2,...,xn. Jest to minimalizacja funkcji w kierunku.
Zbieżność metody:
Jeżeli funkcja celu f(x) ma postać f(x) = 1/2 x^T A x to metoda Gaussa-Seidela jest zbieżna do punktu ekstremalnego x wtedy i tylko wtedy, gdy macierz A jest dodatnio określona.
Gradient funkcji: grad f = A x , stąd przesunięcie punktu w i-tej iteracji wynosi na podstawie warunku koniecznego na istnienie ekstremum w kierunku :

Z równania tego otrzymuje się l_i minimalizujące funkcję f(x) w kierunku xi:

aⁱ - i-ty wiersz macierzy A, a_ii - odpowiedni element tej macierzy.
Wartość funkcji celu w punkcie

wynosi:

, a po podstawieniu poprzedniego równania:

Oznacza to, że wartość funkcji celu będzie malała w kolejnych iteracjach, gdyż a_ii > 0 dla A dodatnio określonej.
a) informacje wejściowe:
xo - punkt startowy
x1, x2,...,xn - baza wektorów ortogonalnych
eo - początkowa długość kroku
e_j - wymagana dokładność obliczeń minimum w j-tym kierunku
e_o - wymagana dokładność obliczeń globalnego minimum
n - liczba zmiennych niezależnych

b) algorytm obliczeń

dla j = 1, 2,...,n oblicz l_j minimalizujące
oraz współrzędne nowego punktu
jeżeli kryterium zbieżności nie zostało spełnione podstaw x_j w miejsce x_o i wróć do (1).

METODA ITERACJI
W przypadku gdy liczba niewiadomych układu równań jest duża, rozwiązanie takiego układu metodami dokładnymi (np. metodą eliminacji Gaussa) staje się skomplikowane. W takim razie dogodniejsze staje się wykorzystanie do obliczeń metod przybliżonych. Jedną z takich metod jest metoda iteracji. Pod względem czasu obliczeń metody iteracyjne mogą być lepsze od dokładnych dla macierzy rzadkich .

Dany jest układ równań

po wprowadzeniu macierzy

, , ,

układ równań można zapisać w postaci równania macierzowego

Ax=b

Rozwiązujemy pierwsze równanie układu względem x₁, drugie równanie względem x₂ itd. Zakładamy przy tym, że elementy na głównej przekątnej a_ii0 (i=1, 2, ..., n). Otrzymujemy układ równoważny

gdzie

, , dla

oraz

dla i=j i, j = 1, 2, ..., n .

Po wprowadzeniu macierzy

oraz

układ równań (1.50) możemy zapisać w postaci

Aby rozwiązać układ równań, za przybliżenie zerowe przyjmujemy kolumnę wyrazów wolnych, czyli bierzemy

Tworzymy następnie macierze kolumnowe

- pierwsze przybliżenie

- przybliżenie drugie i.t.d

Dowolne (k+1)- sze przybliżenie obliczamy według wzoru

, k = 0, 1, 2, ...

Iterację kończymy gdy spełniony jest warunek

, gdzie oznacza zadaną dokładność.

Jeżeli ciąg przybliżeń x⁽⁰⁾, x⁽¹⁾, ..., x^(k), ... ma granicę , to granica ta jest rozwiązaniem układu równań .

Ogólnie dla układu równań określonego wzorem

, i = 1, 2, ..., n

można przyjąć , gdzie , ( i = 1, 2, ..., n ). Wówczas dany układ równoważny jest układowi

, i = 1, 2, ..., n ,

gdzie

, , dla .

Warunek dostateczny zbieżności.

Jeżeli dla układu równań sprowadzonego do postaci zachodzi co najmniej jeden z warunków:

i = 1, 2, ..., n ,

lub

j = 1, 2, ..., n ,

to proces iteracyjny k = 0, 1, 2, ... jest zbieżny do jednoznacznego rozwiązania, niezależnie od tego, jaki wybierzemy wektor początkowy. Zatem metoda iteracji jest zbieżna dla układu i = 1, 2, ..., n, jeżeli zachodzą następujące nierówności:

i = 1, 2, ..., n,

czyli wtedy, gdy wartości bezwzględne współczynników na głównych przekątnych są dla każdego równania układu większe od sumy wartości bezwzględnych pozostałych współczynników tego równania (nie licząc wyrazów wolnych).

Metody Numeryczne

poniedziałek, 12 listopada 2012

Zmienne losowe

poniedziałek, 5 listopada 2012

METODY ITERACYJNE