Metody Rungego-Kutty - Runge–Kutta methods

Równania różniczkowe
Równania różniczkowe Naviera-Stokesa stosowane do symulacji przepływu powietrza wokół przeszkody
Zakres Nauki przyrodnicze Inżynieria Astronomia Fizyka Chemia Biologia Geologia Matematyka stosowana Mechanika kontinuum Teoria chaosu Układy dynamiczne Nauki społeczne Ekonomia Dynamika populacji
Klasyfikacja
Rodzaje Zwykły Częściowy Różniczkowo-algebraiczny Całko-różnicowy Frakcyjny Liniowy Nieliniowy Według typu zmiennej Zmienne zależne i niezależne Autonomiczny Złożony Połączone / Oddzielone Dokładny Jednorodne  / Niejednorodne Cechy Zamówienie Operator Notacja
Związek z procesami Różnica (dyskretny analog) Stochastyczny Stochastyczne częściowe Opóźnienie
Rozwiązanie
Istnienie i wyjątkowość Twierdzenie Picarda-Lindelöfa Twierdzenie o istnieniu Peano Twierdzenie o istnieniu Carathéodory'ego Twierdzenie Cauchy'ego-Kowalewskiego
Tematy ogólne wroński Portret fazowy Przestrzeń fazowa Lapunow  / Asymptotyczna  / Stabilność wykładnicza Wskaźnik konwergencji Seria  / Rozwiązania integralne Całkowanie numeryczne Funkcja delta Diraca
Metody rozwiązania Kontrola Metoda charakterystyki Euler Wykładnicza formuła odpowiedzi Różnica skończona  ( Crank-Nicolson ) Końcowy element Nieskończony element Skończona objętość Galerkin Pietrow-Galerkin Czynnik integrujący Przekształcenia całkowe Teoria zaburzeń Runge-Kutta Separacja zmiennych Nieokreślone współczynniki Zmienność parametrów
Ludzie Izaak Newton Gottfrieda Leibniza Leonhard Euler Emil Picard Józef Maria Hoene-Wroński Ernst Lindelöf Rudolf Lipschitz Augustin-Louis Cauchy John Crank Phyllis Nicolson Carl David Tolmé Runge Martin Kutta
v T mi

W analizie numerycznej , że Algorytm Rungego-Kutty ( angielski: / r ʊ ŋ ə k ʊ t ɑː / ( słuchać ) RUUNG -ə- KUUT -tah ) są rodziną ukrytych i jawnych metod iteracyjnych, które obejmują dobrze znaną procedurę zwaną metodą Eulera , używaną w dyskretyzacji czasowej do przybliżonych rozwiązań równań różniczkowych zwyczajnych . Metody te zostały opracowane około 1900 roku przez niemieckich matematyków Carla Runge i Wilhelma Kuttę .

Metoda Rungego-Kutty

Najbardziej znany członek rodziny Runge-Kutty jest ogólnie określany jako „RK4”, „klasyczna metoda Runge-Kutta” lub po prostu jako „metoda Runge-Kutta”.

Niech problem z wartością początkową będzie określony w następujący sposób:

${\ Displaystyle {\ Frac {dy} {dt}} = f (t, r), \ quad r (t_ {0}) = r_ {0}.}$

Oto nieznana funkcja (skalarna lub wektorowa) czasu , którą chcielibyśmy przybliżyć; powiedziano nam, że , tempo, w jakim zmienia się, jest funkcją i od siebie. Na początku odpowiednia wartość to . Funkcja i początkowe warunki , podane. ${\displaystyle y}$${\displaystyle t}$${\displaystyle {\frac {dy}{dt}}}$${\displaystyle y}$${\displaystyle t}$${\displaystyle y}$${\displaystyle t_{0}}$${\displaystyle y}$${\displaystyle y_{0}}$${\displaystyle f}$ ${\displaystyle t_{0}}$${\displaystyle y_{0}}$

Teraz wybierz rozmiar kroku h > 0 i zdefiniuj

${\ Displaystyle {\ zacząć {wyrównany} y_ {n + 1} i = y_ {n} + {\ Frac {1} {6}} h \ lewo (k_ {1} + 2 k_ {2} + 2 k_ {3} +k_{4}\prawo),\\t_{n+1}&=t_{n}+h\\\end{wyrównany}}}$

dla n = 0, 1, 2, 3, ..., używając

${\ Displaystyle {\ zacząć {wyrównany} k_ {1} i = \ f (t_ {n}, y_ {n}), \ \ k_ {2} i = \ f \ lewo (t_ {n} + {\ Frac {h}{2}},y_{n}+h{\frac {k_{1}}{2}}\right),\\k_{3}&=\ f\left(t_{n}+{ \frac {h}{2}},y_{n}+h{\frac {k_{2}}{2}}\prawo),\\k_{4}&=\ f\left(t_{n} +h,y_{n}+hk_{3}\prawo).\end{wyrównany}}}$

(Uwaga: powyższe równania mają różne, ale równoważne definicje w różnych tekstach).

Oto przybliżenie RK4 , a następna wartość ( ) jest określona przez wartość bieżącą ( ) plus średnią ważoną czterech przyrostów, gdzie każdy przyrost jest iloczynem wielkości przedziału h i szacunkowego nachylenia określonego przez funkcja f po prawej stronie równania różniczkowego. ${\displaystyle y_{n+1}}$${\ Displaystyle y (t_ {n + 1})}$${\displaystyle y_{n+1}}$${\ Displaystyle y_ {n}}$

• ${\displaystyle k_{1}}$jest nachyleniem na początku przedziału, przy użyciu ( metoda Eulera );${\displaystyle y}$
• ${\displaystyle k_{2}}$jest nachyleniem w punkcie środkowym przedziału, używając i ;${\displaystyle y}$${\displaystyle k_{1}}$
• ${\displaystyle k_{3}}$to znowu nachylenie w punkcie środkowym, ale teraz używamy i ;${\displaystyle y}$${\displaystyle k_{2}}$
• ${\displaystyle k_{4}}$jest nachyleniem na końcu przedziału, używając i .${\displaystyle y}$${\displaystyle k_{3}}$

Przy uśrednianiu czterech zboczy większą wagę przywiązuje się do zboczy w punkcie środkowym. Jeżeli jest niezależna od , tak że równanie różniczkowe jest równoważne całce prostej, to RK4 jest regułą Simpsona . ${\displaystyle f}$${\displaystyle y}$

Metoda RK4 jest metodą czwartego rzędu, co oznacza, że lokalny błąd obcięcia jest rzędu , podczas gdy całkowity skumulowany błąd jest rzędu . ${\ Displaystyle O (h ^ {5})}$${\ Displaystyle O (h ^ {4})}$

W wielu praktycznych zastosowaniach funkcja jest niezależna od (tzw. system autonomiczny lub system niezmienniczy w czasie, zwłaszcza w fizyce), a ich przyrosty w ogóle nie są obliczane i nie są przekazywane do funkcji , a do wykorzystania jest jedynie końcowa formuła . ${\displaystyle f}$${\displaystyle t}$${\displaystyle f}$${\displaystyle t_{n+1}}$

Wyraźne metody Runge-Kutta

Rodzina wyraźnych metod Runge-Kutty jest uogólnieniem metody RK4 wspomnianej powyżej. Jest to podane przez

${\ Displaystyle y_ {n + 1} = y_ {n} + h \ suma _ {i = 1} ^ {s} b_ {i} k_ {i}}$

gdzie

${\ Displaystyle {\ zacząć {wyrównany} k_ {1} i = f (t_ {n}, y_ {n}), \ \ k_ {2} i = f (t_ {n} + c_ {2} h, y_ {n}+h(a_{21}k_{1})),\\k_{3}&=f(t_{n}+c_{3}h,y_{n}+h(a_{31}k_ {1}+a_{32}k_{2})),\\&\ \ \vdots \\k_{s}&=f(t_{n}+c_{s}h,y_{n}+h( a_{s1}k_{1}+a_{s2}k_{2}+\cdots +a_{s,s-1}k_{s-1})).\end{aligned}}}$

(Uwaga: powyższe równania mogą mieć różne, ale równoważne definicje w niektórych tekstach).

Aby określić konkretną metodę należy podać liczbę całkowitą s (liczbę stopni) oraz współczynniki a _ij (dla 1 ≤ j < i ≤ s ), b _i (dla i = 1, 2, ..., a ) i c _i (dla i = 2, 3, ..., s ). Matryca [ _ij ] nazywa się matrycę Runge-Kutty , natomiast b _I i c _i są znane jako obciążników i węzłami . Dane te są zwykle ułożone w urządzeniu mnemonicznym, znanym jako tableau Butchera (od Johna C. Butchera ):

${\ Displaystyle 0}$
${\displaystyle c_{2}}$	${\ Displaystyle a_ {21}}$
${\displaystyle c_{3}}$	${\ Displaystyle a_ {31}}$	${\ Displaystyle a_ {32}}$
${\displaystyle \vdots}$	${\displaystyle \vdots}$		${\displaystyle \ddots}$
${\displaystyle c_{s}}$	${\displaystyle a_{s1}}$	${\displaystyle a_{s2}}$	${\displaystyle \cdots}$	${\displaystyle a_{s,s-1}}$
	${\displaystyle b_{1}}$	${\displaystyle b_{2}}$	${\displaystyle \cdots}$	${\displaystyle b_{s-1}}$	${\displaystyle b_{s}}$

Taylor serii przedstawiono rozszerzalności metoda Runge-Kutty są zgodne wtedy i tylko wtedy

${\ Displaystyle \ suma _ {i = 1} ^ {s} b_ {i} = 1.}$

Istnieją również wymagania towarzyszące jeśli wymaga metody, aby mieć pewien porządek s , co oznacza, że lokalny błąd obcięcia wynosi O ( h ^{p +1} ). Można je wyprowadzić z samej definicji błędu obcięcia. Na przykład metoda dwuetapowa ma porządek 2, jeśli b ₁ + b ₂ = 1, b ₂ c ₂ = 1/2, a b ₂ a ₂₁ = 1/2. Zauważ, że popularnym warunkiem określania współczynników jest

${\ Displaystyle \ suma _ {j = 1} ^ {i-1} a_ {ij} = c_ {i} {\ tekst {dla}} i = 2, \ ldots, s.}$

Sam ten warunek nie jest jednak ani wystarczający, ani konieczny do zachowania spójności.

Ogólnie rzecz biorąc, jeśli jawna metoda -etapowa Runge-Kutta ma porządek , można udowodnić, że liczba etapów musi spełniać , a jeśli , to . Nie wiadomo jednak, czy granice te są ostre we wszystkich przypadkach; na przykład wszystkie znane sposoby rzędu 8 mają co najmniej 11 etapów, chociaż możliwe jest, że istnieją sposoby z mniejszą liczbą etapów. (Związana powyżej sugeruje, że nie może być metodą z 9 etapów, ale może to być również, że granica nie jest po prostu ostry). Rzeczywiście, jest problemem otwartym, co precyzyjnie minimalna liczba etapów jest dla wyraźnego Runge-Kutta metoda, aby mieć porządek w tych przypadkach, w których nie odkryto jeszcze metod, które spełniają powyższe granice równością. Niektóre znane wartości to: ${\displaystyle s}$${\displaystyle p}$${\displaystyle s\geq p}$${\displaystyle p\geq 5}$${\displaystyle s\geq p+1}$${\displaystyle s}$${\displaystyle p}$

${\ Displaystyle {\ rozpocząć {tablica} {c | cccccccc} p i 1 i 2 i 3 i 4 i 5 i 6 i 7 i 8 \ \ \ hline \ min s i 1 i 2 i 3 i 4 i 6 i 7 i 9 i 11 \ koniec {tablica}}}$

