This is a preprint of: “Global dynamics of the real secant method”, Antoni Garijo, Xavier Jarque, Nonlinearity, vol. 32(11), 4557–4578, 2019. DOI: [https://doi.org/10.1088/1361-6544/ab2f55] GLOBAL DYNAMICS OF THE REAL SECANT METHOD ANTONIO GARIJO AND XAVIER JARQUE Abstract. We investigate the root finding algorithm given by the secant method applied to a real polynomial p as a discrete dynamical system defined on R2 . We study the main dynamical properties associated to the basins of attraction of the roots of p and show the existence of stable dynamics not related to them. We extend the secant map to the punctured torus T2∞ and the real projective plane RP2 which allow us to better understand the dynamics of the secant method near ∞. Keywords: Root finding algorithms, iteration, secant method. 1. Introduction Root finding algorithms are commonly used as an efficient way to find numerical solutions of non linear equations which cannot be solve explicitly. Consequently its range of applicability is wide over all areas like engineering, economics, sociology or biology. The common idea behind any such algorithm is to consider an initial guess or seed of the unknown solution and construct a sequence converging to the actual solution. There are three immediate questions. If the equation has more than one solution, as it happens in most cases, how to find different seeds converging to all of them? Is it possible to have open regions where seeds do not converge to any solution? What can be said about the speed (number of steps) to have a reasonable approximation of the solution? One way to find out wide and deep answers to these questions is to study the root finding algorithms as discrete dynamical systems. Set X = {Rn , Cn , RPn , CPn , Tn }. Roughly speak- ing a discrete dynamical system over X, known as phase space, is a map f : X → X and the orbits induced by this map starting at x0 ∈ X, that is, {xn := f n (x0 )}n∈N where fn = f ◦ · · · ◦ f . | {z } n times The main goal when studding dynamical systems is to describe the global picture of the asymptotic behaviour of those orbits when x0 runs over all X. In particular the study of fixed points, i.e. x0 in X such that f (x0 ) = x0 , or periodic points of (minimal) period q or q-periodic points, i.e. x0 in X such that there exist q ≥ 2 satisfying f q (x0 ) = x0 and f ` (x0 ) 6= x0 for all ` < q. Those points, which can be either attracting or repelling (or none) depending if all nearby seeds correspond to orbits converging or diverging (or both) to them, play a key role on the global dynamics. In fact, given an attracting fixed (q = 1) or q-periodic point (orbit) x0 ∈ X, its basin of attraction is denoted by A (x0 ) and given by A (x0 ) = {x ∈ X | f nq (x) → x0 , as n → ∞}, Date: June 18, 2018. This work has been partially supported by MINECO-AEI grants MTM-2017-86795-C3-2-P and MTM-2017- 86795-C3-3-P, and the AGAUR grant 2017 SGR 1374. 1 2 ANTONIO GARIJO AND XAVIER JARQUE or, in other words, A(x0 ) could be defined as the maximal open set where orbits converge to x0 . The connected component A? (x0 ) ⊂ A (x0 ) which contains x0 is called the immediate basin of attraction of x0 . How this connect with root finding algorithms is almost direct. Let p be a polynomial and suppose we want to solve p(x) = 0 where x belongs to X. A root finding algorithm is a discrete dynamical system fp : X → X so that its orbits {xn := fpn (x0 )}n∈N , converge to the roots of p for most initial conditions. The most well-known and universal root finding algorithm is Newton’s method. Assume, to simplify the presentation, that p is a real polynomial with deg(p) ≥ 2. The Newton’s method, is defined as p(z) Np : C 7→ C, Np (z) = z − 0 . p (z) Observe that zeroes of p coincide with the fixed points of Np . Moreover easy computations show that if ζ ∈ C is a simple root of p then Np0 (ζ) = 0. This implies that every root ζ belongs to A(ζ) the immediate basin of attraction of ζ, for which the sequences {zn := Npn (z0 )}n∈N tend to ζ; so Newton’s method is a root finding algorithm. Certainly the dynamical system is not well defined at the critical points of p. To go over this problem we extend the phase space from C to Ĉ = C ∪ {∞}, where Ĉ denotes the Riemann sphere. One can show by the use of the charts defined on Ĉ that the Newton’s map is well defined at the whole Riemann sphere, and ∞ is a repelling fixed point of N . Since Newton’s method is one of the most powerful tools for solving polynomial or transcen- dental equations, the literature about it, from a dynamical system point of view, is extremely large and it was the starting point of holomorphic dynamics (see [Cay79a, Cay79b, Cay80]). This approach has had important numerical implications. For instance we refer to M. Shishikura [Shi09] who proved a remarkable theorem implying the simple connectivity of the immediate basins of attraction (see also [Prz89]), and we refer to J. Hubbard, D. Schle- icher and S. Sutherland [HSS01], who provided a universal set (only depending on the degree of the polynomial) of initial conditions to find out all roots of a polynomial. As a counterpart it is known that for certain polynomials of degree larger than two there are open sets of ini- tial conditions for which Np do not converge to any root of p (see [McM87]) and so Newton’s method might have problems as a root funding algorithm. Finally we refer to [BFJK14] and [BFJK15] for Newton’s method applied to transcendental maps. Alternative to Newton’s method, another well known root finding algorithm is the secant method. Surpassingly, there are few references about the secant method as a dynamical system. This is in fact the main topic of this paper. More precisely, if again we denote by p a real polynomial, with deg(p) ≥ 2, the secant method is the root finding algorithm associated to the function     2 2 z w Sp : C 7→ C , Sp : 7→ w − p(w) w−z . w p(w)−p(z) One major difference with respect to Newton’s method is that Newton’s map depends on one variable (real or complex) while secant method depends on two variables (real or complex). Thus, the natural phase space for the secant method is R2 or C2 . Of course there are several papers in the literature studding discrete dynamical systems on C2 (or CP2 ). For example there are many papers on polynomial automorphisms of C2 (see for instance [BS91a, BS91b, BS92, Duj04, DL15]) or, more focussed, on the complex version of the (polynomial) Hénon map (see for instance[HOV94, HOV95, HPV00, BS06, FsS92, ABFsP17]). DYNAMICS OF THE SECANT METHOD 3 There is also a wide literature on birational maps (see [CMn11, BD05, Bed03, CZ14]) but essentially all of these works refer to dynamical systems generated by diffeomorphisms. In contrast the secant map defined in the R2 or in C2 is not an injective map at all, introducing new and rich potential dynamics. A first step towards the understanding of the complexity of this dynamical system is to restrict the attention to the real version of the secant method. More precisely, we will assume through the whole paper that p is a monic, real polynomial of degree k ≥ 2 having n ≤ k simple real roots denoted by α1 < α2 < . . . < αn . Then we consider the secant method acting on R2 which is the root finding algorithm generated by the real secant map     2 2 x y (1) S := Sp : R 7→ R , S: 7→ y−x , y y − p(y) p(y)−p(x) where the orbit of (x0 , y0 ) ∈ R2 is given by the points {(xn , yn ) = S n (x0 , y0 ) ∈ R2 }n∈N . Observe that the real versions of Newton and secant methods are based on a similar idea. In the Newton case, for a given seed x0 ∈ R, the next value x1 = Np (x0 ) is the intersection between the x−axis and the tangent line through the point (x0 , p(x0 )) with the while in the secant case for a given seed (x0 , y0 ) ∈ R2 , the next value is (y0 , x1 ) = S (x0 , y0 ) where x1 is the intersection between the x−axis and the secant line through the points (x0 , p(x0 )) and (y0 , p(y0 )). It is also worth to be noticed that S has no definition at points where the denominator of the second component is zero. We will run over with this difficulty later. The natural framework for studding S as a plane dynamical system is the iteration of rational-like maps on R2 (see [BGM99, BGM03, BGM05], and reference therein, for a more complete discussion). We introduce here the notation we need to state our main results. Consider the iteration of a map defined in the plane given by     x F (x, y) (2) T : 7→ , y N (x, y)/D(x, y) where F , N and D are assumed to be differentiable functions. Of course (1) is a particular case. Let δT = {(x, y) ∈ R2 | D(x, y) = 0}, be the subset of R2 where T is not, a priori, well-defined. Therefore the map T : E → E defines a smooth dynamical system on E, where [ E := ET = R2 \ T −n (δT ). n≥0 From definition E corresponds to points whose infinite T -orbit is well defined, or equivalently, its complement in R2 are all seeds for which the orbit gets eventually truncated. Roughly speaking T sends points of δT to infinity since the denominator D is zero, except at those points of δT where also the numerator N is zero and hence the value of T is uncertain. We say that a point Q in δT is a focal point if the second component of T evaluated at Q takes the form 0/0 (i.e. N (Q) = D(Q) = 0), and there exists a smooth simple arc γ(τ ), τ ∈ [0, ), with γ(0) = Q, such that limτ →0+ T (γ(τ )) exists and it is finite. We denote by Q the set of all focal points of the dynamical system given by (2). Focal points are point of discontinuity of the map T (see Figure 1). By definition the set of focal points Q is a subset of the set of no definition of the secant map δT . 4 ANTONIO GARIJO AND XAVIER JARQUE We are ready to state our main results. The first one is about the shape and distribution of the basins of attraction of the fixed points of S, in particular we show that any focal point belongs to the boundary of the basin of attraction of all the roots of the polynomial p. We recall that p is a monic, real polynomial of degree k ≥ 2 having n ≤ k simple real roots denoted by α1 < α2 < . . . < αn . Theorem A. The secant map S defined in (1) induces a smooth dynamical system on E. Moreover the following statements hold. (a) The only fixed points of S are the points (α` , α` ) , ` = 1, . . . , n, and they are all attracting. (b) Each basin of attraction A (α` ) := A (α` , α` ) , ` = 1, . . . n, is unbounded. (c) If n = 1 or n = 2, then A? (α1 ) (and A? (α2 ), if n = 2) are unbounded. If n ≥ 3 then A? (α1 ) and A? (αn ) are unbounded while A? (α` ) with 2 ≤ ` ≤ n − 1 are bounded. (d) The set of focal points of the secant map is Q = {(αi , αj ) , i, j = 1 . . . n, i 6= j}. Moreover \ Qi,j ∈ ∂A (α` ) and Qj−1,j ∈ ∂A? (αj ) 1≤`≤n A natural question when studding root finding algorithms is to have a control of the possible stable dynamics different from the attracting basins of the roots of the polynomial, studied above (see again [McM87]). The existence of those open sets will bound the effectiveness of the method as a root finding algorithm. Theorem B. The following statements hold. (a) The secant map S defined in (1) has no periodic orbits of minimal period either two or three. (b) There exists a polynomial p such that the secant map applied to p exhibits an attracting periodic orbit of minimal period four. In particular the dynamical plane has open regions of initial conditions for which S does not converge to any root of the polynomial p. We turn our attention to the behavior of the secant map near infinity. Using the expression of the secant map it is possible to continuously extend the secant map on the limit points of vertical lines (parallel to x = 0), horizontal lines (parallel to y = 0), and lines passing through the origin. In Section 3 we study the extension of the secant map, denoted by Ŝ, to the space T2∞ . Using this approach we are able to define Ŝ at all points in R2 except at the set Q of focal points. As we will see points in δS \ Q firstly go to infinity in a particular direction and secondly come back to the finite plane in a continuous way. We can also prove the existence of a periodic orbit of minimal period three using this way to go and come back to infinity. This special phenomenon occurs at the set of points δS2 = {(β, β) ∈ R2 , p0 (β) = 0}. Numerical experiments illustrate an stable asymptotic dynamics near the points in δS2 , following this periodic orbit of minimal period three. It turns out, however, that the extension Ŝ is non smooth at those critical points and hence we cannot apply the differential matrix to study their stability. However, some numerical experiments seem to indicate that there are nearby points whose orbit converge to this three periodic orbit. In the next theorem we collect the main result on the dynamics of Ŝ defined on T2∞ . DYNAMICS OF THE SECANT METHOD 5 Theorem C. The map Ŝ : T2∞ \ Q 7→ T2∞ \ Q defines a continuous extension of S. The map Ŝ is smooth except at the points in δS2 = {(β, β) ∈ R2 with p0 (β) = 0}. Moreover at these points Ŝ exhibits a periodic orbit of minimal period three. In Section 4 we extend S to the real projective plane RP2 . Using homogeneous coordinates, we built a new extension of S is such a way the line at infinity `∞ ⊂ RP2 is invariant. The behaviour of the restricted dynamical system at the line of infinity allow us to conclude important dynamical properties of S as a plane dynamical system. Precisely we prove the following result. k−1 −1 Theorem D. Let k = deg(p). Let ϕ(x) = xxk −1 , where x ∈ R. The secant map admits an 2 extension S̃ over RP . In particular S̃ : `∞ → `∞ defines the smooth dynamical system (in homogeneous coordinates)      S̃(x) := S̃ 1 : x : 0 = 1 : ϕ(x) : 0 , (3) S̃|`∞ = S̃(∞) := S̃ 0 : 1 : 0 = 1 : 0 : 0 , having a unique attracting fixed point ηk > 0. Moreover the following statements hold. (a) If k is even, then S̃ has a repelling fixed point τk < 0. Moreover, S̃ n (x) → ηk as n → ∞, for all x ∈ R ∪ {∞} such that x 6= τk . (b) If k is odd, then S̃ n (x) → ηk as n → ∞, for all x ∈ R ∪ {∞}. The acknowledge of the behaviour of S near infinity given by this result allow us to conclude some relevant information of the dynamics of S on the plane (see Section 5). We organize the paper as follows. In Section 2 we prove Theorems A and B. In Section 3 we present the first extension of S over the torus T2∞ and prove Theorem C. In section 4 we introduce the homogeneous coordinates for the projective plane, extend S to it and prove Theorem D. In Section 5 we conclude and present some final remarks. Acknowledges. The authors are in depth to Armengol Gasull who point out the works of Bischi et al. We also want to thank Arturo Vieiro for helpful comments on previous stages of this work. 2. The secant map on the real plane: Proof of Theorems A and B In this section, as well as in the next sections, we will describe the phase portrait of the dynamical system generated by the iterates of the secant map S applied to a real polynomial p of degree k ≥ 2 having 1 ≤ n ≤ k simple real roots denoted by α1 < α2 < . . . < αn . Its primer explicit formula is given in (1). It is clear that, due to the rational character of S there is an implicit uncertainty on how to define the image at points where the denominator of the second component is zero. In order to partially run over this problem we set the following sets   δS1 = (x, y) ∈ R2 | p(x) = p(y) with x 6= y , δS2 = (x, x) ∈ R2 | p0 (x) = 0 , ∞ [ (4) δS = δS1 ∪ δS2 and E = R2 \ S −n (δS ) n≥1 The following lemma shows that S extends easily to the points (x0 , x0 ) ∈ R2 , since they are removable singularities of S, unless p0 (x0 ) = 0. 6 ANTONIO GARIJO AND XAVIER JARQUE Lemma 2.1. The secant map defined in (1) admits the following well defined expression on R2 \ δ S     y, yq(x,y)−p(y) if y 6= x,  q(x,y)  (5) S(x, y) = 0  x, xp (x)−p(x) if y = x, p0 (x) where q(x, y) is a symmetric polynomial such that p(x) − p(y) = (x − y)q(x, y). Moreover, q(x, x) = p0 (x) and for any (x0 , y0 ) such that x0 6= y0 we have that ∂q p0 (x0 ) − q (x0 , y0 ) ∂q q (x0 , y0 ) − p0 (y0 ) (6) (x0 , y0 ) = and (x0 , y0 ) = . ∂x x0 − y0 ∂y x0 − y0 In particular (5) defines a smooth dynamical system on E. Remark 1. Observe that for a given x, y ∈ R with x 6= y the value of q(x, y) is the slope of the secant line through the points (x, p(x)) and (y, p(y)). Moreover Sp (x, x) = (x, Np (x)) where Np is the Newton method applied to p. Proof. Fix a natural j ≥ 1. Simple computations show that xj − y j = (x − y)(xj−1 + xj−2 y + · · · xy j−2 + y j−1 ) := (x − y) qj (x, y) Thus if we write qj (x, y) := xj−1 + xj−2 y + · · · xy j−2 + y j−1 k X (7) q(x, y) := aj qj (x, y) j=1 we easily conclude k X k X j j  (8) p(x) − p(y) = aj x − y = (x − y) aj qj (x, y) = (x − y) q(x, y). j=1 j=1 In other words the factor (x−y) divides p(x)−p(y) and the resultant polynomial is symmetric. Moreover, since qj (x, x) = xj−1 + xj−2 x + · · · + xxj−2 + xj−1 = jxj−1 , we get k X k X q(x, x) = ai qi (x, x) = ai ixi−1 = p0 (x). i=1 i=1 According to this new notation it is immediate to see that (1) writes as (5), while deriving at both sides of the expression (8) we obtain (6).  According to (2), and the definition of focal point, by taking different paths, γ(τ ) landing at Q, the value of limτ →0+ T (γ(τ )) might take different finite values on the, so called, focal line LQ = {(x, y) ∈ R2 | x = F (Q)}. In other words, when we land at a focal point Q with a curve γ(τ ) with tangent slope m at Q then the image by T tends to a concrete value (F (Q), y(m)), where N (γ(τ )) (9) y(m) = lim . τ →0 D(γ(τ )) In particular, the operator T is not continuous at the focal points. See Figure 1. A natural question to ask is the relation between the slope m and the value of the limit (9). Next result gives an answer for the generic case. DYNAMICS OF THE SECANT METHOD 7 γ1 T (γ1 ) γ2 δT [D(x, y) = 0] y(m1 ) Q m1 T (γ2 ) T y(m2 ) m2 LQ [x = F (Q)] Figure 1. Discontinuity of T at a focal point Q. Theorem 2.2 ([BGM99]). Let T be the rational map described in (2). Let Q be one of its focal points and assume Nx (Q)Dy (Q) − Ny (Q)Dx (Q) 6= 0. Then there is a one-to-one correspondence between the non δT -tangent slopes m ∈ R of arcs γ(τ ) landing at Q, and the points (F (Q), y) ∈ LQ . The correspondence writes as (see Figure 1) Nx (Q) + mNy (Q) m 7→ (F (Q), y(m)) with y(m) = Dx (Q) + mDy (Q) (10) Dx (Q)y − Nx (Q) (F (Q), y) 7→ m(y) with m(y) = Ny (Q) − Dy (Q)y The focal points belong to R2 \ E but they, and their focal lines, play a key role on the understanding of the global dynamics of the dynamical system generated by T , and so S Lemma 2.3. The set Q of all the focal points of S contains n(n − 1) points located at the points Qi,j = (αi , αj ) , i 6= j. Moreover, for a given focal point Qi,j , the focal line is given by LQi,j = {(x, y) ∈ R2 | x = αj }, and hence, for a given i, the n − 1 focal points Qi,j , j = 1, . . . n, j 6= i share the same focal line. Proof. As stated if Q = (x0 , y0 ) ∈ R2 is a focal points of S then the evaluation of its second component at the point Q takes the form 0/0. According to (5) there are no focal points at the line x = y, otherwise we would have p(Q) = p0 (Q) = 0, a contradiction with the assumption that p has no multiple roots. Therefore, again from (5), focal points should be solutions of the system of equations  yq(x, y) − p(y) = 0, q(x, y) = 0, with x 6= y. If q(x, y) = 0, we conclude that p(y) = 0, and we recall that p(x) − p(y) = (x − y)q(x, y) = 0, then a focal point should satisfy p(x) = p(y) = 0 and x 6= y. Therefore we conclude that S has n(n − 1) focal points and they are located at Qi,j = (αi , αj ), i, j = 1, . . . n, i 6= j. It is easy to check that p0 (αi )p0 (αj ) Nx (Qi,j )Dy (Qi,j ) − Ny (Qi,j )Dx (Qi,j ) = 6= 0, αi − αj since, by hypothesis, the zeros of p are simples. From definition of focal line, for a given Qi,j , i, j = 1, . . . , n i 6= j, the focal line is given by LQi,j = {(x, y) ∈ R2 | x = αj }, 8 ANTONIO GARIJO AND XAVIER JARQUE and the lemma follows. In Figure 2 we sketch the situation for n = 3.  y=x Q1,3 Q2,3 (α3 , α3 ) Q1,2 (α2 , α2 ) Q3,2 (α1 , α1 ) Q2,1 Q3,1 x = α1 x = α2 x = α3 Figure 2. Sketch of the dynamical plane of Sp where p is a polynomial with three simple real roots α1 < α2 < α3 . The focal focal points Q2,1 and Q3,1 share the focal line x = α1 . The focal points Q1,2 and Q3,2 share the focal line x = α2 , and finally, the focal points Q1,3 and Q2,3 share the focal line x = α3 . Red points converge to (α1 , α1 ), green points converge to (α2 , α2 ) and blue points converge to (α3 , α3 ). The following consequence of Hôpital’s rule will be needed in the proof of Theorem A. Lemma 2.4. Let f, g : (−ε, ε) → (−ε, ε) be two smooth functions such that for some a ∈ R and b 6= 0 we have lim f (τ ) = lim g(τ ) = 0, lim f 0 (τ ) = a and lim g 0 (τ ) = b. τ →0+ τ →0+ τ →0+ τ →0+ Then  0 f (τ ) 1  00 a lim = f (0) − g 00 (0) . τ →0+ g(τ ) 2b b Proof. Since   f (τ ) 0 f 0 (τ )g(τ ) − g 0 (τ )f (τ ) 0 lim = lim 2 = , τ →0 + g(τ ) τ →0+ g (τ ) 0 we apply Hôpital’s rule to obtain    00  f (τ ) 0 f (τ ) g 00 (τ )f (τ ) 1  00 00 a lim = lim − = f (0) − g (0) . τ →0+ g(τ ) τ →0+ 2g 0 (τ ) 2g 0 (τ )g(τ ) 2b b  2.1. Proof of Theorem A. First we prove that the map S : E → E is of class C 1 . We denote the two components of S = (S 1 , S 2 ). From the expression of S (5) it is clear that we only need to check the smoothness of the second component of S on the straight line y = x when p0 (x) 6= 0. Fix a point (x0 , x0 ) satisfying this condition. We claim that ∂S 2 ∂S 2 1 p(x0 )p00 (x0 ) (x0 , x0 ) = (x0 , x0 ) = · . ∂x ∂y 2 p0 (x0 )2 DYNAMICS OF THE SECANT METHOD 9 From definition we have that ∂S 2 1   (x0 , x0 ) = limh→0 S 2 (x0 + h, x0 ) − S 2 (x0 , x0 ) h ∂x h  i 1 h p(x0 ) = limh→0 h x 0 − p(x 0 ) p(x0 +h)−p(x0 ) − x 0 − 0 p (x0 ) h i p(x0 ) h 1 = limh→0 − h − 0  p(x0 +h)−p(x0 ) p (x0 )  p(x0 ) 1 1 = limh→0 − h 0 p00 (x0 ) 2 − p0 (x0 ) , p (x0 )+ 2 h+O(h ) 00 (x ) where the last equality follows from the fact that p(x0 +h) = p(x0 )+p0 (x0 )h+ p 2 0 h2 +O(h3 ). Moreover, taking series, we also have 1 1 p0 (x0 )2 p00 (x − = − h + O(h2 ). p0 (x0 ) + 0) h + O(h2 ) p0 (x0 ) 2p00 (x0 ) 2 All together imply ∂S 2 1 p(x0 )p00 (x0 ) (x0 , x0 ) = · . ∂x 2 p0 (x0 )2 ∂S 2 ∂S 2 Using the fact that S 2 (x, y) = S 2 (y, x) we conclude that ∂x (x0 , x0 ) = ∂y (x0 , x0 ) using 2 the definition of these partial derivatives. Now we show that the partial derivative ∂S ∂x is a 2 continuous map in a neighborhood of (x0 , x0 ) (by symmetry ∂S ∂y will be also a continuous map). Let (x1 , y1 ) ∈ E with x1 6= y1 . We have ∂S 2 p(y1 ) ∂q (x1 , y1 ) = 2 (x1 , y1 ). ∂x q (x1 , y1 ) ∂x From (7) we have ∂qj j(j − 1) j−2 lim (x1 , y1 ) = xj−2 0 (1 + · · · + j − 1) = x0 , and (x1 ,y1 )→(x0 ,x0 ) ∂x 2 ∂q p00 (x0 ) lim (x1 , y1 ) = . (x1 ,y1 )→(x0 ,x0 ) ∂x 2 Finally, we get ∂S 2 1 p(x0 )p00 (x0 ) lim (x1 , y1 ) = = S 2 (x0 , y0 ). (x1 ,y1 )→(x0 ,x0 ) ∂x 2 p0 (x0 )2 Since the maps S 1 and S 2 are continuous maps in a neighbourhood of (x0 , x0 ) we have that S is a differentiable map at (x0 , x0 ) with ! 0 1 DS(x0 , x0 ) = p(x0 )p00 (x0 ) p(x0 )p00 (x0 ) . 2p0 (x0 )2 2p0 (x0 )2 Now we prove (a). From (5) we see that if (x0 , y0 ) is a fixed point of S then x0 = y0 . Moreover it should satisfy (11) p0 (x) 6= 0 and p0 (x)x = xp0 (x) − p(x), 10 ANTONIO GARIJO AND XAVIER JARQUE so x should be a zero of p. Fix (α` , α` ) , 1 ≤ ` ≤ n. Since p has all its roots simple, its differential matrix writes as   0 1 DS (α` , α` ) = , 1≤`≤n 0 0 So the two eigenvalues of DS (α` , α` ) are equal to 0, proving thus that the fixed point (α` , α` ) is attracting. This proves (a). Fix ` = 1, . . . n. It is easy to see from (5) that, on the one hand, if j 6= ` and x 6= αj then S (x, α` ) = (α` , α` ); and, on the other hand, if y ∈ R, then S (α` , y) = (y, α` ). This proves (b) since the attracting basin of each fixed point (α` , α` ) of S contains unbounded segments of the straight lines rH := {(x, y) ∈ R2 | y = α` } and rV := {(x, y) ∈ R2 | x = α` }. The above arguments also prove (c) if n = 1 or n = 2. Assume n ≥ 3. We observe that if ` = 2, . . . , n − 1 the fixed point (α` , α` ) belongs to the rectangle R` with ∂R` =[(α`−1 , α`−1 ) , (α`+1 , α`−1 )] ∪ [(α`+1 , α`+1 ) , (α`−1 , α`+1 )] ∪ (12) [(α`−1 , α`−1 ) , (α`−1 , α`+1 )] ∪ [(α`+1 , α`−1 ) , (α`+1 , α`+1 )] where [a, b], a, b ∈ R2 denotes the straight segment from a to b. See Figure 2. Stament (c) now follows from the fact that ∂R` ∩A? (α` ) = ∅, according to the arguments of the paragraph above. We now will prove statement (d). Fix Q := Qi,j = (αi , αj ) ∈ R2 , a focal point. First we claim that here is a one-to-one correspondence between the non δS -tangent slopes of the paths landing at Q and the points of the prefocal line LQ = {(x, y) ∈ R2 | x = αj }. Let (13) F (x, y) = y, N (x, y) = yq(x, y) − p(y) and D(x, y) = q(x, y). From Lemma 2.1 and easy computations we have αj p0 (αi ) −αi p0 (αj ) p0 (αi ) p0 (αj ) (14) Nx (Q) = Ny (Q) = Dx (Q) = and Dy (Q) = − , αi − αj αi − αj αi − αj αi − αj which, in particular, implies p0 (αi )p0 (αj ) Nx (Q)Dy (Q) − Ny (Q)Dx (Q) = 6= 0. αi − αj Now Theorem 2.2 tells us that under these hypothesis, there is a one-to-one correspondence between the slope, m, of any non δSp -tangent path γ(τ ) landing at Q, and the points of LQ . Moreover, from (10) and (14) it is easy to see that the bijection is given by αj p0 (αi ) − αi p0 (αj )m p0 (αi ) (αj − y) (15) y(m) = or m(y) = . p0 (αi ) − p0 (αj )m p0 (αj ) (αi − y) In particular, m = 0 corresponds to y = αj and m = ∞ corresponds to y = αi . Observe that we know that the horizontal line rH := {(x, y) ∈ R2 | y = αj }, outside the focal points, is mapped to the fixed point (αj , αj ), and the prefocal line LQj,i := {(x, y) ∈ R2 | x = αi }, outside the focal points, maps in two iterates to the fixed point (αi , αi ). This implies that Q ∈ ∂A (αj ) ∩ ∂A (αi ). To finish the proof we need to show that Q ∈ ∂A (α` ) for all ` 6= j, i. Clearly the non δS -tangent slopes given by p0 (αi ) (αj − αk ) (16) mk = for 1 ≤ k ≤ n with k 6= i, j, p0 (αj ) (αi − αk ) DYNAMICS OF THE SECANT METHOD 11 correspond, through the one-to-one correspondence, to the focal points Qj,` = (αj , α` ) ∈ LQ with ` 6= j, i. So, every path, γ(τ ), τ ∈ (0, ε), landing at Q with finite slope m ∈ R with m 6= mk , k = 1, . . . , n, k 6= i, j, satisfies that S (γ(τ )) lands at a non focal point of LQ and so, it eventually belongs to the basin of attraction of the fixed point (αj , αj ). Therefore the only paths landing at Q with finite slope which could eventually belong to A (α` ) for ` 6= i, j are the ones defined in (16). We claim that for every mk we have paths landing at Q with slope mk which eventually belong to each A (α` ) for ` 6= i, j. To see the claim let us fix m` one of the singular slopes defined in (16), and let us consider the following κ-family of paths parametrized by τ ∈ (−ε, ε)   1 2 1 2 1 2 γκ (τ ) =: (x(τ ), y(τ )) = (αi , αj ) + (1, m` )τ + (1, κ)τ = αi + τ + τ , αj + m` τ + κτ . 2 2 2 Certainly γκ (0) = Q, γκ0 (0) = (1, m` ) and γκ00 (0) = (1, κ). Our aim is to prove that there is a one-to-one correspondence between κ and (S ◦ γ)0 (0), or equivalently, we want to show that choosing different values of κ we are landing at the corresponding focal point (according to m0 ) with all possible slopes. Observe that     0 f (τ ) 0 (S ◦ γ) (0) = m` , |τ =0 , g(τ ) where f (τ ) := N (x(τ ), y(τ )) and g(τ ) := D (x(τ ), y(τ )), and N and D are defined in (13). Since Q is a focal point we have f (τ ) 0 lim = . τ →0 g(τ ) + 0 Some computations show that lim f 0 (τ ) = αj p0 (αi ) − αi p0 (αj ) m0 := a and lim g 0 (τ ) = p0 (αi ) − p0 (αj ) m0 := b. τ →0+ τ →0+ We claim that b 6= 0. Indeed, otherwise, y (m` ) = ∞ (see (10)) while singular slopes corre- spond to focal points of the form (αj , α` ) , ` 6= j. Hence, we are on the hypothesis of Lemma 2.4 to get  0 f 1  00 a (17) lim (τ ) = f (0) − g 00 (0) . τ →0+ g 2b b Finally some computations show that f 00 (τ ) = [Nxx (x(τ ), y(τ )) x0 (τ ) + Nxy (x(τ ), y(τ )) y 0 (τ )] x0 (τ ) + Nx (x(τ ), y(τ )) x00 (τ ) [Nyx (x(τ ), y(τ )) x0 (τ ) + Nyy (x(τ ), y(τ )) y 0 (τ )] y 0 (τ ) + Ny (x(τ ), y(τ )) y 00 (τ ), and g 00 (τ ) = [Dxx (x(τ ), y(τ )) x0 (τ ) + Dxy (x(τ ), y(τ )) y 0 (τ )] x0 (τ ) + Dx (x(τ ), y(τ )) x00 (τ ) [Dyx (x(τ ), y(τ )) x0 (τ ) + Dyy (x(τ ), y(τ )) y 0 (τ )] y 0 (τ ) + Dy (x(τ ), y(τ )) y 00 (τ ). Thus, f 00 (0) = Nxx (Q) + 2Nxy (Q)m` + Nyy (Q)m2` + Nx (Q) + Ny (Q)κ (18) g 00 (0) = Dxx (Q) + 2Dxy (Q)m` + Dyy (Q)m2` + Dx (Q) + Dy (Q)κ Substituting on the right hand side expression of (17) we see that the κ-coefficient is given by p0 (αi ) (αj − αi ) 6= 0, as desired. Hence statement (d) follows. 12 ANTONIO GARIJO AND XAVIER JARQUE In Figure 3 we illustrate Theorem A for a concrete polynomial of degree three with three roots. In Figure 3(b) we can see that in a neighbourhood of the focal point Q3,2 all directions except two correspond to green (basin of attraction of the fixed point (α2 , α2 )). One direction correspond to blue (basin of attraction of (α3 , α3 )) and there is one singular direction with red (basin of attraction of the fixed point (α1 , α1 )). In fact the picture shows that with m = ∞ there is also red. But in any event Figure 3(b) illustrate that, for this example, Q3,2 ∈ ∂A (α1 ) ∩ ∂A (α2 ) ∩ ∂A (α3 ) c(α3 , α3 ) (α2 , α2 ) c Q3,2 Q3,2 c (α1 , α1 ) (a) Range [-1,5]x[-1,5]. (b) Range [2.34,3.85]x[1.28,2.79]. Figure 3. Dynamical plane of S applied to the polynomial p(x) = x(x − 2)(x − 3). We show in red the basin of attraction of (0, 0), in green the basin of attraction of (2, 2) and in blue the basin of attraction of (3, 3). We show the set δS where the map S is not well defined. We also plot the line y = x where belong the three attracting points of S(a). Zoom in the dynamical plane around the focal point Q2,3 (b). 2.2. Proof of Theorem B. We show statement (a) by contradiction. We first assume the existence of a periodic orbit of minimal period 2 in E, that is S(a, b) = (c, d) and S(c, d) = (a, b) for some a, b, c, d ∈ R such that (a, b) and (c, d) are in E. From (5) we conclude that c = b and d = a. So, S(a, b) = (b, a) and S(b, a) = (a, b) with a 6= b (otherwise we would have a fixed point). From (5), if S(a, b) = (b, a) we conclude that b−a a = b − p(b) . p(b) − p(a) Notice that p(a) 6= p(b) since (a, b) ∈ E. The above equation writes as   p(b) (b − a) 0 = (b − a) 1 − = p(a) . p(b) − p(a) p(b) − p(a) Since a 6= b the above equation concludes p(a) = 0. Interchanging the role of a and b we also conclude p(b) = 0. All together imply (a, b) 6∈ E. DYNAMICS OF THE SECANT METHOD 13 We secondly assume the existence of a periodic orbit of minimal period 3 in E, that is S(a, b) = (c, d), S(c, d) = (e, f ) and S(e, f ) = (a, b) for some a, b, c, d, e, f ∈ R such that (a, b), (c, d) and (e, f ) are in E. Arguing in a similar way as before we have that c = b, e = d and f = a, so we have that S(a, b) = (b, d), S(b, d) = (d, a) and S(d, a) = (a, b). Since the minimal period of the orbit is three we conclude that the three real numbers a, b and d are different. Without lost of generality we might assume a < b < d (otherwise we rename the letters). Since the secant line through (a, p(a)) and (d, p(d)) should cut the line y = 0 at the point x = b (observe that S(d, a) = (a, b)) we know that p(a)p(d) < 0. Assume p(a) > 0 and p(d) < 0 (the other case is similar). This force p(b) > 0, since the secant line passing through (a, p(a)) and (b, p(b)) should intersect the line y = 0 at x = d (observe that S(a, b) = (b, d)). Accordingly the secant line through (b, p(b)) and (d, p(d)) will intersect the line y = 0 at a point η ∈ (b, d), a contradiction with S(b, d) = (d, a) and a < b. This finish the proof of statement (a). Now we deal with statement (b) by showing of the existence of (attracting) periodic S-orbits of minimal period 4. We denote by a, b, c and d four real numbers such that a < b < c < d. Arguing in a similar way as we did above, after relabelling the real numbers involved in the construction of the periodic orbit of period 4 the configuration should be (see Figure 4), a < b < c < d and (19) S(a, b) = (b, d) S(b, d) = (d, c) S(d, c) = (c, a) S(c, a) = (a, b). y p(a) p(b) c d a b x p(c) p(d) Figure 4. Configuration of the period 4 cycle. To simplify the construction we assume that the secant lines passing through (a, p(a)) and (b, p(b)), and through (c, p(c)) and (d, p(d)) have slope equal to −1. Under this assumption and the fact that we S(a, b) = (b, d) and S(d, c) = (c, a) we get (20) p(a) = d − a > 0, p(b) = d − b > 0, p(c) = a − c < 0 and p(d) = a − d < 0. In order to satisfy all equalities in (19) we need to still force two conditions: that the secant line passing through (b, p(b)) and (d, p(d)) crosses the line y = 0 at the point x = c, and that the line passing through (a, p(a)) and (c, p(c)) crosses the line y = 0 at the point x = b. Easy 14 ANTONIO GARIJO AND XAVIER JARQUE computations show that these two conditions write as (a − d)(d − b) (d − a)(a − c) (21) c=d− and b = a − . a + b − 2d c + d − 2a Choosing the following concrete values 1 √  1 √  ā = 1 < b̄ = 2 < c̄ = 3 + 5 ≈ 2.618 < d¯ = 5 + 5 ≈ 3.618 2 2 the polynomial p satisfying (22) p(ā) = d¯ − ā > 0, p(b̄) = d¯ − b̄ > 0, p(c̄) = ā − c̄ < 0 ¯ = ā − d¯ < 0 and p(d) is such that S has a periodic orbit of period four given by the points    { ā, b̄ , b̄, d¯ , d, ¯ c̄ , (c̄, ā)}. The unique interpolating polynomial of degree three through these points writes as pā,b̄,c̄,d¯(x) = 2.61803 − (x − 1) − 2.61803(x − 1)(x − 2) + 2(x − 1)(x − 2)(x − 2.61803) Observe that the arguments used above implicitly provide a huge family of polynomials for which the secant method has a four periodic orbit. Our aim is to find one having an attracting four periodic orbit. The strategy will be to keep the parameters ā < b̄ < c̄ < d,¯ as well as their images in (20), but modify the values of the derivative (so, the new polynomial will have a higher degree). Due to the fact that our dynamical system in E is smooth (see Theorem A) the local behaviour (attracting, repelling or other) of the cycle is governed by the eigenvalues of the matrix Λ where (23) ¯ DS(d, Λ = DS(ā, b̄) DS(b̄, d) ¯ c̄) DS(c̄, ā), with DS (x0 , y0 ) denoting the differential matrix of the map S at the point (x0 , y0 ). In particular if the eigenvalues of Λ have both absolute value less than one then the cycle is attracting. Taking partial derivatives from (5) when x 6= y (which is our case here) we have   0 1 (24) DS (x0 , y0 ) = A (x0 , y0 ) B (x0 , y0 ) where p(y0 ) [p0 (x0 ) − q(x0 , y0 )] p(x0 ) [q(x0 , y0 ) − p0 (y0 )] A (x0 , y0 ) = and B (x0 , y0 ) = . q 2 (x0 , y0 ) [x0 − y0 ] q 2 (x0 , y0 ) [x0 − y0 ] ¯ given by (22), their images given by (20) and According with our parameters {ā, b̄, c̄, d} √  Remark 1 we know that q(ā, b̄) = q(d, ¯ c̄) = −1 and q(c̄, ā) = q(b̄, d) ¯ = −1/2 3 − 5 . Substituting we have √  √  A(ā, b̄) = − 21 1 + 5 (1 + p0 (ā)) B(ā, b̄) = 21 3 + 5 (1 + p0 (b̄)) √  √  √  √  ¯ = A(b̄, d) 1 −2 + 5 3 + 5 + 2p0 (b̄) ¯ d) B(d, ¯ = 1 ¯ 7 − 3 5 3 + 5 + 2p0 (d) 2 4 √   √  ¯ c̄) = − 1 1 + A(d, ¯ 5 1 + p0 (d) ¯ c̄) = B(d, 1 3+ 5 (1 + p0 (c̄)) 2 2 1 √  √  1 √  √  A(c̄, ā) = 2 −2 + 5 3 + 5 + 2p0 (c̄) B(c̄, ā) = 4 7 − 3 5 3 + 5 + 2p0 (ā) . DYNAMICS OF THE SECANT METHOD 15 ¯ so that the All we need to do is to choose suitable values of p0 (ā), p0 (b̄), p0 (c̄) and p0 (d) eigenvalues of Λ are of modulus less than one. ¯ = −1 we get Fixing a polynomial p such that p0 (ā) = p0 (b̄) = p0 (c̄) = p0 (d)     ¯ 0 1 ¯ 0√  √ 1 DS(ā, b̄) = DS(d, c̄) = , DS(b̄, d) = DS(c̄, ā) = 1 , 0 0 2 3− 5 5−2  √ 2 √   1 1 Λ= 4 3− 5 2 5 5 − 11 . 0 0 √  2 The eigenvalues of Λ are 0 and 14 3 − 5 ≈ 0, 14589803 < 1. Therefore using the Hermite interpolation we obtain the existence of a polynomial of degree seven for which the secant map ¯ 7→ (d, exhibits an attracting periodic orbit of period four (ā, b̄) 7→ (b̄, d) ¯ c̄) 7→ (c̄, ā) 7→ (ā, b̄). In Figure 5 we show the dynamical plane of the secant map applied to this interpolating polynomial. Remark 2. The strategy for proving Theorem B (b) could be modify to find out polynomi- als p satisfying the statement with lower degree. For instance one can modify some of the parameters used in the proof of Theorem B (b) to produce a degree six polynomial with an attracting period four cycle. But we do not know if six is the lower degree for a polynomial with an attracting periodic orbit of period four. In Figure 5 we show the dynamical plane of S applied to a polynomial of degree 7 (the one constructed in the proof of Theorem B). In the dynamical plane we observe the basin of attraction of each one of the seven real roots of the polynomial and the attracting cycle of period four. 3. The secant map on a torus: Proof of Theorem C In the previous section the secant map is defined on R2 \ δS , where δS is the set of no definition of S. More precisely δS contains all the points (x, y) with x 6= y such that p(x) = p(y) and all the points (x, x) with p0 (x) = 0 (see Equation 4). There is no hope to extend continuously the dynamical system generated by S on the whole plane since focal points are intrinsically points of discontinuity of S. We recall that the set Q containing all the focal points is a subset of δS . However a continuous extension of S is possible outside Q, as long as infinity is added to the domain of definition of an extension of S. A first step in this direction is to enlarge R2 to get a torus T2∞ minus one point by adding certain directions to ∞ with identifications. Moreover, this extension is smooth on T2∞ \ Q except at the points in δS2 = {(x, x) ∈ R2 | p0 (x) = 0}. Before entering in the definition of the space T2∞ and the extension of the secant map we can compute the dynamics near infinity. Concretely, we can evaluate the limit of the secant map at some specific directions. Lemma 3.1. Let p be a polynomial of degree k ≥ 2, and let r be a real number. Then, (a) lim S(r, y) = (±∞, r), y→±∞ (b) lim S(x, r) = (r, r). x→±∞ Proof. From the definition of the secant map (1) we have that     y−r p(y)r − yp(r) S(r, y) = y, y − p(y) = y, , p(y) − p(r) p(y) − p(r) 16 ANTONIO GARIJO AND XAVIER JARQUE (a) (b) (c) (d) (e) Figure 5. (a) Dynamical plane of the Secant method applied to a a polyno- mial of degree 7 with seven real roots (red) and an attracting 4-cycle (blue). See the proof of Theorem B for the construction of this polynomial. In the picture we show the line y = x and an small circle around each one √of the seven fixed points of S.√(b) Zoom near √ (1, 2). (c) Zoom near (2, 5/2 √ + 5/2). (d) Zoom near (5/2 + 5/2, 3/2 + 5/2). (e) Zoom near (3/2 + 5/2, 1). DYNAMICS OF THE SECANT METHOD 17 and thus S(r, y) → (±∞, r) as the variable y tends to ±∞, since the polynomial p has degree k ≥ 2. In a similar way computing S(x, r) we obtain     x−r p(x)r − p(r)x S(x, r) = r, r − p(r) = r, , p(x) − p(r) p(x) − p(r) concluding that S(x, r) → (r, r) as the variable x tends to ±∞.  The idea of the extension of S is the following. Firstly we can extend the space R2 adding an external boundary of the form (x, ±∞) and (±∞, y) and later on we identify the symbols +∞ and −∞ obtaining an space homeomorphic to the torus minus one point. Secondly we continuously extend the map S using Lemma 3.1, that says that the image under S of the vertical line x = r near infinity is the horizontal line y = r near infinity, and the image under S of the horizontal line y = r near infinity is close to the point (r, r). Thus we have a way to go to infinity, using vertical lines, and a way to come back from infinity using horizontal lines. Now we formalize this extension. We first recall the construction of the two-dimensional torus T2 using the identification of the unit square Q = {(x, y) ∈ R2 ; 0 < x < 1 , 0 < y < 1}, then a natural topological model for T2 is given by T2 := Q/ ∼ with the identifications (x, 0) ∼ (x, 1) and (0, y) ∼ (1, y). Notice that T20 := Q/ ∼ is the torus minus one point (0, 0) ∼ (1, 0) ∼ (0, 1) ∼ (1, 1). See Figure 6. Figure 6. The topological model of the Torus T2 and the tours minus one point (erasing the four extreme boundary points). Inspired on this model, our goal is to enlarge R2 adding certain points at infinity. More precisely, we take Q∞ = {(x, y) ∈ R2 } ∪ {(x, ±∞) , x ∈ R} ∪ {(±∞, y) , y ∈ R} with the following identifications (x, +∞) ∼ (x, −∞) and (+∞, y) ∼ (−∞, y). Observe that the resultant object that we obtain after identifying the points at infinity is T2∞ := Q∞ / ∼ which correspond precisely to the torus minus one point (−∞, −∞) ∼ (−∞, ∞) ∼ (∞, −∞) ∼ (∞, ∞). To simplify notation we write T2∞ = {(x, y) ∈ R2 } ∪ {(x, ∞) , x ∈ R} ∪ {(∞, y) , y ∈ R}, 18 ANTONIO GARIJO AND XAVIER JARQUE and the following three charts define an atlas on the surface ϕ1 (x, y) := Id(x, y) = (x, y) if (x, y) ∈ R2 (  (25)  0) if y = ∞ (x, (0, y) if x = ∞ ϕ2 (x, y) = 1 and ϕ3 (x, y) = 1 x, y if y 6= {0, ∞} x, y if x 6= {0, ∞}. Given a point p ∈ T2∞ we denote by Up a small enough open neighborhood of p on the surface and Up the open image by the corresponding chart on R2 . Using this atlas we are able to define an extension of S on T2∞ \ Q. For all (x, y) ∈ R2 , set     y, yq(x,y)−p(y) if y 6= x,  q(x,y)  (26) G(x, y) := 0  x, xp (x)−p(x) if y = x, p0 (x) Observe this is in fact the precise expression (5) of the map S, well defined in R2 \ δS . Then    G (x, y)  if (x, y) ∈ Up where p ∈ R2 \ δS  −1 ϕ2 ◦ G (x, y)  if (x, y) ∈ Up where p ∈ δS \ Q (27) Ŝ(x, y) := −1   ϕ3 ◦ G ◦ ϕ 2 (x, y) if (x, y) ∈ Up where p = (x0 , ∞)  (G ◦ ϕ3 ) (x, y) if (x, y) ∈ Up where p = (∞, y0 ) 3.1. Proof of Theorem C. Observe that the focal points are points of discontinuity of the map Ŝ since they are already points of discontinuity of the map S. On the other hand since the map Ŝ coincides with G at the set R2 \ δS we conclude that Ŝ is differentiable on R2 \ δS (see Theorem A). So, we only need to study the differentiability of Ŝ at the points in δS \ (Q ∪ δS2 ), at the points (x, ∞), x ∈ R, and at the points (∞, y), y ∈ R. Thus, we split the proof into three cases. Case (i). Let p = (x0 , y0 ) be a point in δS \ (Q ∪ δS2 ) ⊂ T2∞ and let Up be a neighbourhood of (x0 , y0 ), or in other words a point (x0 , y0 ) such that p(x0 ) = p(y0 ) with x0 6= y0 . Easy computations from (25), (26) and (27) show that   p(x) − p(y) Ŝ(x, y) = y, , (x, y) ∈ Up . y p(x) − x p(y) Since Ŝ has a rational expression and the denominator does not vanished by taking a neigh- borhood of p small enough, we conclude that Ŝ is a smooth map with Ŝ(x0 , y0 ) = (y0 , 0). Case (ii). Let p = (x0 , ∞) be a point in T2∞ . Using the expressions of the charts (25) and the map Ŝ (27) we obtain   q(y)x − p(x)y k−1 Ŝ(x, y) = y, , q(y) − p(x)y k where p(z) = a0 + a1 z + · · · + ak−1 z k−1 + z k , z ∈ {x, y}, and q(y) = 1 + ak−1 y + · · · + a1 y k−1 + a0 y k . We notice that Ŝ(x0 , 0) = (0, x0 ) and that Ŝ is a smooth map whenever it is defined (the denominator is not zero near (x0 , 0)). Case (iii). Let p = (∞, y0 ) ∈ T2∞ . Using the corresponding charts and the definition of the secant map we have that Ŝ writes as, DYNAMICS OF THE SECANT METHOD 19 p(y)xk−1 − yq(x) (28) Ŝ(x, y) = . p(y)xk − q(x) As before, considering Ŝ near the point (0, y0 ), we have Ŝ(0, y0 ) = (y0 , y0 ) and Ŝ is also smooth in a sufficiently small neighborhood of p. This finish the proof of the smoothness of the extension of the real secant map S on the torus. The existence of a periodic orbit of minimal period three on T2∞ (compare with Theorem B) is a direct application of the definition of Ŝ. Indeed, if x0 is such that p0 (x0 ) = 0 then (x0 , x0 ) ∈ δS \ Q and its Ŝ-orbit is given by, Ŝ(x0 , x0 ) = (x0 , ∞), Ŝ(x0 , ∞) = (∞, x0 ) and Ŝ(∞, x0 ) = (x0 , x0 ). This finish the proof of Theorem C. Remark 3. As a consequence of Theorem C every point (x0 , x0 ) with p0 (x0 ) = 0 generates a periodic orbit (x0 , x0 ) 7→ (x0 , ∞) 7→ (∞, x0 ) 7→ (x0 , x0 ), and the natural question is to investigate the local behavior of this cycle. One can see that Ŝ is not differentiable at (x0 , x0 ) and so the local behaviour cannot be explained by the eigenvalues of the differential matrix. We have explored numerically this phenomenon and we conjecture that there exists a simply connected region U(x0 ,x0 ) and for every point w in U(x0 ,x0 ) the sequence {S 3n (w)}n≥0 converges (very slowly) toward (x0 , x0 ) as n tends to infinity. Moreover, the point (x0 , x0 ) belongs to the boundary of U(x0 ,x0 ) . If this conjecture is true we obviously have countably many images and preimages of U(x0 ,x0 ) . We have observed this phenomenon around every critical point (x0 , x0 ) such that p0 (x0 ) = 0, see for example the small black sets (that is points not converging to the roots of the polynomial) in Figures 3 and 5. We also have constructed a detailed numerical analysis for the polynomial p(x) = 13 x3 − 4x + 3, focusing in a small neighborhood of the critical point (2, 2), since p0 (2) = 0. In Figure 7 we show in black a numerical approximation of the region U(2,2) . 4. The secant map on the line at infinity: Proof of Theorem D In order to give a more detailed global behaviour of the dynamical system defined by the secant map S we consider now another extension of S on the projective plane RP2 = R2 tRP1 , where t denotes the disjoint union. Recall that RP2 is a compact, non orientable space. Indeed it can be defined defined as the space of lines through the origin in R3 . Using this approach we can visualize RP2 as the union of the plane R2 and the compact line RP1 . Consider the plane z = 1. We identify every line through the origin with the intersecting point between this line and the plane z = 1. Observe that all lines contained in the  plane z = 0 are excluded. See Figure 8(a). So, we might parametrized these points by x : y : 1 . The set of lines excluded in this construction forms a line called the line at infinity of the real projective plane and it is denoted by `∞ := RP1 (see Figure 8(b)). To induce coordinates on `∞ we use the slope of the lines m := y/x when x 6= 0 and the remaining point directly by 0 : 1 : 0 . In Figure 8(b) we show four examples of points of the type [1 : m : 0] (black) and the point [0 : 1 : 0] (grey). We notice that when m → ∞ we obtain precisely the point 20 ANTONIO GARIJO AND XAVIER JARQUE Figure 7. Dynamical plane of the secant map applied to the polynomial p(x) = 1 3 3 x −4x+3 near the critical point (2,2). Range of the picture [1.92, 2.08]×[1.92, 2.08]. Points in color black denote points in the set U(2,2) converging to (2, 2) under S 3 , while points in color pink denote points attracted by the root x = 3 of p. We also show the lines x = 2 and y = 2, thus the point (2, 2) is located at the center of the picture. [0 : 1 : 0]. Finally RP2 admits the following coordinates,      x:y:1 with (x, y) ∈ R2      2 (29) RP = 1:m:0 with m ∈ R        0:1:0 We notice that points in the finite plane are characterized by the third coordinate equal to 1, while points at the line at infinity have the third coordinate equal to 0. Notice also that antipodal points are identified. 4.1. Proof of Theorem D. We firstly deduce the expression of the extended secant map defined on `∞ , using homogeneous coordinates, and secondly we deal with the dynamical system defined on it. In order to define S̃[1 : m : 0], m 6= 0 we consider a general sequence of points (un , vn ) over the line vn = mun with lim un = ∞. Then if we write (rn , sn ) := S (un , vn ) we will define n→∞ sn S̃[1 : m : 0] = [1 : lim : 0]. n→∞ rn From the definition of the secant map (1) we have   un − vn (rn , sn ) = vn , vn − p(vn ) . p(un ) − p(vn ) Clearly rn = vn = mun and using the highest term of the monic polynomial p, i.e. the one leading near inifnity, we have that p(un ) ≈ ukn and p(vn ) = p(mun ) ≈ (mun )k . So   k un − mun lim sn = lim mun − (mun ) k = lim mun ϕ(m), n→∞ n→∞ un − (mun )k n→∞ DYNAMICS OF THE SECANT METHOD 21 y z [1 : m2 : 0] z=1 [1 : m1 : 0] 1 x [1 : 0 : 0] y z=0 [1 : m3 : 0] x [0 : 1 : 0] (a) The space of all lines through the origin in (b) The space of all lines through the origin R3 . in R2 . Figure 8. A model for the real projective plane RP2 = R2 t `∞ (a). The line of infinity `∞ (b). as desired. We notice that mk−1 − 1 (k − 1)mk−2 k−1 lim ϕ(m) = lim k = lim = , m→1 m→1 m − 1 m→1 kmk−1 k and so the map ϕ has a removable singularity at m = 1. Similarly when m = 1 we can compute directly S(un , un ) using the expression of q(x, x) = p0 (x) from Lemma 2.1 obtaining the same result. To define the map S̃ at the points [1 : 0 : 0] (m = 0) and [0 : 1 : 0] (m = ∞) we simply extend S̃ continuously on `∞ . In particular S̃ 0 : 1 : 0 = 1 : 0 : 0 . In fact if we consider a vertical line x = 0 and we take (0, vn ) with limn→∞ vn = ∞ we obtain     vn vn p(0) (rn , sn ) = vn , vn − p(vn ) = vn , − p(vn ) − p(0) p(vn ) − p(0) and so, sn lim =0 rn n→∞ Thus the image of a vertical line x = 0 is mapped to the horizontal line y = 0 close to infinity showing the compatibility with the definition of the extended map at infinity. Remark 4. We notice that the map S̃ can be considered a “continuous”  extension of the real secant map S. The only discontinuity happens to be at [0 : 1 : 0 , since at this point we     have S̃ 0 : 1 : 0 = 1 : 0 : 0 ∈ `∞ while S (x, α) ≡ (α, α) for all x ∈ R, and for all α such that p (α) = 0. We also remark that the definition of Ŝ and S̃ coincide where defined except precisely at this point. Now we turn to investigate the dynamical system governed by the map mk−1 − 1 ϕ(m) = . mk − 1 22 ANTONIO GARIJO AND XAVIER JARQUE y y=m y y=m τk −1 −1 ηk m ηk m (a) Graphic of ϕ for k even. (b) Graphic of ϕ for k odd. Figure 9. Dynamics of the secant method on the line at infinity `∞ . We split the proof depending on the oddity of k. We proof statement (a) which correspond to the case where k is even and left the proof of statement (b) to the reader since follows similarly. See Figure 9. We assume that k is an even number. Clearly the map ϕ(m) has a unique vertical asymptote at m = −1, and a horizontal asymptote since ϕ(m) → 0± as m → ±∞. Easy computations show −1 ϕ0 (m) = mk−2 ψ(m), (m − 1)2 k  where ψ(m) = mk − [k(m − 1) + 1] . Since k is even, we have sign (ϕ0 (m)) = −sign (ψ). But observe that ψ(m) measures the difference from the graph of the function y = mk and the graph of the function y = k(m − 1) + 1 which is precisely the tangent line to the graph of y = mk at the point m = 1. Hence ψ(m) ≥ 0 for all m ∈ R and ψ(m) = 0 if and only if m = 1. In particular this implies that ϕ is strictly decreasing in its domain of definition. All together prove that ϕ has a unique fixed point τk ∈ (−∞, −1) and, since ϕ(1/2) > 1/2 and ϕ(1) = (k − 1)/k < 1, ϕ has a unique fixed point ηk ∈ (1/2, 1). See Figure 9 (a). We claim that the positive fixed point ηk is locally attracting, that is, |ϕ0 (ηk )| < 1. To see this we notice that ϕ0 (m) after simplification (removing the indetermination at m = 1) also writes as  0 mk−2 mk−2 + 2mk−3 + . . . + (k − 2)m + k − 1 ϕ (m) = − 2 . (mk−1 + mk−2 + . . . + m + 1) Doing some computations we get Pk+1 2k−j + (k − 1)mk−2 0 j=4 (j − 3)m ϕ (m) = − P , ζ(m) + k+1 j=4 (j − 1)m 2k−j + (k − 1)mk−2 where ζ(m) > 0 for all m > 0 (in fact is a polynomial with positive coefficients). Accordingly |ϕ0 (m)| < 1 for all m > 0 since j − 3 < j − 1 and so the positive fixed point ηk of ϕ is locally attracting. DYNAMICS OF THE SECANT METHOD 23 To finish the proof we will see that the fixed point τ := τk < −1 is repelling. Observe that 1 h i 0 k−2 k k−1 k−1 ϕ (m) = 2 (k − 1)m (m − 1) − km (m − 1) (mk − 1)  and since τ is a fixed point of ϕ we conclude that τ k−1 −1 = τ τ k − 1 . So some computations give τ k−2  2  ϕ0 (τ ) = − k(τ − 1) + 1 . τk − 1 Since τ < −1 and k is even it is clear that ϕ0 (τ ) < 0. We claim that ϕ0 (τ ) < −1 and so τ is a repelling fixed point of ϕ. Indeed 1 k −ϕ0 (τ ) > k + − > 1. τ2 τ2 In Table 1 we compute numerically the fixed points of ϕ for several values of k. k attracting fixed point ηk of ϕ repelling fixed point τk of ϕ 2 ≈ 0,61803399 ≈ -1,61803399 3 ≈ 0,75487766 —— 4 ≈ 0,81917251 ≈ -1,38027757 5 ≈ 0,85667488 —— 6 ≈ 0,88127146 ≈ -1,28519903 7 ≈ 0,89865371 —— 8 ≈ 0,91159235 ≈ -1,23205463 9 ≈ 0,92159932 —— ··· ··· ··· 20 ≈ 0.9650705 ≈ -1,1186991 ··· ··· ··· 50 ≈ 0.9860941 ≈ -1.05933705 Table 1. Fixed points of the map S̃ on `∞ . Finally we prove that S̃ n (x) → ηk as n → ∞, for all x ∈ R ∪ {∞} such that x 6= τk . By the graphical analysis of ϕ, see Figure 9 (a), we conclude that for x > −1 we have that S̃ n (x) → ηk as n → ∞, in fact any point x0 ∈ (−1, ηk ) “jumps” to the interval (ηk , +∞) and viceversa forming two monotone sequence of iterates {S̃ 2m (x0 )}m≥0 and {S̃ 2m+1 (x0 )}m≥0 both tending to x0 , the first one strictly increasing and the second one strictly decreasing. The point corresponding to m = ∞ is mapped by S̃ to the corresponding point with m = 0 and hence tending to ηk , the same happens with m = −1 since ϕ(−1) = ∞. Now let w1 the unique premiere of −1 under S̃, then all x ∈ (−∞, w1 ] are mapped into the interval [−1, 0) and then attracted by ηk . Arguing similarly we denote by w2 the unique preimage of w1 in the interval (τk , −1), then all point in the interval [w2 , −1) “jumps” to the interval (−∞, w1 ] and then converge to ηk . Taking inductively preimages of w0 s we conclude that all points in R ∪ {∞} converge toward ηk under S̃ except the repelling fixed point τk . 24 ANTONIO GARIJO AND XAVIER JARQUE 5. Conclusions In this paper we give a global description of the possible dynamical behaviours that might occur in the dynamical plane of the secant method S applied to real polynomials with simple roots. To do so we have extended in a natural way the secant map to infinity and we have used these further information to have a better understanding of the global dynamics of S as a plane map. On the one hand we have shown from the extension of S to a map Ŝ on a torus allows us to prove the existence of virtual period three cycles, that is, regions of the dynamical plane where orbits follows a periodic three cycle formed by one point in R and two points at infinity. So, the wrong seeds not converging to the roots of the polynomial not only belong to attracting basins of higher period cycles not related with the zeros of the polynomial (Theorem B) but they also belong to regions where points use infinity (Theorem C). On the other hand we also consider the extension of S to the circle at infinity `∞ ⊂ RP2 and show how its dynamical behaviour only depends of the parity of k, the degree of the polynomial p. The basins of attraction of the roots of a polynomial p extend to infinity in the direction of the horizontal lines y = α where α is a root of p. This horizontal lines correspond to the point [1 : 0 : 0], or m = 0 in the homogeneous coordinates, at the line of infinity. When k is odd there exist two preimage of m = 0 under the dynamics induced by the secant map at `∞ which are m = ∞ and m = −1. So, in the dynamical plane of the secant map Sp where p is a polynomial of degree odd we can see preimages of the basins of attraction at the direction of the lines y = −x and the vertical line y = 0. Moreover, when k is even the unique preimage of m = 0 is m = ∞. In Figure 10(a) we have drawn the dynamical plane of the polynomial p(x) = x(x − 1)(x − 2)(x − 3) while in Figure 10(b) we have drawn the dynamical plane of the polynomial p(x) = x(x − 1)(x − 2). In particular we deduce that if p is a degree k polynomial having at least one root, initial conditions on the line y = τk x (for x large enough in absolute value) S-converge with high speed to the greatest and smallest root of p. During all the present work we have assumed that the roots of the polynomial p are simple. Many of the results can be done also for the case of multiple roots. However at a multiple root of the polynomial different phenomena occurs at the same point. Let β be a multiple rootof p then, on the one hand, the point (β, β) is not a fixed point of Sp , in fact it is worst since the map Sp is not defined in R2 at this point! and, on the other hand, now the point (β, β) exhibits a period three cycle since p0 (β) = 0. References [ABFsP17] Leandro Arosio, Anna Miriam Benini, John Erik Fornæ ss, and Han Peters. Dynamics of transcen- dental Hénon maps. preprint, 2017. [BD05] Eric Bedford and Jeffrey Diller. Real and complex dynamics of a family of birational maps of the plane: the golden mean subshift. Amer. J. Math., 127(3):595–646, 2005. [Bed03] Eric Bedford. On the dynamics of birational mappings of the plane. J. Korean Math. Soc., 40(3):373–390, 2003. [BFJK14] Krzysztof Barański, Núria Fagella, Xavier Jarque, and Boguslawa Karpińska. On the connectivity of the Julia sets of meromorphic functions. Invent. Math., 198(3):591–636, 2014. [BFJK15] Krzysztof Barański, Núria Fagella, Xavier Jarque, and Boguslawa Karpińska. Connectivity of julia sets of newton maps: A unified approach. to appear Revista Iberoamericana, 01 2015. [BGM99] Gian-Italo Bischi, Laura Gardini, and Christian Mira. Plane maps with denominator. I. Some generic properties. Internat. J. Bifur. Chaos Appl. Sci. Engrg., 9(1):119–153, 1999. DYNAMICS OF THE SECANT METHOD 25 (a) Dynamical plane of Sp with deg(p) odd. (b) Dynamical plane of Sp with deg(p) even. Figure 10. We have proven that the line y = αj (m = 0) belong to the basin of attraction of the fixed point (αj , αj ), j = 1, . . . n. This explains the horizontal colors associated to the different basins of attraction. Moreover since x = αj (m = ∞) is a preimage of y = αj we also have those colors at the y-axis. For polynomials of odd degree (figure (b)) since m = 0 has m = −1 as a (further) finite ϕ-preimage, we see near infinity, copies of the basins of attraction drawn with colors. The range of the pictures is [−25, 25] × [−25, 25]. [BGM03] Gian-Italo Bischi, Laura Gardini, and Christian Mira. Plane maps with denominator. II. Noninvert- ible maps with simple focal points. Internat. J. Bifur. Chaos Appl. Sci. Engrg., 13(8):2253–2277, 2003. [BGM05] Gian-Italo Bischi, Laura Gardini, and Christian Mira. Plane maps with denominator. III. Nonsim- ple focal points and related bifurcations. Internat. J. Bifur. Chaos Appl. Sci. Engrg., 15(2):451–496, 2005. [BS91a] Eric Bedford and John Smillie. Polynomial diffeomorphisms of C2 : currents, equilibrium measure and hyperbolicity. Invent. Math., 103(1):69–99, 1991. [BS91b] Eric Bedford and John Smillie. Polynomial diffeomorphisms of C2 . II. Stable manifolds and recur- rence. J. Amer. Math. Soc., 4(4):657–679, 1991. [BS92] Eric Bedford and John Smillie. Polynomial diffeomorphisms of C2 . III. Ergodicity, exponents and entropy of the equilibrium measure. Math. Ann., 294(3):395–420, 1992. [BS06] Eric Bedford and John Smillie. The Hénon family: the complex horseshoe locus and real parameter space. In Complex dynamics, volume 396 of Contemp. Math., pages 21–36. Amer. Math. Soc., Providence, RI, 2006. [Cay79a] Arthur Cayley. Applications of the Newton-Fourier Method to an imaginary root of an equation. Quat. J. of Pure and App. Math., 16:179–185, 1879. [Cay79b] Arthur Cayley. The Newton-Fourier Method imaginary problem. Am. J. of Math., 2:97, 1879. [Cay80] Arthur Cayley. On the Newton-Fourier imaginary problem. Proc. Camb. Phil. Soc., 3:231–232, 1880. [CMn11] Anna Cima and Francesc Mañosas. Real dynamics of integrable birational maps. Qual. Theory Dyn. Syst., 10(2):247–275, 2011. [CZ14] Anna Cima and Sundus Zafar. Integrability and algebraic entropy of k-periodic non-autonomous Lyness recurrences. J. Math. Anal. Appl., 413(1):20–34, 2014. 26 ANTONIO GARIJO AND XAVIER JARQUE [DL15] Romain Dujardin and Mikhail Lyubich. Stability and bifurcations for dissipative polynomial au- tomorphisms of C2 . Invent. Math., 200(2):439–511, 2015. [Duj04] Romain Dujardin. Hénon-like mappings in C2 . Amer. J. Math., 126(2):439–472, 2004. [FsS92] John Erik Fornæ ss and Nessim Sibony. Complex Hénon mappings in C2 and Fatou-Bieberbach domains. Duke Math. J., 65(2):345–380, 1992. [HOV94] John H. Hubbard and Ralph W. Oberste-Vorth. Hénon mappings in the complex domain. I. The global topology of dynamical space. Inst. Hautes Études Sci. Publ. Math., (79):5–46, 1994. [HOV95] John H. Hubbard and Ralph W. Oberste-Vorth. Hénon mappings in the complex domain. II. Projective and inductive limits of polynomials. In Real and complex dynamical systems (Hillerød, 1993), volume 464 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 89–132. Kluwer Acad. Publ., Dordrecht, 1995. [HPV00] John Hubbard, Peter Papadopol, and Vladimir Veselov. A compactification of Hénon mappings in C2 as dynamical systems. Acta Math., 184(2):203–270, 2000. [HSS01] John Hubbard, Dierk Schleicher, and Scott Sutherland. How to find all roots of complex polyno- mials by Newton’s method. Invent. Math., 146(1):1–33, 2001. [McM87] Curt McMullen. Families of rational maps and iterative root-finding algorithms. Ann. of Math. (2), 125(3):467–493, 1987. [Prz89] Feliks Przytycki. Remarks on the simple connectedness of basins of sinks for iterations of rational maps. In Dynamical systems and ergodic theory (Warsaw, 1986), volume 23 of Banach Center Publ., pages 229–235. PWN, Warsaw, 1989. [Shi09] Mitsuhiro Shishikura. The connectivity of the Julia set and fixed points. In Complex dynamics, pages 257–276. A K Peters, Wellesley, MA, 2009. Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Catalonia. E-mail address: antonio.garijo@urv.cat Departament de Matemàtiques i Informàtica at Universitat de Barelona and Barcelona Graduate School of Mathematics, 08007 Barcelona, Catalonia. E-mail address: xavier.jarque@ub.edu