Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Beeman's algorithm
open-in-new
<h2 id="equation">Equation</h2> <p>The formula used to compute the positions at time t + Δ t {\displaystyle t+\Delta t} in the full predictor-corrector<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> scheme is: </p> <ul><li>Predict x ( t + Δ t ) {\displaystyle x(t+\Delta t)} from data at times t and t − Δ t {\displaystyle t{\text{ and }}t-\Delta t} </li></ul> x ( t + Δ t ) = x ( t ) + v ( t ) Δ t + 1 6 ( 4 a ( t ) − a ( t − Δ t ) ) Δ t 2 + O ( Δ t 4 ) {\displaystyle x(t+\Delta t)=x(t)+v(t)\Delta t+{\frac {1}{6}}{\Bigl (}4a(t)-a(t-\Delta t){\Bigr )}\Delta t^{2}+O(\Delta t^{4})} . <ul><li>Correct position and velocities at time t + Δ t {\displaystyle t+\Delta t} from data at times t and t + Δ t {\displaystyle t{\text{ and }}t+\Delta t} by repeated evaluation of the differential equation to get the acceleration a ( t + Δ t ) {\displaystyle a(t+\Delta t)} and of the equations of the implicit system</li></ul> x ( t + Δ t ) = x ( t ) + v ( t ) Δ t + 1 6 ( a ( t + Δ t ) + 2 a ( t ) ) Δ t 2 + O ( Δ t 4 ) ; v ( t + Δ t ) Δ t = x ( t + Δ t ) − x ( t ) + 1 6 ( 2 a ( t + Δ t ) + a ( t ) ) Δ t 2 + O ( Δ t 4 ) ; {\displaystyle {\begin{aligned}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)+{\frac {1}{6}}{\Bigl (}2a(t+\Delta t)+a(t){\Bigr )}\Delta t^{2}+O(\Delta t^{4});\end{aligned}}} 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. <p>Using only the predictor formula and the corrector for the velocities one obtains a direct or explicit method<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> which is a variant of the Verlet integration method:<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> x ( t + Δ t ) = x ( t ) + v ( t ) Δ t + 1 6 ( 4 a ( t ) − a ( t − Δ t ) ) Δ t 2 + O ( Δ t 4 ) v ( t + Δ t ) = v ( t ) + 1 6 ( 2 a ( t + Δ t ) + 5 a ( t ) − a ( t − Δ t ) ) Δ t + O ( Δ t 3 ) ; {\displaystyle {\begin{aligned}x(t+\Delta t)&=x(t)+v(t)\Delta t+{\frac {1}{6}}{\Bigl (}4a(t)-a(t-\Delta t){\Bigr )}\Delta t^{2}+O(\Delta t^{4})\\v(t+\Delta t)&=v(t)+{\frac {1}{6}}{\Bigl (}2a(t+\Delta t)+5a(t)-a(t-\Delta t){\Bigr )}\Delta t+O(\Delta t^{3});\end{aligned}}} <p>This is the variant that is usually understood as <i>Beeman's method</i>. </p><p>Beeman<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> also proposed to alternatively replace the velocity update in the last equation by the second order <a href="/facts/Linear_multistep_method/Q1taSMtG">Adams–Moulton method</a>: </p> v ( t + Δ t ) = v ( t ) + 1 12 ( 5 a ( t + Δ t ) + 8 a ( t ) − a ( t − Δ t ) ) Δ t + O ( Δ t 3 ) {\displaystyle 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})} <p>where </p> <ul><li> t {\displaystyle t} is present time (i.e.: independent variable)</li> <li> Δ t {\displaystyle \Delta t} is the time step size</li> <li> x ( t ) {\displaystyle x(t)} is the position at time t</li> <li> v ( t ) {\displaystyle v(t)} is the velocity at time t</li> <li> a ( t ) {\displaystyle a(t)} is the acceleration at time t, computed as a function of x ( t ) {\displaystyle x(t)} </li> <li>the last term is the error term, using the <a href="/facts/Big_O_notation/weFFjSWg">big O notation</a></li></ul> <h2 id="predictorcorrector-modifications">Predictor–corrector modifications</h2> <p>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 + Δ t {\displaystyle t+\Delta t} are predicted and the forces calculated, before producing a corrected form of the velocities. </p><p>An example is: </p> x ( t + Δ t ) = x ( t ) + v ( t ) Δ t + 2 3 a ( t ) Δ t 2 − 1 6 a ( t − Δ t ) Δ t 2 + O ( Δ t 4 ) . {\displaystyle 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}).} <p>The velocities at time t = t + Δ t {\displaystyle t=t+\Delta t} are then calculated (predicted) from the positions. </p> v ( t + Δ t ) (predicted) = v ( t ) + 3 2 a ( t ) Δ t − 1 2 a ( t − Δ t ) Δ t + O ( Δ t 3 ) . {\displaystyle v(t+\Delta t)~{\text{(predicted)}}=v(t)+{\frac {3}{2}}a(t)\Delta t-{\frac {1}{2}}a(t-\Delta t)\Delta t+O(\Delta t^{3}).} <p>The accelerations a ( t + Δ t ) {\displaystyle a(t+\Delta t)} at time t = t + Δ t {\displaystyle t=t+\Delta t} are then calculated from the positions and predicted velocities, and the velocities are corrected. </p> v ( t + Δ t ) (corrected) = v ( t ) + 5 12 a ( t + Δ t ) Δ t + 2 3 a ( t ) Δ t − 1 12 a ( t − Δ t ) Δ t + O ( Δ t 3 ) . {\displaystyle v(t+\Delta t)~{\text{(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}).} <h2 id="error-term">Error term</h2> <p>As shown above, the local error term is O ( Δ t 4 ) {\displaystyle O(\Delta t^{4})} for position and O ( Δ t 3 ) {\displaystyle O(\Delta t^{3})} velocity, resulting in a global error of O ( Δ t 3 ) {\displaystyle O(\Delta t^{3})} . In comparison, Verlet is O ( Δ t 2 ) {\displaystyle O(\Delta t^{2})} for position and velocity. In exchange for greater accuracy, Beeman's algorithm is moderately computationally more expensive. </p> <h2 id="memory-requirements">Memory requirements</h2> <p>The simulation must keep track of position, velocity, acceleration and previous acceleration vectors per particle (though some clever workarounds 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. </p> <ul><li>Sadus, Richard J. (2002), <i>Molecular Theory of Fluids: Theory, Algorithms and Object-Orientation</i>, Elsevier, p. 231, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-51082-6</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Schofield, P. (1973), "Computer simulation studies of the liquid state", Computer Physics Communications, 5 (1): 17–23, Bibcode:1973CoPhC...5...17S, doi:10.1016/0010-4655(73)90004-0 <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Beeman, David (1976), "Some multistep methods for use in molecular dynamics calculations", Journal of Computational Physics, vol. 20, no. 2, pp. 130–139, Bibcode:1976JCoPh..20..130B, doi:10.1016/0021-9991(76)90059-0 <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Beeman, David (1976), "Some multistep methods for use in molecular dynamics calculations", Journal of Computational Physics, vol. 20, no. 2, pp. 130–139, Bibcode:1976JCoPh..20..130B, doi:10.1016/0021-9991(76)90059-0 <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Schofield, P. (1973), "Computer simulation studies of the liquid state", Computer Physics Communications, 5 (1): 17–23, Bibcode:1973CoPhC...5...17S, doi:10.1016/0010-4655(73)90004-0 <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Levitt, Michael; Meirovitch, Hagai; Huber, R. (1983), "Integrating the equations of motion", Journal of Molecular Biology, 168 (3): 617–620, doi:10.1016/S0022-2836(83)80305-2, PMID 6193281 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Beeman, David (1976), "Some multistep methods for use in molecular dynamics calculations", Journal of Computational Physics, vol. 20, no. 2, pp. 130–139, Bibcode:1976JCoPh..20..130B, doi:10.1016/0021-9991(76)90059-0 <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> </ol>