November 3, 2005 --- Class 18 --- Finding Bifurcation Points, Instability
			and Chaos, Lyapunov Exponent

	Finding Bifurcation Points

	Previously we discussed how to find the values of r that lead to
	to superstable trajectories, i.e., the trajectories that include
	x=0.5.  We are also interested in finding the bifurcation points
	where we go from stable attractors of period 2^n to stable
	attractors of period 2^(n+1).  This can be done using the code
	in fixed_pts.c in my home directory, which is compiled and in my
	bin directory.  Recall that we used this code to prepare a
	diagram like Fig. 6.2 on page 134 of CSM.  We also know that at
	the bifurcation points, the convergence is very slow.  We can
	use this to iteratively run the code with narrower windows and
	more initial iterations discarded to find the bifurcation
	points.

	For instance, if you run:

	fixed_pts .7 .999 0.001 1000 128 |axis m 0 |xplot

	you will get a nice diagram like Fig 6.2.  If you look at the
	output of fixed_pts, you will see that for each value of r,
	there are 128 lines with the x values that result after 1000
	iterations are discarded.  Away from the r values that
	correspond to bifurcation points, convergence is fast and many 
	of the x values are repeated as we loop over the points in
	stable attractors of period smaller than 128.  However, near the
	bifurcation points, convergence can be slow and we will find
	more than the expected number of unique x values.  How can we
	use this to find the bifurcation points?

	Unix has a utility called sort that is very useful.  The option
	-u, which stands for unique, will throw out repeated lines.  For
	example, in the output of 
	
	fixed_pts .7 .999 0.001 1000 128 | sort -u | more

	you will find output like this:

	7.430000e-01    6.635262e-01
	7.440000e-01    6.639785e-01
	7.450000e-01    6.644295e-01
	7.460000e-01    6.648794e-01
	7.470000e-01    6.653278e-01
	7.470000e-01    6.653279e-01
	7.470000e-01    6.653280e-01
	7.470000e-01    6.653281e-01
	7.470000e-01    6.653282e-01
	7.480000e-01    6.657665e-01
	7.480000e-01    6.657666e-01
	7.480000e-01    6.657667e-01
	7.480000e-01    6.657669e-01
	7.480000e-01    6.657670e-01
	7.480000e-01    6.657671e-01
	7.480000e-01    6.657673e-01
	7.480000e-01    6.657674e-01
	7.480000e-01    6.657675e-01

	Notice that r= 0.743 to 0.746 only appear once.  For those
	values of r, convergence is complete (to the printed accuracy)
	after 1000 iterations.  However, starting with .747, converence
	is so slow that we do not just have 1 or 2 values corresponding
	to a stable attractor of period 1 or 2.

	We can use awk to count the number of lines for each value of r.
	Here is a little awk script pts.a from my home directory:

BEGIN {old_r=0; count=0;}
{if($1 != old_r) {print old_r,count; old_r=$1; count=1;} else ++count;}
END {print old_r,count;}
	
	Combine the commands:

	fixed_pts .7 .999 0.001 1000 128 | sort -u | awk -f pts.a |mo

	Part of the output now looks like this:

	7.440000e-01 1
	7.450000e-01 1
	7.460000e-01 1
	7.470000e-01 5
	7.480000e-01 106
	7.490000e-01 128
	7.500000e-01 128
	7.510000e-01 41
	7.520000e-01 2
	7.530000e-01 2
	7.540000e-01 2
	7.550000e-01 2
	7.560000e-01 2

	and another part looks like this:

	8.590000e-01 2
	8.600000e-01 2
	8.610000e-01 2
	8.620000e-01 128
	8.630000e-01 5
	8.640000e-01 4
	8.650000e-01 4
	8.660000e-01 4

	In this we we can find ranges of r that correspond to the
	transitions between stable attractors of different periods.  You
	may then bracket these regions, decrease the granularity in r
	and increase the number of initial iterations that are thrown
	away.  It is important to note that the first value of r for
	which the number of unique values increases will likely be a
	little below the bifurcaton point.

	Instability and Chaos

	A key issue in chaotic systems is sensitivity to initial
	conditions.  This is discussed in CSM in Problem 6.3 on page
	134.  We looked at r=0.91 as described in part (a) of that
	problem.  It is easy to write a program that will follow two
	trajectories starting at nearby values and see how they converge
	or diverge.  We found that for r=0.91, nearby starting points
	diverge.  The divergence is roughly exponential.  We reproduced
	Fig. 6.8 on page 147.
	
	Lyapunov Exponent

	Near the end of class we briefly discussed the Lyapunov exponent
	which describes the exponential growth or decay of the
	difference between two nearby trajectories.  Equations (6.15)
	and (6.16) are the basis of a computer code to calculate the
	Lyapunov  exponent.  We reproduced Fig. 6.9 on page 149.
	Bifurcation points correspond to the Lyapunov exponent going to
	zero.  The big dips correspond to the superstable attractors.
	The transtion to chaos occurs when the Lyapunov exponent first
	becomes positive.  Note some islands of stability above that
	transition point where the Lyapunov exponent becomes negative.