Algorytm skokowy

Algorytm skokowy

Algorytm skokowy (znany również jako algorytm żabiego skoku, ang. leapfrog integration) to technika numeryczna wykorzystywana do całkowania równań w formie:

{\displaystyle {\ddot {x}}=F(x),}

lub w równoważnej postaci:

{\displaystyle {\dot {v}}=F(x),\;{\dot {x}}\equiv v,}

metoda ta jest często stosowana w mechanice klasycznej przy opisie układów dynamicznych.

Opis algorytmu

Problemy opisane przez równanie

{\displaystyle {\ddot {x}}=F(x)}

często przybierają formę:

{\displaystyle {\ddot {x}}=-\nabla V(x),}

gdzie V oznacza funkcję energii wyrażoną wzorem:

{\displaystyle E(x,v)={\tfrac {1}{2}}|v|^{2}+V(x),}

gdzie V jest energią potencjalną układu. Całkowanie przy użyciu metody skokowej (leapfrog) polega na aktualizacji pozycji

{\displaystyle x(t)}

i prędkości

{\displaystyle v(t)={\dot {x}}(t)}

w naprzemiennych momentach czasu, w taki sposób, że „przeskakują one nad sobą”, co tłumaczy nazwę algorytmu (ang. leapfrog – skok przez plecy). Na przykład, położenie jest aktualizowane w pełnych wielokrotnościach kroku czasowego, natomiast prędkość w chwilach przesuniętych o

{\displaystyle \Delta t/2.}

Algorytm skokowy to metoda drugiego rzędu, w przeciwieństwie do metody Eulera, która jest metodą pierwszego rzędu, chociaż liczba wywołań funkcji w każdym kroku jest taka sama. W przeciwieństwie do całkowania metodą Eulera, algorytm ten jest stabilny w przypadku ruchu oscylacyjnego o częstości

{\displaystyle \omega ,}

pod warunkiem, że krok czasowy

{\displaystyle \Delta t}

jest stały oraz

{\displaystyle \Delta t\leqslant 2/\omega }

W algorytmie skokowym równania dla położenia i prędkości w kolejnych momentach czasu wyglądają następująco:

{\displaystyle {\begin{aligned}x_{i}&=x_{i-1}+v_{i-1/2}\,\Delta t,\\[0.4em]a_{i}&=F(x_{i})\\[0.4em]v_{i+1/2}&=v_{i-1/2}+a_{i}\,\Delta t,\end{aligned}}}

gdzie x jest położeniem w kroku i, v jest prędkością w kroku i+1/2, a a to przyspieszenie w kroku i. Równania te można zapisać również w formie, w której prędkość jest obliczana dla pełnych wielokrotności kroku czasowego. Niemniej jednak, nawet w tej zsynchronizowanej wersji, krok czasowy Δt musi być stały, aby zapewnić stabilność.

{\displaystyle {\begin{aligned}x_{i+1}&=x_{i}+v_{i}\,\Delta t+{\tfrac {1}{2}}\,a_{i}\,\Delta t^{\,2},\\[0.4em]v_{i+1}&=v_{i}+{\tfrac {1}{2}}\,(a_{i}+a_{i+1})\,\Delta t.\end{aligned}}}

Jednym z częstych zastosowań algorytmu skokowego są symulacje oddziaływań grawitacyjnych, gdzie przyspieszenie zależy wyłącznie od pozycji. Mimo to, metody wyższego rzędu (np. metody Rungego-Kutty) są znacznie częściej wykorzystywane.

Algorytm skokowy ma dwie istotne zalety:

  • Odwracalność w czasie – oznacza, że po wykonaniu n kroków można odwrócić kierunek całkowania i wrócić do tej samej pozycji wyjściowej.
  • Symplektyczność – algorytm ten zachowuje (nieznacznie zmodyfikowaną) całkę energii systemów dynamicznych, co oznacza, że całkowita energia układu oscyluje wokół pewnej stałej wartości bliskiej początkowej energii całkowitej. Jest to szczególnie ważne przy obliczaniu orbit w układach dynamicznych, gdzie inne metody całkowania, takie jak metody Rungego-Kutty, nie zachowują energii układu, co prowadzi do jego znacznego „płynięcia” w czasie.

Ze względu na te dwie właściwości, algorytm skokowy jest również stosowany w metodach Monte Carlo.

Przykładowa implementacja

Poniżej przedstawiono kod w środowisku MATLAB, który realizuje algorytm żabiego skoku w zsynchronizowanej formie. Program rozwiązuje równanie:

{\displaystyle {\frac {d^{t}{\bar {r}}}{dt^{2}}}={\frac {\bar {r}}{r^{3}}}}

opisujące oddziaływanie grawitacyjne dwóch ciał, przy czym przyjęto taki układ odniesienia, w którym suma dwóch oddziałujących ze sobą mas wynosi 1, a stała grawitacji także jest równa 1.

Zobacz też

  • metoda Eulera
  • algorytm Rungego-Kutty
  • algorytm Verleta

Przypisy

Linki zewnętrzne

Opis algorytmu. einstein.drexel.edu. [zarchiwizowane z tego adresu (2016-03-06)], Drexel University

Przeczytaj u przyjaciół: