Introduction to Rigorous Dynamics

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.

x' = (l-b)x-cy+x(z+d(1.0-z^{2}))

y' = cx+(l-b)y+y(z+d(1.0-z^{2}))

z' = lz-(x^{2}+y^{2}+z^{2})

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.