Iterative Prediction

This page describes iterative prediction, a technique used to predict the motion of particles over a period of time often used in simulations.

The Main Idea

Iterative prediction is a mathematical technique for approximating the behavior of one or more particles over an interval of time. An iteration is a repeated procedure, so iterative prediction uses repeated procedures to predict the motion of a system. To perform iterative prediction, the initial position, initial momentum, and mass of each particle must be known, and the forces acting on each particle must be known. This information is used to update the position of each particle periodically.

To perform iterative prediction, the time interval of interest must be divided into small sub-intervals of duration [math]\displaystyle{ \Delta t }[/math] called time steps. For each time step, the following steps should be performed:

1. The Net Force acting on each particle should be calculated,
2. The Linear Momentum of each particle should be updated from the last time step using the newly calculated net force, and
3. The position of each particle should be updated from the last time step using its newly calculated Velocity.

This is a visual representation of iterative prediction being used to repeatedly update a particle's momentum. It was taken from this page of the Projects & Practices in Physics website, where it was provided under a CC Attribution-Noncommercial-Share Alike 3.0 Unported license. It is shown here under the same license.

The size of the time steps used during iterative prediction is called the resolution of the model. Dividing a time interval into a few large time steps is called low resolution, while dividing the same time interval into many small time steps is called high resolution. Performing iterative prediction with a higher resolution produces more accurate results but requires more computations. This is because steps 2 and 3 assume constant force and velocity respectively during the duration of each time step (see the "mathematical model" section). In reality, force and velocity change continually, so this is where inaccuracy is introduced. However, if the time steps are small enough that force and velocity do not significantly change during any time step, iterative prediction is a sufficiently accurate model. In the limit where the time interval is divided into an infinite number of infinitely small time steps, iterative prediction becomes a perfectly accurate model. However, this would require an infinite number of computations, and is therefore impossible to do, although in some simple situations, calculus can be used to this end instead. Deciding what time step to use requires consideration of both the computational resources available and the resolution required to accurately approximate the situation. When performing iterative prediction by hand, it is impractical to perform more than a few time steps, which cannot be used to accurately model much. If computers are available, it becomes feasible to divide the time interval into thousands of time steps, which can accurately simulate most day-to-day situations. Some of the most sensitive simulations, however, require incredibly small time steps. For example, some physicists perform atom-by-atom simulations of molecular structures interacting. A slight change in the position of an atom can cause a huge change in the forces acting on it, so tiny time steps must be used in order to ensure that force and velocity do not significantly change during any one time step. These simulations are run on the world's most powerful supercomputers and often take weeks to complete. They can simulate time intervals of several nanoseconds ([math]\displaystyle{ 10^{-9} }[/math] s) using time steps of only a few femtoseconds. ([math]\displaystyle{ 10^{-15} }[/math] s) (Click here for an example of a paper about such a simulation.)

Iterative prediction is only an approximation, but it is a very powerful tool because it can model complex systems that are impossible to model using known analytical approaches such as calculus and kinematics due to unsolvable differential equations and other obstacles.

A Mathematical Model

Below are the mathematical formulas required for each of the three steps outlined above.

1. The net force acting on each particle should be calculated.
This step varies widely from program to program, depending on what system is being modeled. Sometimes, the forces acting on each particle are constant, such as when modeling the motion of a ball with a specific weight thrown near the surface of the earth. Other times, the forces are functions of properties such as the particles' positions, such as when modeling the motion of celestial bodies whose gravitational attraction is greater when they are closer together. Sometimes, there is only one force acting on each particle, and other times, the net force must be found by adding together the individual force vectors.
2. The momentum of each particle should be updated from the last time step using the newly calculated net force.
This step uses the impulse-momentum theorem (see Impulse and Momentum). The impulse-momentum theorem states that [math]\displaystyle{ \vec{p}_f = \vec{p}_i + \vec{J} = \vec{p}_i + \vec{F}_{net, avg} * \Delta t }[/math]. In iterative prediction, the initial momentum is always known; it is simply the momentum the particle had during the previous time step (or, if there is no previous time step, the initial momentum of the particle). [math]\displaystyle{ \vec{F}_{net, avg} }[/math] represents the average net force that has been acting on the particle since the previous time step, resulting in a new momentum this time step. To calculate it, the net force found in step 1 should be used. Note that in reality, the net force acting on the particle is constantly changing, and the net force found in step 1 is the final net force, which is not truly the average net force over the course of the previous time step (except in a scenario with constant force). As described in the introductory section, this introduces inaccuracy that can be reduced by using shorter time steps; if short time steps are used, the net force does not have much time to change over the course of the time step, meaning the average net force is very similar to the final net force.
3. The position of each particle should be updated from the last time step using its newly calculated velocity.
This step uses the kinematic equation [math]\displaystyle{ \vec{r}_f = \vec{r}_i + \vec{v}_{avg} * \Delta t }[/math]. In iterative prediction, the initial position is always known; it is simply the position the particle had during the previous time step (or, if there is no previous time step, the initial position of the particle). [math]\displaystyle{ \vec{v}_{avg} }[/math] represents the average velocity with which the particle has been moving since the previous time step, resulting in a new position this time step. To calculate it, the momentum found in step 2 should simply be divided by the mass of the particle: [math]\displaystyle{ \vec{v}_f = \frac{\vec{p}_f}{m} }[/math]. Note that in reality, the velocity of the particle is constantly changing, and the velocity found above is the final velocity, which is not truly the average velocity over the course of the previous time step (even in a scenario with constant force). As described in the introductory section, this introduces inaccuracy that can be reduced by using shorter time steps; if short time steps are used, the velocity does not have much time to change over the course of the time step, meaning the average velocity is very similar to the final velocity.

