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 L₄ 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 L₄ 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 e^tB 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