Integracja Runge-Kutta (RK4) z fizyką gry
Gaffer o grach ma świetny artykuł o używaniu integracji RK4 dla lepszej fizyki gry. Implementacja jest prosta, ale matematyka za nią myli mnie. Rozumiem pochodne i całki na poziomie koncepcyjnym, ale dawno nie manipulowałem równaniami.
Oto ciężar implementacji Gaffera:
void integrate(State &state, float t, float dt)
{
Derivative a = evaluate(state, t, 0.0f, Derivative());
Derivative b = evaluate(state, t+dt*0.5f, dt*0.5f, a);
Derivative c = evaluate(state, t+dt*0.5f, dt*0.5f, b);
Derivative d = evaluate(state, t+dt, dt, c);
const float dxdt = 1.0f/6.0f * (a.dx + 2.0f*(b.dx + c.dx) + d.dx);
const float dvdt = 1.0f/6.0f * (a.dv + 2.0f*(b.dv + c.dv) + d.dv)
state.x = state.x + dxdt * dt;
state.v = state.v + dvdt * dt;
}
Czy ktoś może wyjaśnić w prosty sposób jak działa RK4? Konkretnie, dlaczego uśredniamy pochodne na 0.0f, 0.5f, 0.5f, i 1.0f? Czym różni się uśrednianie pochodnych do czwartego rzędu od prostego całkowania Eulera z mniejszym znacznikiem czasu?
Po przeczytaniu zaakceptowanej Odpowiedzi poniżej i kilku innych artykułów, mam pojęcie, jak działa RK4. Aby odpowiedzieć na własne pytania:
Czy ktoś może wyjaśnić w prosty sposób jak działa RK4?
RK4 wykorzystuje fakt, że możemy uzyskać znacznie lepsze przybliżenie funkcji, jeżeli używamy jego pochodne wyższego rzędu, a nie tylko pierwsza lub druga pochodna. Dlatego seria Taylora zbiega się znacznie szybciej niż Euler przybliżenia. (spójrz na animacja po prawej stronie strona)
Konkretnie, dlaczego uśredniamy pochodne na 0.0f, 0.5f, 0.5f, i 1.0f?
Metoda Runge ' a-Kutta jest przybliżenie funkcji, która przykładowe pochodne kilku punktów w czasie, w przeciwieństwie do Taylor seria, która tylko próbki pochodne jednego punktu. Po pobraniu próbek te pochodne musimy wiedzieć, jak aby zważyć każdą próbkę, aby uzyskać możliwe zbliżenie. Na łatwym sposobem na to jest wybranie stałe, które pokrywają się z Taylor series, czyli jak stałe równania Runge ' a-Kutta są zdeterminowani.
Ten artykuł sprawił, że stało się to bardziej zrozumiałe dla ja. Zauważ jak
(15)jest Taylor seriale rozszerzenie, podczas gdy(17)jest Derywacja Runge-Kutta.
Czym różni się uśrednianie pochodnych do czwartego rzędu od prostego całkowania Eulera z mniejszym znacznikiem czasu?
Matematycznie, to zbiega się znacznie szybszy od wielu Eulerów przybliżenia. Oczywiście, z wystarczającą Przybliżenia Eulera możemy uzyskać równe dokładność do RK4, ale obliczeniowa potrzebna moc nie usprawiedliwia używania Euler.
3 answers
Może to być nieco uproszczone, jeśli chodzi o rzeczywistą matematykę, ale rozumiane jako intuicyjny przewodnik po integracji Runge Kutta.
Biorąc pod uwagę pewną ilość w pewnym czasie t1, chcemy znać ilość w innym czasie t2. Dzięki równaniu różniczkowemu pierwszego rzędu możemy poznać szybkość zmiany tej ilości przy t1. Nic więcej nie możemy wiedzieć na pewno; reszta to zgadywanie.
Integracja Eulera jest najprostszym sposobem zgadywania: ekstrapolacja liniowa z t1 do t2, używając dokładnie znanej szybkości zmian przy t1. To zwykle daje złą odpowiedź. Jeśli t2 jest daleko od t1, ta liniowa ekstrapolacja nie pasuje do żadnej krzywizny w idealnej odpowiedzi. Jeśli zrobimy wiele małych kroków od t1 do t2, będziemy mieli problem z odejmowaniem podobnych wartości. Błędy Roundoff zrujnują wynik.
t2. To, uśrednione z (dokładną) szybkością zmiany przy t1, lepiej reprezentuje typowe nachylenie prawdziwej odpowiedzi między t1 i t2. Używamy tego do nowej ekstrapolacji liniowej od t1 do t2. Nie jest oczywiste, czy powinniśmy przyjąć średnią prostą, czy nadać większą wagę szybkości w t1, bez robienia obliczeń w celu oszacowania błędów, ale tutaj jest wybór. W każdym razie, to lepsza odpowiedź niż daje Euler.
Być może lepiej, zrobić naszą początkową ekstrapolację liniową do punktu w czasie w połowie drogi między t1 i t2 i użyć równania różniczkowego, aby obliczyć szybkość zmian. To daje mniej więcej tak dobrą odpowiedź, jak średnia właśnie opisana. Następnie użyj tego do liniowej ekstrapolacji z t1 do t2, ponieważ naszym celem jest znalezienie ilości w t2. Jest to algorytm punktu środkowego.
Można sobie wyobrazić, używając oszacowania średniej stopy zmiana w celu dokonania kolejnej liniowej ekstrapolacji ilości z t1 do punktu środkowego. Dzięki równaniu różniczkowemu otrzymujemy lepsze oszacowanie nachylenia. Używając tego, kończymy ekstrapolacją z t1 aż do t2, gdzie chcemy uzyskać odpowiedź. Jest to algorytm Runge Kutta.
Runge Kutta stosuje równanie różniczkowe do punktu początkowego t1, dwa razy do punktu środkowego i raz do punktu końcowego t2. Pomiędzy punktami jest kwestia wyboru. Możliwe jest wykorzystanie innych punktów pomiędzy t1 i t2 do dokonywania tych ulepszonych szacunków nachylenia. Na przykład, możemy użyć t1, punktu o jednej trzeciej drogi w kierunku t2, innego 2/3 drogi w kierunku t2 I at t2. Wagi dla średniej z czterech pochodnych będą różne. W praktyka to naprawdę nie pomaga, ale może mieć miejsce w testowaniu, ponieważ powinno dać tę samą odpowiedź, ale zapewni inny zestaw błędów zaokrąglić.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-05-13 09:45:00
Jeśli chodzi o twoje pytanie dlaczego: przypominam sobie, że kiedyś pisałem symulator tkaniny, w którym tkanina była serią sprężyn połączonych w węzłach. W symulatorze siła wywierana przez sprężynę jest proporcjonalna do tego, jak daleko sprężyna jest rozciągnięta. Siła powoduje przyspieszenie w węźle, co powoduje prędkość poruszającą węzeł rozciągający sprężynę. Istnieją dwie całki (integrujące przyspieszenie do uzyskania prędkości i integrujące prędkość do uzyskania pozycji) i jeśli są niedokładne, to błędy snowball: zbyt duże przyspieszenie powoduje zbyt dużą prędkość, co powoduje zbyt duże rozciąganie, co powoduje jeszcze większe przyspieszenie, co sprawia, że cały system jest niestabilny.
Trudno to wyjaśnić bez grafiki, ale spróbuję: powiedzmy, że masz f(t), gdzie F(0) = 10, F(1) = 20 i f(2) = 30.
Właściwa integracja f (t) w przedziale 0
Integracja reguły prostokąt przybliża, że powierzchnia z prostokątem, gdzie szerokość jest deltą w czasie, a długość jest nową wartością f (t), więc w przedziale 0
Teraz, jeśli narysujesz te punkty i narysujesz przez nie linię, zobaczysz, że jest ona w rzeczywistości trójkątna, o powierzchni 30 (jednostek), a zatem integracja Eulera jest niewystarczająca.
Aby uzyskać dokładniejsze oszacowanie powierzchni (całki) można wykonać mniejsze odstępy t, oceniając na przykład F (0), f (0.5), f(1), f(1.5) i f(2).
Jeśli nadal mnie śledzisz, metoda RK4 jest po prostu sposobem szacowania wartości f (t) dla t0
(ale jak powiedzieli inni, przeczytaj artykuł Wikipedii, aby uzyskać bardziej szczegółowe wyjaśnienie. RK4 jest w kategorii całkowanie numeryczne )
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-11-03 16:11:31
RK4 w najprostszym sensie jest dokonaniem funkcji przybliżenia, która jest oparta na 4 pochodnych i punkt dla każdego kroku czasowego: stan początkowy w punkcie początkowym A, pierwsze przybliżone nachylenie B na podstawie punktu danych A w Twoim czasie Krok / 2 i nachylenie z a, trzecie przybliżenie C, które ma wartość korekty dla nachylenia w B, aby odzwierciedlić zmiany kształtu twojej funkcji, i wreszcie końcowe nachylenie na podstawie skorygowanego nachylenia w punkcie C.
Więc w zasadzie ta metoda umożliwia obliczanie za pomocą punktu początkowego, uśrednionego punktu środkowego, który ma korekty wbudowane w obie części, aby dostosować się do kształtu, oraz podwójnie skorygowanego punktu końcowego. To sprawia, że efektywny wkład z każdego punktu danych 1/6 1/3 1/3 i 1/6, więc większość odpowiedzi opiera się na poprawkach dotyczących kształtu twojej funkcji.
Okazuje się, że kolejność aproksymacji RK (Euler jest uważany za RK1) odpowiada temu, jak jego dokładność skaluje się z mniejszymi krokami czasowymi.
Zależność między przybliżeniami RK1 jest liniowa, więc dla 10-krotnej precyzji otrzymujemy około 10-krotną lepszą zbieżność.
Dla RK4, 10 razy dokładność daje około 10^4 razy lepszą zbieżność. Tak więc, podczas gdy twój czas obliczania zwiększa się liniowo w RK4, zwiększa twoją dokładność wielomianowo.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-09-27 18:43:15