Table of Contents
1 Iteration and fixed points 9
1.1 Square roots 9
1.1.1 Analyzing the steps 9
1.2 Newton's method 11
1.2.1 A fixed point of the iteration scheme is a solution to our problem 12
1.2.2 The guts of the method 12
1.2.3 A vector version 13
1.2.4 Problems with the implementation of Newton's method 14
1.2.5 The existence theorem 15
1.2.6 Review 18
1.2.7 Basins of attraction 18
1.2.8 Cayley's complex version 20
1.3 The implicit function theorem via Newton's method 22
1.3.1 The continuity, differentiability of the implicit function, and the computation of its derivative 23
1.4 Attractors and repellers 25
1.4.1 Attractors 25
1.4.2 The basin of attraction of an attractor 25
1.4.3 Repellers 26
1.4.4 Superattractors 26
1.4.5 Notation for iteration 26
1.4.6 Periodic points 26
1.5 Renormalization group 27
1.6 Iteration for kindergarten 31
2 Bifurcations 33
2.1 The logistic family 33
2.1.1 0 < μ ≤ 1 34
2.1.2 μ = 1 34
2.1.3 μ > 1 34
2.1.4 1 < μ < 2 35
2.1.5 μ = 2 - the fixed point is superattractive 37
2.1.6 2 < μ < 3 37
2.1.7 μ = 3 40
2.1.8 μ > 3, points of period two appear 40
2.1.9 3 < μ < 1 + &sqrt;6 41
2.1.10 Superattracting period two points 43
2.1.11 1 + &sqrt;6 < μ 43
2.1.12 Reprise 43
2.2 The fold bifurcation 46
2.3 The period doubling bifurcation 51
2.3.1 Description of the period doubling bifurcation 51
2.3.2 Statement of the period doubling bifurcation theorem 52
2.3.3 Proof of the period doubling bifurcation theorem 54
2.4 Newton's method and Feigenbaum's constant 56
2.5 Feigenbaum renormalization 58
3 Sarkovsky's theorem, Singer's theorem, intermittency 63
3.1 Period 3 implies all periods 63
3.1.1 The Sarkovsky ordering 65
3.1.2 Periodic points of period three for the logistic family 65
3.2 Singer's theorem 67
3.2.1 The Schwarzian derivative and some of its properties 67
3.2.2 Proof and statement of Singer's theorem 69
3.2.3 Application to the logistic family 70
3.3 Intermittency 70
4 Conjugacy 77
4.1 Affine equivalence 77
4.1.1 Conjugacy in general 78
4.2 The tent transformation and L4 79
4.3 Chaos 81
4.3.1 Transitivity 81
4.3.2 Density of periodic points 83
4.3.3 A definition of chaos 83
4.3.4 The sawtooth transformation and the shift 84
4.4 Sensitivity to initial conditions 89
4.5 Conjugacy for monotone maps 91
4.6 Sequence space and symbolic dynamics 93
4.6.1 A new sequence space 98
4.6.2 The itinerary map 99
5 Space and time averages 103
5.1 Histograms and invariant densities 103
5.1.1 Historgrams of iterations 103
5.2 The histogram of L4 107
5.3 The mean ergodic theorem 110
5.4 The arc sine law 113
5.4.1 The random walk 113
5.4.2 The reflection principle 115
5.5 The Beta distributions 121
5.6 Two proofs of Stirling's formula 125
5.6.1 The Euler-Maclauren summation formula 125
5.6.2 Euler's integral and Stirling's formula 126
6 The contraction fixed point theorem 129
6.1 Metrics and metric spaces 129
6.2 Completeness and completion 133
6.2.1 Normed vector spaces 134
6.3 The contraction fixed point theorem 134
6.3.1 Local contractions 135
6.4 Dependence on a parameter 136
6.5 The Lipschitz implicit function theorem 137
6.5.1 The inverse function theorem 137
6.5.2 The implicit function theorem 139
6.6 The local existence theorem for solutions of differential equations 140
7 The Hausdorff metric and Hutchinson's theorem 143
7.1 The Hausdorff metric 143
7.1.1 Contractions and the Hausdorff metric 145
7.2 Hutchinson's theorem 145
7.3 Affine examples 146
7.3.1 The classical Cantor set 146
7.3.2 The Sierpinski gasket 148
7.3.3 A one line code for creating the Sierpinski gasket 149
7.4 Hausdorff dimension 153
7.5 Similarity dimension of contracting ratio lists 154
7.5.1 Contracting ratio lists 154
7.6 Iterated function systems and fractals 155
7.6.1 Realizations of a contracting ratio list 155
7.7 Fractals and fractal dimension 156
8 Hyperbolicity 159
8.1 The conjugacy theorem 159
8.1.1 A global version 160
8.1.2 The local version 163
8.1.3 C∞ conjugacy 165
8.2 Invariant manifolds 165
8.2.1 The Lipschitzian case 167
9 The Perron-Frobenius theorem 175
9.1 Non-negative and positive matrices 175
9.1.1 Primitive and irreducible non-negative square matrices 176
9.1.2 Statement of the Perron-Frobenius theorem 176
9.1.3 Proof of the Perron-Frobenius theorem 177
9.2 Graphology 181
9.2.1 Non-negative matrices and directed graphs 181
9.2.2 Cycles and primitivity 182
9.2.3 The Frobenius analysis of the irreducible non-primitive case 183
9.3 Asymptotic behavior of powers of a primitive matrix 185
9.4 The Leslie model of population growth 186
9.4.1 When is the Leslie matrix primitive? 188
9.4.2 The limiting behavior when the Leslie matrix is primitive 188
9.5 Markov chains in a nutshell 189
9.6 The Google ranking 189
9.6.1 The basic equation 190
9.6.2 Problems with H, the matrix S 190
9.6.3 Problems with S, the Google matrix G 191
9.6.4 Avoiding multiplying by G 192
9.7 Eigenvalue sensitivity and reproductive value 193
10 Some topics in ordinary differential equations 195
10.1 Linear equations with constant coefficients 195
10.1.1 Linear homogenous equations with constant coefficients 195
10.1.2 etB where B is a two by two real matrix 197
10.2 Hyperbolicity for differential equations 199
10.3 Bifurcations of differential equations 199
10.4 Variation of constants 199
10.4.1 The operator version 200
10.4.2 The parametrix expansion 201
10.5 The Poincaré-Bendixon theorem 202
10.5.1 The ω-limit set 202
10.5.2 Statement of the Poincaré-Bendixon theorem 203
10.5.3 Properties of the omega limit set of a trajectory, in the general case 203
10.6 Proof of Poincaré-Bendixon 205
10.7 The van der Pol and Lienard equations 209
10.7.1 The van der Pol equation 209
10.7.2 The Lienard equations 209
10.7.3 Proofs 211
10.7.4 Relaxation oscillations 216
11 Lotka - Volterra 219
11.1 The original Lotka - Volterra equations 219
11.1.1 The null-clines and the zeros 220
11.1.2 Volterra's explanation of why fishing decreases the number of predators 222
11.2 A more realistic model 222
11.3 Competition between species 225
11.4 The n-dimensional Lotka-Volterra equation 228
11.4.1 A theorem of Liapounov 228
11.4.2 Food chains 232
11.5 Replicator dynamics and evolutionary stable strategies 234
11.5.1 The replicator equation 234
11.5.2 Linear fitness 234
11.5.3 Hofbauer's equivalence theorem 235
11.5.4 Nash equilibria 236
11.6 Evolutionary stable states 237
11.7 Entropy and communication 238
11.7.1 Codes 238
11.7.2 Uniquely decipherable codes and instantaneous codes 239
11.7.3 The expected length of a code 239
11.7.4 Shannon's "first theorem" 240
12 Symbolic dynamics 245
12.1 Sequence spaces 245
12.1.1 Exclusions 246
12.1.2 Shifts 246
12.1.3 Homomorphisms between shifts are sliding block codes 247
12.2 Shifts of finite type 248
12.2.1 One step shifts 249
12.3 Directed multigraphs 249
12.3.1 The adjacency matrix of a directed multigraph 250
12.3.2 The number of fixed points 251
12.3.3 The zeta function 251
12.4 Topological entropy 252
12.5 Factors of finite shifts 256
12.6 The Henon map and symbolic dynamics 257
Bibliography 261
Index 263
