Metody Numeryczne ver

SAVE OFFLINE

Autorami niniejszego opracowania są: Daniel Wlazło, Piotr Poskart, Adam Radomski, Jakub Pierewoj, Mateusz Garczyk (MEL AiR 2011)

Część Pierwsza – Metody Jawne (Daniel W.) Postać standardowa równania różniczkowego =

,

czyli: =

,

=

,

=

,

,

, …



,

, …



, …

, …



Co to jest rząd metody? Rząd dokładności metody numerycznej jest to ostatnia potęga przy rozkładzie w szeregu Taylora, której odpowiada rozwiązanie uzyskane za pomocą danej metody. Jest to także kryterium warunkujące to ilokrotnie (w której potędze) będzie nam spadał błąd.

Podstawowe metody jednokrokowe: - metoda Eulera:

=

- metoda RK2:

+ℎ∗

=ℎ∗

=ℎ∗ =

- metoda RK4:

=ℎ∗ =ℎ∗

+

=ℎ∗

1 2

;

;

+

+ ;

1 + ℎ; 2

1 + ℎ; 2

+ +

1 2

1 2

=

=ℎ∗ +

+ ℎ;

1 6

+2

+

+2

+

Jak w metodzie jednokrokowej osiąga się rząd dokładności? W metodach jednokrokowych R-K, wysoki rząd dokładności uzyskuje się wielokrotnym wywołaniem funkcji prawej strony w każdym kroku czasowym. Rząd dokładności nie jest jednak taki sam jak liczba wywołań (dla metod powyżej 4 rzędu). Dlatego, w praktyce, metod powyżej 5 rzędu się nie stosuje (zysk z wyższego rzędu dokładności jest skutecznie redukowany przez liczbę wywołań funkcji). Jak w metodzie wielokrokowej osiąga się rząd dokładności? W metodach wielokrokowych wysoki rząd dokładności uzyskuje się poprzez wykorzystanie historii rozwiązań i funkcji prawych stron. Pozwala to znacząco zredukować liczbę obliczeń (jedynym problemem może być przechowywanie historii rozwiązań). Jak odróżnić metodę jawną od niejawnej? Ogólnie zapisana metoda wielokrokowa: %

= ! "# ∗

$#

#&

kombinacja liniowa poprzednich rozwiązań równania

gdzie: $#

=

$# ,

)

%

+ ! '# ∗ #&(

$#

kombinacja liniowa rozwiązań prawej strony $# * …

)

$# *

Jeżeli '( ≠ 0 to jest uwikłane po obu stronach równania. Oznacza to, że metoda jest niejawna. Jeżeli '( = 0 to mamy do czynienia z metodą jawną. Zatem (w skrócie) jeżeli w równaniu opisującym metodę pojawi się człon jest niejawna. Podstawowe jawne metody wielokrokowe: Metody Adamsa-Bashforda (ekstrapolacyjne): Ogólny wzór na AB: AB2: AB3:

=

=

+

+

.

.

=

/0 $/012

+ ∑%#& '# ∗

/0 $ 3/012 $4/015

$#

oznacza to że metoda

AB4:

=

+

. 44/0 $46/012

7/015 $6/018

Czym się różnią metody wielokrokowe od R-K? Metody wielokrokowe są metodami wykorzystującymi historię rozwiązania i to na ich podstawie poprawiają dokładność. Metody R-K są metodami jednokrokowymi, u których źródłem wzrostu dokładności jest częstsze odwoływanie się do funkcji prawych stron. Metody RK są metodami samostartującymi, metody AB potrzebują kilku punktów startowych (wyznaczonych np. z metody AB).

Część Druga – Metody Niejawne (Piotr P.) Niejawny schemat metod wielokrokowych w rozwiązywaniu równań różniczkowych

r

r

j= 1

j=0

Y k+ 1= ∑ α j Y k + 1− j + h ∑ β j F (t k+ 1− j , y k + 1− j ) Ogólny schemat metod wielokrokowych:

W drugiej sumie pojawia się składnik: β0 F (t k+ 1 , y k + 1) , co oznacza, że schemat jest NIEJAWNY i powyższy wzór określa wektor Y k+ 1 w sposób uwikłany. Jeśli β0≠ 0 to w każdym kroku czasowym trzeba rozwiązać na ogół nieliniowy układ równań algebraicznych dla elementów wektora Y k+ 1 .

Jednymi z metod niejawnych są metody Adamsa-Moultona. −

konstruowane w oparciu o interpolację – tak jak w metodach Adamsa-Bashforta + dodatkowa interpolacja dla węzła ( F k+ 1 , t k + 1 ) t k+ 1

Y k+ 1= Y k + − formuła metody A-M otrzymywana tak samo jak A-B: qΦ -wielomian interpolacyjny

∫

tk

qΦ (τ ) d τ ,gdzie

Metoda trapezów – Metoda Adamsa-Moultona II rzędu (r=2, krok h): Y k+ 1= Y k +

1 h( F k + F k+ 1) 2

przy czym : F k+ 1= F (t k+ 1 , Y k+ 1)

// wzór AM2 -na pamięć!

Wyjaśnij pochodzenie nazwy : metoda trapezów, ponieważ każdy kolejny krok jest równoważny obliczeniu całki metodą trapezów pomiędzy t k i t k+ 1 z funkcji pochodnej i dodaniu jej do wartości w poprzednim kroku..

Metoda Adamsa-Moultona III rzędu (r=3, krok h): Y k+ 1= Y k +

h ( 5Fk+ 1+ 8F k − F k− 1 ) 12

F k+ 1= F (t k+ 1 , Y k+ 1)

Y k+ 1= Y k +

( Metoda Adamsa-Moultona IV rzędu (r=4)):

1 h( 9Fk+ 1+ 19F k − 5Fk − 1+ F k− 2 ) 24

Wszystkie powyższe formuły są uwikłane ze względu na Y k+ 1 i w celu znalezienia rozwiązania trzeba rozwiązać najpierw na ogół nieliniowe równanie (układ równań)

Metody niejawne stodowane są często w metodach predyktor – korektor, metoda niejawna pełni rolę korektora i wykorzystuje wynik metody jawnej do poprawy wyniku np: P k+ 1= Y k +

Y k+ 1= Y k +

1 h [ 3F(t k , Y k )− F (t k− 1 , Y k− 1)] 2

- predyktor -metoda AB2 (jawna)

1 h[ F (t k+ 1 , P k + 1 )+ F (t k ,Y k )] 2

- korektor – metoda AM2 (niejawna)

metoda ta (predyktor-korektor) jest de facto jawna

Różnica między korektorem a predyktorem pozwala oszacować błąd względem ścisłego rozwiązania : −1 Y (t k + 1)− Y k+ 1≈ (Y k + 1 − P k+ 1) 6 Y (t k + 1) - rozw. ścisłe (wyprowadzenie w notatkach)

Metody (wielokrokowe) inne niż Adamsa-Moultona – metody Milne-Simpsona: użycie metody jawnej i niejawnej Milne-Simpsona jako predyktor-korektor pozwala na oszacowanie błędu dla predyktora i wprowadzenie kroku pośredniego ulepszającego predyktor...i z tego wychodzi „ulepszona metoda Mine-Simpsona”

Jak w metodach wielokrokowych osiąga się wyższy rząd dokładności i czym to się różni od RK4? W metodach wielokrokowych wyższy rząd dokładności osiąga się przez odwołanie do rozwiązań w poprzednich krokach, w przeciwienstwie do RK4 która korzysta z aktualnych wartości rozwiązania; także poprzez odwołanie się do rozwiązania które chcemy wyliczyć czyli uwikłanie rozwiązaniazwiększa ono koszty obliczeń ale polepsza dokładność. W metodach wielokrokowych unikamy tez zbyt częstego odwolywania się do wektora prawych stron który począwszy od RK4 rosnie szybciej niż rząd metody RK co zwiększa koszty obliczeń. Zwiększyć dokładnośc można również łącząc metody jawne i niejawne czyli stosując metodę predyktor-korektor.

Część trzecia – Stabilność (Adam R.) I twierdzenie Dahlquista Maksymalny rząd dokładności metody 0-stabilnej wynosi co najwyżej k+1 dla k nieparzystego i k+2 dla k parzystego. Jeżeli β0=0 to rząd metody wynosi co najwyżej k.

II twierdzenie Dahlquista (bariera Dahlquista) Nie ma liniowych metod jawnych które są A-stabilne. Ponadto A-stabilna niejawna metoda wielokrokowa liniowa jest co najwyżej rzędu drugiego.

Co to znaczy że metoda jest zgodna? Metoda postaci: %

= ! "#

$#

#&

%

+ ℎ ! '# ′ #&(

$#

Jest zgodna gdy spełnione są następujące warunki: %

%

%

#&

#&

#&(

! "# = 1 :; ? L-macierz dolna trójkątna z zerową diagonalną główną \: _[# = 0 , X ≤ ? uV] = aV] , X < ? U-macierz górna trójkątna z zerową diagonalną główną a: R[# = 0 , X ≥ ? S + \ + a d = e Sd = − \ + a d + e d = −S$f \ + a d + S$f e = −S$f \ + a d + S$f e ; gh = −S$f \ + a ; ih = S$f e d j[

[$

1 = k − !