Logistical nightmare

When initially fiddling around and getting to grips with Matlab a while ago, I had a go at implementing the ‘logistic map’, a well known mathematical process which leads to deterministic chaos.

http://en.wikipedia.org/wiki/Logistic_map

The mathematical operations involved are extremely simple, namely for some value of k we repeatedly perform the operation

x \rightarrow kx(1-x).

Starting at x_0 = 0.5, after a single iteration we should end up at x_1 = k/4, and after another we should be at x_2 = k \cdot k/4 \cdot (1 - k/4) = k^2/4 - k^3/16. Continuing this process, you might expect that we should converge on some function f which stipulates x_{final} = f(k). Calculating this function is trivial, we look for a ‘fixed point’ of the map above and solve:

x = kx(1-x) \Rightarrow x = 1 - \frac{1}{k}.

If we plot a few iterations and our ‘solution’ below, note a few interesting things.

FirstIteration

The functions are all bounded between 0 and 1 for 0 < k < 4, and increase in polynomial order as we increase the number of iterations, much like a Taylor series. However, the ‘final’ function contains a term \propto 1/k, which can’t be approximated by a finite number of positively-powered polynomial terms. In other words, no matter how many iterations we produce, our resulting functions f(k) will never contain a 1/k term and so will never quite reach the ‘actual’ function.

This reminds me slightly of a calculation in condensed matter field theory, where the pairing potential between electrons is calculated to be of the form e^{(1/V)}, where V is some (assumed small) interaction between electrons. This is then a non-perturbative result, as no amount of perturbation orders, i.e. terms proportional to V^n, will lead to a function containing a 1/V term.

Anyway, physics distractions aside, we can continue this iteration process and see where we end up.

ManyIteration

All of the iterations up to 1000 are plotted on top of one another, the first k/4 one is visible, and successive iterations converge upon the blue line representing x = 1 - 1/k. Great! That is, until k = 3 where something funky happens – the line splits into 2 and diverges from our supposed solution.

Like all great experimental scientists, we should examine our theory again in light of new evidence. Guided by what we’ve seen, lets suppose there exist 2 solutions to our map, call them x_A and x_B. Then we have

x_B = kx_A(1-x_A)

x_A = kx_B(1-x_B)

x_A^3 - 2x_A^2 + \frac{k+1}{k}x_A + \frac{1-k^2}{k^3} = 0.

This is a cubic equation with 3 solutions (thank you symbolic algebra toolbox!):

x = 1 - \frac{1}{k}

x = \frac{k \pm \sqrt{(k+1)(k-3)} + 1}{2k}

Accounting for the possibility x_A = x_B, one of the solutions ends up being our original solution which is nice. The second two represent the two new branches of the map above k = 3, and as we can see plotted below, fit very nicely. Also, we see why the branches occur at this point – the new solutions become imaginary for k < 3 and so the map reverts back to the single solution again.

Analytic

Unfortunately, at around k \approx 3.45 the map splits again, and in solving for this we would have to deal with a 15th degree polynomial, which isn’t ideal. However, by dividing out the above solutions (because 1 and 2 are factors of 4, then the above solutions must be included as we could have all 4 solutions the same, or two sets of two) we end up with a 12th degree polynomial, and by investigating its discriminant we find the onset of the 4 solutions at k = 1 + \sqrt{6} \approx 3.449....

This doubling process occurs quicker and quicker until in a finite period we end up with chaos – the mess above k \approx 3.5. Nevertheless there are still patterns in here, hinting at the underlying deterministic order. We can zoom in and we find smaller copies of the overall pattern

Zoom

and so again in this blog we have what looks like a fractal. Nothing as fancy as complex numbers need get involved here, just the kind of equation you could understand in secondary school, and eminently simple to visualise if you feel like a bit of programming on a wet Sunday afternoon.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s