Dynamical Systems

Shlomo Sternberg

• Publisher: Dover Publications
• Year: 2014
• ISBN:
  9780486135144
• Topic: Mathematics
• Subtopic: Differential Equations
• Index: Mathematics

Celebrated mathematician Shlomo Sternberg, a pioneer in the field of dynamical systems, created this modern one-semester introduction to the subject for his classes at Harvard University. Its wide-ranging treatment covers one-dimensional dynamics, differential equations, random walks, iterated function systems, symbolic dynamics, and Markov chains. Supplementary materials offer a variety of online components, including PowerPoint lecture slides for professors and MATLAB exercises.
`Even though there are many dynamical systems books on the market, this book is bound to become a classic. The theory is explained with attractive stories illustrating the theory of dynamical systems, such as the Newton method, the Feigenbaum renormalization picture, fractal geometry, the Perron-Frobenius mechanism, and Google PageRank.` — Oliver Knill, PhD, Preceptor of Mathematics, Harvard University.

Chapter1

Iteration and fixed points.

1.1Square roots.

Perhaps the oldest algorithm in recorded history is the Babylonian algorithm (circa 2000BCE) for computing square roots: If we want to find the square root of a positive number a we start with some approximation, x₀ > 0 and then recursively define

This is a very effective algorithm which converges extremely rapidly.

Here is an illustration. Suppose we want to find the square root of 2 and start with the really stupid approximation x₀ = 99. We get:

1.1.1Analyzing the steps.

For the first seven steps we are approximately dividing by two in passing from one step to the next, also (approximately) cutting the error - the deviation from the true value - in half.

After line eight the accuracy improves dramatically: the ninth value, 1.416… is correct to two decimal places. The tenth value is correct to five decimal places, and the eleventh value is correct to eleven decimal places.

To see why this algorithm works so well (for general a > 0), first observe that the algorithm is well defined, in that we are steadily taking the average of positive quantities, and hence, by induction, x_n > 0 for all n. Introduce the relative error in the n–th approximation:

so

As x_n > 0, it follows that

Then

This gives us a recursion formula for the relative error:

This implies that e_n+1 > 0 so after the first step we are always overshooting the mark. Now 2e_n < 2 + 2e_n for n ≥ 1 so (1.2) implies that

so the error is cut in half (at least) at each stage after the first, and hence, in particular,

the iterates are steadily decreasing.

Eventually we will reach the stage that

From this point on, we use the inequality 2 + 2e_n > 2 in (1.2) and we get the estimate

So if we renumber our approximation so that 0 ≤ e₀ < 1 then (ignoring the 1/2 factor in (1.3)) we have

an exponential rate of convergence.

If we had started with an x₀ < 0 then all the iterates would be < 0 and we would get exponential convergence to −

. Of course, had we been so foolish as to pick x₀ = 0 we could not get the iteration started.

1.2Newton’s method.

This is a generalization of the above algorithm to find the zeros of a function P = P(x) and which reduces to (1.1) when P(x) = x² − a. It is

If we take P(x) = x² − a then P′(x) = 2x the expression on the right in (1.5) is

so (1.5) reduces to (1.1).

Here is a graphic illustration of Newton’...

Table of contents

• Cover
• Title Page
• Copyright Page
• Preface
• Contents
• 1 Iteration and fixed points
• 2 Bifurcations
• 3 Sarkovsky’s theorem, Singer’s theorem, intermittency
• 4 Conjugacy
• 5 Space and time averages
• 6 The contraction fixed point theorem
• 7 The Hausdorff metric and Hutchinson’s theorem
• 8 Hyperbolicity
• 9 The Perron-Frobenius theorem
• 10 Some topics in ordinary differential equations
• 11 Lotka - Volterra
• 12 Symbolic dynamics