NUMERYCZNE zagadnienia na egz.docx

(148 KB) Pobierz

1. METODY ROZWIĄZYWANIA RÓWNAŃ LINIOWYCH - OGÓLNIE

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

-------------------------------------------------------------------------------------------------------------------------------------------------------------------

2. METODY ROZWIĄZYWANIA RÓWNAŃ RÓŻNICZKOWYCH METODĄ. ADAMSA I OJLERA

Pierwsza grupa, tj. metody Adamsa-Bashfortha mają charakter ekstrapolacyjny, tzn. współczynnik b0=0 (nie dają równania uwikłanego).

Przykładowo, metoda Adamsa-Bashfortha rzędu trzeciego ma wzór:

Metody Adamsa-Moultona to metody interpolacyjne, wykorzystujące informację o pochodnej w szacowanym punkcie stanu, wymagają więc rozwiązania równania uwikłanego.

Przykładowo, metoda Adamsa-Moultona rzędu trzeciego ma wzór:

Do wystartowania tych metod kilka pierwszych wartości stanu wyznacza się metodą samo startującą (np. Euler albo RK).

------------------------------------------------------

Najprostszy algorytm Eulera (o znaczeniu bardziej dydaktycznym niż praktycznym) wykorzystuje tylko informację dostępną w bieżącym punkcie (np. w punkcie startowym danym przez warunek początkowy jak na rysunkach).

Wynika stąd algorytm Eulera (ekstrapolacyjny, predykcyjny):

Jego odmianą jest algorytm Eulera w postaci uwikłanej (interpolacyjny, korekcyjny):

Wzory te można też wyprowadzić z rozwinięcia x(t ) wokół punktu t=tk w szereg Taylora (co można dalej uogólnić dla wyższego rzędu).

Wadą algorytmu Eulera jest kumulacja błędów w kolejnych krokach i konieczność stosowania małych kroków symulacji Δt z powodu zgrubnego oszacowania kierunku z pierwszej pochodnej

Niech będzie dane równanie różniczkowe zwyczajne dane zależnością: y' = f(x,y) z warunkiem początkowym: y(x0) = y0.

Metoda Eulera polega na zastąpieniu krzywej całkowej: y = y(x) łamaną: M0M1M2... (wierzchołki) składającej się z odcinków prostych.

Punkt rozpoczęcia i-tego odcinka prostej określony jest punktem osiągnięcia przez (i-1)-szy odcinek prostej odciętej: xi = x0 + ih, gdzie h - stały krok obliczeń. Punkt M0 rozpoczęcia pierwszego odcinka określony jest przez warunki początkowe (x0,y0). Współczynnik kątowy (nachylenie i-tego odcinka wyrażony jest wzorem

$tg \alpha_i=f(x_i,y_i) \,$ , gdzie

$y_{i+1}=y_i + \Delta y_i \,$

$\Delta y_i=hf(x_i,y_i) \,$ ,i=0,1,2,...

-------------------------------------------------------------------------------------------------------------------------------------------------------------------

3. METODY ROZWIĄZYWANIA RÓWNAŃ LINIOWYCH METETODĄ RUNGE-KUTTA

Mamy równanie postaci: y' = f(x,y). Znamy początkową wartość y: y(x0) = y0 i chcemy poznać kolejne wartości y.

Przyjmując dowolne h, będące wielkością kroku różniczkowania, iteracyjny wzór na y według metody Rungego-Kutty 4. rzędu to:

yn + 1 = yn + Δyn

${\Delta y_n} = {1 \over 6}h (k_1 + 2k_2 + 2k_3 + k_4)$

gdzie

$k_1 = f \left( x_n, y_n \right)$

$k_2 = f \left( x_n + {h \over 2}, y_n + {1 \over 2} h k_1 \right)$

$k_3 = f \left( x_n + {h \over 2}, y_n + {1 \over 2} h k_2 \right)$

$k_4 = f \left( x_n + h, y_n + h k_3 \right)$

Jak widać, wartość (yn+1) zależy od wartości (yn) i h.

-------------------------------------------------------------------

Metoda RK 2. rzędu

Jawna metoda RK 2, znana jako metoda punktu pośredniego (ang. midpoint method)

$y_{n+1} = y_n + h k_2\,$

oznaczenia takie same.

Istnieje również jej niejawna, ulepszona wersja, zwana metodą Heuna.

$y_{n+1} = y_n + {h \over 2}\left(k_1+k_2\right)\,$

w której pochodna jest obliczana jako średnia arytmetyczna z pochodnych w ostatnim punkcie znanym i kolejnym.

--------------------------------------------------------------------------------------------------------------------------------------------------------------------

4. PRZYBLIŻONE ROZWIĄZYW.RÓWNAŃ NIELINIOWYCH METODĄ REGULA FALSI

Dwie pierwsze iteracje algorytmu, dla przykładowej funkcji (oznaczona na czerwono); na niebiesko zaznaczono sieczne

Regula falsi (łac. fałszywa linia prosta, fałszywa reguła) — algorytm rozwiązywania równań nieliniowych jednej zmiennej.

Na funkcję y = f(x) nakładane są następujące ograniczenia:

W przedziale [a,b] znajduje się dokładnie jeden pojedynczy pierwiastek.

Na końcach przedziału funkcja ma różne znaki: f(a)f(b) < 0.

Pierwsza i druga pochodna istnieją i mają na tym przedziale stałe znaki.

Algorytm przebiega następująco:

Na początku przez punkty A = (a,f(a)) i B = (b,f(b)) przeprowadzana jest cięciwa.

Punkt przecięcia x1 z osią OX jest brany jako pierwsze przybliżenie pierwiastka.

Jeśli to przybliżenie jest wystarczająco dobre, algorytm kończy się.

Jeśli nie, to prowadzona jest cięciwa przez punkty (x1,f(x1)) oraz A lub B – wybierany jest ten punkt, którego rzędna ma znak przeciwny do f(x1). Jednak w praktyce, dzięki ograniczeniu nr 3 już na początku algorytmu wiadomo, który z tych punktów będzie stały, tzn. wybierany za każdym razem.

Następnie wyznaczane jest przecięcie nowo wyznaczonej cięciwy z osią OX (xi) i algorytm powtarza się.

Nazwa metody pochodzi od łacińskich słów: regula1 znaczące zarówno linię prostą, jak i regułę i falsus, fałszywy — metoda bazuje na fałszywym twierdzeniu (regule), że na pewnym przedziale funkcja jest liniowa. Można więc tę nazwę przetłumaczyć zarówno jako "fałszywa linia prosta" jak i "fałszywa reguła" i obydwa te tłumaczenia mają w tym kontekście sens.

Wzory

$x_{1}=\frac{af(b)-bf(a)}{f(b)-f(a)}$

$x_{i+1}=\left\{\begin{matrix} \frac{x_i f(a) - a f(x_i)}{f(a) - f(x_i)} & gdy &f(a)f(x_i)\le 0 \\ \\ \frac{x_i f(b) - b f(x_i)}{f(b) - f(x_i)} & gdy&f(b)f(x_i)<0 \end{matrix}\right.$

dla i = 1,2,.

----------------------------------------------------------------------------------------------------------------------------------------------------------------

5. PRZYBLIŻONE ROZWIĄZYW.RÓWNAŃ NIELINIOWYCH METODĄ SIECZNYCH

----------------------------------------------------------------------------------------------------------------------------------------------------------------

6. PRZYBLIŻONE ROZWIĄZYW.RÓWNAŃ NIELINIOWYCH METODĄ STYCZNYCH NEWTONA

Zadaniem metody jest znalezienie pierwiastka równania zadanej funkcji ciągłej f:

$\mathbb{R} \supset [a,b] \ni x \mapsto f(x) \in \mathbb{R}$

w przedziale [a,b]. A zatem znalezienie takiego $x^{\ast} \in [a,b]$ , które spełnia następujące równanie:

$f(x^{\ast})=0$

Opis metody

Ilustracja działania metody Newtona, pokazane zostały 4 pierwsze kroki.

Metoda Newtona przyjmuje następujące założenia dla funkcji $f\;$ :

W przedziale $[a,b]\;$ znajduje się dokładnie jeden pierwiastek.

Funkcja ma różne znaki na krańcach przedziału, tj. $f\left(a\right) \cdot f\left(b\right) < 0$ .

Pierwsza i druga pochodna funkcji mają stały znak w tym przedziale.

W pierwszym kroku metody wybierany jest punkt startowy $x_1\;$ (zazwyczaj jest to wartość $a, b, 0, \;$ , lub $1\;$ ), z którego następnie wyprowadzana jest styczna w $f(x_1)\;$ . Odcięta punktu przecięcia stycznej z osią OX jest pierwszym przybliżeniem rozwiązania (ozn. $x_2\;$ ).

Jeśli to przybliżenie nie jest satysfakcjonujące, wówczas punkt $x_2\;$ jest wybierany jako nowy punkt startowy i wszystkie czynności są powtarzane. Proces jest kontynuowany, aż zostanie uzyskane wystarczająco dobre przybliżenie pierwiastka

Kolejne przybliżenia są dane rekurencyjnym wzorem:

$x_{k+1} = x_k - \frac{f(x_k)}{f^\prime(x_k)}$

Szacowanie błędu

Błąd k-tego przybliżenia można oszacować poprzez nierówności (x* to dokładna wartość pierwiastka):

$|x^{\ast} - x_k| \leqslant \frac{f(x_k)}{m}$

lub

$|x^{\ast} - x_k| \leqslant \frac{M}{2m}(x^{\ast} - x_{k-1})^2$

gdzie stałe wyznacza się ze wzorów:

$m=\min_{x \in [a,b]} |f'(x)|$

oraz

$M=\max_{x \in [a,b]} |f''(x)|$

Warunek stopu

Metoda Newtona wykonuje iteracyjnie obliczenia, aż do momentu gdy jej wyniki będą satysfakcjonujące. W praktyce stosowanych jest kilka kryteriów warunków stopu dla algorytmu (ε to przyjęta dokładność obliczeń):

1. wartość funkcji w wyznaczonym punkcie jest bliska 0:

$\left| f(x_k) \right| \leqslant \epsilon$

2. odległość pomiędzy kolejnymi przybliżeniami jest dość mała:

$\left| x_{k+1} - x_k \right| \leqslant \epsilon$

3: szacowany błąd jest dostatecznie mały:

$\frac{M}{2m}(x_k - x_{k-1})^2 \leqslant \epsilon$

4. kryterium mieszane (punkty 1 i 2 jednocześnie)

Zbieżność

Metoda Newtona-Raphsona jest metodą o zbieżności kwadratowej - rząd zbieżności wynosi 2 (wyjątkiem są zera wielokrotne dla których zbieżność jest liniowa i wynosi 1), zaś współczynnik zbieżności M/2m. Oznacza to, iż przy spełnionych założeniach błąd maleje kwadratowo wraz z ilością iteracji.

Metoda Newtona jest metodą rozwiązywania równań często używaną w solverach, ze względu na jej szybką zbieżność (w algorytmie liczba cyfr znaczących w kolejnych przybliżeniach podwaja się). Wadą jej jest niestety fakt, iż wspomniana zbieżność nie musi zawsze zachodzić. W wielu przypadkach metoda bywa rozbieżna - przeważnie kiedy punkt startowy jest zbyt daleko od szukanego pierwiastka równania.

Profesjonalne solvery wykorzystują stabilniejsze lecz mniej wydajne metody (jak np. metoda bisekcji) do znalezienia obszarów zbieżności w dziedzinie funkcji, a następnie używają metody Newtona-Raphsona do szybkiego i dokładniejszego obliczenia lokalnego pierwiastka równania. Dodatkowo solvery posiadają zabezpieczenia przed nadmierną ilością wykonywanych iteracji (przekroczenie ustalonej liczby iteracji jest równoznaczne z niepowodzeniem algorytmu w zadanym przedziale).

----------------------------------------------------------------------------------------------------------------------------------------------------------------

7. NUMERYCZNE OBLICZANIE CAŁKI OZNACZONEJ METODĄ PROSTOKĄTÓW

Metoda prostokątów[edytuj]

Prawdopodobnie najprostszym wzorem jest metoda punktu środkowego (midpoint rule):

$\int\limits_{x_*}^{x_*+h} f(x) dx \approx h f\left( x_* + \frac h 2 \right)$

Jeśli funkcja f(x) zmienia się w niewielkim stopniu na przedziale (x * ,x * + h), reguła taka da dobre przybliżenie całki.

----------------------------------------------------------------------------------------------------------------------------

8. NUMERYCZNE OBLICZANIE CAŁKI OZNACZONEJ METODĄ SIMPSONA

Metoda parabol (Simpsona)

Wymaga podzielenia przedziału całkowania na parzystą liczbę podprzedziałów, tzn.

$h = \frac {b-a} {2n}$

dla uproszcze...

Plik z chomika:

EMICHAEL

Inne pliki z tego folderu:

interpolacja.doc (28 KB)
interpolacja.pdf (118 KB)
matoda stycznych newtona.doc (72 KB)
metoda eulera i adamsa.pdf (237 KB)
metoda prostokątów trapezów i simpsona.doc (55 KB)

NUMERYCZNE zagadnienia na egz.docx

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: