Talk:Verlet integration

Untitled

I suggest everything below and including "Constraints" should be deleted, or moved to its own article about the use of the Verlet algorithm in game programming. —Preceding unsigned comment added by 145.116.227.10 (talk) 22:20, 2 February 2008 (UTC)

Isn't this more physics than maths?

A little harsh, but I agree it needs to be expanded. Velocity-Verlet and leapfrog should be explored, or at least linked to. The derivation of verlet itself is easy enough to show (it comes from an algebraic manipulation of the third order taylor expansions, one forward and one backward in time). Also, some accuracy details would be nice (ie: 4th order accurate, 2nd order, etc.) --Numsgil 16:48, 12 February 2006 (UTC)

The section titled "the algorithm" starts on the wrong foot "At first it may seem simpler". This section IMHO should contain only a cold, clear, crisp statement of the Verlet formulas. No "may" "if" or "but". The comparison to the simpler Euler method is valuable but belongs later on in a derivation or discussion section. (As for the third order Taylor expansion derivation, it seems to me that the 14 year old has already provided it :-) ). We might also want to mention that Verlet is an example of "symplectic integration" methods that are designed to respect the properties of mechanical systems (such as conservation of energy and reversibility in time). Encyclops 17:32, 12 February 2006 (UTC)

Basic Verlet

It might seem misleading when one uses t_0 for the current time. Normally one mentions t_0 as the initial time and uses t further on. Also all positions, velocities and accelerations should be in vector notation. It should be mentioned for the Basic Verlet algorithm that for the first time step one should use another formula, while x(t - \Delta t) is not known at t = 0.

Shouldn't

$\nabla ^{2}{\vec {x}}(t)={\frac {{\vec {x}}(t+\Delta t)-2{\vec {x}}(t)+{\vec {x}}(t)}{\Delta t^{2}}}+{\mathcal {O}}(\Delta t^{4})$

be

$\nabla ^{2}{\vec {x}}(t)={\frac {{\vec {x}}(t+\Delta t)-2{\vec {x}}(t)+{\vec {x}}(t-\Delta t)}{\Delta t^{2}}}+{\mathcal {O}}(\Delta t^{4})$

instead? -- Jagot 17:01, 5th June 2009 (GMT+1) —Preceding undated comment added 15:01, 5 June 2009 (UTC).

Velocity error term

As far as I can tell from [1] the velocity error term is delta t^2. If I'm reading it wrong, feel free to correct me. --Numsgil 12:44, 15 February 2006 (UTC)

So what? This agrees with the article, which says

$v(t_{0})={\frac {x(t_{0}+\Delta t)-x(t_{0}-\Delta t)+O(\Delta t^{3})}{2\Delta t}}={\frac {x(t_{0}+\Delta t)-x(t_{0}-\Delta t)}{2\Delta t}}+O(\Delta t^{2}).$

Or do you mean something else? -- Jitse Niesen (talk) 13:16, 15 February 2006 (UTC)

oh, does the delta t at the bottom of the fraction cancel out an order of magnitude for the error function? That seems unclear to me, perhaps the second error form should be used instead of the first, to heighten clarity? --Numsgil 19:09, 15 February 2006 (UTC)

I agree the second form is clearer, so I used that one instead. Regarding the cancellation: $O(\Delta t^{3})$ means roughly $C(\Delta t)^{3}$ for some constant C, and

${\frac {C(\Delta t)^{3}}{\Delta t}}=C(\Delta t)^{2}.$

To my surprise, this is not mentioned on Big-O notation; perhaps it should be? -- Jitse Niesen (talk) 19:56, 15 February 2006 (UTC)

What's the problem with these error terms? It's clear that this is an expansion in \Delta t linear in \Delta t, which means O(\Delta t^2). If you like I'll give a proof for this, based on the Basic Verlet algorithm later this week. The whole discussion on this page about the error term is a bit knotty. -- anon

The problem that Numsgil was having is resolved, as far as I know.

You're right that the article is not very clear, and I would welcome any improvements. In particular, I feel that it should start by writing down the equation solved by the algorithm. What determines the acceleration and how is it computed? -- Jitse Niesen (talk) 14:38, 16 December 2007 (UTC)

Velocity Verlet

There should also be mentioned what the difficulty's are while using this algorithm, for example when simulating many body problems with long ineraction potentials, how to take \Delta t, conservation laws, ...

Constraints

This should be a slightly more efficient way of doing what is currently demonstrated in the Constraints section.

$\Delta x=x_{1}-x_{2}\,$

$d=0.5\left(1.0-{\frac {r}{\sqrt {\Delta x^{2}}}}\right)\,$

$x_{1}=x_{1}-\Delta xd\,$

$x_{2}=x_{2}+\Delta xd\,$

And some pseudo-code:

/* Pre-defined variables */
vector x1, x2  // Positions of the particles
double r       // The length at which the constraint is at rest

vector delta = x1 - x2
double d = 0.5 * (1.0 - r / sqrt(delta * delta))

x1 -= delta * d
x2 += delta * d

N.B. The described constraint method (e.g. Jacobsen's Verlet projection method, which it is popularly referred to in the game physics litterature) isn't faithful to the scientific literature. It would be more apropriate to describe the RATTLE and SHAKE methods, and show that in velocity form, with the right hand side terms neglected, we end up having a simple, but often broken (very heavily damped) method, which indeed is this projection method by Verlet integration that is described here. —Preceding unsigned comment added by 89.160.50.2 (talk) 18:51, 17 September 2007 (UTC)

sorry for nitpicking, isn't is cleaner with |x| rather than with sqrt(sqr(x)) ;)? --- ca1 147.229.179.174 (talk) 16:06, 7 April 2008 (UTC)

Inverting a Matrix

In regards to Arnero's edit, while my gut tells me that this is right, that satisfying constraints is similar to matrix inversion, I don't have the mathematical background to see it, let alone put it to practical use. I'm sure others are in the same boat.

I would appreciate a simple explanation of what the matrix would even be or look like (if you would construct such a matrix), where to start, how to compare my "home grown" constraint satisfier with gaussian elimination or other methods, etc.

The two primary concerns in a constraint satisfier in any real time application are the order of convergence (how many time steps it takes to reach an acceptable answer) and overall stability over time (more difficult to quantify). If techniques from linear algebra can provide better solutions, I'd personally like to explore them.

--Numsgil 23:13, 2 November 2006 (UTC)

I wanted to integrate wisdom from the open dynamics engine: The author says verlet is unstable. Personally i like kiss systems and I looked into simulation of maxwell equations and of fluid dynamics and there global algorithms are pure nonsense. But if mechanics is simlated in so large time steps, that sound waves cannot be simulated, I understand that constraints need to be simulated with abstract code (violating KISS). My theoretical mechanics professor liked to use lagrangian mechanics and solve the equations analytically. But I understand that this is only possible for the samll systems he researched (up to 10 joints). So for real world applications I would calculate the violation of constraints every frame. By approximating the constraints (containing cos, sqrt etc) by a linear equation around its current value it is possible to correct the deviations by linar algebra methods (matrix inversion) and to limit the movement to the tangent space. As we use small steps anyway the approximation is in harmony with the rest of the simulation. Because the matrix inversion connects every joint, the constraint are met better globally. Stiffness is avoided. Stiffness is very evil so we go large distance to avoid it.

But the open dynamics engine is moving away from precise matrix inversion. I glanced over conjugate gradient method, but I have the impression that they are not better than pure verlet integration, but only formulated in a way, which is above my comprehension.Arnero 14:34, 4 November 2006 (UTC)

The above comment, comparing CG with Verlet projection is pretty confused. Anderson's RATTLE method is the correct starting point, and this method can be solved either by direct methods, or by iterative methods such as a linear relaxation method e.g. Gauss-Seidel, Jacobi, or Krylov type of methods like Conjugate Gradient. The advantage of e.g. GS over CG is that it conserves momentum and energy locally and thus works well with damping, while CG can cause local jittery behaviour. On the other hand CG has much better convergence if you need to go to higher precision. —Preceding unsigned comment added by 89.160.50.2 (talk) 18:56, 17 September 2007 (UTC)

If GS has an advantage over CG in that it conserves energy and momentum locally, then why not suggest that multigrid methods be used in Verlet integration? — Preceding unsigned comment added by 2603:6011:6C06:A200:A8E1:F854:688B:8D22 (talk) 00:42, 23 February 2021 (UTC)

acceleration, another methods, constraints

acceleration

$x(t_{0}+\Delta t)=2x(t_{0})-x(t_{0}-\Delta t)+a\Delta t^{2}$

Is the acceleration a in time t0? So is it a(t0)? Or is it something different?

But what if in my problem the a(t) depends on v(t)? (For example air drag, where air drag force depends on the speed and the acceleration depend on this force.) It seems that I can't use this integration method for such problem. Or can anybody explain better the part of this article with the "very simple damping effect"?

\vec{a}(t + \Delta t) is calculated using values of \vec{x} and \vec{v} dependent on the potential of the interaction.

You can probably use the old v(t - dt). But the damping effect can be also implemented directly into the Verlet equations, as shown in the article. Note that it is better to scale the constant f with the current dt (i.e. use coefficients (2-f*dt) and (1-f*dt), where f is a constant, and 0 < f*dt < 1).

another methods

Could anybody please compare Verlet integration with another integration methods? (I don't call Euler integration a "method".)

Range-Kutta? Predictor-Corrector.

constraints

Could anybody please compare kind of solving constraints mentioned in this article with Lagrange multipliers?

--147.230.151.146 12:20, 30 November 2006 (UTC)

There is an error in the formula

The acceleration term is written as a(delta_t)^2.

It should have been a(t0)*delta_2^2. This is consistent with the derivation section where the correct value is shown.

Please read the comments I added in the beginning of this discussion under "Basic Verlet" about the t0.

—Preceding unsigned comment added by 85.82.232.123 (talk) 19:26, 10 December 2007 (UTC)

 Done. I no longer see any bare "a" referring to acceleration anywhere.

All of them have been fixed to read ${\vec {a}}_{i}$ or ${\vec {a}}(t)$ or $A{\big (}{\vec {x}}(t){\big )}$. Thank you! --DavidCary (talk) 21:33, 27 October 2019 (UTC)

Is the "Constraints" section related to Verlet integration at all?

The formulas in the current Constraints sections does not use any information at all from the previous timestep, so how is it an application of Verlet integration? --Dolda2000 (talk) 02:42, 1 April 2008 (UTC)

They're both mentioned in the Jakobsen article mainly, which has a lot of notoriety amongst indie game programmers (maybe some professional ones too. Couldn't say.) You're right, it doesn't necessarily belong in this article. I'd vote to remove it. --Numsgil (talk) 07:30, 1 April 2008 (UTC)

Fixed the equations in that section -- the constraint resolution is time-dependent and only works in a Verlet-like scheme. The attached source code, however, is just wrong... Is this in the Jakobsen article? Why do we have code in a theoretical article anyway? Anyway, the main article on this subject is Constraint algorithm -- I will add a link at the top to that effect. Cheers, pedro gonnet - talk - 01.04.2008 07:39

Estimating velocity using the mean value theorem

The recommendation of this article is to take the position at time t + h and time t - h, and use the mean value theorem to approximate the slope (velocity). However, I've been doing some experimenting, and it seems to me that taking the position at time t and t + h gives a better approximation to the velocity. This makes intuitive sense, as well, since the velocity term will respond better to local changes in force. My test cases are all damped spring equations where the force (acceleration) is related to position and velocity. So, I guess my point is that either I'm not understanding something, or the bit about approximating the velocity should be changed. --Numsgil (talk) 05:58, 2 June 2008 (UTC)

unclear wording

In the opening paragraph, it says:

"However, this kind of integration suffers from many problems, as discussed at Euler integration. Stability of the technique depends fairly heavily upon either a uniform update rate, or the ability to accurately identify positions at a small time delta into the past."

This is a bit unclear -- the stability of "the technique" refers to Euler, or to Verlet? Can whoever wrote this please clarify? Thanks, 71.130.208.192 (talk) 20:31, 29 November 2008 (UTC)

4 stage algorithm

It provides 4 stages in the "Velocity Verlet" section although the displacement calculated in step 1) is not required in the subsequent 3 stages to calculate the velocity. Thus, including step 1) in the calculation of the velocity is strictly incorrect.

