METODY NUMERYCZNE I METODY PROBABILISTYCZNE : stycznia 2013

WIELKIE UKŁADY RÓWNAŃ LINIOWYCH

Wraz z coraz większymi modelami pojawiającymi się w praktyce obliczeniowej, coraz częściej zachodzi potrzeba rozwiązywania zadań algebry liniowej, w której macierze są co prawda wielkiego wymiaru, ale najczęściej rozrzedzone, to znaczy jest w nich bardzo dużo zer. Bardzo często zdarza się, że macierz wymiaru $\displaystyle N$ ma tylko $\displaystyle O(N)$ niezerowych elementów. Wykorzytanie tej specyficznej własności macierzy nie tylko prowadzi do algorytmów istotnie szybszych od ich analogów dla macierzy gęstych (to znaczy takich, które (w założeniu) mają $\displaystyle N^2$ elementów), ale wręcz są jedynym sposobem na to, by niektóre zadania w ogóle stały się rozwiązywalne przy obecnym stanie techniki obliczeniowej!
Jednym ze szczególnie ważnych źródeł układów równań z macierzami rozrzedzonymi są np. równania różniczkowe cząstkowe (a więc np. modele pogody, naprężeń w konstrukcji samochodu, przenikania kosmetyków do głębszych warstw skóry, itp.).
Modele wielostanowych systemów kolejkowych (np. routera obsługującego wiele komputerów) także prowadzą do gigantycznych układów równań z macierzami rozrzedzonymi o specyficznej strukturze.
Z reguły zadania liniowe wielkiego wymiaru będą miały strukturę macierzy rozrzedzonej, gdyż najczęściej związki pomiędzy niewiadomymi w równaniu nie dotyczą wszystkich, tylko wybranej grupy.

Przykład: Macierz z kolekcji Boeinga

Spójrzmy na macierz sztywności dla modelu silnika lotniczego, wygenerowaną swego czasu w zakładach Boeinga i pochodzącą z dyskretyzacji pewnego równania różniczkowego cząstkowego. Pochodzi z kolekcji Tima Davisa. Jest to mała macierz, wymiaru 8032 (w kolekcji spotkasz równania z milionem i więcej niewiadomych).

Struktura niezerowych elementów macierzy bcsstk38.

Jej współczynnik wypełnienia (to znaczy, stosunek liczby niezerowych do wszystkich elementów macierzy) wynosi jedynie $\displaystyle 0.006$ , a więc macierz jest bardzo rozrzedzona: w każdym wierszu są średnio tylko 44 niezerowe elementy.

PODSTAWY TEORII WERYFIKACJI HIPOTEZ

Formułowanie hipotezy statystycznej rozpoczyna się zebraniem informacji na temat populacji i jej możliwego rozkładu. Dzięki temu możliwe jest zbudowanie zbioru hipotez dopuszczalnych Ω, czyli zbioru rozkładów, które mogą charakteryzować badaną populację. Hipoteza statystyczna to każdy podzbiór zbioru hipotez dopuszczalnych

Podział hipotez statystycznych

Hipotezy statystyczne można podzielić na:

parametryczne - hipoteza dotyczy wartości parametru rozkładu
nieparametryczne - hipoteza dotyczy postaci funkcyjnej rozkładu

Według innego kryterium podział przebiega następująco:

proste - hipoteza jednoznacznie określa rozkład danej populacji, czyli odpowiadający jej podzbiór zbioru Ω zawiera jeden element (rozkład)
złożone - hipoteza określa całą grupę rozkładów, zaś odpowiadający jej podzbiór zbioru Ω zawiera więcej niż jeden element
alternatywna - przyjmujemy ją kiedy odrzucamy hipotezę zerową

Hipotezy weryfikujemy za pomocą testów statystycznych.

Test statystyczny: metoda postępowania, która każdej próbce x₁, x₂, ...,x_n przyporządkowuje ustalonym prawdopodobieństwem decyzje odrzucenia lub przyjęcia sprawdzanej hipotezy.

parametryczne testy istotności - służą do weryfikacji hipotez parametrycznych – odrzucić czy też nie hipotezę wyjściową (zerową);

testy zgodności - testy weryfikujące hipotezy dotyczące zgodności pomiędzy rozkładem wartości w próbce i rozkładem teoretycznym.

Przykładem jest test c² Pearsona;

Parametryczne testy istotności

Rozpatrzymy poniżej 3 parametryczne testy istotności dotyczące:

a) wartości oczekiwanej;

b) różnicy wartości oczekiwanych w dwóch próbkach;

c) wariancji i odchylenia standardowego.

Teza rzeczowa – to, co mamy udowodnić metodą statystyczną, np. że wartość średnia obliczona dla próby jest większa od wartości oczekiwanej w populacji generalnej. W tym celu formułujemy hipotezę, którą zamierzamy weryfikować. Nazywamy ją hipotezą zerową i oznaczamy H₀. Może ona brzmieć następująco: wartość oczekiwana jest równa m₀, co zapiszemy H₀: m=m₀. Zwykle testujemy hipotezę zerową wobec hipotezy alternatywnej H_a, np. H_a: m=m₁¹m₀. Wyniki weryfikacji jakiejś hipotezy nie dają nam absolutnej pewności, ale wnioski możemy sformułować z dowolnie dużym prawdopodobieństwem. Tezę rzeczową, którą chcemy udowodnić metodą statystyczną zwykle nie przyjmujemy jako hipotezy zerowej H_0,ale jako hipotezę alternatywną, którą przyjmujemy po ewentualnym odrzuceniu hipotezy zerowej H₀.

Testowanie składa się z następujących etapów:

1.Sformułowanie tezy rzeczowej i ustaleniu hipotez H₀ i H_a;

2.Wyboru właściwej funkcji testowej (statystyki z próby);

3.Przyjęciu stosownego poziomu istotności a

4.Odczytaniu wartości krytycznych w tablicach dystrybuanty właściwego rozkładu i ustaleniu obszaru krytycznego;

5.Odrzuceniu hipotezy zerowej na korzyść hipotezy alternatywnej, gdy funkcja testowa obliczona z próby znajduje się w obszarze krytycznym i nie odrzucenie jej, gdy funkcja testowa jest poza obszarem krytycznym

Przykład

Należy dokonać oceny partii pudelek zapalek liczącej 100 tys. sztuk. dostawca twierdzi, że w pudelku znajdują się przecietnie 54 zapalki. Zweryfikować hipotezę

H 0 (m = m 0 = 54)

. Ponieważ nie znamy rozkładu liczby zapałek w pudełkach w populacji generalnej, a mozemy łatwo pobrać próbę >= 30 możemy wieć w przybliżeniu skorzystać z rozkładu normalnego. Zkaldamy, że przy próbie o wielkości n = 100 odnotowano średnią arytmetyczną

m n = 51,21

natomiast

σ n' = 2,54

. Weryfikujemy przy poziomie istotności

α = 0,02

ponieważ obraliśmy dużą próbę wiec $\sigma_{M_n} \approx {{\sigma_n'} \over { \sqrt{n}}} = 0{,}245$ . Musimy zatem wyznaczyć t dla ktorego $P \left ( {{|M_n-m_0|} \over {\sigma_{M_n}}} \ge t \right ) = 0{,}02$
Definiujemy unormowaną zmienną Y:
$Y={{M_n-m_0} \over {\sigma_{M_n}}}$
podstawiamy do wzoru
$P(|Y| \ge t) = 0{,}02$
Z własności bezwzględnej wartości:
$P[(Y \ge t) \vee (Y \le -t)] = 0{,}02$
$P(Y \ge t)+P(Y \le -t) = 0{,}02$
Ponieważ funkcja gęstości jest dla rozkładu N(0,1) parzysta to zachodzi równość:
$P(Y \ge t) = P(Y \le -t)$
$2P(Y \ge t) = 0{,}02$
$P(Y \ge t) = 0{,}01$
Wiadomo, że P(A) to to samo co 1-P(A') więc:

1 - P (Y < t) = 0,01

P (Y < t) = 0,99

A P(Y<x) to dystrybuanta - czyli F(x):

F (t) = 0,99

Teraz w tablicy rozkładu normalnego znajdujemy najmniejszą wartość t dla której F(t) wynosi conajmniej 0,99. Jest to wartość 2,33.
Hipotezę

H 0

należy wiec odrzucić na poziomie istotności

α

jeżeli $|M_n - 54| \ge t \cdot 0{,}245$ , w przeciwnym wypadku przy zadanej istotności

α = 0,02

nie możemy ani potwierdzić hipotezy, ani jej odrzucić.
Zgodnie z naszymi danymi wychodzi:

| M n - 54 | = | 51,21 - 54 | = 2,79

$\sigma_{M_n} \cdot t = 0{,}245 \cdot 2{,}33 = 0{,}57085$
Więc:
$| M_n - 54 | \ge \sigma_{M_n} \cdot t$
$2{,}79 \ge 0{,}57085$
Zatem hipotezę możemy odrzucić (jeśli wyjdzie odwrotnie to piszemy że nie odrzucamy ani nie potwierdzamy - tak właśnie trzeba było zrobić na egzaminie, bo wychodziło <).

METODY NUMERYCZNE I METODY PROBABILISTYCZNE

12.01.2013

WEKTORY I WŁASNOŚCI WŁASNE

Obliczanie wartości własnych i wektorów własnych macierzy.

RACHUNEK PRAWDOPODOBIEŃSTWA

WIELKIE UKŁADY RÓWNAŃ LINIOWYCH

PODSTAWY TEORII WERYFIKACJI HIPOTEZ

Przykład