Runge-Kutta i ponowne wykorzystywanie punktów danych

11

Próbuję zaimplementować metodę Runge-Kutta czwartego rzędu do rozwiązywania ODE pierwszego rzędu w Pythonie, tj. . Rozumiem, jak działa ta metoda, ale próbuję napisać skuteczny algorytm, który minimalizuje liczbę obliczeń f (x, y), ponieważ jest to dość kosztowne. Powiedziano mi, że możliwe jest ponowne wykorzystanie punktów danych, które zostały wcześniej obliczone, gdy zwiększasz liczbę kroków, ale nie wiesz, jak to zrobić. Czy ktoś wie, jak to zrobić, czy jest to niemożliwe?f ( x , y )dydx=f(x,y)f(x,y)

joshlk
źródło
„Zapamiętywanie” badań. Możesz łatwo „zawinąć” swoje, f(x,y)aby wyniki zostały zapamiętane.
2
@ S.Lott: Termin „memoization”, bez „r”.
1
@DietrichEpp: całkowicie poprawne. Mac OS X ma nową, agresywną funkcję sprawdzania pisowni, która w ogóle nie wymaga wiedzy technicznej.
Czy jest to system drugiego rzędu symulowany metodą czwartego rzędu?
Oto ogromna lista alternatywnych rozwiązań: google.com/... Każde z nich prawdopodobnie będzie pomocne.

Odpowiedzi:

8

Jeśli zamierzasz od yp_1 = f(x_1, y_1)celu yp_2 = f(x_1+h, y_2)będziesz potrzebować punktów pośrednich:

K1 = f(x_1+h/2, y_1+h/2*yp_1)
K2 = f(x_1+h/2, y_1+h/2*K1)
K3 = f(x_1+h, y_1+h*K2)

x_2 = x_1 + h
y_2 = y_1 + h/6*(yp_1+2*K1+2*K2+K3)
yp_2 = f(x_2, y_2)

Zasadniczo żaden z punktów pośrednich nie jest użyteczny w następnym kroku. Ponieważ K1<> K2i K3<> yp_2.

ja72
źródło
4

Ogólnie rzecz biorąc, jawne metody Runge-Kutty rzędu wymagają co najmniej oceny funkcji i absolutnie nie ma sposobu, aby tego uniknąć. W przeszłości wymagają więcej niż oceny funkcji.N N = 4 N.N NN=4N

Jeśli chcesz ponownie wykorzystać wcześniejsze oceny funkcji, musisz użyć metody wieloetapowej, takiej jak Adams-Bashforth.

W każdym razie płacisz za każdą strategię. Metody jednoetapowe wymagają największej liczby ocen funkcji, ale metody wieloetapowe mają największe wymagania dotyczące pamięci.

Edycja: Korekta. Moje stwierdzenie jest prawdziwe tylko w przypadku jawnych metod. W przypadku metod niejawnych sytuacja jest mniej jasna, ponieważ liczba etapów nie przekłada się bezpośrednio na liczbę ocen funkcji.

Reid.Atcheson
źródło
Powinienem chyba być bardziej konkretny. Zobacz Butcher po więcej szczegółów: Butcher, JC i J. Wiley. Metody numeryczne dla zwykłych równań różniczkowych. Wiley Online Library, 2008. Doskonałe odniesienie do rozwiązań ODE, a także zapewnia wiele dowodów nieistnienia dla metod RK (np. Nie istnieje metoda 5 Runge-Kutta rzędu, która wykorzystuje tylko 4 oceny funkcji.)
Reid.Atcheson
1
Dla kompletności: twoje twierdzenia nie są prawdziwe w odniesieniu do „ogólnych metod Runge-Kutta”, ale tylko w przypadku jawnych metod Runge-Kutta.
David Ketcheson
Ups! Masz rację, przepraszam za to.
Reid.Atcheson
1

Wiem, że używasz metod Runge-Kutta do rozwiązania ODE, ale jeśli chcesz ponownie użyć starych obliczonych wartości swojego f (x, y), możesz rozważyć metody wieloetapowe, takie jak Adams-Bashforth lub Adams-Moulton metody Oczywiście wadą tych metod jest to, że nie można bardzo łatwo zastosować adaptacyjnego skracania czasu.

Paweł
źródło
0

Sprawdź metody „osadzone”: celem tego typu metod RK jest posiadanie dwóch metod o różnych rzędach, przy czym metoda wysokiego rzędu wykorzystuje te same oceny funkcji co metoda niskiego rzędu. Pozwala to na bardzo wydajne oszacowanie błędu. Patrz str. 165 i dalsze w „Rozwiązywanie równań różniczkowych zwyczajnych I: problemy niesztywne” autorstwa Hairera, Norsetta i Wannera. Typowymi przykładami są metody Fehlberga rzędu 7 (8).

Ponadto, jeśli szukasz rozwiązania ODE w PYTHON, sprawdź assimulo . Bawię się tym pakietem od kilku tygodni i jestem całkiem szczęśliwy.

GertVdE
źródło