Period doubling

(Sethna, “Entropy, Order Parameters, and Complexity”, ex. 12.9)
© 2017, James P. Sethna, all rights reserved.

In this exercise, we use renormalization-group and scaling methods to study the onset of chaos. There are several routes by which a dynamical system can start exhibiting chaotic motion; this exercise studies the period-doubling cascade, first extensively investigated by Feigenbaum.

Chaos is often associated with dynamics which stretch and fold; when a batch of taffy is being pulled, the motion of a speck in the taffy depends sensitively on the initial conditions. A simple representation of this physics is provided by the map
            f(x)=4μx(1−x)
restricted to the domain (0,1). It takes f(0)=f(1)=0, and f(1/2)=μ. Thus, for μ=1 it precisely folds the unit interval in half, and stretches it to cover the original domain.

f[x_,μ_] := 4. μ ...

The study of dynamical systems (e.g., differential equations and maps like the logistic map f(x) above often focuses on the behavior after long times, where the trajectory moves along the attractor. We can study the onset and behavior of chaos in our system by observing the evolution of the attractor as we change μ. For small enough μ, all points shrink to the origin; the origin is a stable fixed-point which attracts the entire interval x∈(0,1). For larger μ, we first get a stable fixed-point inside the interval, and then period doubling.

(a) Iteration Set μ=0.2; iterate f for some initial points x0 of your choosing, and convince yourself that they all are attracted to zero. Plot f and the diagonal y=x on the same plot. Are there any fixed-points other than x=0? Repeat for μ=0.3, μ=0.7, and 0.8. What happens?

Nest[f[#,...]&, ..., ...]

Plot[{x, f[...]}, {x,0,1}, AspectRatio->Equal]

Plot[{x, f[...,0.2], f[...,0.3], ...}, {x,0,1},AspectRatio->Equal, PlotLegends->"Expressions" ]

On the same graph, plot f, the diagonal y=x, and the segments {x0,x0}, {x0,f(x0)}, {f(x0),f(x0)}, {f(x0),f(f(x0))}, ... (representing the convergence of the trajectory to the attractor). See how μ=0.7 and 0.8 differ. Try other values of μ.

Note: We write functions like PlotIterate abstractly, in terms of a function g(x,eta), so that we can also examine fsin(x,B) where η=B instead of η=μ.

PlotIterate[μ_, Nskip_:0, Niter_:100, x0_:0.49]:= Block[{},g1 = Plot[{x,f[x,μ]},{x,0,1}];a0 = Nest[...&,x0,...]; traj = NestList[...&, a0, ...]; 
boxPoints = Flatten[Table[{{traj[[n]],traj[[n]]},{traj[[n]],traj[[n+1]]}},{n,1,Length[traj]-1}],1];g2 = ListPlot[boxPoints, Joined->True, PlotRange->All]; Show[g1,g2, PlotLabel->"μ="<>ToString[μ], AspectRatio->1]]

PlotIterate[0.2]

Table[PlotIterate[μ], {μ, {0.7, 0.75, 0.8, 0.9}}]

By iterating the map many times, find a point a0 on the attractor. As above, then plot the successive iterates of a0 for μ=0.7, 0.8, 0.88, 0.89, 0.9, and 1.0.

PlotIterate[0.2,10]

Table[PlotIterate[μ,...], {μ, {0.7, 0.75, 0.8, 0.9}}]

You can see at higher μ that the system no longer settles into a stationary state at long times. The fixed-point where f(x)=x exists for all μ>1/4, but for larger μ it is no longer stable. If x* is a fixed-point (so f(x*)=x*) we can add a small perturbation f(x*+ϵ)≈f(x*)+f’(x*) ϵ = x*+f’(x*) ϵ; the fixed-point is stable (perturbations die away) if |f′(x∗)|<1. (In a continuous evolution, perturbations die away if the Jacobian of the derivative at the fixed-point has all negative eigenvalues. For mappings, perturbations die away if all eigenvalues of the Jacobian have magnitude less than one.)
In this particular case, once the fixed-point goes unstable the motion after many iterations becomes periodic, repeating itself after two iterations of the map---so f(f(x)) has two new fixed-points. This is called period doubling. Notice that by the chain rule df(f(x))/dx=f’(x)f’(f(x)), and indeed
			df[N]dx=df(f(…f(x)…))dx=f’(x)f’(f(x))…f’(f(…f(x)…)),
so the stability of a period-N orbit is determined by the product of the derivatives of f at each point along the orbit.

(b) Analytics: Find the fixed-point x∗(μ) of the map f(x), and show that it exists and is stable for 1/4<μ<3/4. If you are ambitious or have a computer algebra program, show that the period-two cycle is stable for 3/4<μ<(1+(Sqrt[6]))/4.

NSolve[{f[xStar, μ]==..., D[f[xStar,μ], xStar] ==...}, {xStar,μ}]

NSolve[{f[f[xStar, μ],μ]==xStar, D[f[f[xStar,μ],μ], xStar] == -1}, {xStar,μ}]
Print["Is there a solution with μ = ", (1+Sqrt[6])/4.]

(c) Bifurcation diagram: Plot the attractor as a function of μ, for 0<μ<1.. (Pick regularly-spaced δμ, run Ntransient steps, record Ncycles steps, and plot. After the routine is working, you should be able to push Ntransient and Ncycles both larger than 100, and δμ<0.01.)  Also on the bifurcation diagram, plot the line x=1/2 where f(x) reaches its maximum.

Attractor[η_,Nskip_:100, Niter_:100,g_:f, x0_:0.49] := Block[{a0 = Nest[...]}, attractor = NestList[...]; points = Table[{η,x}, {x, attractor}]]

BifurcationDiagram[g_:f, ηMin_:0, ηMax_: 1, δη_:0.001, Nskip_:100, Niter_:100,x0_:0.49]:= Block[{},
g1 = ListPlot[Flatten[Table[Attractor[...], {η,ηMin,ηMax,δη}],1]];
g2 = Plot[0.5, {η,...}, AxesLabel->{μ, x}, PlotStyle->{Green, Dashed}, LabelStyle->Large];
Show[g2, g1, ImageSize->Full]]

BifurcationDiagram[]

BifurcationDiagram[... {Zoom in; decrease δη and increase Nskip until it looks nice}]

Also plot the attractor for another one-humped map
	fSin(x)=Bsin(πx),
for 0<B<1. Do the bifurcation diagrams appear similar to one another?

fSin[x_,B_] := ...
BifurcationDiagram[fSin]

Notice the complex, structured, chaotic region for large μ. How do we get from a stable fixed-point μ<3/4 to chaos? The onset of chaos in this system occurs through a cascade of period doublings. There is the sequence of bifurcations as μ increases---the period-two cycle starting at μ1=3/4, followed by a period-four cycle starting at μ2, period-eight at μ3---a whole period-doubling cascade. The convergence appears geometrical, to a fixed-point μ∞:
μn≈μ∞−Aδ−n,
so
δ=limn→∞(μn−1−μn−2)/(μn−μn−1)
and there is a similar geometrical self-similarity along the x axis, with a (negative) scale factor α relating each generation of the tree.

In the exercise ‘Invariant Measures’, we explained the boundaries in the chaotic region as images of x=1/2. These special points are also convenient for studying period-doubling. Since x=1/2 is the maximum in the curve, f’(1/2)=0. If it were a fixed-point (as it is for μ=1/2), it would not only be stable, but unusually so: a shift by ϵ away from the fixed point converges after one step of the map to a distance ϵf’(1/2)+ϵ2/f’’(1/2)=O(ϵ2). We say that such a fixed-point is superstable. (The superstable points are the values of μ in the figure above which intersect the green line x=1/2.) If we have a period-N orbit that passes through x=1/2, so that the Nth iterate fN(1/2)≡f(…f(1/2)…)=1/2, then the orbit is also superstable, since the derivative of the iterated map is the product of the derivatives along the orbit, and hence is also zero.
These superstable points happen roughly half-way between the period-doubling bifurcations, and are easier to locate, since we know that x=1/2 is on the orbit. Let us use them to investigate the geometrical convergence and self-similarity of the period-doubling bifurcation diagram from part~(d). We will measure both the superstable values of μ and the size of the centermost ‘leaf’ in the bifurcation diagram (crossed by the line x=1/2 where f(x) takes its maximum).  For this part and part~(h), you will need a routine that finds the roots G(y)=0 for functions G of one variable y.


(d) The Feigenbaum numbers and universality: Numerically, find the values of μs[n] at which the 2n-cycle is superstable (the intersections of the attractor with the green line x=1/2), for the first few values of n. (Hint: Define a function G(μ)=(f^([(2^n)]))μ(1/2)−1/2, and find the root as a function of μ. (Note: You’ll want to define G[μ_Real] to avoid having Mathematica generating giant symbolic expressions.) In searching for μs[n+1], you will want to search in a range (μs[n]+ϵ,μsn+(μsn−μsn−1)/A) where A∼3 works pretty well. Calculate μS0 and μS1 by hand.)

μS0=0.5;
Solve[f[f[1/2,μ],μ]==1/2, μ]
μS1 = μ /. Solve[f[f[1/2,μ],μ]==1/2, μ][[3]]

nMax = 11;
GetSuperstablePointsAndIntervals[g_, nMax_:nMax, ηS0_,ηS1_,xMax_:0.5]:=
Module[{ϵ=10.^-10, A = 3, ηS, leafSizes},ηS[0] = ηS0; ηS[1]=ηS1; leafSizes[1] = ...;
For[n=2, n≤nMax, n+=1, {ηMin=...; ηMax=...; 
G[η_Real]:= Nest[...]-xMax;
ηS[n] = η /. FindRoot[G[η], {η,ηMin,ηMax}]; leafSizes[n] = Nest[g[#,ηS[n]]&, xMax, 2^...]-xMax}];{ηS,leafSizes}]

{μS, leafSizes} = GetSuperstablePointsAndIntervals[f,11,μS0, μS1];

Table[μS[n],{n,0,10}]
Table[leafSizes[n],{n,1,10}]

Calculate the ratios ((Subscript[(μ^s), n-1])−(Subscript[(μ^s), n-2]))/((Subscript[(μ^s), n])−(Subscript[(μ^s), n-1])); do they appear to converge to the Feigenbaum number δ=4.6692016091029909…? Estimate μ∞ by using your last two values of (Subscript[(μ^s), n]), your last ratio estimate of δ, and the equations μn≈μ∞−((Aδ)^(-n)) and δ=(lim_(n→∞))(((Subscript[(μ^s), n-1])−(Subscript[(μ^s), n-2]))/((Subscript[(μ^s), n])−(Subscript[(μ^s), n-1])) above. In the superstable orbit with 2n points, the nearest point to x=1/2 is (f^([(2^(n-1))]))(1/2). (This is true because, at the previous superstable orbit, (2^(n-1)) iterates returned us to the original point x=1/2.) Calculate the ratios of the amplitudes (f^([(2^(n-1))]))(1/2)−1/2 at successive values of n; do they appear to converge to the universal value α=−2.50290787509589284…?

ExponentEstimates[g_, ηS_, leafSizes_, xMax_:0.5, nMax_:nMax]:= Module[{δ,α,η∞},
For[n=2, n≤nMax, n+=1, {δ[n]= ...; α[n] = ...}]; η∞ = ηS[nMax] + ...; {δ,α,η∞}]

{δs, αs, μ∞} = ExponentEstimates[f,μS, leafSizes];

Table[{δs[n], αs[n]}, {n,2,nMax}]

Calculate the same ratios for the map f2(x)=Bsin(πx); do α and δ appear to be universal (independent of the mapping)?

BS0 = B /. Solve[fSin[1/2,B]==..., B][[1]]
BS1 = B /.FindRoot[...==1/2, {B,...}]
{Bs, leafSizesSin} =GetSuperstablePointsAndIntervals[...,11,..., ...];

{δSin, αSin, B∞} = ExponentEstimates[g,Bs, leafSizesSin];
{δSin[nMax], αSin[nMax], B∞}

The limits α and δ are independent of the map, so long as it folds (one hump) with a quadratic maximum. They are the same, also, for experimental systems with many degrees of freedom which undergo the period-doubling cascade. This self-similarity and universality suggests that we should look for a renormalization-group explanation.

(e) Coarse-graining in time. Plot f(f(x)) vs.\ x for μ=0.8, together with the line y=x. Notice that the period-two cycle of f becomes a pair of stable fixed-points for f[2].<\em> (We are coarse-graining in time---removing every other point in the time series, by studying f(f(x)) rather than f.) Compare the plot with that for f(x) vs.\ x for μ=0.5. Notice that the region zoomed in around x=1/2 for f[2]=f(f(x)) looks quite a bit like the entire map f at the smaller value μ=0.5. Plot f[4](x) at μ=0.875; notice again the small one-humped map near x=1/2.

Plot[{x,...}, {x,0,1}, PlotLabel->"f(f(x)), μ=0.8", AspectRatio->1]
Plot[{x,...}, {x,0,1}, PlotLabel->"f(x), μ=0.5", AspectRatio->1]
Plot[{x,...}, {x,0,1}, PlotLabel->"f(f(f(f(x)))), μ=0.875", AspectRatio->1]

The fact that the one-humped map reappears in smaller form just after the period-doubling bifurcation is the basic reason that succeeding bifurcations so often follow one another. The fact that many things are universal is due to the fact that the little one-humped maps have a shape which becomes independent of the original map after several period-doublings.
Let us define this renormalization-group transformation T, taking function space into itself. Roughly speaking, T will take the small upside-down hump in f(f(x)), invert it, and stretch it to cover the interval from (0,1). Notice in your graphs for part~(g) that the line y=x crosses the plot f(f(x)) not only at the two points on the period-two attractor, but also (naturally) at the old fixed-point x∗[f] for f(x). This unstable fixed-point plays the role for f[2] that the origin played for f; our renormalization-group rescaling must map (x∗[f],f(x∗))=(x∗,x∗) to the origin. The corner of the window that maps to (1,0) is conveniently located at 1−x∗, since our map happens to be symmetric about x=1/2. (For asymmetric maps, we would need to locate this other corner f(f(xc))=x∗ numerically. As it happens, breaking this symmetry is irrelevant at the fixed-point.) For a general one-humped map g(x) with fixed-point x∗[g] the side of the window is thus of length 2(x∗[g]−1/2). To invert and stretch, we must thus rescale by a factor α[g]=−1/(2(x∗[g]−1/2)). Our renormalization-group transformation is thus a mapping T[g] taking function space into itself, where
	T[g](x) = α[g] (g(g(x/α[g]+x*[g])) − x*[g]).
(This is just rescaling x to squeeze into the window, applying g twice, shifting the corner of the window to the origin, and then rescaling by α to fill the original range (0,1)×(0,1).)

(f) Scaling and the renormalization group: Write routines that calculate x∗[g] and α[g], and define the renormalization-group transformation T[g]. Plot T[f], T[T[f]],... and compare them. Are we approaching a fixed-point f* in function space?

Clear[xStar, α]
xStar[g_,η_] := xStar[g,η] = x /. FindRoot[..., {x,0.5, 1.}]
α[g_,η_] := α[g,η] = 1.0/ ...

Clear[T]
T[g_] := T[g] = α[g,#2] (g[g[#1/ ... + ...,#2],#2]-...)&

Plot[{f[x,μ∞], T[f][x,μ∞],T[T[f]][x,μ∞]}, {x,0,1}, AspectRatio->1, PlotLegends->"Expressions"]

Plot[{T[T[f]][x,μ∞],T[T[fSin]][x,B∞]}, {x,0,1}, AspectRatio->1, PlotLegends->"Expressions"]