A Computational Model

Iterative prediction is typically done on computers because many computations are necessary in order to perform it with a meaningful resolution. vPython is a useful program to perform iterative prediction with because of it can graphically display the positions of the particles each time step. Below is an example of a vPython program that uses iterative prediction to simulate a ball thrown near the surface of the earth. Be sure to read and understand the source code by clicking on "view this program" in the top left corner; there are comments for each line designed to introduce readers to their first iterative prediciton program.

high resolution ball trajectory simulation

To demonstrate differing resolutions, here is a lower resolution version of the same simulation, which uses larger time steps:

low resolution ball trajectory simulation

Note that the first program is more realistic; the more frequent position updates result in a smoother curve that more closely approximate the true trajectory of a ball. On the other hand, the second program has fewer calculations to do. Both programs are artificially slowed using the "rate" command in order to simulate a realistic travel time, but if both programs were allowed to run as quickly as possible, the second program would finish first. For larger, more complicated simulations, time can be a significant factor.

Here is another more complicated simulation that uses iterative prediction to simulate the motion of a mass swinging on a spring. This is an example of iterative prediction with a varying force; during each time step, the forces acting on the mass must be calculated depending on its position using Hooke's Law.

spring mass simulation

Note: both projectile motion and spring-mass systems can be analytically modeled; that is, in both of the above systems, analytical techniques such as calculus and kinematics can be used to find the position of the particles as a function of time. However, for some other, more complicated systems, analytical approaches may not exist, while iterative prediction often still works. For example, it would be easy to modify the projectile motion simulation to include the effects of air resistance, which is difficult to take into account analytically.

Examples

In addition to the example below, know how to create vPython simulations using iterative prediction with both constant and varying forces.

1. (Middling)

A 2kg particle is released from rest at time t=0. A constant force of 6N is applied to it. How far has the particle traveled after 4 seconds?

Solve this question

A.) analytically (using kinematic equations)

B.) using iterative prediction with 12 equal time steps

C.) using iterative prediction with 4 equal time steps

D.) using iterative prediction with a single time step

Pay attention to how the resolution of the iterative prediction affects the accuracy of the answer. The analytical answer is completely accurate.

A.) To solve this analytically, the following kinematic equation should be used:

[math]\displaystyle{ \Delta x = \frac{1}{2} a t^2 + v_0 t }[/math]

Using Newton's Second Law: the Momentum Principle, we know that [math]\displaystyle{ a = \frac{f}{m} = 3 }[/math]m/s^2. We are also given that [math]\displaystyle{ v_0 = 0 }[/math], and we are interested in the time t=4. Substituting these values into the kinematic equation yields

[math]\displaystyle{ \Delta x = \frac{1}{2} (3) (4)^2 = 24 }[/math]m.

B.) To solve this using iterative prediction, a computational tool should be used. Since an animation isn't necessary for this problem, I used Microsoft Excel; each row populates itself based on the information in the previous row using formula functions. Google Slides can also be used, as can vPython or any other programming language.

Using 12 time steps of 1/3 seconds each results in a simulated displacement of 26m, which is fairly close to the actual amount of 24m.

C.)

using 4 time steps of 1 second each results in a simulated displacement of 30m, which is fairly different from the actual amount of 24m.

D.)

using 1 time step of 4 seconds results in a simulated displacement of 48m, which is twice the actual amount!

This demonstrates that higher-resolution simulations with smaller time steps are able to predict the motion of particles more accurately than lower-resolution simulations with larger time steps. It also demonstrates that as the length of each time step approaches 0, the predicted motion of the particles approaches their actual motion. It is important to choose a resolution that keeps error within an acceptable margin.

Connectedness

Application: video game industry

One popular application of iterative prediction is in physics-based video games. These are often little more than physics simulations with player input. Iterative prediction is used in most major video games to predict the motion of in-game objects. It can be used even if the laws of physics within the video game are different from those of the real world.

History

The impulse-momentum theorem, which is used in iterative prediction to update the momenta of particles, is derived from Newton's Second Law, which Isaac Newton (1643-1727) publish in his 1687 book Principia Mathematica. From this point onward, all of the math necessary for iterative prediction was known, but it was not useful to perform iterative prediction until significant computational advances in the twentieth century allowed for high resolutions.

See also

• Linear Momentum
• Impulse and Momentum
• Analytical Prediction
• Iterative Prediction of Spring-Mass System
• Determinism

External links

• Iterative Prediction with VPython

References

• Georgia Institute of Technology. Physics Department. PHYS 2211. Fall 2016. Wednesday, Week 2 Lecture Slides. Fenton, Flavio H
• Georgia Institute of Technology. Physics Department. PHYS 2211. Fall 2016. Monday, Week 3 Lecture Slides. Fenton, Flavio H
• Georgia Institute of Technology. Physics Department. PHYS 2211. Fall 2016. Lab 07 Fancart Energy & Spring-Mass Instructions, Greco, Edwin
• http://p3server.pa.msu.edu/coursewiki/doku.php?id=183_notes:iterativepredict
• Bañó-Polo, M., Baeza-Delgado, C., Tamborero, S., Hazel, A., Grau, B., Nilsson, I., … Mingarro, I. (2018). Transmembrane but not soluble helices fold inside the ribosome tunnel. Nature communications, 9(1), 5246. doi:10.1038/s41467-018-07554-7