Algorytm Verleta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Algorytm Verletametoda 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]

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

gdzie oznacza liczbę równań, jest zmienną niezależną (zwykle jest nią czas), to zmienne zależne (zwykle odpowiadające położeniom), są dowolnymi funkcjami i , natomiast zapis oznacza drugą pochodną 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 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:

gdzie oznacza masę -tego ciała, a jest wypadkową siłą działającą na -te ciało w chwili . 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]

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

  • algorytm podstawowy
  • algorytm prędkościowy (velocity Verlet)
  • algorytm skokowy (leap-frog method)
  • postać sumacyjna (uzupełnić)

gdzie:

- krok czasowy
- prędkość w chwili
- położenie w chwili
- siła w chwili

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]

Numeryczne rozwiązanie problemu pierwotnej wartości, krok czasowy jest wybranym przykładowo punktem z rozważanej sekwencji . Zadaniem jest skonstruowanie sekwencji punktów blisko punktów 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ą.

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


Cechy algorytmu[edytuj]

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 . 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]