# An Algorithm to Automatically Detect the Smale Horseshoes

Authors: Qingdu Li; Lina Zhang; Fangyan Yang
Journal: Discrete Dynamics in Nature and Society
 (2012)

---

## Abstract

Smale horseshoes, curvilinear rectangles and their U-shaped images patterned on Smale's famous example, provide a rigorous way to study chaos in dynamical systems. The paper is devoted to constructing them in two-dimensional diffeomorphisms with the existence of transversal homoclinic saddles. We first propose an algorithm to automatically construct “horizontal” and “vertical” sides of the curvilinear rectangle near to segments of the stable and of the unstable manifolds, respectively, and then apply it to four classical chaotic maps (the Duffing map, the Hénon map, the Ikeda map, and the Lozi map) to verify its effectiveness.


---

## Body

## 1. Introduction

Among a variety of mathematical characteristics of chaos, the existence of a horseshoe (by S. Smale) has been recognized as the most important signature of chaos from geometrical point of view. The horseshoe theory is based on the geometry of continuous maps on some subsets of interest in state space. Here the images of the subsets can be computed reliably, so rigorous investigation of chaos becomes possible even for systems without explicit solutions.Although the theory provides a powerful tool for many rigorous studies of chaos, such as estimating topological entropy, verifying existence of chaos, and revealing invariant sets of chaotic attractors, it has not been used extensively like many other numerical methods, such as computing Lyapunov exponents or bifurcation diagrams. Beside of reliable computation based on interval arithmetic, another main reason is probably because it is not as convenient to find horseshoes in practical systems as other nonrigorous methods. In recent years, much work has been done in providing more applicable criteria to guarantee the existence of horseshoes [1–4]. The criteria have been applied to many dynamical systems [3, 5–7]. Recently, a progress was made in [8] which proposed a method for finding horseshoes in two-dimensional (2D) chaotic maps (or Poincaré maps). The method was implemented with A MATLAB GUI program (http://www.mathworks.com/matlabcentral/fileexchange/14075) to help readers to improve efficiency and has been successfully applied to some novel cases, for example, a hyperchaotic spacecraft circuit [9], the fractional-order unified system [10], and so forth. However, researches still need to find horseshoes manually with their own experiences. So this paper proposes a simple algorithm to automatically detect the Smale horseshoes in 2D chaotic maps.The paper is organized as follows. Section2 revisits the Smale horseshoe and tries finding some key points; Section 3 introduces our algorithm as well as some classical examples; Section 4 draws conclusions.


## 2. The Smale Horseshoe

First let us recall the notion of the Smale horseshoe. Consider a squareS⊂R2 with four vertices A,B,C, and D. The diffeomorphism(2.1)h:S⟶h(S)⊂R2
is defined as follows: First the map contracts the square S horizontally with a factor less than 1/2, stretches it vertically with a factor greater than 2, then folds it like a horseshoe, and puts it back on the square S, as shown in Figure 1, where h sends A to A′, B to B', C to C', and D to D'.Figure 1
Smale horseshoe.As shown in Figure1, p is a period-1 saddle point, Ws and Wu are the corresponding stable manifold {z:hn(z)→pasn→+∞} and unstable manifold {z:hn(z)→pasn→-∞} of p. Another intersection q is what Poincaré called a homoclinic point. The homoclinic point here is transverse in the sense that the stable and unstable manifolds are not tangent at q.The main point in the Smale horseshoe is not the shape of the squareS and its image of under h, but the “crossing” relation that h(S) goes through S twice between AD and CB while any point of A'B' and C'D' does not locate inside of S, which guarantees the existence of the two disjoint blocks S0 and S1. So the Smale horseshoes can be used extensively in many practical systems, where S will no longer be a square.


## 3. The Algorithm for Finding the Smale Horseshoes in 2D Maps

For convenience, we use a subscript to denote the iteration times, for example,q1=h(q), q0=q, q-1=h-1(q), and use a combination of two points with a different cap to denote a piece of a different manifold between them; for example, pq̂ denotes the piece of Wu from p to q, and qp̆ denotes the piece of Ws from q to p.The key to detecting a Smale horseshoe is the boundary ofS. For the standard case demonstrated in Figure 1, the process is very easy. When we iterate each point of qq1̆ reversely from q to q1, q-1q̆=h-1(qq1̆) must intersect pq̂ three times at least. The first and last intersection points are q-1 and q, respectively. We denote the second one with r-1. Let SW be a block with four sides: pq-1̂,q-1r-1̆,r-1q̂, and qp̆. The map h sends the sides to pq̂,qr̆,rq1̂, and q1p,̆ respectively. Here, q-1r-1̆and rq1̂ intersect twice at s and s¯, respectively. It is obvious that h(SW) and SW also satisfy the relation of the Smale horseshoe.However, for a practical chaotic mapf:R2→R2, we will face the following five difficulties. (1) There are many saddle points with all periods; we have to pick a proper one to ensure the rest computation, but p in Figure 1 is only period-1. (2) Both Ws and Wu have two branches, but Figure 1 only illustrates one of them. (3) The two eigenvalues of f at p can be positive or negative, but Figure 1 only illustrates the positive one. (4) h has a horseshoe, but f may not. (5) SW cannot be applied in rigorous studies of chaos because there exist unavoidable numerical errors in practical computations. An algorithm which can automatically detect a Smale horseshoe must handle the above difficulties.So in our algorithm, we first find a transverse homoclinic point, then we locateSW using the stable and unstable manifolds, and last we extend the boundary of SW outside to get S. The algorithm is as follows with its detailed flowchart illustrated in Figure 2.(1)
Find a periodic pointp at first. Supposing that p has period N, we compute the eigenvalues of the Jacobian matrix of fN at p. If one eigenvalue locates in the inside of the unit circle and the other one locates outside the unit circle, then p is a saddle point of fN; otherwise, we need to find another p and try again. If any of the eigenvalues is negative, then we take I=2; otherwise, I=1. Let g=fIN; then, we find a transverse homoclinic point q by computing the corresponding stable and unstable manifolds of p.(2)
DetectSW by finding a proper iteration time M and a proper intersection point r with the following procedure. Let M=1 andr=p, that is, r1-M=p. Iterate the map g reversely for each point of q1-Mr1-M̆from q1-Mto r1-M until q-Mr-M̆ intersects pq̂ again (not q-M). If the new intersection point is not in r1-Mq̂, then set r-M to be r1-M, M=M+1 and try it again; otherwise, set r-M to be the point and compute the image of r-Mq̂ under the map gM. If rqM̂ does not intersect the new q-Mr-M̆ twice, we increase M with step 1 and try it again; otherwise, we take the manifold pieces pq-M̂, q-Mr-M̆,r-Mq,̂ and qp̆ as the boundary of SW.(3)
Extend the boundary ofSW outward with an equally small distance of δ to get a new boundary S. Then we compute the image of S under gM, and check whether the condition of the Smale horseshoe is satisfied. Generally, the smaller the δ is, the easier the condition can be satisfied; therefore we should decrease δ when the condition fails.Figure 2
The flowchart of the algorithm.Remark 3.1.
The algorithm is based on a saddle with transversal homoclinic. Whether it is fully automatic depends on the procedure to detect this saddle via the periodic orbit and the manifolds computation in the first step. Fortunately, they are both fundamental problems in numerical study of dynamical systems, and there are many good algorithms and software packages in the literature to do this, for example, [11, 12]. So it can be handled by the detailed control flow shown in Figure 2.Remark 3.2.
The intersection of the stable manifold and the unstable manifold must be transversal (not tangential), which guarantees that the algorithm will terminate in a finite number of steps according to the general geometry described by Wiggins [13].Now we demonstrate the ability and efficiency of this algorithm by finding horseshoes of several classical chaotic maps in the following four examples.Example 1 (the Duffing map).
The Duffing map is a discrete version of the Duffing equation [13]. It takes a point(xn,yn) in the plane and maps it to a new point given by
(3.1)xn+1=yn,yn+1=-bxn+ayn-yn3,
where the two parameters usually set to a=2.75 and b=0.2 to produce chaotic behavior. Numerical computation shows that the map has three fixed saddle points. Among them, the Jacobian matrix at the origin has two positive eigenvalues, λ1≈0.07476 and λ2≈2.67524. Clearly, I=N=1, then we find a homoclinic point q=(1.6057128,0.1206999). After a process illustrated in Figure 3, where the solid lines (blue) indicate the stable manifold and the dot lines (red) indicate the unstable manifold, we detect Sw at M=3, and finally find a horseshoe, as illustrated in Figure 4.Figure 3
The process of detectingSw.Figure 4
A Smale horseshoe found in the Duffing map.Example 2 (the Hénon map).
The Hénon map, as a discrete model of the Lorenz system, is one of the most studied dynamical systems that exhibit chaotic behavior. It maps a point(xn,yn) in the plane to a new point given by
(3.2)xn+1=yn+1-axn2,yn+1=bxn,
where the two parameters canonically take a=1.4 and b=0.3 [14]. Our computation shows that the map has two fixed saddle points. We randomly choose one, that is, p=(0.6313545,0.1894063). The corresponding Jacobian matrix has one positive eigenvalue of λ1≈0.155946and one negative eigenvalue of λ2≈-1.92374. So N=1 and I=2. Then we find a homoclinic point q=(0.584132,0.101649). When M=1, we find a horseshoe illustrated in Figure 5.Figure 5
A Smale horseshoe found in the Hénon map.Example 3 (the Ikeda map).
The Ikeda map is a discrete-time dynamical system simplified from a plane-wave model. The map is given by(3.3)xn+1=1+u(xncos⁡⁡tn-ynsin⁡⁡tn),yn+1=u(xnsin⁡⁡tn+yncos⁡⁡tn),
where tn=0.4-6/(1+xn2+yn2)and u is a parameter [15]. The map has a strange attractor for u=0.9. Our computation only finds one fixed saddle point, that is, p=(0.5327546,0.2468968). The corresponding Jacobian matrix has two negative eigenvalues, λ1≈-0.33896 and λ2≈-2.38969. Therefore, we set N=1 and I=2, and then find a homoclinic point q=(0.5370113,-0.8444263). When M=1, we find a horseshoe, illustrated in Figure 6. Because the boundary of S is automatically generated by the algorithm, it appears very different from other horseshoes in the literature where the boundaries usually are polygons.Figure 6
A Smale horseshoe found in the Ikeda map.Example 4 (the Lozi map).
The Lozi map is a two-dimensional map similar to the Hénon map but with the termxn2 replaced by |xn|. It is given by the equations
(3.4)xn+1=1-a|xn|+yn,yn+1=bxn,
where the two parameters also take a=1.4 and b=0.3. Our computation shows that the map has two fixed saddle points. However, the stable and unstable manifolds of each point do not intersect. In order to find a homoclinic point, we try period two. Consequently, we only find one period-2 obit, that is, p=(0.8571429,-0.0857143), and the corresponding Jacobian matrix has two negative eigenvalues with λ1≈-0.06975and λ2≈-1.2902. Obviously, N=2 and I=2; then, we find a homoclinic point q=(0.849499,-0.0943964). When M=1, we find a horseshoe, illustrated in Figure 7, finally.Figure 7
A Smale horseshoe found in the Lozi map.Remark 3.3.
The “crossing” relation betweenh(S) and S is the key to the existence of horseshoe. The relation remains unchanged if we map h(S) and S to their images by a homeomorphism. Therefore, if we find a horseshoe with a certain homoclinic point q, then we have infinitly many horseshoes just by iterating S with the system map f. On the other hand, if we find a different homoclinic point, then we may get a different horseshoe, which may be transformed from the original S under some iterations of the system map. For example, we can get a new horseshoe of the Duffing map only by changingq to (0.1207000,0.00902376). A horseshoe similar to this one, for example, that in Figure 8, can be gotten by Figure 2 under two time iterations of the Duffing map.Figure 8
Another Smale horseshoe found in the Duffing map.


## 4. Conclusions

We have proposed an algorithm for finding the Smale horseshoes in 2D chaotic maps. Numerical studies for four classical maps suggest that this algorithm can effectively find their horseshoes. Comparing with [8], this method is dedicated to the Smale horseshoes in 2D maps. The advantage of the algorithm is that horseshoes can be found automatically by only a few given parameters, which is less dependent on researchers’ experience. In [8], one has to find a horseshoe manually by a lot of trials, which may take hours sometime. The time consumed for the above examples is shown in Table 1, which takes a few seconds at most. So the algorithm is more efficient. In the algorithm, each side of the boundaries is a curve taken parallel along a stable or unstable manifold. This way, the existence of a Smale horseshoe is guaranteed. From this point of view, the algorithm is more applicable than methods using rectangles or polygons to compose boundaries, for example, [8].Table 1
The time consumed for all examples in MATLAB. (The code is downloadable fromhttp://www.mathworks.com/matlabcentral/fileexchange/authors/27275).
Chaotic mapsSaddle detection (S)Horseshoe detection (S)Total (S)The Duffing map0.432.963.39The Hénon map0.270.731.00The Ikeda map0.480.921.40The Lozi map1.203.244.44



---

*Source: 283179-2012-03-29.xml*