Discrete time dynamical systems

What is a discrete time dynamical system (DTDS)?

A DTDS is a dynamical system that evolves its state in discrete time steps, rather than through continuous evolution as is usually the case. By choosing a small enough time step a DTDS can approximate a continuous-time dynamical system. All algorithms can be formulated in the language of DTDS, because algorithms are stepwise procedures whose steps can be implemented as individual DTDS time steps. An algorithm running on a piece of hardware is nothing more than a set of rules telling that hardware how to update its state at each tick of the clock. This idea generalises to multiple pieces of hardware with independent clocks.

So DTDS are really useful. How can they be neatly implemented in software?

DTDS are very easy to implement in Mathematica. The archetypal DTDS is a cellular automaton, and where the "universe" consists of an array of discrete-valued cells, and the "laws of physics" consist of a set of cell update rules. A well known example of a cellular automaton is Conway's "Game of Life". More generally, the states of the cells can be anything you want (discrete-valued or continuous-valued), and the update rules can be implemented as any update algorithm you want to apply to the current state of the "universe" of cells. Mathematica has been designed with the simulation of cellular automata in mind, which is why DTDS are very easy to implement in Mathematica.

The Lorenz attractor is a good example to illustrate the implementation of a DTDS in Mathematica.

Initialise a pair of constants. The value of e controls the size of the discrete steps used by the DTDS version of the Lorentz equations to approximate the continuous version of the Lorenz equations.

e=0.013;
r=28;

Define the initial conditions.

x[0]={0.1,0.1,10.0};

Define the Lorenz equations.

x[t_]:=x[t]=
{
  x[t-1][[1]]+10e(x[t-1][[2]]-x[t-1][[1]]),
  x[t-1][[2]]+e(r x[t-1][[1]]-x[t-1][[1]]x[t-1][[3]]-x[t-1][[2]]),
  x[t-1][[3]]+e(x[t-1][[1]]x[t-1][[2]]-(8x[t-1][[3]])/3)
};

The x[t_]:=x[t]=... construct is Mathematica's way of implementing dynamic programming, where the result of evaluating the right hand side of the Lorenz equations is "memorised" using x[t]=..., and then x[t_]:=... can subsequently be used to retrieve this memorised value. This dynamical programming trick ensures that when going from t-1 to t the DTDS memorises its updated state x[t], so that it never needs to recompute x[t].

Call in a graphics package.

Needs["Graphics`Graphics3D`"];

Plot the Lorenz attractor.

ScatterPlot3D[Table[x[t],{t,0,1000}],PlotJoined->True,AspectRatio->1];



Although {x[1],x[2],...,x[1000]} have not actually been evaluated prior to evaluating ScatterPlot3D[...], their evaluation is then forced by evaluating Table[x[t],{t,0,1000}]. In effect the evolution of the DTDS happens as a side effect of asking for its evolution to be plotted. The memorisation of intermediate results using the x[t_]:=x[t]=... construct then ensures that all of {x[0],x[1],x[2],...,x[1000]} are available for immediate reuse, and do not need to be recomputed.

This memorisation of results means that if you want to restart the computation using different initial conditions x[0], then you have to explicitly erase the previously computed values {x[1],x[2],...,x[1000]} otherwise they will not be recomputed based on the new initial condition. An approach that avoids the need to erase values is to enforce the new initial condition on x[1001], and then to carry the computations forwards from there as {x[1002],x[1003],...}. I prefer this latter method because it avoids doing what is effectively a backwards jump in time.

Tag: Mathematica