This page describes the objective of the Cascade algorithm, a new method to rigorously compute the orbits of dynamical systems. Here rigorously refers to the fact that no errors whatsoever are unaccounted for, be it round off, approximation or discretization errors. The dynamical system can either be genuinely discrete

u(n+1) = f(u(n));
u(0) = u0,

or continuous given by an ordinary differential equation

v'(t) = f(t,v(t));
v(t0) = v0.

The initial points u0 and v0 do not have to be specified exactly, but are allowed to lie in an initial confidence set. The method then constructs set enclosures Z(n) for u(n) in the discrete case and for v(t_n) in the continuous case, where t_n is a sequence of time steps. The sets Z(n) are zonotopes of high order.

There is an Java applet which implements the algorithm for planar, discrete dynamical systems.

On the left you can see a screen snapshot of the applet at work.

The Langford vector field

x' = (l-b)x-cy+x(z+d(1.0-z²))
y' = cx+(l-b)y+y(z+d(1.0-z²))
z' = lz-(x²+y²+z²)

is an example for a continuous dynamical systems. For the image on the right the parameters b=3.0, c=0.25, d=0.2 and l=2.01 were chosen. The initial set is a box centered at the point (0.1, 0.1, 0.1) with radius 1E-9 and is indicated by an arrow. Note that all the zonotopes in the image needed to be magnified to make them visible.

To implement the dynamical system u(n+1) = f(u(n)) rigorously on a computer, it is replaced by a set valued dynamical system

Z(n+1)  is subset of  f(Z(n));
u0  is element of  Z(0).

This is easily done by enclosing the range f(Z) by a linear image of Z plus some error set E which accounts for all errors, mostly linearization errors, i.e.,

f(Z)   is subset of  E+TZ.

The error set E will usually be an interval which is computed, together with the matrix T, by means of interval analysis.

Now suppose we start with an initial error set E(0) and iterate the inclusion relation

Z(n)=E(n)+T(n)Z(n-1).

Then successive iterates are

E(0) -> E(1)+T(1)E(0) -> E(2)+T(2)E(1)+T(2)T(1)E(0) -> ···

or Z(n)=E(n)+sum[j=0..n]R(j)E(j) with transition matrices R(j)=T(j)..T(1). Obviously, the number of summands of Z(n) increases linearly in n, and the time to compute Z(n) increases quadratically. This scheme is therefore, without modifications, practically useless. The only possibility is to wrap the error sets E(n) introduced at each stage to one of the summands. This way the number of summands can be kept fixed and finite. The Cascade algorithm does this in a efficient and effective way.

I have written three papers about this subject. An easy, introductory paper and two more technical papers on discrete and continues dynamical systems.