InvestigatingDynamicsby
MultilevelPhaseSpace
Discretization
VonderFakultät
Informatik,ElektrotechnikundInformationstechnik
derUniversitätStuttgart
zurErlangungderWürdeeinesDoktors
derNaturwissenschaften(Dr. rer. nat.)
genehmigteAbhandlung
Vorgelegtvon
DannyGeorgFundinger
ausPforzheim
Hauptberichter: Prof. Dr. P. Levi
Mitberichter: Prof. Dr. G. S. Osipenko
TagdermündlichenPrüfung: 10.3.2006
InstitutfürParalleleAbteilungBildverstehen
undVerteilteSysteme
UniversitätStuttgart
InstitutfürParalleleundVerteilteSytemederUniversitätStuttgart,2006Abstract
The subject of the thesis is the numerical investigation of dynamical systems.
The aim is to provide approaches for the localization of several topological
structures which are of vital importance for the global analysis of dynamical
systems, namely, periodic orbits, the chain recurrent set, repellers, attractors and
their domains of attraction as well as stable, unstable and connecting manifolds.
The techniques introduced do not require any a priori knowledge about a system,
and are also not restricted by the stability of the solution. Furthermore, they can
generallybeappliedtoawiderangeofdynamicalsystems.
Two theoretical concepts are considered to be at the center of the research –
symbolic analysis and the RIM method. The underlying basic approach for both
of them is multilevel phase space discretization. This means that a part of the
phase space, the area of investigation, is subdivided in a finite number of sets.
Then, instead of each point of the phase space, only these sets are subject of
further analysis. The main target of every method proposed is to find those sets
which contain parts of the solution and subdivide them into smaller parts until a
desiredaccuracyisreached.
In case of symbolic analysis, a directed graph is constructed which represents
the structure of the state space for the investigated dynamical system. This
graph is called the symbolic image of the focused system and can be seen as
an approximation of the system flow. The theoretical background regarding the
symbolic image graph as well as the constructive methods applied on it were
already described in a series of works by G. Osipenko. In this work, strategies
are introduced for a practical application. This requires the extension of the
theoretical concepts and the development of appropriate algorithms and data
structures. In practice, it turned out that these aspects are essential cornerstones
fortheusabilityofthediscussedmethods. Alsosomesophisticatedtuningsofthe
basicmethodsareproposedinordertoextentthefieldofpracticalinvestigation.
Although symbolic analysis can be seen as the main stimulation of this work, the
iii
investigation was not limited to it. Indeed, several shortcomings regarding the
solution of some problems can be observed if the method is applied in practice.
ThisledtothedevelopmentoftheRIMmethod. Thecoreintentionofthemethod
is to solve the root finding problem. The standard approach toward this task is
the application of an iteration scheme based on the Newton method. However,
it has shown that such Newton schemes have several structural disadvantages
which are especially crucial in the context of the fields of investigation which are
relevant to this work. The RIM method proposes an alternative approach which
does not require the application of any Newton like method. Numerical case
studies revealed that in several nontrivial scenarios the RIM method provides
better results than both, symbolic analysis as well as Newton based methods.
Two applications of the RIM method for the investigation of dynamical systems
are provided. One of them is the detection of periodic points. The other is the
computationofstablemanifolds.
The proposed methods contribute not only to the direct investigation and sim
ulation of specific dynamical processes but also to the research in the field of
dynamicalsystemtheoryingeneral. Thisisduetothefactthatprogressintheory
depends to a large extent on the observation and investigation of phenomenons.
These phenomenons can often only be revealed, analyzed and verified by
numericalexperiments. Thepresentednumericalcasestudiesgivesomeconcrete
examples for the application of the methods. Hereby, the dynamical models
are taken from different fields of scientific research, like geography, biology,
meteorology,orphysics.Acknowledgements
This work was carried out as a cooperative research project involving the
Non Linear Dynamics Group of the University of Stuttgart, Germany and the
Laboratory of Mathematical Modeling at the St. Petersburg State Polytechnic
University, Russia. This interdisciplinary environment was a highly stimulating
andexcellentworkplace. Iwouldliketothankallthosepeopleatbothuniversities
whocontributedtothisworkwiththeircommitmentandinvaluableadvice.
It would have been impossible for me to accomplish this project without the gen
erous support of Prof. Dr. Paul Levi and Prof. Dr. George Sergeevich Osipenko.
The many fruitful and challenging discussions with Prof. Dr. Osipenko built the
sound foundation of this work and encouraged me in my efforts to step deeper
intothefascinatingworldofscience.
The competent advice and ongoing support of Dr. Michael Schanz can also not
be appreciated high enough. His personal confidence and scientific support were
astrongbackingduringmywork.
Although it has been a few years ago since Dr. Viktor Avrutin introduced me
to the fascinating field of dynamical systems theory, his ideas and questions are
still an ongoing source of inspiration and motivation which were truly invaluable
for this work. The discussions with him deeply improved my knowledge. His
expertiseguidedmethroughthegroundsofdynamicalsystemstheory.
The joint research work with Torsten Lindström from the University of Kalmar
and Gunnar Söderbacka from the University of Lulea were a lively source of
inspiration across the borders of scientific disciplines. Their interest in my work
wereamotivatingforcewhichencouragedmetoproceedandextendmyresearch.
Of no minor importance is the ongoing support of my family. Although some
times it was probably not so easy for them to follow me on my way they never
losttheirconfidenceIamgoingtherightpath.
iiiiv
Lastbutnotleast,Ihavetothankthepersonwhoisthemostimportantinmylife
–Yulia. Withoutyoutherewouldbealargegapinmylife.
There are still many other people in Russia and Germany who contributed in one
way or another to this work. I would like to thank all of those who encouraged
andchallengedme.Contents
1 Introduction 1
1.1 MotivationandTargets . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 FundamentalConceptualFrameworks . . . . . . . . . . . . . . . 5
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 FieldsofInvestigation 11
2.1 DynamicalSystems . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 PeriodicPoints . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 TheChainRecurrentSet . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Attractors,RepellersandBasins . . . . . . . . . . . . . . . . . . 19
2.5 StableandUnstableManifolds . . . . . . . . . . . . . . . . . . . 22
2.6 FiltrationsandConnectingManifolds . . . . . . . . . . . . . . . 26
3 TheSymbolicImageGraph 29
3.1 TheoreticalBackground . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 ImplementationDetails . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 BoxandCellObjects . . . . . . . . . . . . . . . . . . . . 34
3.2.2 ConstructionoftheSymbolicImage . . . . . . . . . . . . 37
3.2.3 SubdivisionProcess . . . . . . . . . . . . . . . . . . . . 42
3.2.4 ComparisonwithaSimilarImplementation . . . . . . . . 43
3.3 BasicInvestigations . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3.1 LocalizationoftheChainRecurrentSet . . . . . . . . . . 44
3.3.2ofPeriodicPoints . . . . . . . . . . . . . . . 46
3.4 PerformanceAnalysis . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5 AccuracyoftheComputations . . . . . . . . . . . . . . . . . . . 54
3.6 NumericalCaseStudies . . . . . . . . . . . . . . . . . . . . . . . 55
3.6.1 IkedaMap . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.6.2 CoupledLogisticMap . . . . . . . . . . . . . . . . . . . 62
vvi CONTENTS
4 ExtensionsandTunings 67
4.1 ExtensionsfortheGraphConstruction . . . . . . . . . . . . . . . 68
4.1.1 DynamicalSystemsContinuousinTime . . . . . . . . . . 68
4.1.2 ErrorToleranceforBoxImages . . . . . . . . . . . . . . 71
4.2 TuningsfortheGraphInvestigation . . . . . . . . . . . . . . . . 73
4.2.1 UseofHigherIteratedFunctions . . . . . . . . . . . . . . 73
4.2.2 DiscretizationTimeforSystemsContinuousinTime . . . 78
4.2.3 ReconstructionofFragmentedSolutions . . . . . . . . . . 80
4.3 NumericalCaseStudies . . . . . . . . . . . . . . . . . . . . . . . 81
4.3.1 LorenzSystem . . . . . . . . . . . . . . . . . . . . . . . 81
4.3.2 DiscreteFoodChainModel . . . . . . . . . . . . . . . . 84
5 InvestigationoftheSymbolicImage 89
5.1 LocalizationofAttractorsandTheirBasins . . . . . . . . . . . . 89
5.1.1 AttractorsonaSymbolicImage . . . . . . . . . . . . . . 90
5.1.2 ConstructionoftheAcyclicGraphDG . . . . . . . . . . 92
5.1.3 SelectionofanAttractorL . . . . . . . . . . . . . . . . . 94
5.1.4 LocalizationoftheDomainofAttraction . . . . . . . . . 95
5.1.5 Subdivisionoftheof . . . . . . . . . . 98
5.2 AspectsofFiltration . . . . . . . . . . . . . . . . . . . . . . . . 101
5.2.1 FiltrationsonaSymbolicImage . . . . . . . . . . . . . . 102
5.2.2 OrderRelations . . . . . . . . . . . . . . . . . . . . . . . 104
5.2.3 ConnectingRecurrentSets . . . . . . . . . . . . . . . . . 105
5.3 ConstructionofAttractorsandRepellers . . . . . . . . . . . . . . 107
5.4 Detecting(Un)stableandConnectingManifolds . . . . . . . . . . 113
5.5 PerformanceAnalysis . . . . . . . . . . . . . . . . . . . . . . . . 114
5.6 ComparisonwithOtherApproaches . . . . . . . . . . . . . . . . 116
5.7 NumericalCaseStudies . . . . . . . . . . . . . . . . . . . . . . . 119
5.7.1 DuffingSystem . . . . . . . . . . . . . . . . . . . . . . . 119
5.7.2 IkedaMap . . . . . . . . . . . . . . . . . . . . . . . . . 122
6 TheRIMMethod 129
6.1 TheoryoftheMethod . . . . . . . . . . . . . . . . . . . . . . . . 130
6.1.1 TheCoreAlgorithm . . . . . . . . . . . . . . . . . . . . 130
6.1.2 TheSubdivisionCriteria . . . . . . . . . . . . . . . . . . 132
6.1.3 ConvergenceoftheMethod . . . . . . . . . . . . . . . . 137
6.2 ImplementationDetails . . . . . . . . . . . . . . . . . . . . . . . 142
6.3 PerformanceAnalysis . . . . . . . . . . . . . . . . . . . . . . . . 145
6.4 ComparisonsandNumericalCaseStudies . . . . . . . . . . . . . 147CONTENTS vii
7 ApplicationoftheRIMMethod 153
7.1 DetectionofPeriodicPoints . . . . . . . . . . . . . . . . . . . . 153
7.1.1 DefinitionoftheInvestigationTask . . . . . . . . . . . . 154
7.1.2 ComparisonsandNumericalCaseStudies . . . . . . . . . 155
7.2 LocalizationofStableManifolds . . . . . . . . . . . . . . . . . . 162
7.2.1 OutlineoftheMethod . . . . . . . . . . . . . . . . . . . 165
7.2.2 ModificationsoftheAlgorithm . . . . . . . . . . . . . . 166
7.2.3 ComparisonsandNumericalCaseStudies . . . . . . . . . 169
8 Conclusion 179
8.1 Achievements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
8.2 ComparisonofApproaches . . . . . . . . . . . . . . . . . . . . . 181
8.2.1 SymbolicAnalysisandtheRIMMethod . . . . . . . . . 182
8.2.2 RelatedApproaches . . . . . . . . . . . . . . . . . . . . 184
8.2.3 OtherInvestigationMethods . . . . . . . . . . . . . . . . 185
8.3 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
A Zusammenfassung 191
A.1 RelevanzderArbeit . . . . . . . . . . . . . . . . . . . . . . . . . 191
A.2 ZieleundVorgehensweise . . . . . . . . . . . . . . . . . . . . . 192
A.3 VorgestellteUntersuchungsmethoden . . . . . . . . . . . . . . . . 193
A.4 PraktischerNutzen . . . . . . . . . . . . . . . . . . . . . . . . . 197
Bibliography 199
Glossary 209
Index 212viii CONTENTS