Velocity verlet is not equal to leapfrog verlet =

The article implies they are the same thing, whereas if you go to the link that is references there, a distinction is made between the two methods.

I agree here. They are not the same. —Preceding unsigned comment added by 88.67.163.187 (talk) 18:35, 22 June 2010 (UTC)

I think they are the same. One can write the velocity at either the current time step, or half-way between the current and next time step; both equations are usually presented when describing Velocity Verlet (see for instance Hairer et al 2006 page 8) and are easily shown to be mathematically equivalent. TotientDragooned (talk) 20:33, 5 August 2010 (UTC)

The Velocity Verlet scheme is the same as the Newmark-$\beta$ scheme with $\beta =0$, though, no? This might be worth mentioning. Pipping (talk) 13:35, 13 February 2013 (UTC)

This article hides how Verlet integration works

It should be possible to quickly find the numerical method that is used in Verlet integration. This is not the case now. By looking at the section headings, you will first find "Basic Störmer–Verlet", followed by "Velocity Verlet" which is clearly not the same thing as Verlet integration. So is maybe "Basic Störmer–Verlet" the same thing as Verlet integration? Okay, let's give it a shoot.

The subsections under "Basic Störmer–Verlet" reads "Equations of motion" — which is clearly not what we are looking for, since this contains no temporally discretized equations — then "Störmer's method" and then comes examples, so Verlet integration must have already been presented, hence in the subsection "Störmer's method". But "Störmer's method", who the heck is Störmer? I wanted to read about Verlet integration.

Then, if you start the read the article from the beginning, in the leading paragraph it becomes apparent that Störmer appears to have been the first guy we know of who has used Verlet integration, and that therefore the method is also called "Störmer's method". This still doesn't make it okay to suddenly change from "Verlet integration", which after all is the title of the article and what the reader is looking for in the article and expects to find, to "Störmer's method". This is inconsistent and makes the reader confused, and heck, it has made me write all this section ranting about this bad section naming instead of just simply change the section name from "Störmer's method" to "Verlet integration". —Kri (talk) 15:50, 15 November 2013 (UTC)

Error in 'Non-constant time differences' formula?

The formula at the end of this section seems to have an error: as it stands, the ${\frac {\Delta t_{i-1}+\Delta t_{i-1}}{2}}$ term could be simplified to just $\Delta t_{i-1}$. I'm not sure what the correct formula is, but I suspect that one of the $\Delta t_{i-1}$ should be a $\Delta t_{i}$? Corryn (talk) 10:33, 22 April 2014 (UTC)

I think you are quite correct; I changed the formula accordingly. 128.214.72.131 (talk) 20:42, 6 May 2014 (UTC)

Constraints Section - tone

The tone seems very instructional and conversational, in addition it seems a bit out of context, like it was just pasted from a lecture somewhere. I can't quite figure out what this section is about. If it is about Verlet integration in solving multiple-particle systems, it should be retitled and replaced with an overview of that.Cyrej (talk) 17:39, 12 October 2015 (UTC)

I've removed some details and rewritten the same content in hopefully clearer and more encyclopedic style, still not sure about the content itself. The section should include a better overview of constraints or multiple-particle problems or whatever it is about. — Preceding unsigned comment added by Cyrej (talk • contribs) 20:02, 12 October 2015 (UTC)

Anything referencing Jonathan Dummer should be removed

This article should not be referenced, because "the article either misapplies or misderives every integration method it demonstrates" (quoting myself here).

This is the article http://www.gamedev.net/page/resources/_/technical/math-and-physics/a-simple-time-corrected-verlet-integration-method-r2200

Here's my StackOverflow answer about it http://stackoverflow.com/questions/32709599/the-time-corrected-verlet-numerical-integration-fomula?lq=1

Here's another http://stackoverflow.com/questions/10139670/time-corrected-verlet-integration-and-too-big-timesteps/28061393#28061393

I was the "Aru" person there. It was rather easy to derive this for myself, which is why I was concerned that it seemed so many people could be taking this article seriously, when it's clearly wrong, and takes a misleading approach to everything. It's misapplying methods right from the start, using them with silly assumptions and ignoring their conditions. And I see now that it has even leaked it's way into wikipedia, which seems like the opposite of the right direction.

I haven't looked at this in a long time, and I could re-derive it if I really have to, but I assume any of you could do it easily as well. So, please remove all references to this article, and fix anything it has tainted in the wikipedia article? In fact, in might even be a good idea to mention that the article's proposed "method", the "time-corrected verlet", is patently wrong, just so that readers coming here are no longer confused by it.

edit: I guess, I'm saying this instead of "being bold" because I know that if I just remove it myself, someone will revert. Even if I both remove it and explain why here, some will revert. So, I'm explaining why, and someone else can remove it (or give me permission to do so). LieAfterLie (talk) 03:50, 6 March 2016 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Verlet integration/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Close to B class, in terms of amount of information, but it needs vigorous editing, esp. the constraints and collisions section. Geared too much towards specific applications. Needs more analysis, especially on why it's stable (and when it isn't). Jitse Niesen (talk) 07:26, 10 May 2007 (UTC)

Last edited at 07:26, 10 May 2007 (UTC). Substituted at 02:40, 5 May 2016 (UTC)

Speaking of 'Time Reversibility'...

   The algorithm was first used in 1791 by Delambre and has been rediscovered many times since then, most recently by Loup Verlet in the 1960s for use in molecular dynamics.

Should these just be reversed or is there something more to it?

Sobeita (talk) 20:57, 29 March 2018 (UTC)