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=t_k 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(x₀) = y₀.

Metoda Eulera polega na zastąpieniu krzywej całkowej: y = y(x) łamaną: M₀M₁M₂... (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: x_i = x₀ + ih, gdzie h - stały krok obliczeń. Punkt M₀ rozpoczęcia pierwszego odcinka określony jest przez warunki początkowe (x₀,y₀). Współczynnik kątowy (nachylenie i-tego odcinka wyrażony jest wzorem

, gdzie

,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(x₀) = y₀ 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:

y_{n + 1} = y_n + Δy_n

gdzie

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

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

Metoda RK 2. rzędu

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

oznaczenia takie same.

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

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 x₁ 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 (x₁,f(x₁)) oraz A lub B – wybierany jest ten punkt, którego rzędna ma znak przeciwny do f(x₁). 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 (x_i) i algorytm powtarza się.

Nazwa metody pochodzi od łacińskich słów: regula¹ 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

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:

w przedziale [a,b]. A zatem znalezienie takiego , które spełnia następujące równanie:

Opis metody

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

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

W przedziale znajduje się dokładnie jeden pierwiastek.

Funkcja ma różne znaki na krańcach przedziału, tj. .

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

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

Jeśli to przybliżenie nie jest satysfakcjonujące, wówczas punkt 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:

Szacowanie błędu

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

lub

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

oraz

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:

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

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

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):

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.

dla uproszczenia oznaczamy:

x_i = a + ih oraz f_i = f(x_i)

wykonując całkowanie wielomianu interpolacyjnego Lagrange'a z 3 kolejnych punktów otrzymujemy wzór Simpsona:

dla całego przedziału (a,b) otrzymujemy:

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

9. NUMERYCZNE OBLICZANIE CAŁKI OZNACZONEJ METODĄ TRAPEZU

Metoda trapezów polega na tym, że figurę ABCD zastępujemy figurą złożoną z trapezów wpisanych, tzn. krzywą aproksymujemy linią łamaną w nią wpisaną. Przedział całkowania (a,b) dzielimy przy tym na n równych części o długościach:

.

Punktami podziału (końcami części) są wówczas:

Wówczas pole figury złożonej z trapezów wynosi

gdzie

y_i: = f(x_i) – wartości funkcji w punktach podziału.

Stąd otrzymujemy wzór przybliżony w metodzie trapezów:

Oszacowanie błędu tej metody wynosi

Gdzie

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

10. INTERPOLACJA WIELOMIANOWA LAGRANŻA

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.

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

11. INTERPOLACJA WIELOMIANOWA NEWTONA

Interpolacja wielomianowa

Interpolacja liniowa

 Osobny artykuł: Interpolacja wielomianowa.

Interpolacja wielomianowa polega na przybliżaniu funkcji za pomocą wielomianów. Metoda ta była rozwinięta przez Josepha Lagrange'a a jej podstawą jest twierdzenie, że

Dla danych n + 1 punktów pomiarowych istnieje jedyny wielomian stopnia co najwyżej n interpolujący te punkty.

Zwykle zakłada się o funkcji interpolowanej, że jest ciągła, choć często dodaje się warunki różniczkowalności, które umożliwiają dokładniejsze oszacowania błędów przybliżeń. Najprostszym przypadkiem jest interpolacja liniowa, zadanie interpolacji dla dwóch węzłów x₀ i x₁. Rozwiązaniem w klasie wielomianów pierwszego stopnia jest wtedy funkcja liniowa, której wykres przechodzi przez punkty (x₀,f(x₀)) i (x₁,f(x₁) (por. rysunek).

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