Z powyższych granic dających się udowodnić wynika, że ​​nie możemy znaleźć metod zleceń, które wymagają mniejszej liczby etapów niż metody, które już znamy dla tych zleceń. Można sobie jednak wyobrazić, że możemy znaleźć metodę porządkowania, która ma tylko 8 etapów, podczas gdy jedyne znane dziś mają co najmniej 9 etapów, jak pokazano w tabeli. ${\displaystyle p=1,2,\ldots,6}$${\displaystyle p=7}$

Przykłady

Metoda RK4 mieści się w tych ramach. Jego obrazem jest

0
1/2	1/2
1/2	0	1/2
1	0	0	1
	1/6	1/3	1/3	1/6

Niewielka odmiana „metody” Rungego-Kutty jest również spowodowana Kuttą w 1901 roku i nazywana jest regułą 3/8. Główną zaletą tej metody jest to, że prawie wszystkie współczynniki błędów są mniejsze niż w popularnej metodzie, ale wymaga ona nieco więcej FLOP (operacji zmiennoprzecinkowych) na krok czasowy. Jego obraz rzeźnika to

0
1/3	1/3
2/3	-1/3	1
1	1	-1	1
	1/8	3/8	3/8	1/8

Jednak najprostszą metodą Runge-Kutty jest metoda (w przód) Eulera , podana wzorem . Jest to jedyna spójna jawna metoda Runge-Kutta z jednym etapem. Odpowiednia tablica to ${\ Displaystyle y_ {n + 1} = y_ {n} + hf (t_ {n}, y_ {n})}$

0
	1

Metody drugiego rzędu z dwoma etapami

Przykład metody drugiego rzędu z dwoma etapami dostarcza metoda punktu środkowego :

${\ Displaystyle y_ {n + 1} = y_ {n} + hf \ lewo (t_ {n} + {\ Frac {1} {2}} h, y_ {n} + {\ Frac {1} {2} }hf(t_{n},\ y_{n})\prawo).}$

Odpowiednia tablica to

0
1/2	1/2
	0	1

Metoda punktu środkowego nie jest jedyną metodą Runge-Kutty drugiego rzędu z dwoma etapami; istnieje rodzina takich metod, sparametryzowana przez α i określona wzorem

${\ Displaystyle y_ {n + 1} = y_ {n} + h {\ bigl (} (1-{\ tfrac {1} {2 \ alfa}}) f (t_ {n}, y_ {n}) + {\tfrac {1}{2\alpha }}f(t_{n}+\alpha h,y_{n}+\alpha hf(t_{n},y_{n})){\bigr )}.}$

Jego obraz rzeźnika to

0
${\ Displaystyle \ alfa}$	${\ Displaystyle \ alfa}$
	${\ Displaystyle (1-{\ tfrac {1} {2 \ alfa}})}$	${\displaystyle {\tfrac {1}{2\alfa}}}$

W tej rodzinie podaje metodę punktu środkowego i jest metodą Heuna . ${\ Displaystyle \ alfa = {\ tfrac {1} {2}}}$${\ Displaystyle \ alfa =1}$

Posługiwać się

Jako przykład rozważmy dwustopniową metodę Runge-Kutty drugiego rzędu z α = 2/3, znaną również jako metoda Ralstona . Daje to tableau

	0
	2/3	2/3
		1/4	3/4

z odpowiednimi równaniami

${\ Displaystyle {\ zacząć {wyrównany} k_ {1} i = f (t_ {n}, \ y_ {n}), \ \ k_ {2} i = f (t_ {n} + {\ tfrac {2} {3}}h,\ y_{n}+{\tfrac {2}{3}}hk_{1}),\\y_{n+1}&=y_{n}+h\lewo({\tfrac {1}{4}}k_{1}+{\tfrac {3}{4}}k_{2}\right).\end{aligned}}}$

Ta metoda służy do rozwiązywania problemu z wartością początkową

${\ Displaystyle {\ Frac {dy} {dt}} = \ tan (y) + 1 \ quad y_ {0} = 1 \ t \ w [1,1.1]}$

przy wielkości kroku h = 0,025, więc metoda wymaga czterech kroków.

Metoda przebiega w następujący sposób:

${\displaystyle t_{0}=1\okrężnica}$
	${\displaystyle y_{0}=1}$
${\ Displaystyle t_ {1} = 1,025 \ dwukropek }$
	${\displaystyle y_{0}=1}$	${\displaystyle k_{1}=2.557407725}$	${\displaystyle k_{2}=f(t_{0}+{\tfrac {2}{3}}h,\ y_{0}+{\tfrac {2}{3}}hk_{1})=2.7138981400 }$
	${\displaystyle y_{1}=y_{0}+h({\tfrac{1}{4}}k_{1}+{\tfrac {3}{4}}k_{2})={\podkreślenie { 1.066869388}}}$
${\displaystyle t_{2}=1,05\okrężnica}$
	${\displaystyle y_{1}=1.066869388}$	${\displaystyle k_{1}=2.813524695}$	${\displaystyle k_{2}=f(t_{1}+{\tfrac {2}{3}}h,\ y_{1}+{\tfrac {2}{3}}hk_{1})}$
	${\displaystyle y_{2}=y_{1}+h({\tfrac{1}{4}}k_{1}+{\tfrac {3}{4}}k_{2})={\podkreślenie { 1.141332181}}}$
${\displaystyle t_{3}=1,075\okrężnica}$
	${\displaystyle y_{2}=1.141332181}$	${\displaystyle k_{1}=3,183536647}$	${\displaystyle k_{2}=f(t_{2}+{\tfrac {2}{3}}h,\ y_{2}+{\tfrac {2}{3}}hk_{1})}$
	${\displaystyle y_{3}=y_{2}+h({\tfrac{1}{4}}k_{1}+{\tfrac {3}{4}}k_{2})={\podkreślenie { 1.227417567}}}$
