Algorytm Verleta

Algorytm Verleta

Algorytm Verleta to metoda numeryczna, która służy do całkowania równań ruchu, co pozwala na obliczanie położeń i prędkości układów ciał w interakcji w funkcji czasu.

Jest on powszechnie stosowany w symulacjach fizycznych, szczególnie w obszarze dynamiki molekularnej, chociaż pojawia się również w grafice komputerowej. Znany jest również pod innymi nazwami, takimi jak jawna metoda różnic centralnych. Jest to najprostszy przykład metody Störmera.

Przeznaczenie algorytmu

Algorytm Verleta jest wykorzystywany do numerycznego rozwiązywania układów równań różniczkowych zwyczajnych drugiego rzędu, które mają postać:

{\displaystyle {\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 czas),
  • xi to zmienne zależne (zwykle odpowiadające położeniom),
  • ai to funkcje zależne od t i xi,
  • {\ddot {x}} oznacza drugą pochodną x względem czasu.

Równania tego typu obejmują m.in. równanie Newtona, które opisuje ruch układów punktów materialnych w polu zewnętrznych sił. To jeden z głównych powodów, dla których algorytm Verleta jest popularny w symulacjach dynamiki molekularnej oraz w realistycznych symulacjach cząsteczek w grafice komputerowej. W związku z tym w równaniu pojawiają się przyspieszenia ai, które często interpretowane są jako przyspieszenia lub formułowane w kontekście mas obiektów i działających na nie sił:

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

gdzie:

  • mi oznacza masę i-tego ciała,
  • Fi to wypadkowa siła działająca na i-te ciało w chwili t.

W przypadku symulacji w dwóch (lub więcej) wymiarach należy uwzględnić, że zarówno położenie, jak i siła mają więcej niż jedną składową.

Warianty algorytmu

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

  • Algorytm podstawowy:

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

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

  • Algorytm prędkościowy (velocity Verlet):

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

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

  • Algorytm skokowy (leap-frog method):

    {\displaystyle r(t+\Delta t)=r(t)+\Delta t v(t+\Delta t/2)}

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

  • Postać sumacyjna: (do uzupełnienia)

Wszystkie warianty algorytmu Verleta mają równoważność matematyczną, 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, gdzie krok czasowy Δt jest dodatni, pozwala na skonstruowanie sekwencji punktów bliskich rozwiązaniu trajektorii:

{\displaystyle t_{n}=n\Delta t}

Metoda Eulera wykorzystuje przybliżenie pierwszej pochodnej, podczas gdy integracja Verleta może być stosowana z drugą pochodną.

Integracja (algorytm) Verleta jest również używana jako opis metody Störmera, aby uzyskać kolejną pozycję wektora z dwóch poprzednich, stosując prędkości:

{\displaystyle {\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:

  • Jest odwracalny w czasie.
  • Zachowuje strukturę symplektyczną dynamiki Hamiltonowskiej (m.in. objętość potoku fazowego).
  • Generalnie nie zachowuje całkowitej energii, ale utrzymuje wartość pewnego zaburzonego Hamiltonianu H’, co sprawia, że całkowita energia układu fluktuuje wokół zadanej wartości w dłuższej perspektywie czasowej.
  • Wymaga jedynie jednokrotnego obliczania sił w każdym kroku czasowym.
  • Jest szybki, lecz niezbyt dokładny (zaliczany do algorytmów o dokładności globalnej rzędu drugiego).
  • Może być zaimplementowany na trzech tablicach (położenia, prędkości, siły).
  • Nie jest algorytmem ogólnym – jego zastosowanie ogranicza się do problemów, które można zapisać jako równania różniczkowe zwyczajne drugiego rzędu.
  • Może być problematyczny, gdy siły są uzależnione od prędkości.

Uwagi: Właściwości 1–3 obowiązują z dokładnością do błędów zaokrągleń. Popularne algorytmy, takie jak metoda Rungego-Kutty, koncentrują się na dokładności, lecz nie spełniają kluczowych dla fizyki postulatów 1–3. W symulacjach dynamiki molekularnej często mamy do czynienia z układami chaotycznymi, dlatego nie dąży się do uzyskania dokładnego rozwiązania, lecz do utrzymania trajektorii na powierzchni stałej energii.

Uwzględnienie sił zależnych od prędkości (np. tarcia) w algorytmie Verleta jest możliwe, choć niekoniecznie dokładne; takie uogólnione podejście stosuje się w symulacjach efektów specjalnych, jak w 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)].

Przeczytaj u przyjaciół: