Algorytm Verleta

Algorytm Verleta – metoda numeryczna służąca do całkowania równań ruchu, czyli do obliczania położeń i prędkości układu oddziałujących ciał w funkcji czasu. Rutynowo wykorzystywany w symulacjach fizycznych (głównie w dynamice molekularnej), rzadziej w grafice komputerowej. Znany jest także pod innymi nazwami, np. jako jawna metoda różnic centralnych. Stanowi najprostszy przykład metody Störmera.

Przeznaczenie algorytmu

Algorytm Verleta służy do numerycznego rozwiązywania układów równań różniczkowych zwyczajnych rzędu drugiego postaci

${\ddot {x}}_{i}=a_{i}(t,x_{1},x_{2},\dots ,x_{n}),\qquad i=1,2,\dots ,n,$

gdzie $n$ oznacza liczbę równań, $t$ jest zmienną niezależną (zwykle jest nią czas), $x_{i}$ to zmienne zależne (zwykle odpowiadające położeniom), $a_{i}$ są dowolnymi funkcjami $t$ i $x_{i},$ natomiast zapis ${\ddot {x}}$ oznacza drugą pochodną $x$ po czasie.

Równaniami tego typu są m.in. równanie Newtona, opisujące ruch układu oddziałujących punktów materialnych w polu zewnętrznych sił. Jest to jeden z powodów popularności algorytmu Verleta w symulacjach dynamiki molekularnej oraz w symulacjach tzw. realistycznych układów cząsteczkowych w grafice komputerowej. Z tego powodu występujące w powyższym wzorze wielkości $a_{i}$ zwykle interpretuje się jako przyspieszenia bądź też od razu równania te formułuje się w postaci uwzględniającej masy obiektów oraz działające na nie siły:

${\ddot {x}}_{i}={\frac {F_{i}(t,x_{1},x_{2},\dots ,x_{n})}{m_{i}}},\qquad i=1,2,\dots ,n$

gdzie $m_{i}$ oznacza masę $i$-tego ciała, a $F_{i}$ jest wypadkową siłą działającą na $i$-te ciało w chwili $t.$ Oczywiście w przypadku symulacji dwu- (lub więcej) wymiarowych należy uwzględniać fakt, że położenie i siła mają dwie (lub więcej) składowe.

Warianty algorytmu

Algorytm Verleta występuje w kilku wariantach, z których najpopularniejsze, to

• algorytm podstawowy

$r(t+\Delta t)=2r(t)-r(t-\Delta t)+{\frac {f(t)}{m}}\Delta t^{2}$

$v(t)={\frac {r(t+\Delta t)-r(t-\Delta t)}{2\Delta t}}$

• algorytm prędkościowy (velocity Verlet)

$r(t+\Delta t)=r(t)+v(t)\Delta t+{\frac {f(t)}{2m}}\Delta t^{2}$

$v(t+\Delta t)=v(t)+{\frac {f(t+\Delta t)+f(t)}{2m}}\Delta t$

• algorytm skokowy (leap-frog method)

$r(t+\Delta t)=r(t)+\Delta tv(t+\Delta t/2)$

$v(t+\Delta t/2)=v(t-\Delta t/2)+\Delta t{\frac {f(t)}{m}}$

• postać sumacyjna (uzupełnić),

gdzie:

$\Delta t$ – krok czasowy,

$v(t)$ – prędkość w chwili $t,$

$r(t)$ – położenie w chwili $t,$

$f(t)$ – siła w chwili $t.$

Wszystkie warianty algorytmu Verleta są równoważne matematycznie, różnią się jednak sposobem propagacji błędów zaokrągleń.

Integracja (algorytm) Verleta (bez prędkości)

Numeryczne rozwiązanie problemu pierwotnej wartości, krok czasowy $\Delta t>0$ jest wybranym przykładowo punktem z rozważanej sekwencji $t_{n}=n\Delta t.$ Zadaniem jest skonstruowanie sekwencji punktów ${\vec {x}}_{n}$ blisko punktów ${\vec {x}}(t_{n})$ na trajektorii wymaganego rozwiązania.

Metoda Eulera używa przybliżenia pierwszej pochodnej w równaniu różniczkowym. Integracja Verleta może być także używana z drugą pochodną.

${\frac {\Delta ^{2}{\vec {x}}_{n}}{\Delta t^{2}}}={\frac {{\frac {{\vec {x}}_{n+1}-{\vec {x}}_{n}}{\Delta t}}-{\frac {{\vec {x}}_{n}-{\vec {x}}_{n-1}}{\Delta t}}}{\Delta t}}={\frac {{\vec {x}}_{n+1}-2{\vec {x}}_{n}+{\vec {x}}_{n-1}}{\Delta t^{2}}}={\vec {a}}_{n}=A({\vec {x}}_{n}).$

Integracja (algorytm) Verleta używana jest także jako opis metody Störmera. Stosuje się to równanie, aby uzyskać następną pozycję wektora z dwóch poprzednich używając prędkości

${\vec {x}}_{n+1}=2{\vec {x}}_{n}-{\vec {x}}_{n-1}+{\vec {a}}_{n}\,\Delta t^{2},\qquad {\vec {a}}_{n}=A({\vec {x}}_{n}).$

Cechy algorytmu

Algorytm Verleta:

1. Jest odwracalny w czasie.
2. Zachowuje strukturę symplektyczną dynamiki Hamiltonowskiej (a więc m.in. objętość potoku fazowego).
3. Z reguły nie zachowuje całkowitej energii, ale zachowuje wartość pewnego zaburzonego Hamiltonianu $H'.$ Oznacza to, że nawet podczas długotrwałych symulacji całkowita energia układu w sposób kontrolowany fluktuuje wokół wartości zadanej.
4. Wymaga tylko jednokrotnego obliczania sił w każdym kroku czasowym.
5. Jest szybki, ale niezbyt dokładny (zaliczany jest do algorytmów o dokładności globalnej rzędu drugiego).
6. Może być w całości zaimplementowany na zaledwie trzech tablicach (położenia, prędkości, siły).
7. Nie jest algorytmem ogólnym – znajduje zastosowanie głównie do problemów, które można zapisać w postaci równań różniczkowych zwyczajnych rzędu drugiego.
8. Jest kłopotliwy, jeśli siły zależą od prędkości.

Uwagi.

• Właściwości 1–3 spełnione są z dokładnością do błędów zaokrągleń.
• Popularne, ogólne algorytmy rozwiązywania równań różniczkowych zwyczajnych (np. Rungego-Kutty) koncentrują się na uzyskaniu jak najdokładniejszego wyniku jak najmniejszym nakładem obliczeń, nie spełniają jednak kluczowych dla fizyki postulatów 1–3. Symulacje dynamiki molekularnej zwykle mają do czynienia z układami chaotycznymi z losowo dobranym warunkiem początkowym i choćby z tego powodu nie dążą do osiągnięcia dokładnego rozwiązania – dużo ważniejsze jest utrzymanie trajektorii rozwiązania na powierzchni stałej energii.
• Uwzględnienie w algorytmie sił zależących od prędkości (np. tarcia) jest łatwe, o ile nie zależy nam na dokładności. Taki uogólniony algorytm Verleta stosuje się m.in. przy tworzeniu komputerowych efektów specjalnych, np. w symulacjach ruchu tkanin.

Linki zewnętrzne

• Algorytm Verleta. fisica.uniud.it. [zarchiwizowane z tego adresu (2004-08-03)].
• Teoria symulacji z Dynamiki Molekularnej. ch.embnet.org. [zarchiwizowane z tego adresu (2006-04-26)]. – dół strony