Lyapunov exponents

Consider a computation (a function) f, turning an input x into an output f(x). Usually, our data is not exact, that means, we don’t know the exact value of x, but an approximation x + e, e being an error. Thus, the result of our computation is not f(x), but f(x + e) = f(x) + d.

There can be different cases. For example, |d| is greater than |e|. That means, any error in our data is amplified. If we iterate the compuation of f many, many times, this can mean that the final result we obtain and the true result have not even a slight similarity. Another possible case is that |d| is smaller than |e|. That means, inital errors don’t play an important role, they don’t make an important difference. It can be even the case that d = 0, that means, we get the exact result even if our data contains errors.

All tis considerations are not too exciting unless we do not regard many iterations. We define f¹(x) = f(x), fⁿ⁺¹(x) = f(fⁿ(x)). Assume f has a first derivation (at least at most points), called f’. Now, if e is small, then the following holds:

|f’(x)| < 1 --> |e| > |f(x) - f(x + e)|
|f’(x)| > 1 --> |e| < |f(x) - f(x + e)|

That means, knowing the first derivation, we know wether errors are amplified (chaotic, not predictable behaviour) or diminished (ordered, predictable behaviour). We have to consider, of course, not only the derivation of the first iteration, but of all iterations. That means, we want to know wether

|f’(f¹(x))| * |f’(f²(x))| * |f’(f³(x))| * ...
= Prod(i = 1 to infinity) { |f’(fⁱ(x))| }

tends towards 0 (that means, lower than 1) or infinity (that means, greater than 1). Unfortunatly, computing an infinite or even a very large product is itself a task with computational difficulties. Instead of asking wether this product is lower or greater than 1, we consider the logarithm of the whole thing:

Prod(i = 1 to infinity) { |f’(fⁱ(x))| } < 1

log(Prod(i = 1 to infinity) { |f’(fⁱ(x))| }) < log(1)

Sum(i = 1 to infinity) { log(|f’(fⁱ(x))|) } < 0

That is, we examinate a sum instead of a product and ask wether this sum is positive (chaos) or negative (stable). To compute something, we don’t investigate the whole infinte sum, but a finite portion. We can norm this with the length of the sum. We define

lambda(f, x, N) = Sum(i = 1 to N) { log(|f’(fⁱ(x))|) / N }

With some luck, this sum converges with growing N. We can now define the Lyapunov exponent of f at x as

lambda(f, x) = lim(N --> infinity) { Sum(i = 1 to N) { log(|f’(fⁱ(x))|) / N } }

Let us consider a trivial example: f(x) = x². If we start with a x with |x| < 1, the Lyapunov exponent is negative (negative infinity, to be exact), and fⁿ(x) converges (towards 0). That means, if we consider x or x + e, in both cases fⁿ converges towards the same value. If we considere a x with |x| > 1, then the Lyapunov exponent is positive (positive infinity, to be exact), and x diverges. Any difference between x and x + e becomes greater and greater with any further iteration of f.

This Lyapunov exponent is a well known tool in the investigation of dynamic systems (elsewhere I explain how to use it to compute images of the mandelbrot set). It is named after Aleksandr Mikhailovich Lyapunov. He was born 6 June 1857 in Yaroslavl (Russia) and died 3 November 1918 in Odessa (he committed suicide three days after the death of his wive). He looked like this:

Alternating systems

To make things a little bit more complicated, we now consider a function f depending not only on x, but also on a further parameter r. This parameter should change with increasing iterations. For example, r could switch between a value A and a value B:

f²ⁿ⁺¹(x) = f(f²ⁿ(x), A)

f²ⁿ⁺²(x) = f(f²ⁿ⁺¹(x), B)

That means, r follows a pattern ABABABAB... Other patterns are possible, like ABBABBABB... We will consider only finite patterns, patterns that repeat. To refer to such a pattern, we write down only the first repetition. That means, we write AB if we mean the pattern ABABAB..., ABB if we mean ABBABBABB...

If we have a real function f(x, r) and a seed value x and a pattern like ABABB, there are infinite many possible combinations of A and B. All these combinations can be regarded as points within a two-dimensional plane (the AB-plane). We can now compute an abbreviation of the Lyapunov exponent of this system (like evaluating the first thousend iterations). Depending on the result, we can set a color to every point of the AB-plane. With this algorithm, we may get astonishing images, depending on the parameters we have chosen. Those images have been investigated first by Mario Markus (see, for example, Scientific American 5/1995). Initially, he wanted to explore the behaviour of beer yeast. In some popular fractal packages like FRACTINT, those Markus systems are called Lyapunov exponents. Usually, a not too exciting negative parabel is chosen for f.

The Lyapunov exponents of alternating iterations of a sinus function

Markus not only considered a negative parabel, but also a sinus function:

f(x) = b * sin²(x + r)

This function repeats after pi, that means, we have to consider only the intervall [0, pi[, since outside this intervall nothing new happens. This also means that the behaviour of the AB-plane is a repetition of the behaviour of the [0, pi[ x [0, pi[-square (you can use this to get tiled wallpapers). The initial value of x usually plays no crucial role: if the Lyapunov exponent of a seed value x is positive, chances are good that it is positive for most other possible seed values. Instead, the value of b (controlling the steepness of the function) plays a critical role. The greater b is, the more points of the AB-plane usually lead to chaotical behaviour. Also very important is the used A-B-sequence. Even the simple sequence AB has bizarre results, but more complicated sequences have even more complicated results.

Main Lyapunov Index Page
Main Jan Page

31.5.2001
Corrected embarrising error 30.4.2004
Jan Thor
www.janthor.com
jan@janthor.de