World Library  
Flag as Inappropriate
Email this Article

Beeman's algorithm

Article Id: WHEBN0004077261
Reproduction Date:

Title: Beeman's algorithm  
Author: World Heritage Encyclopedia
Language: English
Subject: Numerical differential equations, Crank–Nicolson method, Runge–Kutta methods, Verlet integration, Numerical methods for ordinary differential equations
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Beeman's algorithm

Beeman's algorithm is a method for numerically integrating ordinary differential equations of order 2, more specifically Newton's equations of motion \ddot x=A(x). It was designed to allow high numbers of particles in simulations of molecular dynamics. There is a direct or explicit and an implicit variant of the method. The direct variant was published by Schofield [1] in 1973 as personal communication by Beeman. This is what is commonly known as Beeman's method. It is a variant of the Verlet integration method. It produces identical positions, but uses a different formula for the velocities. Beeman[2] in 1976 published a class of implicit (predictor-corrector) multi-step methods, where Beeman's method is the direct variant of the third order method in this class.

Contents

  • Equation 1
  • Predictor-Corrector Modifications 2
  • Error term 3
  • Memory Requirements 4
  • References 5

Equation

The formula used to compute the positions at time t + \Delta t in the full predictor-corrector[2] scheme is:

  • Predict x(t+\Delta t) from data at times t\text{ and }t - \Delta t
x(t+\Delta t) = x(t) + v(t) \Delta t + \frac{1}{6}\Bigl( 4 a(t) - a(t - \Delta t)\Bigr)\Delta t^2 + O( \Delta t^4) .
  • Correct position and velocities at time t + \Delta t from data at times t\text{ and }t+\Delta t by repeated evaluation of the differential equation to get the acceleration a(t+\Delta t) and of the equations of the implicit system
\begin{align} x(t+\Delta t) &= x(t) + v(t) \Delta t + \frac{1}{6}\Bigl(a(t+\Delta t) + 2a(t)\Bigr)\Delta t^2 + O(\Delta t^4);\\ v(t+\Delta t)\Delta t &=x(t+\Delta t)-x(t) + \frac16 \Bigl(2a(t+\Delta t) + a(t)\Bigr)\Delta t^2 + O(\Delta t^4); \end{align}
In tests it was found that this corrector step needs to be repeated at most twice. The values on the right are the old values of the last iterations, resulting in the new values on the left.

Using only the predictor formula and the corrector for the velocities one obtains a direct or explicit method[1] which is a variant of the Verlet integration method:[3]

\begin{align} x(t+\Delta t) &= x(t) + v(t) \Delta t + \frac{1}{6}\Bigl( 4 a(t) - a(t - \Delta t)\Bigr)\Delta t^2 + O( \Delta t^4) \\ v(t+\Delta t) &=v(t) + \frac16 \Bigl(2a(t+\Delta t) + 5a(t)-a(t-\Delta t)\Bigr)\Delta t + O(\Delta t^3); \end{align}

This is the variant that is usually understood as Beeman's method.

Beeman[2] also proposed to alternatively replace the velocity update in the last equation by the second order Adams–Moulton method:

v(t + \Delta t) = v(t) + \frac{1}{12}\Bigl(5a(t + \Delta t) + 8a(t) - a(t - \Delta t)\Bigr)\Delta t + O(\Delta t^3)

where

  • t is present time (i.e.: independent variable)
  • \Delta t is the time step size
  • x(t) is the position at time t
  • v(t) is the velocity at time t
  • a(t) is the acceleration at time t, computed as a function of x(t)
  • the last term is the error term, using the big O notation

Predictor-Corrector Modifications

In systems where the forces are a function of velocity in addition to position, the above equations need to be modified into a predictor-corrector form whereby the velocities at time t + \Delta t are predicted and the forces calculated, before producing a corrected form of the velocities.

An example is:

x(t+\Delta t) = x(t) + v(t) \Delta t + \frac{2}{3}a(t) \Delta t^2 - \frac{1}{6} a(t - \Delta t) \Delta t^2 + O( \Delta t^4).

The velocities at time t =t + \Delta t are then calculated from the positions.

v(t + \Delta t) (predicted) = v(t) + \frac{3}{2}a(t) \Delta t - \frac{1}{2}a(t - \Delta t) \Delta t + O( \Delta t^3)

The accelerations at time t =t + \Delta t are then calculated from the positions and predicted velocities.

v(t + \Delta t) (corrected) = v(t) + \frac{5}{12}a(t + \Delta t) \Delta t + \frac{2}{3}a(t) \Delta t - \frac{1}{12}a(t - \Delta t) \Delta t + O( \Delta t^3)

Error term

As shown above, the local error term is O(\Delta t^4) for position and O(\Delta t^3) velocity,resulting in a global error of O(\Delta t^3). In comparison, Verlet is O(\Delta t^4) for position and O(\Delta t^2) for velocity, however, the more important global error is O(\Delta t^2). In exchange for greater accuracy, Beeman's algorithm is moderately computationally more expensive.

Memory Requirements

The simulation must keep track of position, velocity, acceleration and previous acceleration vectors per particle (though some clever work-arounds for storing the previous acceleration vector are possible), keeping its memory requirements on par with velocity Verlet and slightly more expensive than the original Verlet method.

References

  1. ^ a b Schofield, P. (1973), "Computer simulation studies of the liquid state", Computer Physics Communications 5 (1): 17–23,  
  2. ^ a b c Beeman, David (1976), "Some multistep methods for use in molecular dynamics calculations", Journal of Computational Physics 20 (2): 130–139,  
  3. ^ Levitt, Michael; Meirovitch, Hagai; Huber, R. (1983), "Integrating the equations of motion", Journal of Molecular Biology 168 (3): 617–620,  
  • Sadus, Richard J. (2002), Molecular Theory of Fluids: Theory, Algorithms and Object-Orientation, Elsevier, p. 231,  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.