METODY NUMERYCZNE I PROBABILISTYCZNE

Uniwersytet Technologiczno Humanistyczny w Radomiu

Metody numeryczne

Metody Numeryczne zajmują się szukaniem i udoskonalaniem sposobów rozwiązywania zadań matematyki za pomocą skończonej liczby działań arytmetycznych i logicznych. Praktyczne wykorzystanie metod numerycznych już od lat wiąże się z maszynami cyfrowymi. Współczesne metody numeryczne są konstruowane z myślą o ich realizacji na maszynach cyfrowych. Wykonanie obliczeń numerycznych na komputerach tworzy nową klasę problemów. Wynikają one między innymi ze stosowanej arytmetyki. Każda liczba w pamięci komputera jest reprezentowana przez swoje skończone rozwinięcie. W każdym działaniu arytmetycznym powstaje błąd, ponieważ wynik jest również skończonym rozwinięciem. Dlatego nie wolno nam przyjmować ich bezkrytycznie, i uważać je za poprawne tylko dlatego, że obliczone zostały przez komputer

Metody probabilistyczne i statystyka

Metody probabilistyczne polegają na zastosowaniu rachunku prawdopodobieństwa do rozwiązywania problemów kombinatorycznych. Na przykład zamiast konstruować explicite jakiś obiekt o żądanych własnościach (kolorowanie grafu, strategię wygrywającą w grze, kod do przesyłania wiadomości itp.) pokazujemy, że losowy wybrany obiekt posiada taką własność z niezerowym prawdopodobieństwem. Tego typu niekonstruktywne techniki, wprowadzone po raz pierwszy przez Paula Erdösa, okazały się niezwykle skuteczne zarówno w czystej matematyce (m. in. w kombinatoryce, grafach losowych, geometrii), jak i w informatyce teoretycznej i algorytmice (np. w teorii złożoności czy algorytmach randomizowanych). Obecnie rachunek prawdopodobieństwa to podstawowe narzędzie z przybornika każdego szanującego się kombinatoryka (i nie tylko).

Metody probabilistyczne i statystyka - test sprawdzający wiedzę

index.htm

Metody probabilistyczne i statystyka - rozwiązania testów

Test nr 1 - 100%

Test nr 2 - 100%

Test nr 3 - 100%

Test nr 4 - 100%

Test nr 5 - 100%

Test nr 6 - 100%

Test nr 7 - 100%

Test nr 8 - 100%

Test nr 9 - 100%

Test nr 10 - 100%

Przykładowe metody numeryczne:

Interpolacja liniowa szczególny przypadek interpolacji za pomocą funkcji liniowej. Jeśli $x$ określa wartość z przedziału $x_0 < x < x_1$ , a $y_0 = f(x_0)$ i $y_1 = f(x_1)$ tablicę wartości danej funkcji, oraz $h = x_1 - x_0$ odstęp pomiędzy argumentami, wówczas liniową interpolację wartości $L(x)$ funkcji $f$ otrzymujemy jako:

$L(x) = y_0 + \frac{y_1 - y_0}{h}(x-x_0).$

Metoda Monte Carlo (MC) jest stosowana do modelowania matematycznego procesów zbyt złożonych (obliczania całek, łańcuchów procesów statystycznych), aby można było przewidzieć ich wyniki za pomocą podejścia analitycznego. Istotną rolę w metodzie MC odgrywa losowanie (wybór przypadkowy) wielkości charakteryzujących proces, przy czym losowanie dokonywane jest zgodnie z rozkładem, który musi być znany.

Typowym przykładem może być modelowanie wyniku zderzenia cząstki o wysokiej energii z jądrem złożonym, gdzie każdy akt zderzenia elementarnego (z pojedynczym nukleonem jądra) modelowany jest oddzielnie poprzez losowanie liczby, rodzaju, kąta emisji, energii itp. cząstek wtórnych emitowanych w wyniku takiego zderzenia. Następnym etapem jest modelowanie losu każdej z cząstek wtórnych (w wyniku kolejnego losowania prawdopodobieństwa oddziaływania lub wyjścia z jądra). Kontynuując taką procedurę można otrzymać pełny opis "sztucznie generowanego" procesu złożonego. Po zebraniu dostatecznie dużej liczby takich informacji można zestawić ich charakterystyki z obserwowanymi wynikami doświadczalnymi, potwierdzając lub negując słuszność poczynionych w całej procedurze założeń.

Metoda została opracowana i pierwszy raz zastosowana przez Stanisława Ulama.

Interpolacja wielomianowa, nazywana też interpolacją Lagrange'a, od nazwiska pioniera badań nad interpolacją Josepha Lagrange'a, lub po prostu interpolacją jest metodą numeryczną przybliżania funkcji tzw. wielomianem Lagrange'a stopnia n, przyjmującym w n+1 punktach, zwanych węzłami interpolacji wartości takie same jak przybliżana funkcja.

Interpolacja jest często stosowana w naukach doświadczalnych, gdzie dysponuje się zazwyczaj skończoną liczbą danych do określenia zależności między wielkościami.

Zgodnie z twierdzeniem Weierstrassa dowolną funkcję y=f(x) ciągłą na przedziale domkniętym można dowolnie przybliżyć za pomocą wielomianu odpowiednio wysokiego stopnia.

Szybka transformacja Fouriera (ang. FFT od Fast Fourier Transform) to algorytm liczenia dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej.

Czasem używana jest też forma szybka transformata Fouriera w odniesieniu do tej metody. Ściśle jednak transformacja jest przekształceniem, a transformata wynikiem tego przekształcenia.

Niech x₀, ...., x_N-1 będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera jest określona wzorem

$X_k = \sum_{n=0}^{N-1} x_n e^{-{2\pi i \over N} nk } \qquad k = 0,\dots,N-1.$

Obliczanie tych sum za pomocą powyższego wzoru zajęłoby O(N²) operacji.

Algorytmy (jak algorytm Cooleya-Tukeya) obliczające szybką transformację Fouriera bazują na metodzie dziel i zwyciężaj rekurencyjnie dzieląc transformatę wielkości N = N₁N₂ na transformaty wielkości N₁ i N₂ z wykorzystaniem O(N) operacji mnożenia.

Całkowanie metodą Simpsona – jedna z metod przybliżania wartości całki oznaczonej funkcji rzeczywistej.

Metoda ma zastosowanie do funkcji stablicowanych w nieparzystej liczbie równo odległych punktów (wliczając końce przedziału całkowania). Metoda opiera się na przybliżaniu funkcji całkowanej przez interpolację wielomianem drugiego stopnia.

Znając wartości $y_0,\ y_1,\ y_2$ funkcji $f(x)$ w 3 punktach $x_0,\ x_1,\ x_2$ (przy czym $x_2-x_1 = x_1-x_0 = h\;$ ), przybliża się funkcję wielomianem Lagrange'a i, całkując w przedziale $[x_0,x_2]$ , otrzymuje przybliżoną wartość całki:

$\int\limits_{x_0}^{x_2}f(x)dx\approx \frac h 3 (y_0+4y_1+y_2)$

Błąd, który przy tym popełniamy, jest równy: $R = \frac{1}{90} h^5 |f^{(4)}(c)|$ , gdzie:

$c \in [x_0; x_2]$ .

Nie znamy położenia punktu c, więc posługujemy się poniższym szacowaniem, mającym zastosowanie w obliczeniach numerycznych:

$R \leqslant \frac{1}{90} h^5 \max_{x \in [x_0; x_2]} |f^{(4)}(x)|$ .

Kwadraturami Gaussa nazywamy metody całkowania numerycznego polegające na takim wyborze wag $w_1, w_2, \ldots, w_n$ i węzłów interpolacji $t_1, t_2, \ldots, t_n \in [a,b]$ aby wyrażenie

$\sum_{i=1}^n w_i f(t_i)$

najlepiej przybliżało całkę

$I(f) = \int\limits_a^b w(x) f(x) dx$

gdzie $f$ jest dowolną funkcją określoną na odcinku $[a,b]$ , a $w$ jest tzw. funkcją wagową spełniającą warunki

$w(x)\ge 0$ ,
$\forall_{k\in \mathbb{N}} \int\limits_a^b x^k w(x) dx$ jest skończona,
Jeżeli $p$ jest wielomianem takim, że $\forall_{x\in [a,b]}\;p(x)\ge 0$ , to jeśli $\int\limits_a^b w(x) p(x) dx=0$ , mamy wtedy $p\equiv0$ .