${\ Displaystyle t_ {4} = 1,1 \ dwukropek }$
	${\displaystyle y_{3}=1,227417567}$	${\displaystyle k_{1}=3.796866512}$	${\displaystyle k_{2}=f(t_{3}+{\tfrac {2}{3}}h,\ y_{3}+{\tfrac {2}{3}}hk_{1})}$
	${\ Displaystyle y_ {4}= y_ {3} + h ({\ tfrac {1} {4}} k_ {1} + {\ tfrac {3} {4}} k_ {2}) = {\ podkreślenie { 1.335079087}}.}$

Rozwiązania numeryczne odpowiadają wartościom podkreślonym.

Adaptacyjne metody Runge-Kutty

Metody adaptacyjne mają na celu oszacowanie lokalnego błędu obcięcia pojedynczego kroku Runge-Kutta. Odbywa się to za pomocą dwóch metod, jednej z zamówieniem, a drugiej z zamówieniem . Metody te przeplatają się ze sobą, tzn. mają wspólne etapy pośrednie. Dzięki temu oszacowanie błędu ma niewielki lub znikomy koszt obliczeniowy w porównaniu do kroku metodą wyższego rzędu. ${\displaystyle p}$${\displaystyle p-1}$

Podczas integracji wielkość kroku jest dostosowywana w taki sposób, że oszacowany błąd pozostaje poniżej progu zdefiniowanego przez użytkownika: Jeżeli błąd jest zbyt wysoki, krok jest powtarzany z mniejszą wielkością kroku; jeśli błąd jest znacznie mniejszy, rozmiar kroku jest zwiększany, aby zaoszczędzić czas. Daje to (prawie) optymalny rozmiar kroku, co oszczędza czas obliczeń. Co więcej, użytkownik nie musi tracić czasu na znalezienie odpowiedniego rozmiaru kroku.

Krok niższego rzędu jest podany przez

${\ Displaystyle y_ {n + 1} ^ {*} = y_ {n} + h \ suma _ {i = 1} ^ {s} b_ {i} ^ {*} k_ {i}}$

gdzie są takie same jak dla metody wyższego rzędu. Więc błąd jest ${\displaystyle k_{i}}$

${\ Displaystyle e_ {n + 1} = y_ {n + 1} -y_ {n + 1} ^ {*} = h \ suma _ {i = 1} ^ {s} (b_ {i} - b_ {i }^{*})k_{i},}$

czyli . Tabela rzeźnika dla tego rodzaju metody została rozszerzona o wartości : ${\ Displaystyle O (h ^ {p})}$${\ Displaystyle b_ {i} ^ {*}}$

	0
	${\displaystyle c_{2}}$	${\ Displaystyle a_ {21}}$
	${\displaystyle c_{3}}$	${\ Displaystyle a_ {31}}$	${\ Displaystyle a_ {32}}$
	${\displaystyle \vdots}$	${\displaystyle \vdots}$		${\displaystyle \ddots}$
	${\displaystyle c_{s}}$	${\displaystyle a_{s1}}$	${\displaystyle a_{s2}}$	${\displaystyle \cdots}$	${\displaystyle a_{s,s-1}}$
		${\displaystyle b_{1}}$	${\displaystyle b_{2}}$	${\displaystyle \cdots}$	${\displaystyle b_{s-1}}$	${\displaystyle b_{s}}$
		${\displaystyle b_{1}^{*}}$	${\displaystyle b_{2}^{*}}$	${\displaystyle \cdots}$	${\ Displaystyle b_ {s-1} ^ {*}}$	${\ Displaystyle b_ {s} ^ {*}}$

Metoda Rungego-Kutty-Fehlberga ma dwie metody rzędu 5 i 4. Jej rozszerzona tablica rzeźnika to:

	0
	1/4	1/4
	3/8	3/32	9/32
	12/13	1932/2197	-7200/2197	7296/2197
	1	439/216	-8	3680/513	-845/4104
	1/2	−8/27	2	−3544/2565	1859/4104	-11/40
		16/135	0	6656/12825	28561/56430	-9/50	2/55
		25/216	0	1408/2565	2197/4104	-1/5	0

Jednak najprostsza adaptacyjna metoda Runge-Kutty polega na połączeniu metody Heuna , czyli rzędu 2, z metodą Eulera , która jest rzędu 1. Jej rozszerzona tablica Butchera to:

	0
	1	1
		1/2	1/2
		1	0

Inne adaptacyjne metody Runge-Kutty to metoda Bogackiego-Shampine'a (zamówienia 3 i 2), metoda Cash-Karp i metoda Dormand-Prince (obie z zamówieniami 5 i 4).

Niezlewne metody Runge-Kutty

Mówi się, że metoda Runge-Kutty jest niekonfluentna, jeśli wszystkie są różne. ${\displaystyle c_{i},\,i=1,2,\ldots,s}$

Metody Rungego-Kutty-Nyströma

Metody Runge-Kutty-Nyströma są wyspecjalizowanymi metodami Runge-Kutty, które są zoptymalizowane pod kątem równań różniczkowych drugiego rzędu o następującej postaci:

${\ Displaystyle {\ Frac {d ^ {2} r} {dt ^ {2}}} = f (r {\ kropka {y}} t).}$

Niejawne metody Runge-Kutta

Wszystkie metody Runge-Kutta wymienione do tej pory są metodami jawnymi . Wyraźne metody Runge-Kutty są na ogół nieodpowiednie do rozwiązywania sztywnych równań, ponieważ ich obszar absolutnej stabilności jest mały; w szczególności jest ograniczona. Zagadnienie to jest szczególnie ważne przy rozwiązywaniu równań różniczkowych cząstkowych .

Niestabilność wyraźnych metod Runge-Kutty motywuje rozwój metod niejawnych. Niejawna metoda Runge-Kutty ma postać

${\ Displaystyle y_ {n + 1} = y_ {n} + h \ suma _ {i = 1} ^ {s} b_ {i} k_ {i}}$

gdzie

${\ Displaystyle k_ {i} = f \ lewo (t_ {n} + c_ {i} h, \ y_ {n} + h \ suma _ {j = 1} ^ {s} a_ {ij} k_ {j} \right),\quad i=1,\ldots ,s.}$

Różnica w stosunku do metody jawnej polega na tym, że w metodzie jawnej suma po j wzrasta tylko do i − 1. Pokazuje to również w tabeli Butchera: macierz współczynników metody jawnej jest trójkątna dolna. W metodzie niejawnej suma nad j wzrasta do s, a macierz współczynników nie jest trójkątna, co daje tablicę Butchera w postaci ${\displaystyle a_{ij}}$

${\ Displaystyle {\ rozpocznij tablicę} {c | cccc} c_ {1} i a_ {11} i a_ {12} i \ kropki i a_ {1 s} \ \ c_ {2} i a_ {21} i a_ {22} i \ kropki &a_{2s}\\\vkropki &\vpunkty &\vkropki &\ddots &\vpunkty \\c_{s}&a_{s1}&a_{s2}&\kropki &a_{ss}\\\hline &b_{1}&b_ {2}&\dots &b_{s}\\&b_{1}^{*}&b_{2}^{*}&\dots &b_{s}^{*}\\\end{array}}={\ begin{array}{c|c}\mathbf {c} &A\\\hline &\mathbf {b^{T}} \\\end{array}}}$

Zobacz metody Adaptive Runge-Kutta powyżej dla wyjaśnienia wiersza. ${\ Displaystyle b ^ {*}}$

Konsekwencją tej różnicy jest to, że na każdym kroku trzeba rozwiązać układ równań algebraicznych. To znacznie zwiększa koszt obliczeniowy. Jeżeli do rozwiązania równania różniczkowego o składowych m zostanie zastosowana metoda z etapami s , to układ równań algebraicznych ma składowe ms . Można to skontrastować z niejawnymi liniowymi metodami wieloetapowymi (inna duża rodzina metod dla ODE): niejawna liniowa wieloetapowa metoda s- krokowa musi rozwiązać układ równań algebraicznych z tylko m składowymi, więc rozmiar układu nie wzrasta wraz ze wzrostem liczby kroków.

Przykłady

Najprostszym przykładem niejawnej metody Runge-Kutty jest wsteczna metoda Eulera :

${\ Displaystyle y_ {n + 1} = y_ {n} + hf (t_ {n} + h, \ y_ {n + 1}). \,}$

Tableau Rzeźnika do tego jest po prostu:

${\ Displaystyle {\ zacząć {tablica} {c | c} 1 i 1 \ \ hline i 1 \ \ \ koniec {tablica}}}$

Ta tableau Rzeźnika odpowiada formułom

${\ Displaystyle k_ {1} = f (t_ {n} + h \ y_ {n} + hk_ {1}) \ quad {\ tekst {i}} \ quad y_ {n + 1} = y_ {n} +hk_{1},}$

które można przeorganizować, aby uzyskać wzór na metodę wsteczną Eulera wymienioną powyżej.

Innym przykładem niejawnej metody Runge-Kutty jest reguła trapezów . Jego stół rzeźnika to:

${\ Displaystyle {\ zacząć {tablica} {c | cc} 0 i 0 i 0 \ \ 1 i {\ Frac {1} {2}} i {\ Frac {1} {2}} \ \ \ hline i {\ Frac {1} {2}}&{\frac {1}{2}}\\&1&0\\\end{array}}}$

Reguła trapezów jest metodą kolokacyjną (omówioną w tym artykule). Wszystkie metody kolokacji są niejawnymi metodami Runge-Kutta, ale nie wszystkie niejawne metody Runge-Kutta są metodami kolokacji.

Metody Gaussa-Legendre'a tworzą rodzinę metod kolokacji opartych na kwadraturze Gaussa . Metoda Gaussa-Legendre'a z etapami s ma rząd 2 s (w ten sposób można konstruować metody o dowolnie wysokim rzędzie). Metoda z dwoma etapami (a więc kolejność cztery) ma tableau Butcher:

${\ Displaystyle {\ zacząć {tablica} {c | cc} {\ Frac {1} {2}} - {\ Frac {1} {6}} {\ sqrt {3}} i {\ Frac {1} { 4}}&{\frac {1}{4}}-{\frac {1}{6}}{\sqrt {3}}\\{\frac {1}{2}}+{\frac {1 }{6}}{\sqrt {3}}&{\frac {1}{4}}+{\frac {1}{6}}{\sqrt {3}}&{\frac {1}{4 }}\\\hline &{\frac {1}{2}}&{\frac {1}{2}}\\&{\frac {1}{2}}+{\frac {1}{2 }}{\sqrt {3}}&{\frac {1}{2}}-{\frac {1}{2}}{\sqrt {3}}\end{array}}}$

Stabilność

Zaletą niejawnych metod Runge-Kutty nad jawnymi jest ich większa stabilność, zwłaszcza w przypadku zastosowania do sztywnych równań . Rozważ równanie testu liniowego . Metoda Runge-Kutty zastosowana do tego równania sprowadza się do iteracji , z r podanym przez ${\ Displaystyle y' = \ lambda y}$${\ Displaystyle y_ {n + 1} = r (h \ lambda) \ y_ {n}}$

${\ Displaystyle r (z) = 1 + zb ^ {T} (I-ZA) ^ {-1} e = {\ Frac {\ Det (I-ZA + Zeb ^ {T})} {\ Det (I -zA)}},}$

gdzie e oznacza wektor jedynek. Funkcja r nazywana jest funkcją stabilności . Ze wzoru wynika, że r jest ilorazem dwóch wielomianów stopnia s, jeśli metoda ma s etapów. Metody jawne mają ściśle dolną macierz trójkątną A , co implikuje, że det( I − zA ) = 1, a funkcja stabilności jest wielomianem.

Numeryczne rozwiązanie równania testu liniowego zanika do zera, jeśli | r ( z ) | < 1 z z = h λ. Zbiór takich z nazywamy dziedziną stabilności absolutnej . W szczególności mówi się, że metoda jest absolutnie stabilna, jeśli wszystkie z z Re( z ) < 0 są w dziedzinie absolutnej stabilności. Funkcja stabilności jawnej metody Runge-Kutty jest wielomianem, więc jawne metody Runge-Kutty nigdy nie mogą być stabilne.

Jeśli metoda ta kolejność p , wówczas spełnia funkcji stabilności jak . W związku z tym interesujące jest badanie ilorazów wielomianów o danych stopniach, które najlepiej przybliżają funkcję wykładniczą. Są one znane jako aproksymacje Padé . Aproksymant Padé z licznikiem stopnia mi mianownikiem stopnia n jest A-stabilny wtedy i tylko wtedy, gdy m ≤ n ≤ m + 2. ${\ Displaystyle r (z) = {\ textrm {e}} ^ {z} + O (z ^ {p + 1})}$${\displaystyle z\do 0}$

Metoda Gaussa-Legendre'a ze stopniami s ma rząd 2 s , więc jej funkcją stabilności jest przybliżenie Padé z m = n = s . Wynika z tego, że metoda jest A-stabilna. To pokazuje, że A-stabilny Runge-Kutta może mieć dowolnie wysoki porządek. W przeciwieństwie do tego, kolejność liniowych metod wieloetapowych stabilnych A nie może przekraczać dwóch.

B-stabilność

Koncepcja A-stabilności dla rozwiązania równań różniczkowych jest powiązana z liniowym równaniem autonomicznym . Dahlquist zaproponował badanie stabilności schematów numerycznych w zastosowaniu do układów nieliniowych, które spełniają warunek monotoniczności. Odpowiednie koncepcje zdefiniowano jako stabilność G dla metod wieloetapowych (i powiązanych metod jednoetapowych) oraz stabilność B (Butcher, 1975) dla metod Runge-Kutty. Metoda Rungego-Kutty zastosowana do systemu nieliniowego , który weryfikuje , nazywa się B-stabilną , jeśli warunek ten oznacza dla dwóch rozwiązań numerycznych. ${\ Displaystyle y' = \ lambda y}$${\displaystyle y'=f(y)}$${\ Displaystyle \ langle f (y)-f (z), \ yz \ rangle <0}$${\ Displaystyle \ | y_ {n + 1} -z_ {n + 1} \ | \ leq \ | y_ {n}-z_ {n} \ |}$

Niech , i będą trzema macierzami zdefiniowanymi przez ${\ Displaystyle B}$${\ Displaystyle M}$${\displaystyle Q}$${\displaystyle s\times s}$

${\ Displaystyle B = \ operatorname {diag} (b_ {1}, b_ {2}, \ ldots, b_ {s}), \, M = BA + A ^ {T} B-bb ^ {T}, \ ,Q=BA^{-1}+A^{-T}BA^{-T}bb^{T}A^{-1}.}$

Mówi się, że metoda Runge-Kutty jest algebraicznie stabilna, jeśli macierze i obie są nieujemne określone. Wystarczającym warunkiem B-stabilności jest: i są nieujemne określone. ${\ Displaystyle B}$${\ Displaystyle M}$${\ Displaystyle B}$${\displaystyle Q}$

Wyprowadzenie metody czwartego rzędu Runge-Kutty

Ogólnie rzecz biorąc metodę Runge-Kutta porządku można zapisać jako: ${\displaystyle s}$

${\ Displaystyle y_ {t + h} = y_ {t} + h \ cdot \ suma _ {i = 1} ^ {s} a_ {i} k_ {i} + {\ matematyczne {O}} (h ^ { s+1}),}$

gdzie:

${\ Displaystyle k_ {i} = y_ {t} + h \ cdot \ suma _ {j = 1} ^ {s} \ beta _ {ij} f \ lewo (k_ {j}, \ t_ {n} + \ alfa _{i}h\prawo)}$

są przyrostami uzyskanymi z wyceny pochodnych na -tym rzędzie. ${\displaystyle y_{t}}$${\displaystyle i}$

Opracowujemy wyprowadzenie dla metody czwartego rzędu Runge-Kutty przy użyciu ogólnego wzoru z oceną, jak wyjaśniono powyżej, w punkcie początkowym, punkcie środkowym i punkcie końcowym dowolnego przedziału ; w ten sposób wybieramy: ${\displaystyle s=4}$${\ Displaystyle (t \ t + h)}$

${\ Displaystyle {\ zacząć {wyrównany} i \ alfa _ {i} i \ beta _ {ij} \ \ \ alfa _ {1} i = 0 i \ beta _ {21} i = {\ Frac {1} {2 }}\\\alpha _{2}&={\frac {1}{2}}&\beta _{32}&={\frac {1}{2}}\\\alpha _{3}& ={\frac {1}{2}}&\beta _{43}&=1\\\alpha _{4}&=1&&\\\end{wyrównany}}}$

i inaczej. Zaczynamy od zdefiniowania następujących wielkości: ${\ Displaystyle \ beta _ {ij} = 0}$

${\ Displaystyle {\ zacząć {wyrównany} y_ {t + h} ^ {1} i = y_ {t} + hf \ lewo (y_ {t}, \ t \ po prawej) \ \ y_ {t + h} ^ { 2}&=y_{t}+hf\left(y_{t+h/2}^{1},\ t+{\frac {h}{2}}\right)\\y_{t+h}^ {3}&=y_{t}+hf\left(y_{t+h/2}^{2},\ t+{\frac {h}{2}}\right)\end{aligned}}}$

gdzie i . Jeśli zdefiniujemy: ${\ Displaystyle y_ {t + h/2} ^ {1} = {\ dfrac {y_ {t} + y_ {t + h} ^ {1}} {2}}}$${\ Displaystyle y_ {t + h/2} ^ {2} = {\ dfrac {y_ {t} + y_ {t + h} ^ {2}} {2}}}$

${\ Displaystyle {\ zacząć {wyrównany} k_ {1} i = f (y_ {t}, \ t) \ \ k_ {2} i = f \ lewo (y_ {t + h/2} ^ {1}, \ t+{\frac {h}{2}}\right)=f\left(y_{t}+{\frac {h}{2}}k_{1},\ t+{\frac {h}{2 }}\right)\\k_{3}&=f\left(y_{t+h/2}^{2},\ t+{\frac {h}{2}}\right)=f\left( y_{t}+{\frac {h}{2}}k_{2},\ t+{\frac {h}{2}}\right)\\k_{4}&=f\left(y_{t +h}^{3},\ t+h\right)=f\left(y_{t}+hk_{3},\ t+h\right)\end{aligned}}}$

a dla poprzednich relacji możemy wykazać, że następujące równości utrzymują się do : ${\ Displaystyle {\ mathcal {O}} (h ^ {2})}$

${\ Displaystyle {\ zacząć {wyrównany} k_ {2} i = f \ lewo (y_ {t + h/2} ^ {1}, \ t + {\ Frac {h} {2}} \ prawej) = f \ left(y_{t}+{\frac {h}{2}}k_{1},\ t+{\frac {h}{2}}\right)\\&=f\left(y_{t}, \ t\right)+{\frac {h}{2}}{\frac {d}{dt}}f\left(y_{t},\ t\right)\\k_{3}&=f\ left(y_{t+h/2}^{2},\ t+{\frac {h}{2}}\right)=f\left(y_{t}+{\frac {h}{2}} f\left(y_{t}+{\frac {h}{2}}k_{1},\ t+{\frac {h}{2}}\right),\ t+{\frac {h}{2 }}\right)\\&=f\left(y_{t},\ t\right)+{\frac {h}{2}}{\frac {d}{dt}}\left[f\left (y_{t},\ t\right)+{\frac {h}{2}}{\frac {d}{dt}}f\left(y_{t},\ t\right)\right]\ \k_{4}&=f\left(y_{t+h}^{3},\ t+h\right)=f\left(y_{t}+hf\left(y_{t}+{\ frac {h}{2}}k_{2},\ t+{\frac {h}{2}}\right),\ t+h\right)\\&=f\left(y_{t}+hf \left(y_{t}+{\frac {h}{2}}f\left(y_{t}+{\frac {h}{2}}f\left(y_{t},\ t\right ),\ t+{\frac {h}{2}}\right),\ t+{\frac {h}{2}}\right),\ t+h\right)\\&=f\left(y_ {t},\ t\right)+h{\frac {d}{dt}}\left[f\left(y_{t},\ t\right)+{\frac {h}{2}}{ \frac {d}{dt}}\lewo[f\lewo(y_{t},\ t\prawo)+{\frac {h}{2}}{\frac {d}{dt}}f\lewo (y_{t},\ t \right)\right]\right]\end{aligned}}}$

gdzie:

${\ Displaystyle {\ Frac {d} {dt}} f (r_ {t} \ t) = {\ Frac {\ częściowy} {\ częściowy r}} f (r_ {t} \ t) {\ kropka {y}}_{t}+{\frac {\częściowy }{\częściowy t}}f(y_{t},\ t)=f_{y}(y_{t},\ t){\dot { y}}+f_{t}(y_{t},\ t):={\ddot {y}}_{t}}$

jest całkowitą pochodną względem czasu. ${\displaystyle f}$

Jeśli teraz wyrazimy ogólną formułę za pomocą tego, co właśnie wyprowadziliśmy, otrzymamy:

${\ Displaystyle {\ zacząć {wyrównane} y_ {t + h} = {} i y_ {t} + h \ lewo \ lbrace a \ cdot f (y_ {t} \ t) + b \ cdot \ lewo [f ( y_{t},\ t)+{\frac {h}{2}}{\frac {d}{dt}}f(y_{t},\ t)\right]\right.+\\&{ }+c\cdot \left[f(y_{t},\ t)+{\frac {h}{2}}{\frac {d}{dt}}\left[f\left(y_{t} ,\ t\right)+{\frac {h}{2}}{\frac {d}{dt}}f(y_{t},\ t)\right]\right]+\\&{}+ d\cdot \left[f(y_{t},\ t)+h{\frac {d}{dt}}\left[f(y_{t},\ t)+{\frac {h}{2 }}{\frac {d}{dt}}\po lewej[f(y_{t},\ t)+\po lewej.{\frac {h}{2}}{\frac {d}{dt}}f (y_{t},\ t)\right]\right]\right]\right\rbrace +{\mathcal {O}}(h^{5})\\={}&y_{t}+a\cdot hf_{t}+b\cdot hf_{t}+b\cdot {\frac {h^{2}}{2}}{\frac {df_{t}}{dt}}+c\cdot hf_{t }+c\cdot {\frac {h^{2}}{2}}{\frac {df_{t}}{dt}}+\\&{}+c\cdot {\frac {h^{3 }}{4}}{\frac {d^{2}f_{t}}{dt^{2}}}+d\cdot hf_{t}+d\cdot h^{2}{\frac {df_ {t}}{dt}}+d\cdot {\frac {h^{3}}{2}}{\frac {d^{2}f_{t}}{dt^{2}}}+d \cdot {\frac {h^{4}}{4}}{\frac {d^{3}f_{t}}{dt^{3}}}+{\mathcal {O}}(h^{ 5})\end{wyrównany}}}$

i porównując to z szeregu Taylora z dookoła : ${\displaystyle y_{t+h}}$${\displaystyle y_{t}}$

${\ Displaystyle {\ zacząć {wyrównany} r_ {t + h} i = r_ {t} + h {\ kropka {y}} _ {t} + {\ Frac {h ^ {2}} {2}} \ddot {y}}_{t}+{\frac {h^{3}}{6}}y_{t}^{(3)}+{\frac {h^{4}}{24}} y_{t}^{(4)}+{\mathcal {O}}(h^{5})=\\&=y_{t}+hf(y_{t},\ t)+{\frac { h^{2}}{2}}{\frac {d}{dt}}f(y_{t},\ t)+{\frac {h^{3}}{6}}{\frac {d ^{2}}{dt^{2}}}f(y_{t},\ t)+{\frac {h^{4}}{24}}{\frac {d^{3}}{dt ^{3}}}f(y_{t},\ t)\end{wyrównany}}}$

otrzymujemy układ ograniczeń na współczynniki:

${\ Displaystyle {\ zacząć {przypadki} i a + b + c + d = 1 \ \ [6 pkt] i {\ Frac {1} {2}} b + {\ Frac {1} {2}} c + d = { \frac {1}{2}}\\[6pt]&{\frac {1}{4}}c+{\frac {1}{2}}d={\frac {1}{6}}\\ [6pt]&{\frac {1}{4}}d={\frac {1}{24}}\end{przypadki}}}$

które po rozwiązaniu daje jak podano powyżej. ${\ Displaystyle a = {\ Frac {1} {6}}, b = {\ Frac {1} {3}}, c = {\ Frac {1} {3}}, d = {\ Frac {1} {6}}}$

Zobacz też

• Metoda Eulera
• Lista metod Runge-Kutty
• Metody numeryczne dla równań różniczkowych zwyczajnych
• Metoda Rungego-Kutty (SDE)
• Ogólne metody liniowe
• Integrator grupy kłamstw

Uwagi

Bibliografia

• Runge, Carl David Tolmé (1895), „Über die numerische Auflösung von Differentialgleichungen” , Mathematische Annalen , Springer , 46 (2): 167-178, doi : 10.1007/BF01446807.
• Kutta, Martin (1901), "Beitrag zur näherungsweisen Integracja totaler Differentialgleichungen" Zeitschrift für Mathematik und Physik , 46 : 435-453.
• Ascher, Uri M.; Petzold, Linda R. (1998), Metody komputerowe dla równań różniczkowych zwyczajnych i równań różniczkowo-algebraicznych , Filadelfia: Towarzystwo Matematyki Przemysłowej i Stosowanej , ISBN 978-0-89871-412-8.
• Atkinson, Kendall A. (1989), Wprowadzenie do analizy numerycznej (2nd ed.), New York: John Wiley & Sons , ISBN 978-0-471-50023-0.
• Rzeźnik, John C. (maj 1963), „Współczynniki do badania procesów integracji Runge-Kutta”, Journal of the Australian Mathematical Society , 3 (2): 185-201, doi : 10.1017/S1446788700027932.
• Rzeźnik, John C. (1975), „Właściwość stabilności ukrytych metod Runge-Kutta”, BIT , 15 (4): 358-361, doi : 10.1007/bf01931672.
• Rzeźnik, John C. (2008), Metody numeryczne dla równań różniczkowych zwyczajnych , New York: John Wiley & Sons , ISBN 978-0-470-72335-7.
• Cellier, F.; Kofman, E. (2006), Ciągła symulacja systemu , Springer Verlag , ISBN 0-387-26102-8.
• Dahlquist, Germund (1963), „Specjalny problem stabilności dla liniowych metod wieloetapowych”, BIT , 3 : 27-43, doi : 10.1007/BF01963532 , hdl : 10338.dmlcz/103497 , ISSN  0006-3835.
• Forsythe, George E.; Malcolm, Michael A.; Moler, Cleve B. (1977), Metody komputerowe obliczeń matematycznych , Prentice-Hall (patrz rozdział 6).
• Fryzjer, Ernst; Norsett, Syvert Paul; Wanner, Gerhard (1993), Rozwiązywanie równań różniczkowych zwyczajnych I: problemy niesztywne , Berlin, New York: Springer-Verlag , ISBN 978-3-540-56670-0.
• Fryzjer, Ernst; Wanner, Gerhard (1996), Rozwiązywanie równań różniczkowych zwyczajnych II: problemy sztywne i różniczkowo-algebraiczne (2nd ed.), Berlin, New York: Springer-Verlag , ISBN 978-3-540-60452-5.
• Iserles, Arieh (1996), pierwszy kurs analizy numerycznej równań różniczkowych , Cambridge University Press , ISBN 978-0-521-55655-2.
• Lambert, JD (1991), Metody numeryczne dla zwykłych układów różnicowych. Problem wartości początkowej , John Wiley & Sons , ISBN 0-471-92990-5
• Kaw, Autar; Kalu, Egwu (2008), Metody numeryczne z aplikacjami (wyd. 1), autarkaw.com.
• Prasa, William H.; Teukolsky, Saul A. ; Vetterling, William T.; Flannery, Brian P. (2007), "Sekcja 17.1 Metoda Runge-Kutty" , Przepisy numeryczne: The Art of Scientific Computing (3rd ed.), Cambridge University Press , ISBN 978-0-521-88068-8. Również sekcja 17.2. Adaptacyjna kontrola rozmiaru kroków dla Runge-Kutty .
• Stoer, Josef; Bulirsch, Roland (2002), Wprowadzenie do analizy numerycznej (3rd ed.), Berlin, New York: Springer-Verlag , ISBN 978-0-387-95452-3.
• Suli, Endre; Mayers, David (2003), Wprowadzenie do analizy numerycznej , Cambridge University Press , ISBN 0-521-00794-1.
• opalenizna, Delin; Chen, Zheng (2012), „O ogólnej formule metody Runge-Kutta czwartego rzędu” (PDF) , Journal of Mathematical Science & Mathematics Education , 7 (2): 1-10.
• zaawansowana matematyka dyskretna ignou podręcznik (code- mcs033)
• John C. Butcher: „Seria B: Analiza algebraiczna metod numerycznych”, Springer（SSCM, tom 55), ISBN  978-3030709556 (kwiecień 2021).

Zewnętrzne linki

• „Metoda Runge-Kutty” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Metoda 4-go rzędu Runge-Kutta
• Implementacja biblioteki komponentów Tracker w Matlab — Implementuje 32 wbudowane algorytmy Runge Kutta w RungeKStep, 24 wbudowane algorytmy Runge-Kutta Nyström w RungeKNystroemSStepi 4 ogólne algorytmy Runge-Kutta Nyström w RungeKNystroemGStep.