Algorytm Verleta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Algorytm Verleta to 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[edytuj | edytuj kod]

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,\ldots,x_n), \qquad i = 1,2,\ldots,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,\ldots,x_n)}{m_i}, \qquad i = 1,2,\ldots,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[edytuj | edytuj kod]

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 t v( 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)[edytuj | edytuj kod]

Numeryczne rozwiązanie problemu pierwotnej wartości, krok czasowy \Delta t>0 jest wybranm 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]