Algorytm skokowy
Algorytm skokowy (algorytm żabiego skoku, ang. leapfrog integration) – metoda numeryczna służąca do całkowania równań w postaci:
lub w równoważnej formie:
występującej często w mechanice klasycznej przy opisie układów dynamicznych.
Opis algorytmu
Problemy typu często przybierają postać:
z funkcją energii zadaną wzorem:
gdzie jest energią potencjalną układu. Całkowanie metodą skokową (leapfrog) jest równoważne aktualizacji pozycji i prędkości w naprzemiennych chwilach, rozłożonych w ten sposób, że „przeskakują one nad sobą” – stąd nazwa algorytmu (ang. leapfrog – skok przez plecy). Na przykład położenie jest aktualizowane dla całkowitych wielokrotności kroku czasowego, zaś wartość prędkości jest uaktualniana w chwilach czasu przesuniętych o
Algorytm skokowy jest metodą drugiego rzędu, w przeciwieństwie do metody Eulera, która jest metodą pierwszego rzędu, jednak liczba wywołań funkcji w każdym kroku jest taka sama. W przeciwieństwie do całkowania metodą Eulera algorytm jest stabilny w przypadku ruchu oscylacyjnego z częstością dopóki krok czasowy jest stały oraz [1].
W algorytmie skokowym równania opisujące położenie i prędkość w kolejnych chwilach czasu są następujące:
gdzie jest położeniem w kroku jest prędkością, lub pierwszą pochodną w kroku jest przyspieszeniem, lub druga pochodną w kroku oraz rozmiarem każdego kroku. Równania te mogą być zapisane również w postaci, w której prędkość jest również wyznaczana dla całkowitych wielokrotności kroku czasowego[2]. Jednak nawet w tej zsynchronizowanej postaci, krok czasowy musi być stały, aby zachować stabilność[3].
Jednym z częstszych zastosowań algorytmu skokowego są symulacje oddziaływań grawitacyjnych, gdzie przyspieszenie zależy tylko od pozycji. Jednakowoż nawet w tym przypadku metody wyższego rzędu (np. metody Rungeggo-Kutty) są używane znacznie częściej.
Algorytm skokowy ma dwie znaczące zalety:
- odwracalność w czasie – oznacza, że po obliczeniu n kroków możliwe jest odwrócenie kierunku całkowania i dojście do tej samej pozycji wyjściowej.
- symplektyczność – oznacza, że algorytm zachowuje (nieznacznie zmodyfikowaną) całkę energii systemów dynamicznych (tzn. całkowita energia układu oscyluje wokół pewnej stałej wartości bliskiej początkowej energii całkowitej). Jest to szczególnie przydatne podczas obliczania orbit w układach dynamicznych, gdzie pozostałe schematy całkowania, takie jak metody Rungego-Kutty, nie zachowują energii układu i pozwalają układowi na znaczne płynięcie w czasie.
Ze względu na powyższe dwie cechy, algorytm skokowy jest również stosowany w przypadku metod Monte Carlo[4].
Przykładowa implementacja
Poniżej znajduje się kod napisany w środowisku MATLAB realizujący algorytm żabiego skoku w zsynchronizowanej postaci. Program rozwiązuje równanie: opisujące oddziaływanie grawitacyjne dwóch ciał. Przy czym dobrano taki układ odniesienia, w którym suma dwóch oddziałujących ze sobą mas wynosi 1 oraz stała grawitacji jest również równa 1.
close all clear all clc % rozwiązanie równania d^r/dt^2 = - r/r^3 metodą leapfrog dt = 0.001; % krok czasowy % warunki początkowe r = [0; 0.5; 0.75]; v = [0.25; 0; 1]; r2 = r'*r; a = -r/(r2*sqrt(r2)); % czas symulacji T = 10; res = NaN(round(T/dt)+1,6); idx = 0; for t=0:dt:T idx = idx + 1; v = v + 0.5*a*dt; r = r + v*dt; r2 = r'*r; a = -r/(r2*sqrt(r2)); v = v + 0.5*a*dt; res(idx,:) = [r' v']; end comet3(gca,res(:,1),res(:,2),res(:,3))
Zobacz też
- metoda Eulera
- algorytm Rungego-Kutty
- algorytm Verleta
Przypisy
- ↑ C.K. Birdsall and A.B. Langdon, Plasma Physics via Computer Simulations, McGraw-Hill Book Company, 1985, s. 56.
- ↑ 4.1 Two Ways to Write the Leapfrog.
- ↑ R.D. Skeel, Variable Step Size Detabilizes the Stömer/Leapfrog/Verlet Method, „BIT Numerical Mathematics”, Vol. 33, 1993, s. 172–175.
- ↑ Bishop Christopher: Pattern Recognition and Machine Learning. Nowy Jork: Springer-Verlag, 2006, s. 548–554. ISBN 978-0-387-31073-2.
Linki zewnętrzne
- Opis algorytmu. einstein.drexel.edu. [zarchiwizowane z tego adresu (2016-03-06)]., Drexel University