SWEN90004
Modelling Complex Software Systems
Lecture Cx.02 Dynamical Systems and Chaos
Artem Polyvyanyy, Nic Geard
artem.polyvyanyy@unimelb.edu.au;
nicholas.geard@unimelb.edu.au
Semester 1, 2021
SLIDE 1
Overview
In this lecture, you will learn about:
using mathematics to model a system’s behaviour
two mathematical models of population growth (exponential and logistic) chaotic behaviour in (discrete) systems
SLIDE 2
Dynamical systems
SLIDE 3
Recap: what is a dynamical system?
a set of possible states (the state space)
time t (which we may treat as discrete or continuous)
a rule that determines the state at the present time (xt) in terms of states at
earlier times (xt−1,xt−2,…)
For now, we will require this rule to be deterministic, so that the history of the system
(it’s past state) uniquely determines the present state.
also, an initial condition x0 : the state that the system is in when t = 0
SLIDE 4
Functions and iteration
A function takes a number as an input, does something to it, and produces a number as an output; eg,
f(x) = 3x
The function f takes x as an input, multiplies it by 3 and returns the resulting value as
an output
Iteration is simply using the output of the previous application of a function as the input for the next application:
x0, f(x0), f(f(x0)), f(f(f(x0))), . . . x0,x1,x2,x3,…,xt
What happens to the state of a system as time progresses?
SLIDE 5
Population growth
SLIDE 6
Red foxes in Australia
Red foxes were introduced to Australia by settlers from England in the 1830s They are now listed among the world’s 100 worst invasive species
http://en.wikipedia.org/wiki/Red_fox http://en.wikipedia.org/wiki/Australia
SLIDE 7
Red foxes in Australia
Red foxes are an apex predator: they predate on other species (like the bilbies and numbats), but no other species predate on them
FigureBilby FigureNumbat
http://www.murweh.qld.gov.au/bilby-night-talk-and-tour http://www.abc.net.au/news/2011-08-23/numbat-numbers-in-decline-feature/2851582
SLIDE 8
Red foxes in Australia
A female red fox reproduces once per year, producing around 4 kits (baby foxes) To keep things simple, let’s make the following assumptions:
the initial population contained 2 female red foxes a female red fox reproduces in its first year of life a female red fox only reproduces once in it’s life half of newborn kits are female
Therefore, the number of female red foxes will double each year:
xt+1 = 2xt
where xt is the number of female red foxes alive in year t
SLIDE 9
How ‘believable’ the findings of a model are will often rest on the structure of the model and the assumptions that are made in constructing it.
As noted earlier, a model is a simplified version of reality. Simplifying model structure makes it more tractable (whether an analytic or a numerical approach is being taken).
The assumptions that are made are likely to have an important influence on the behaviour of the model. It is therefore important when describing and reporting results from a model to be explicit about the assumptions that have been made in its design. This allows a reader to evaluate whether they agree with the assumptions that have been made, and hence their assessment of the model’s validity.
Red foxes in Australia
Figurefunction plot
What is the general formula for xt?
xt = x02t
Figuretime series plot
The exponential model is often stated as xt = x0rt, where r is a parameter that governs how steeply the curve rises
SLIDE 10
The left plot shows how the input into the function xt+1 = 2xt is related to the output.
The right plot shows how the size of the female red fox population increases over the first few years post-introduction.
In our model, r (the parameter in the general form of the exponential equation) is equal to 2, because the female red fox population doubles each year. If it tripled each year (each female red fox gave birth to 6 kits on average, of which 3 were female), we would use r = 3.
The sequence of states visited as a dynamical system evolves over time is often referred to as an orbit or a trajectory.
But…
This model for the growth of the red fox population in Australia predicts that there should be approximately 2 × 1055 red foxes by 2016!
What is missing?
Before we move on to a different model of population growth: in the model above, we
used r = 2. Think about what happens when:
r=1 r<1
SLIDE 11
r = 1: each female red fox would produce a single female kit, resulting in a stable population size (replacement fertility).
r < 1: each female red fox would produce less than one female kit, resulting in a shrinking population over time (and happy numbats).
Refining our model
Clearly the unlimited growth predicted by the exponential model is unrealistic: the red foxes will eventually run out of food or space
Next, we will consider a model with the additional (more realistic) assumptions that:
when there are few red foxes, there will be plenty of food, and their numbers will grow rapidly
when there are many red foxes, there won’t be enough food to go around, and their numbers will grow more slowly
SLIDE 12
The logistic model of population growth
Pt+1 = rPt where Pt is the population size at time t
Let us say that A is the population size at which the red foxes eat all available food, leading to starvation and zero red foxes next year
Pt+1=rPt 1−
A
When P is close to A, there will be fewer red foxes in the next year When P is close to 0, there will be more red foxes in the next year Dividing through by A and letting x = P/A, we can rewrite this as
xt+1 = rxt(1 − xt) This is known as the logistic map
Pt
SLIDE 13
If Pt = A, then (1 − (Pt/A)) = 0; ie, if the population limit is reached, the population collapses. If P is very small, Pt/A ≃ 0 and population growth is approximately exponential.
Note that P/A is the ratio between the current population size and the population limit, therefore x is the current size as a proportion of this limit and is always in the range [0, 1].
The logistic map
The logistic map (based on a the continuous equation introduced in 1838 by Pierre François Verhulst) displays a diverse range of behaviours, depending on the value of the parameter r
FigureThe logistic map for r = 1 xt+1 = rxt(1 − xt)
rxt corresponds to positive feedback
(1 − xt) corresponds to negative feedback
SLIDE 14
rxt can be thought of as positive feedback because as the value of xt increases, so does the value of rxt. In physical terms, this suggests that the population size next year is the product of the population size this year and the growth rate (much like the exponential model).
(1 − xt) can be thought of as negative feedback becase as the value of xt increases, the value of (1 − xt ) decreases. In physical terms, this captures the decline in population caused by overcrowding and resource depletion.
The logistic map
r = 0.9
SLIDE 15
For any value of r between 0 and 1, the population will die out.
This makes sense because the logistic function is a product of three numbers: r, xn and (1 − xn). As xn is a proportion, all three of these values will be < 1 and hence the population at time t + 1 will always be smaller than at time t.
Zero is a fixed point of the system, and is stable for r in the range [0,1]. This means that at locations around zero, the system will move towards zero.
The logistic map
r = 1.5
SLIDE 16
For r in the range [1, 3), the system is no longer attracted towards zero; a new stable fixed point has appeared at 0.5. The fixed point at zero still exists, but is now unstable, meaning that at locations near zero, the system will move away from zero.
We can identify fixed points of a system numerically by recognising that they occur at values of xt that, when fed into the logistic map, return the same value (ie, xt+1 = xt).
We can also identify them graphically: they occur where the logistic curve (the red parabola) crosses the identity line. When r > 1 this will always occur at two points (one of them being zero).
The logistic map
r = 1.5
SLIDE 17
The system will move towards this stable fixed point irrespective of whether x0 (the initial condition) is above or below it.
The only time it won’t is if x0 is exactly equal to zero. Zero is an unstable fixed point.
The logistic map
r = 3.2
SLIDE 18
For values of r greater than or equal to 3, the system contains no stable fixed points. The behaviour of the system in this instance is an limit cycle with a period of 2.
Again, this period-2 cycle is a stable attractor of the system: nearby values will move towards the 2-cycle.
Zero is still an unstable fixed point.
The transition from a single fixed point to a limit-2 cycle is known as a bifurcation, which may be defined as a qualitative change in a system’s behaviour. Bifurcations are mathematically interesting, and also interesting from a modelling perspective, as they indicate points in parameter space where a system’s behaviour can suddenly change in a dramatic fashion. Bifurcations can be related to the popular notion of ‘tipping points’.
The logistic map
r = 3.52
SLIDE 19
At higher values of r, we observe limit cycles with higher periods. When r = 3.52, we observe a cycle of period 4.
The logistic map
r = 3.56
SLIDE 20
When r = 3.56, we observe a cycle of period 8.
The logistic map
r = 3.84
SLIDE 21
For r = 3.84 we observe a limit cycle of period 3. Note that this attractor takes some time to appear, not until t = 16 or so. This early part of a systems behaviour is often referred to as the transient behaviour of a system.
The logistic map
r = 4.0
SLIDE 22
In this plot, with r = 4, the system’s behaviour appears to be all transient. Even after 50 time steps we observe no periodic behaviour. The system is now displaying the aperiodic behaviour that typifies deterministic chaos.
The mathematical proof that this time series will never repeat exists, but is very complicated.
Chaos
SLIDE 23
A definition of chaos
A system is chaotic if it displays all of the following four properties:
The dynamical update rule is deterministic
The system behaviour is aperiodic
The system behaviour is bounded
The system displays sensitivity to initial conditions
SLIDE 24
First condition: chaotic does not mean random. The logistic map with r ≥ 4 will always display the same behaviour given the same starting point (initial condition).
Second condition: as discussed, the system trajectory does not repeat.
Third condition: consider the exponential function; it’s behaviour was aperiodic (it never repeated), but as it approaches infinity, this aperiodicity is not particularly surprising or interesting (in this context). In contrast, the behaviour of the logistic map is bounded between 0 and 1.
The butterfly effect
Coined by Edward Lorenz while working on a mathematical model of weather: he observed that his model’s behaviour could produce wildly different outputs with only very small modifications to input data:
Two states differing by imperceptible amounts may eventually evolve into two considerably different states . . . If, then, there is any error whatever in observing the present state— and in any real system such errors seem inevitable—an acceptable prediction of an instantaneous state in the distant future may well be impossible … In view of the inevitable inaccuracy and incompleteness of weather observations, precise very-long-range forecasting would seem to be nonexistent.
Lorenz (1963) Deterministic nonperiodic flow, Journal of Atmospheric Sciences 20: 130–141
SLIDE 25
Lorenz used the metaphor of a hurricane, whose occurrence could be influenced by the distant flap of a butterfly’s wings several weeks earlier
The butterfly effect
SLIDE 26
Sensitive dependence on initial conditions
FigureTwo trajectories beginning at x = 0.05 (red) and x = 0.0501 (black)
SLIDE 27
Two trajectories of the logistic map originating from nearby initial conditions (0.05 and 0.0501). While the first few states are similar, by t = 10, the sequence of states visited by each trajectory are visibly different.
Bifurcation diagrams
FigurePoints on attractors of the logistic map for various values of r
Feldman (2012) Chaos and Fractals: An Elementary Introduction, Oxford University Press
SLIDE 28
Often when we are investigating a (model of a) dynamical system, it is useful to be able to get an overview of how the system behaves across its parameter space.
A straightforward approach to this is to systematically sweep through the possible (or interesting) values of the system parameters, recording some output of interest.
The logistic map only has one parameter (r), so we can explore its behaviour using a one-dimensional parameter sweep. The output we are going to record is the value, or series of values that the system converges to (ie, settles on after the initial transient behaviour has passed).
Here, each value of r is shown on a separate line, with the corresponding points in the fixed point or limit cycle attractors indicated. We can clearly see the fixed point at zero, the non-zero fixed point, the 2-cycle, 4-cycle, 8-cycle, 3-cycle and, at the bottom, the chaotic orbit, which visits points across the full state space.
Bifuraction diagrams
FigureThe bifurcation diagram for the logistic map, r in [2.4, 4.0]
http://en.wikipedia.org/wiki/Bifurcation_diagram
SLIDE 29
Thee resulting figure is known as a bifurcation diagram, as it shows the points at which bifurcations occur, and is normally drawn with the system parameter on the x-axis.
Here we have zoomed in on r in the range [2.4,4.0], and can see the emergence of the 2-, 4-, 8- and longer cycles, the appearance of chaotic behaviour, and the windows of stability that exist between chaotic regimes, including the period-3 attractor.
Fascinatingly, if we zoom in on small regions of the bifurcation diagram, we can discover areas that reproduce the structure of the whole diagram on a smaller scale (matlab code is provided on LMS to enable you to explore this behaviour). The bifucation diagram of the logisitc map has fractal (self-similar) properties.
Summary
To model a dynamical system, we define:
our system variables and the states they can take the function that computes the next state
This will usually involve simplifying assumptions about the real world important to record these
When exploring the behaviour of our model, we need to evaluate it against what we know about the real system
This may result in us refining our model
Dynamical systems have several different types of characteristic behaviours
fixed points
limit cycles
aperiodic orbits
The dynamic behaviour that a system exhibits can depend critically on the values of system parameters
SLIDE 30
Next week, we’ll look at some more elaborate mathematical models of complex systems, including returning to our red foxes and their unfortunate prey.
Further reading
(both books available online through UniMelb library) For a gentle introduction:
David P. Feldman, Chaos and Fractals: An Elementary Introduction, Section I on dynamical systems and Section II (parts 9-11) on chaos
For a more mathematically rigorous treatment:
Nino Boccara, Modeling Complex Systems, chapters 4 and 5
Video lectures – Introduction to Dynamical Systems and Chaos (Santa Fe Institute):
http://www.complexityexplorer.org/courses/22-introduction-to-dynamical- systems-and-chaos-winter-2015/
SLIDE 31