summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/springer/svjour/cvs/example.tex
blob: e1a474c2cef63fb8f77a84e39a8b36f9096c4909 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
\documentclass[cvs,envcountsect]{svjour}
\usepackage{amsfonts}
\usepackage{psfig}

\begin{document}


\newcommand{\Ref}[1]{(\ref{#1})}
\newcommand{\R}{{\mathbb R}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\cB}{{\cal B}}
\newcommand{\cM}{{\cal M}}
\newcommand{\diam}{\mathop{\rm diam}\nolimits}

\renewcommand{\labelenumi}{(\roman{enumi})}


\title{An adaptive subdivision technique
        for the approximation\\ of
        attractors and invariant measures}

\author{Michael Dellnitz\thanks{Research of the authors is partly supported
        by the Deutsche Forschungsgemeinschaft under Grant De 448/5-2
        and by the Konrad-Zuse-Zentrum f\"ur Informationstechnik Berlin.},
        Oliver Junge}

\institute{Mathematisches Institut, Universit\"at Bayreuth,
           D-95440 Bayreuth, Germany\\
          {\scriptsize\tt
          (http://www.uni-bayreuth.de/departments/math/\~{}mdellnitz;
          http://www.uni-bayreuth.de/departments/math/\~{}ojunge)}}

\date{Received: 13 January 1997 / Accepted: 29 September 1997 \\[1em]
      Communicated by: P. Deuflhard}

\maketitle

\begin{abstract}
Recently subdivision techniques have been introduced in the
numerical investigation of the temporal behavior of
dynamical systems.  In this article we intertwine the subdivision
process with the computation of invariant measures and propose an
adaptive scheme for the box refinement which is based on the
combination of these methods.  Using this new algorithm the numerical
effort for the computation of box coverings is in general significantly
reduced, and we illustrate this fact by several numerical examples.
\end{abstract}

\section{Introduction}
%
Recently subdivision methods have been successfully applied to the
numerical analysis of complex dynamical behavior
(e.g.\ \cite{Eiden,DH1,DH2,DJ:96,DJchua:97}).  These methods can be used for two
essentially different purposes: the first is to
understand the geometric structure of an underlying attractor.
Secondly the goal may be to approximate the observable dynamical behavior
of the underlying system in a specific region of state space by
the computation of invariant measures.  This paper
concerns the second possibility, and we propose an adaptive scheme
incorporated into the subdivision technique which allows to
reduce the numerical effort significantly.

Obviously the dynamical behavior
just needs to be approximated on the support of a certain invariant measure.
Indeed, the idea for the adaptive principle stated here
is to intertwine the subdivision techniques with the computation of a
natural invariant measure, an {\em SBR-measure}, say.  Roughly speaking,
the size of the covering boxes is reduced in those parts of
state space where the natural invariant measure $\mu$ is concentrated, and,
on the other hand, boxes are not subdivided in areas which have
$\mu$-measure zero.

The main goal of this article is to illustrate the efficiency of
the new method by numerical examples.  For that purpose we
consider several dynamical systems
for which the SBR-measure is known analytically since this allows us to
compare the numerical results obtained by the {\em adaptive\/}
subdivision algorithm to those obtained by the {\em standard\/}
subdivision procedure.  The adaptive algorithm is essentially based
on the combination of two existing methods for which
convergence results are known.  However, this fact does not
immediately imply convergence of the adaptive method as well.
Rather this theoretical but relevant problem is
currently under investigation, and the results will be published elsewhere.

An outline of the paper is as follows: in Sect.\,\ref{sec:CSA} we
recall the standard subdivision technique from \cite{DH1}.  The numerical method
for the approximation of SBR-measures is described in Sect.\,\ref{sec:fp}.
Then, in Sect.\,\ref{sec:ASA}, we present our adaptive subdivision technique, and
the efficiency of this method is illustrated by several examples in
Sect.\,\ref{sec:num}.


\section{The standard subdivision algorithm}
\label{sec:CSA}
%
The purpose is to approximate invariant sets of discrete
dynamical systems of the form
\[
x_{j+1} = f(x_j),\quad j=0,1,\ldots,
\]
where $f$ is a continuous mapping on $\R^n$.
The central object which is approximated by the subdivision algorithm
developed in \cite{DH1} is the so-called {\em relative global attractor},
\begin{equation}
\label{eq:relativAttractor2}
A_Q=\bigcap_{j\geq0}f^j(Q),
\end{equation}
where $Q\subset\R^n$ is a compact subset.  Roughly speaking,
the set $A_Q$ should be viewed as the {\em union of unstable
manifolds of invariant objects inside $Q$}.  In particular,
$A_Q$ may contain subsets of $Q$ which cannot be approximated
by direct simulation.

The subdivision algorithm for the approximation of $A_Q$
generates a sequence $\cB_0,\cB_1,\cB_2,\ldots$ of finite
collections of boxes with the property that for all
integers $k$ the set $Q_k=\bigcup_{B\in\cB_k}B$
is a covering of the relative global attractor under consideration.
Moreover the sequence of coverings
is constructed in such a way that the diameter of the boxes,
\[
\diam(\cB_k) = \max_{B\in\cB_k}\diam(B)
\]
converges to zero for $k\rightarrow\infty$.

Given an initial collection $\cB_0$, one inductively obtains $\cB_k$ from
$\cB_{k-1}$ for $k=1,2,\ldots$ in two steps.
\begin{enumerate}
\item {\em Subdivision:} Construct a new collection $\hat\cB_k$ such that
\begin{eqnarray*}
\bigcup_{B\in\hat\cB_k}B &=& \bigcup_{B\in\cB_{k-1}}B \\
\mbox{and}\quad
\diam(\hat\cB_k) &\leq& \theta\diam(\cB_{k-1})
\end{eqnarray*}
for some $0<\theta<1$.
\item {\em Selection:} Define the new collection $\cB_k$ by
\[
\cB_k=\left\{B\in\hat\cB_k \!:\! f^{-1}(B)\!\cap\!\hat B\!\ne\!\emptyset
\!\!\quad\mbox{for some}\!\!\quad\hat B\!\in\!\hat\cB_k\right\}.
\]
\end{enumerate}

The following proposition establishes a general convergence property of
this algorithm.

\begin{proposition}[\cite{DH1}]
\label{prop:sdconv}
Let $A_Q$ be the global attractor relative to the compact set $Q$,
and let $\cB_0$ be a finite collection of closed subsets with
$Q_0=Q$. Then
\[
\lim\limits_{k\rightarrow\infty}
h\left( A_Q, Q_k \right)=0,
\]
where we denote by $h(B,C)$ the usual Hausdorff distance between two
compact subsets $B,C\subset\R^n$.
\end{proposition}

\setcounter{equation}{0}
\section{Approximation of SBR-measures}
\label{sec:fp}
%
Recently it has been shown in \cite{DJ:96} how to compute numerically
approximations of an {\em SBR-measure\/} supported on a hyperbolic
invariant set.  Since we want to use this method in our adaptive scheme
we now sketch the main ingredients of this algorithm.
To make the ideas more transparent we simplify the description
drastically by avoiding all technical details
concerning the underlying mathematical foundation in Ergodic Theory.

The crucial observation is that the calculation of
invariant measures can be viewed as a fixed point problem.
Let ${\cal M}$ be the set of probability measures on $\R^n$.
Then $\mu\in{\cal M}$ is invariant if and
only if it is a fixed point of the {\em Frobenius-Perron operator\/}
$P:{\cal M}\to {\cal M}$,
\begin{equation}
\label{eq:fp-fixed}
(P\mu)(B)=\mu(f^{-1}(B))\quad\mbox{for all measurable $B\subset\R^n$}.
\end{equation}

For a discretization of the operator $P:\cM\rightarrow\cM$ we
replace $\cM$ by a finite dimensional
set $\cM_k$: let $B_i\in\cB_k$, $i=1,\ldots,N$,
denote the boxes in the covering obtained after $k$ steps in the subdivision
algorithm and set as before $Q_k=\bigcup_{B\in\cB_k}B$.
We choose $\cM_k$ to be the set of ``discrete probability
measures'' on $\cB_k$, that is,
\[
\cM_k = \left\{ u:\cB_k\to [0,1] \quad\Bigg|
\quad \sum_{i=1}^N u(B_i)=1\right\}.
\]
Assuming that $f(Q_k)\subset Q_k$ the discretized
Frobenius-Perron operator $P_k:\cM_k\rightarrow\cM_k$ is given by
\begin{eqnarray}\label{eq:FP}
v= P_k u,\quad v(B_i)=\sum_{j=1}^N
\frac{m(f^{-1}(B_i)\cap B_j)}{m(B_j)}u(B_j),\\
\hfill i=1,\ldots,N,\nonumber
\end{eqnarray}
where $m$ denotes Lebesgue measure. Now a fixed point $u=P_k u$ of
$P_k$ provides an approximation to an invariant measure of $f$.
\begin{remark}
For the mathematically precise statement on the convergence of this
method one would have to introduce the concept of {\em small random
perturbations}.  The reason is that this allows one to use a result of
Yu.\ Kifer on the convergence of invariant measures in the perturbed
systems to the SBR-measure (\cite{Kifer:86}).
However, the purpose of this article is to develop and to test an adaptive
scheme for the box refinement in the subdivision algorithm rather than to
explain the theoretical background concerning the computation of
SBR-measures.  Therefore the
reader is referred to \cite{DJ:96} for the rigorous mathematical
treatment.
\end{remark}


\section{The adaptive subdivision algorithm}
\label{sec:ASA}
%
As mentioned above, the standard subdivision algorithm may approximate
a part of the global attractor which is dynamically irrelevant in the
sense that no invariant measure has support on this subset.
The reason is that {\em each\/} box is subdivided in a step of the
subdivision algorithm regardless of any information on the dynamical
behavior.  In particular, also those subsets of the relative global
attractor corresponding to unstable or transient dynamical behavior
are approximated by the standard procedure.

On the other hand, if one is mainly interested in the approximation of
the support of the (natural) invariant measure rather than in the precise
geometric structure of the global attractor then this strategy may lead to
unnecessary high storage and computation requirements. In the following
we present a modified subdivision strategy which avoids this drawback:
roughly speaking,
\begin{itemize}
\item[--] in the subdivision step we use
the information on the actual approximation of the
invariant measure to decide whether or not a box should be subdivided;
\item[--] in the selection step we keep only those boxes
which have a nonempty intersection with the support of the invariant measure.
\end{itemize}

To be more precise, let $\{\delta_k\}$ be a sequence of positive
real numbers such that $\delta_k\to 0$ for $k\to\infty$. The algorithm
generates a sequence of pairs
\[
(\cB_0, u_0),(\cB_1, u_1), (\cB_2, u_2), \ldots
\]
where the $\cB_k$'s are finite collections of compact subsets of
$\R^n$ and the discrete measures $u_k:\cB_k\to[0,1]$ can be interpreted
as approximations to the SBR-measure $\mu_{SBR}$:
\[
u_k(B) \approx \mu_{SBR}(B)\quad\mbox{for all $B\in\cB_k$}.
\]

Given an initial pair $(\cB_0, u_0)$, one inductively
obtains $(\cB_k, u_k)$ from $(\cB_{k-1}, u_{k-1})$ for
$k=1,2,\ldots$ in three steps:
\begin{enumerate}
\item {\em Subdivision:} Define
\begin{eqnarray*}
\cB_{k-1}^- &=&\{B\in\cB_{k-1}: u_{k-1}(B) < \delta_{k-1}\} \\
\mbox{and}\qquad && \\ \cB_{k-1}^+ &=& \cB_{k-1}\backslash\cB_{k-1}^-.
\end{eqnarray*}
Construct a new (sub-)collection $\hat\cB_k^+$ such that
\[
\bigcup_{B\in \hat\cB_k^+} B = \bigcup_{B\in \cB_{k-1}^+} B
\]
where
\[
\diam(\hat\cB_k^+) \leq \theta\diam(\cB_{k-1}^+)
\]
for some $0 < \theta < 1$.
\item {\em Calculation of the invariant measure:}
Set
\[
\hat \cB_k = \cB_{k-1}^-\cup\hat\cB_k^+.
\]
For the collection $\hat \cB_k$ calculate the approximating
invariant measure as the fixed point $\hat u_k$ of the discretized
Frobenius-Perron operator defined by \Ref{eq:FP}.
\item {\em Selection:} Set
\[
\cB_k = \{ B\in \hat \cB_k: \hat u_k(B) > 0\}
\]
and
\[
u_k = \hat u_k|_{\cB_k}.
\]
\end{enumerate}

\begin{remark}\label{rmk:real}
\begin{itemize}
\item[(a)] In the realization of the algorithm we typically subdivide the
boxes in the collection $\cB_k^+$ by bisection.  This guarantees that
the number of boxes is not growing too fast.  For the details concerning the
implementation the reader is again referred to \cite{DH1,DJ:96}.
\item[(b)] In principle there is some freedom in choosing the sequence
$\{\delta_k\}$ of positive numbers used in the subdivision step. Note however
that this sequence determines the number of boxes which will be subdivided
and hence it has a significant influence on the storage requirement.
In the computations it turned out to be quite efficient to choose the
average
\[
\delta_k = {1\over N_k}\sum_{B\in\cB_k} u_k(B) = {1\over N_k},
\]
where $N_k$ is the number of boxes in $\cB_k$.
\item[(c)] In the numerical realization of the selection step (iii)
we check whether $\hat u_k(B) > \epsilon$ where $\epsilon>0$ is chosen
sufficiently small with respect to the machine precision.
\end{itemize}
\end{remark}


\section{Numerical examples}
\label{sec:num}
%
In this section we illustrate the efficiency of the adaptive scheme by
several numerical examples.  First we consider three one-dimensional
mappings for which the SBR-mea\-sures are known analytically.  For these
cases we
will see that, as expected, the new technique is particularly useful
if the underlying invariant density has singularities.  Additionally we
consider the H\'{e}non map as a two-dimensional
example and show the box refinement produced
by the adaptive subdivision algorithm at a certain step.

Before proceeding let us indicate some details concerning the implementation
of the adaptive subdivision algorithm:
\begin{itemize}
\item[(a)] The subdivision is always done by bisection and the boxes
are stored in a binary tree.  This way we keep the storage requirement
at a low level.
\item[(b)] For the computation of the transition probabilities
\linebreak $m(f^{-1}(B_i)\cap B_j)$ in \Ref{eq:FP}
we use an exhaustion technique as described in \cite{GDK}.  This method
is particularly useful when -- as in our examples -- local Lipschitz constants
are available for the underlying dynamical system.
\item[(c)] The computation of the discrete measures is done by an inverse
power method.  In the solution of the corresponding linear systems
the fact is taken into account that the discretized
Frobenius-Perron operator is extremely sparse.
\end{itemize}
The adaptive algorithm is integrated into the C++ code {\sf GAIO}
({\bf G}lobal {\bf A}nalysis of {\bf I}nvariant {\bf O}bjects).
A link to a detailed description of {\sf GAIO} can be found on
the homepages of the authors.


\subsection*{Three one-dimensional examples}
\label{subsec:1D}
%
Motivated by the numerical investigations in \cite{DingDuLi:93}
we apply the adaptive subdivision algorithm to three different
one-dimensional dynamical systems on the interval $[0,1]$.  In each
case we have chosen the initial collection $\cB_0=\{[0,1]\}$.

\begin{itemize}
\item[{\it 1.}]
As a first example we consider the Logistic Map $f_1:[0,1]\to [0,1]$,
\[
f_1(x)=\lambda x(1-x)
\]
for $\lambda=4$. The unique absolutely continuous invariant measure $\mu$
of $f_1$ has the density
\[
h_1(x)={1\over \pi \sqrt{x(1-x)}}
\]
(see e.g.\ \cite{Lasota:94}). Using the standard and the adaptive
algorithm we have approximated this density on several levels
and the results are shown in Table 1.  We remark that even
the computation for $\ell=20$ only takes about 50 sec
on an MIPS R4400 cpu.

\begin{table} \label{tab:log}
\caption{Comparison between the standard and the adaptive subdivision
algorithm for the Logistic Map.  The minimal box volume in each row
is $2^{-\ell}$}
\begin{tabular}{ l l l l l }
\hline
$\ell$ &
\multicolumn{2}{c}{number of boxes} & \multicolumn{2}{c}{$L^1$-error} \\
  & standard & adaptive & standard & adaptive \\ \hline
6 & 64       &   17 & 0.1390 & 0.1431   \\
8 & 256      &   34 & 0.0670 & 0.0765 \\
12 & 4096    &  151 & 0.0210 & 0.0258 \\
16 & 65536   &  679 & 0.0064 & 0.0073 \\
20 & $2^{20}$  & 2831 &  -     & 0.0021 \\
\hline
\end{tabular}
\end{table}

In Fig.~\ref{fig:log} we illustrate the fact that the size of the boxes
is much smaller for those which are close to zero or one.  Indeed, this is
what we expect since the density has singularities in these points.

\begin{figure*}
\vbox{\hbox to\textwidth{\psfig{figure=cvs21.f1a,width=6cm}\hspace{5mm}
\psfig{figure=cvs21.f1b,width=6cm}\hfill \parbox[b]{50mm}{%
\caption[]{Illustration of the relation between the density and the
           actual box refinement produced by the adaptive subdivision
           algorithm for $\ell =10$: {\bf a} the density $h_1$;
           {\bf b} the radii versus the midpoints of
boxes}\vspace{2mm}}}}
\label{fig:log}
\end{figure*}

\item[{\it 2.}] We consider the map $f_2:[0,1]\to [0,1]$,
\renewcommand{\arraystretch}{2.1}
\[
f_2(x)=\left\{
\begin{array}{ll}
\displaystyle{2x\over 1-x^2} & \mbox{for}\quad 0\le x< \sqrt{2}-1, \\
\displaystyle{1-x^2\over 2x} & \mbox{for}\quad \sqrt{2}-1 \le x \le 1.
\end{array}
\right.
\]
\renewcommand{\arraystretch}{1.0}
Its invariant density is
\[
h_2(x)= {4\over \pi (1+x^2)}\; ,
\]
see Fig.\,\ref{fig:tent}.

\begin{figure*}
\vbox{\hbox to\textwidth{\psfig{figure=cvs21.f2a,width=6cm}\hspace{5mm}%
\psfig{figure=cvs21.f2b,width=6cm}\hfill
\parbox[b]{50mm}{%
\caption[]{{\bf a} The map $f_2$; and {\bf b} its invariant density
           $h_2$}\vspace{1mm}}}}
\label{fig:tent}
\end{figure*}

In Table \ref{tab:tent} we present the numerical results
for this case. As expected the application of the adaptive
subdivision algorithm is not more efficient than the
standard one since the invariant measure is quite close to Lebesgue
measure.

\begin{table}
\caption[]{Comparison of the numerical results for $f_2$
           ($\ell$ as in Table~1)}
\label{tab:tent}
\begin{tabular}{ l l l l l }
\hline
$\ell$ &
\multicolumn{2}{c}{number of boxes} & \multicolumn{2}{c}{$L^1$-error} \\
  & standard & adaptive & standard & adaptive \\ \hline
6  & 64   &   45 &           0.0027 &             0.0053 \\
8  & 256  &  187 & $6.5\cdot 10^{-4}$ &           0.0013 \\
10 & 1024 &  759 & $1.7\cdot 10^{-4}$ & $3.2\cdot 10^{-4}$ \\
12 & 4096 & 3047 & $4.6\cdot 10^{-5}$ & $7.8\cdot 10^{-5}$ \\
\hline
\end{tabular}
\end{table}

\item[{\it 3.}] Finally we consider the map $f_3:[0,1]\to [0,1]$,
\[
f_3(x) = \left({1\over 8} -2 \left|x-{1\over 2}\right|^3\right)^{1\over 3}
+ {1\over 2},
\]
with the invariant density
\[
h_3(x) = 12\left(x-{1\over 2}\right)^2.
\]
The graphs of $f_3$ and $h_3$ are shown in Fig.\,\ref{fig:stahl}.

\begin{figure*}
\vbox{\hbox to\textwidth{\psfig{figure=cvs21.f3a,width=6cm}\hspace{5mm}%
\psfig{figure=cvs21.f3b,width=6cm}\hfill
\parbox[b]{50mm}{%
\caption[]{{\bf a} The map $f_3$; and {\bf b} its invariant density
           $h_3$}\vspace{2mm}}}}
\label{fig:stahl}
\end{figure*}

\begin{figure*}
\vbox{\hbox to\textwidth{\psfig{figure=cvs21.f4a,height=5.3cm}\hspace{5mm}%
\psfig{figure=cvs21.f4b,height=5.3cm}\hfill}}
\caption[]{{\bf a} A tiling of the square $[-2,2]^2$ obtained by the
           adaptive subdivision algorithm; and {\bf b} the subcollection
           $\tilde{\cB}$ of boxes with discrete density bigger than
           $0.35$ (see also \protect\Ref{eq:dm})}
\label{fig:henon}
\end{figure*}

We now discuss the numerical results presented in Table~\ref{tab:stahl}.
Note that the derivative of $f_3$ has singularities at two points
inside $[0,1]$.  This is the reason why several boxes get lost in
the realization of the selection step in the standard subdivision
algorithm.  Consequently the computation of the invariant measure
does not lead to satisfying results.  In contrast to this no boxes are lost
in the application of the adaptive subdivision technique, and accordingly
the $L^1$-error is decreasing with an increasing number of subdivision steps.

\begin{table}
\caption[]{Comparison of the numerical results for $f_3$
           ($\ell$ as in Table~1)}
\label{tab:stahl}
\begin{tabular}{ l l l l l }
\hline
$\ell$ &
\multicolumn{2}{c}{number of boxes} & \multicolumn{2}{c}{$L^1$-error} \\
  & standard & adaptive & standard & adaptive \\ \hline
6  &   63 &  11 & 0.0260 & 0.2931 \\
8  &  249 &  30 & 0.0105 & 0.2583 \\
10 &  993 & 189 & 0.0110 & 0.0435 \\
12 & 3967 & 816 & 0.0133 & 0.0065 \\ \hline
\end{tabular}
\end{table}
\end{itemize}


\subsection*{The H\'enon  map}
\label{subsec:henon}
%
We apply the adaptive subdivision algorithm to a two-di\-men\-sio\-nal
example, namely a scaled version of the well known {\em H\'enon map}
\[
f:\R^2\to \R^2,\quad
f(x,y) = (1-ax^2+y/5,\; 5bx).
\]
In the computations we have fixed the parameters by $a=1.2$, $b=0.2$,
and we have chosen $\cB_0=\{[-2,2]^2\}$.

In Fig.\,\ref{fig:henon} we present a tiling of the square $[-2,2]^2$
obtained by the adaptive subdivision algorithm after several subdivision
steps. The resulting box-collection $\cB$ consists of the
grey boxes shown in part (a) of this figure.
We expect that due to the numerical approximation some boxes have
positive {\em discrete\/} measure although they do not intersect the
support of the {\em real\/} natural invariant measure.
Having this in mind we neglect those boxes with very small discrete
measure and show in Fig.\,\ref{fig:henon}b a subcollection
$\tilde\cB\subset\cB$ with the property that
\begin{equation}
\label{eq:dm}
\sum_{B\in\tilde\cB} u(B) \approx 0.99
\end{equation}
(see also Remark~\ref{rmk:real}(c)).

\begin{figure}
\vbox{\hbox to\textwidth{\psfig{figure=cvs21.f5,width=8.6cm}\hfill}}
\caption[]{Illustration of the (natural) invariant measure for the
           H\'enon map. The picture shows the density of the discrete
           measure on $\tilde\cB$, see \protect\Ref{eq:dm}}
\label{fig:hen2}
\end{figure}

\begin{remark}
For our choice of the parameter values we cannot explicitly
write down a natural invariant measure.  Hence it is impossible
to compare our numerical results using analytical ones.
Moreover, it is not even known for an arbitrary choice of the parameter
values whether or not the H\'enon map possesses an SBR-measure.
However, recently it was proved by M.\ Benedicks and L.-S.\ Young that
the H\'enon map indeed has an SBR-measure for a
``large'' set of parameter values, see \cite{BenYoung}.
\end{remark}


Finally we apply the numerical techniques described in
\cite{DJ:96} to determine the essential dynamical behavior of the
H\'enon map for this choice of parameter values.  An approximation
of the (natural) invariant measure obtained by the adaptive
subdivision algorithm is shown in Fig.\,\ref{fig:hen2}.  This
computation is based on the total number of 1514 boxes inside the
square $[-2,2]^2$, whereas the support of the
invariant measure is covered by 1442 boxes.
The results indicate that the H\'enon map exhibits complicated dynamical
behavior.

Moreover it can be shown that the areas
where the density is colored red resp.\ blue
are permuted cyclically by the mapping.  Hence altogether
we may conclude that for these parameter values the H\'enon
map exhibits a two-cycle (the ``macro-dynamics'') in addition to
unpredictable (chaotic) behavior.  This fact is also demonstrated
by a {\sf Java}-animation for which a link can be found on the
homepages of the authors.  \thisbottomragged



\begin{thebibliography}{10.}

\bibitem{BenYoung}
M.\ Benedicks, L.-S.\ Young.
Sinai-\protect{Bowen}-\protect{Ruelle} measures for certain
  \protect{Henon} maps.
{Invent.\ math.}, {\bf 112}:541--576, 1993

\bibitem{DH2}
M.\ Dellnitz, A.\ Hohmann.
The computation of unstable manifolds using subdivision and
  continuation.
In H.W. Broer, S.A. van Gils, I.~Hoveijn, F.~Takens (eds),
  {Nonlinear Dynamical Systems and Chaos}, pages 449--459. Birkh\"auser,
  {PNLDE} {\bf 19}, 1996

\bibitem{DH1}
M.\ Dellnitz, A.\ Hohmann.
A subdivision algorithm for the computation of unstable manifolds and
  global attractors.
{Numerische Mathematik}, {\bf 75}:293--317, 1997

\bibitem{DJ:96}
M.\ Dellnitz, O.\ Junge.
On the approximation of complicated dynamical behavior.
To appear in SIAM J. on Numerical Analysis, 1998

\bibitem{DJchua:97}
M.\ Dellnitz, O.\ Junge.
Almost invariant sets in \protect{Chua's} circuit.
To appear in {Int.\ J.\ Bif.\ and Chaos}, 1997

\bibitem{DingDuLi:93}
J.~Ding, Q.~Du,, T.~Y. Li.
High order approximation of the {Frobenius}-{Perron} operator.
{Appl.\ Math.\ Comp.}, {\bf 53}:151--171, 1993

\bibitem{Eiden}
M.\ Eidenschink.
{Exploring Global Dynamics: A Numerical Algorithm Based on the
  Conley Index Theory}.
PhD Thesis, Georgia Institute of Technology, 1995
\newpage

\bibitem{GDK}
R.\ Guder, M.\ Dellnitz,, E.\ Kreuzer.
An adaptive method for the approximation of the generalized cell
  mapping.
{Chaos, Solitons and Fractals}, {\bf 8}(4):525--534, 1997
\bibitem{Kifer:86}
Yu.\ Kifer.
General random perturbations of hyperbolic and expanding
  transformations.
{J.\ Analyse Math.}, {\bf 47}:111--150, 1986

\bibitem{Lasota:94}
A.\ Lasota, M.C.\ Mackey.
{Chaos, Fractals and Noise}.
Springer, 1994

\end{thebibliography}

\end{document}