Graphics Reference
In-Depth Information
an initial point
x
0
in
X
(the start state), and
an analysis of the sequence of points
x
n
, n = 1,2,..., defined by
=
()
x
f
x
.
(22.1)
n
+
1
n
This section will look at some aspects of such dynamical systesm.
Consider a map f:
X
Æ
X
.
The
k-fold composite
or
k-fold iterate
of f, f
k
:
X
Æ
X
, is defined recur-
Definition.
sively by
(
)
0
()
=
k
()
=
k
-
1
()
f
xx
and
f
x
f f
x
for
k
>
0
.
Note that with this notation the sequence defined by equation (22.1) can also be
defined by
n
(
0
.
x
=
f
x
n
Definition.
The set {
x
,f
1
(
x
),...,f
n
(
x
),...} of iterates of the point
x
is called the
orbit
of
x
with respect to f. A point
x
is said to be
periodic
of
period k
if
x
= f
k
(
x
).
The kinds of questions to which we want answers are
Question 1.
Do the points
x
n
above converge to some
x
?
Question 2.
Does the sequence of
x
n
s become cyclic?
Question 3.
If one perturbs the initial point
x
0
a little to a point
x
0
¢, then how
different are the orbits of these two points?
The answer to Question 3 is particularly important to computer science because of the
inherent problem with round-off errors. If small changes to initial conditions for a
problem lead to large changes in the solution to the problem, then one would have to
be very skeptical of any solutions to the problem obtained with the help of a computer.
Unstable problems would require much extra care. An example of an unstable system
is the case of a pendulum that is pointed straight up. The pendulum will stay in that
position indefinitely (assuming that no force acts on it), but if it is moved ever so
slightly to either side, then it will immediately fall to that side and start to swing wildly
back and forth until it eventually settles on the bottom. Users who are asked to input
the initial top position to a program would potentially get radically different results.
Unfortunately, many real-life problems involve “unstable” systems. It is important
that one can recognize them.
Definition.
Let (
X
,d) be a metric space. A map f:
X
Æ
X
is said to have
sensitive
dependence
on initial conditions if there is a d>0 with the property that for all
x
Œ
X
and all neighborhoods
U
of
x
, there is a
y
Œ
U
and an n ≥ 0 such that d(f
n
(
x
),f
n
(
y
)) >
d. The map f is
topologically transitive
if for every pair of open sets
U
,
V
Õ
X
there is
an n > 0 so that f
n
(
U
) «
V
πf. The map f is said to be
chaotic
on
X
if
(1) it has sensitive dependence on initial conditions,
(2) it is topologically transitive, and
(3) its periodic points are dense in
X
.
