There are any number of sites on the World Wide Web dedicated to galleries of computer-generated fractal images. Pictures based on Lyapunov Exponent fractals, such as the one pictured above, are some of the most striking and unusual.
Like most fractal images, Lyapunov Exponent fractals are produced by iterating functions and observing the chaotic behaviour that may result.
In this article, we'll be exploring what Lyapunov exponents are, how you iterate functions, what "chaos" really is, and how you go about turning simple maths into marvellous images. There's also a companion article, Computing the Mandelbrot set by Andrew Williams, which looks at the technical details involved in writing a program to compute the Mandelbrot set.
What is iteration?Even simple equations can produce complex behaviour when there is feedback in the system. For example, take a simple function like
Graph of the function f
The number in the definition of the function is there so that the graph of the function fits neatly into the unit box; in other words, if we apply the function to any number in the unit interval , then we get another number in the unit interval.
Now, pick a real number between 0 and 1 (the "initial condition" or "initial point") and apply the function to this to get
For example, suppose we choose ; then we get
Now apply "feedback" to by applying the function again to get
and keep repeating this process to get
and so on.
So, for each number ,..., we put
This process is called "iterating" the function with the initial condition (or "initial point") . The sequence of numbers
is called the "orbit" of the initial condition .
If we add a small error to the initial point , e.g. we look at
and then we look at the orbit ... of , we might expect that the small error is not very important.
However, it turns out that a function like the one above tends to amplify small errors until they become large, so the difference or "error" between the two orbits, i.e. the sequence
tends to grow until it is as large as the numbers themselves.
The following diagrams illustrate this phenomenon: first, we show the orbit of an initial point in blue. We plot the points (for etc.) against the step-number : this is called a "time-series".
Orbit of an initial point
In the next picture, we compare this with the orbit of another close-by point, shown in red. In other words, we add a small error and look at what happens to the orbit:
Orbits of two initially close-by points
Notice that for the first few steps (on the left-hand side of the diagram), the orbits remain very close together and it seems that the small error hasn't made much difference. However, after just a few steps (toward the right-hand side of the diagram) the orbits begin to look completely different. The error has grown until the orbits are far apart.
The next picture shows the size of the error (i.e. the difference between the two orbits) at each step:
Error between the orbits
Notice how the error starts off very small, but after a few steps it has grown as large as the orbits themselves. This is like the noise in a radio transmission becoming as large as the signal itself and swamping it completely.
In fact, no matter how tiny we make the initial error, in most cases it will tend to be amplified until it grows large. This behaviour, where small errors tend to become amplified until they are as large as the "signal" itself, is called sensitive dependence on initial conditions.
Another popular name for this phenomenon is the "Butterfly Effect", so-called because the idea is rather like the tiny flapping of a butterfly’s wings becoming amplified until it causes a hurricane on the other side of the world.
This is because the weather is sensitive to small errors in the same way that the function above is, so that - no matter how accurately we try to measure the weather right now (the temperature, humidity, etc.) - inevitably small errors in our measurements are amplified until they make our long-term weather forecasts unreliable.
This effect is one of the hallmarks of "chaos": chaotic systems all have this feature (but not all sensitive systems are chaotic!) The other hallmarks of chaos are to do with periodic orbits ("cycles", where there is a repeating pattern in the orbit ...) and "mixing" behaviour (like the kneading of dough, where orbits tend to get thoroughly "mixed around" throughout all the possible values).
When all three hallmarks are present (sensitivity, periodic cycles and mixing), we have a phenomenon called "chaos". Unfortunately, Hollywood films have overused the word, so most people think that it means something altogether more wishy-washy, as opposed to a well-defined and precise mathematical term.
Measuring sensitivity: The Lyapunov Exponent
So, we see that when certain systems are iterated, small errors tend to be amplified. How can we measure how quickly this happens?
A quantity called the "Lyapunov Exponent" (after its inventor, Alexander M. Lyapunov, 1857-1918) is used to measure the extent to which ever-smaller "infinitesimal" errors are amplified. In other words, the Lyapunov Exponent measures how sensitive a system is to errors.
Growth of small errors
Remember that we begin with a small initial error. Let’s call this . So, we begin with
i.e. initial condition and error . Then we compare the "exact" orbit ... against the orbit with the error ... and see how the difference between them grows.
In other words, we look at the sequence of errors:
The following picture demonstrates how an initial error grows to give the error at the next step for the function described above:
Growth of an initial error
To see how much the error is amplified at each iteration step , we compute
i.e. we see how big the next error is, in comparison with the current error . (For example, if the next error were twice as big as the current one, then the expression above would have the value .)
After steps, the initial error has been amplified by a factor of:
Now, suppose we had instead just looked at the simple linear function
where is some constant greater than 1. Then any error is simply magnified by at each iteration:
so that after steps, the initial error has been magnified by
(Note that if were less than 1, the error would actually be decreased rather than increased.)
If we want to find out what the value of is for such a linear function , we have
This is the idea behind the Lyapunov exponent: we take a general function and use this same formula to see how much small errors tend to be magnified. We take more and more iterates (larger and larger ) and calculate the corresponding values for . If, as we let grow larger and larger, these values settle down to a constant, then this suggests that the error tends to grow on average like .
Taking the logarithm turns a product into a sum:
The Lyapunov Exponent is defined to be the limiting value of the above quantity as the initial error is made ever smaller-and-smaller, and the number of iterations is sent to infinity.
Lyapunov exponent of a differentiable function
Now, suppose that the function is smooth (i.e. we can differentiate it to get ). In this case, you should notice that the expression on the right-hand side looks familiar! Let’s rewrite it like this (put and ):
If we let go to zero, then this is just the expression for the derivative! So, as tends to zero we have:
Thus we have
Finally, letting go to infinity (i.e. looking at more and more iterates), we obtain a formula for the Lyapunov Exponent of a differentiable function :
If this number is positive, then this means that small errors in the initial condition will tend to be magnified, and the system is showing sensitivity. (Remember that sensitivity is one of the three hallmarks of chaos.) If this number is negative, then small errors tend to be reduced, and the system is showing stability.
So, the Lyapunov exponent gives us a way to measure the stability of our system.
Even some very simple systems are capable of showing both orderly and chaotic behaviour.
These systems may make transitions (called "bifurcations") from one type of behaviour to another, as some parameter is varied, rather like tuning-in to different radio stations by turning the dial on a radio.
For example, remember our function
whose graph was a parabola through , , and . We can add a parameter to let us move the height of the parabola up and down:
For a fixed number (with magnitude between 0 and 1) the graph of against is a parabola still passing through and , but now having its "top" (turning point) at , as shown in the following picture:
Graph of function with a parameter p
You can think of the parameter as being like the radio tuning dial: adjusting the value of moves the top of the parabola up and down smoothly, but as we will soon see the behaviour of the function can change suddenly. When tuning a radio, you sometimes happen to hit the right wavelength and hear a different radio station. In the same way, when the value of (the tuning dial) passes certain special values, the behaviour of orbits can change suddenly.
There is a web page where you can experiment interactively with changing the value of the parabola and the position of the initial point :see Further Reading for details.
Plotting the stability
One idea to help us understand the way that the behaviour changes (as we change the parameter) is to plot the value of the Lyapunov exponent (for some chosen initial point ) against the parameter . This will let us estimate how the stability of our system changes as changes.
The following diagram shows a plot of the calculated Lyapunov exponent (using the starting point ) against the parameter .
Lyapunov exponent vs. parameter
Notice the large negative spikes pointing downward. In reality, these spikes in the graph go off to minus infinity, showing that the behaviour of the function is incredibly stable at those parameter values. Remember that we have calculated an estimate of the logarithm of the error-multiplier: if this value is very large and negative, then the error-multiplier is very small, which indicates that errors tend to vanish away and the orbit of the system is super-stable.
Between the spikes, the graph touches the -axis (so that the Lyapunov exponent is zero): this indicates that these parameters give an orbit which is on the edge of stable and unstable behaviour. It is here that sudden changes (bifurcations) in the behaviour of orbits take place.
Notice that the graph stays below zero until it reaches a point near the right hand side of the plot: this is where sensitivity first appears. As the graph rises above the axis, this means that the Lyapunov exponent is positive so that errors tend to be magnified. Even so, in this right-hand region there are still spikes where super-stable orbits appear.
There is much complicated structure in this diagram and even a simple one-parameter family of functions (like our parabola functions) still holds mysteries for mathematical research. There are also features of this plot that are universal, that is to say that we see them even when we look at very complicated functions, rather than our simple example; looking at simple situations in mathematics can sometimes throw light on more complicated ones.
To make a two-dimensional picture, we look at functions with two parameters (say and ), rather than just one. Then we use a colour to represent the Lyapunov exponent for each choice of the parameters in some rectangle.
Conveniently, we can put these two-parameter functions together from a pair of one-parameter functions. For example, we can simply use the parabola function above. For numbers and we consider the functions:
Then, to make a single function, we combine them in some way. One way to do this is to apply them, one after the other, in some order. For example, we might apply first, then . So we would make our function from:
(i.e. we are alternating between and ) and we then iterate it as usual. (This means that, for example, .) Or, we might choose
or any other sequence of the functions and . Once we have decided what sequence of and to use - let’s choose - we keep it fixed from now on.
Next, we work out the Lyapunov exponent for parameters in a grid. We’re going to build our picture one dot (pixel) at a time.
For each we take the initial point and iterate to estimate the Lyapunov exponent, using the Chain Rule of differentiation to see that
and so we calculate the numbers
for from up to some , and average them. This gives us an estimate of the Lyapunov Exponent. (Choosing a larger value for generally gives a better estimate, but choosing too large means that a computer program will take a very long time to do the calculation for each point .)
We then colour the point corresponding to in our image, depending on the value that we estimated for the Lyapunov exponent. For example, we might choose dark reds for positive Lyapunov Exponents and Yellows for negative values, etc. We can choose a smoothly-spread range of colours when producing our pictures.
Part of the Lyapunov exponent picture for the QP sequence of maps
Understanding the pictures
Another Lyapunov Exponent picture
The sharply-defined curves which sometimes appear in these pictures correspond to very large negative Lyapunov exponents (meaning that the system is very stable, in fact "super"-stable, and errors tend to vanish away).
The background regions indicate positive exponents (where the system is sensitive, i.e. small errors tend to grow, and may be chaotic).
The presence of regions that appear to "cross over" each other reveals that there are two or more different types of behaviour that are "competing" with each other (in fact, these are competing "attractors") - different behaviours "win" the competition for different values of the parameters and , so we see what look like different shapes crossing over each other.
There are also repeating patterns and progressions of shapes, revealing lots of structure that would be difficult to guess just from looking at the simple equations used to generate the pictures. By visualising such structures and seeking to understand them, we can make progress in understanding the behaviour of more complicated models of systems in the real world. The beauty of these, and other, fractal images is an invitation to try and understand such patterns.
Iteration of the logistic map:
If your browser can handle JAVA programs, then you can play with changing the height of the parabola and the position of the initial point (see Order and Chaos in the same system) by looking at the web page Iteration of the Logistic Map.
- Computing the Mandelbrot set in this issue.
Other PASS Maths articles on fractals:
About the author
Andy Burbanks took a BSc in Mathematics and Computation at the University of Loughborough, and stayed on to do a PhD in Mathematics, during which time he developed an interest in mathematical artwork as a hobby.
In addition to his research work, Andy is currently designing mathematical posters for the World Mathematical Year 2000's Posters in the London Underground project.
If we let h tend to 0, then wouldnt f(x +h) - f(x)/h also tend toward 0? I dont understand how that equation is the equation of the derivative of the function f.
When h tends to 0 both the numerator and the denominator of (f(x+h)-f(x))/h tend to 0. This does not mean that the whole expression tends to 0. As an example take f(x)=2x. Then (f(x+h)-f(x))/h=(2(x+h)-2x)/h = 2h/h = 2.
First of all 0/0 is not equal to Zero.
It is 'indeterminate'. For example, think about 5*0/0, 10*0/5*o....
If there is a way to remove the 'thing' that is causing the 0's in the numerator and the denominator you will be able to find the 'vale' of the indeterminate form
I don't understand the graph. If x=1/2, then f'(x)=0, and ln(|f'(x)|)=ln(0)=- infinity. So for x=1/2 Lyapunov exponent should be - infinity for all values of p.