# On the Dynamics of Laguerre’s Iteration Method for Finding thenth Roots of Unity

Authors: Pavel Bělík; HeeChan Kang; Andrew Walsh; Emma Winegar
Journal: International Journal of Computational Mathematics
 (2014)

---

## Abstract

Previous analyses of Laguerre’s iteration method have provided results on the behavior of this popular method when applied to the polynomialspn(z)=zn-1, n∈N. In this paper, we summarize known analytical results and provide new results. In particular, we study symmetry properties of the Laguerre iteration function and clarify the dynamics of the method. We show analytically and demonstrate computationally that for each n≥5 the basin of attraction to the roots is a subset of an annulus that contains the unit circle and whose Lebesgue measure shrinks to zero as n→∞. We obtain a good estimate of the size of the bounding annulus. We show that the boundary of the basin of convergence exhibits fractal nature and quasi self-similarity. We also discuss the connectedness of the basin for large values of n. We also numerically find some short finite cycles on the boundary of the basin of convergence for n=5,...,8. Finally, we demonstrate that when using the floating point arithmetic and the general formulation of the method, convergence occurs even from starting values outside of the basin of convergence due to the loss of significance during the evaluation of the iteration function.


---

## Body

## 1. Introduction

Laguerre’s iteration method (also referred to as Laguerre’s method in this paper) for approximating roots of polynomials [1] is one of the least understood methods of numerical analysis. It exhibits cubic convergence to simple roots of (complex) polynomials and linear convergence to multiple roots, thus outperforming the well-known Newton’s method that exhibits quadratic convergence to simple roots [2] or even the widely used and globally convergent Jenkins-Traub method, which has the order of convergence of (at least) 1+ϕ, where ϕ=(1+5)/2 is the golden ratio [3, 4]. Although Laguerre’s method is implemented inNumerical Recipes [5], it is often overlooked in designing professional software. This is, perhaps, due to the lack of complete analytical understanding of the method. However, some of the known results make it an excellent candidate in many situations. For example, it is known that the method exhibits global convergence (convergence from any initial guess) for real polynomials with real roots [3, 6]. It also allows for automatic switching to the complex domain if there are no real roots; this is due to the appearance of a square root in the definition of the method (see (2) in the next section). In general, although convergence is not guaranteed for all complex starting values, the method seems to perform very well in many cases [2].It is the goal of this paper to provide additional insights into the performance of Laguerre’s method when applied to simple polynomials of the formzn-1. We primarily follow the work of Ray [7] and Curry and Fiedler [8] but provide additional details and clear proofs of all results. In addition, we provide computational results that demonstrate the poor performance of the method when n is large and exact arithmetic is used. This is due to the fact that the basin of convergence to the roots is contained in an annulus that shrinks towards the unit circle S1 as n increases. Points in the complement of the annulus converge to the two-cycle {0,∞}. We also show that the boundary of the basin of convergence has fractal characteristics and becomes quite interesting for large n. Finally, we present some examples to demonstrate that in the floating-point arithmetic the method in its general formulation (2) eventually converges from seemingly any initial complex value due to the loss of significance. This thus ironically contributes to the practicality of the method in this case, and it remains to be seen whether this is also the case for general polynomials.We organize the paper similarly as in [8]. In Section 2, we introduce the method, briefly summarize known results, and provide a simpler expression for the method when applied to the polynomials pn(z)=zn-1. In Section 3, we formulate and prove three propositions regarding the symmetry properties of the iteration function for pn that simplify the analysis in the following sections. Sets in the complex plane that will play a significant role in the study of the dynamics are defined in Section 4, and their algebraic characterization is provided in the same section. The dynamics of the method on the unit circle and in the neighborhood of the two-cycle {0,∞} is studied in Sections 5.1 and 5.2, respectively. In Section 5.3 we provide proofs of convergence to the roots of unity when the initial guess is in a relevant annulus containing the unit circle. The boundary of the basin of convergence is contained in two annuli shown as the “gray areas” in Figure 1, and some relevant numerical results pertinent to the boundary are shown in Section 6. We conclude with Section 7, in which we summarize some of the open questions, and demonstrate the “convergence” of the method even from the basins of attraction of the two-cycle {0,∞}.Figure 1
Sets of significance forn=16. The thick solid curves are ∂D, S1, and ∂E, and they divide C∖{0} into the regions D, K0, K1, and E. The dots indicate the positions of the roots, the thick dashed lines are Θ1, and the thin dotted lines are Θ0. The gray annuli are discussed in Remark 5.


## 2. Laguerre’s Iteration Method

In this section, we provide the basic details of Laguerre’s method, mention known results, and apply the method to the polynomialspn(z)=zn-1 with n≥2 and z∈C. We will denote by z1/2 the set of the two solutions {w,-w}⊂C such that w2=z (unless, of course, z=0, in which case w=0). We will use the notation z for the principal square root of z; that is, if z=reiθ with r>0 and -π<θ≤π, then z=reiθ/2 is the principal value for the square root with argument in the interval (-π/2,π/2].Laguerre’s iteration method for complex polynomials p(z) of degree n≥2 is defined as [1, 3]
(1)zk+1=Lzkz0∈Cgiven,
where L(z) denotes theLaguerre iteration function [9] given by
(2)Lz=z-npzp′z±n-12p′z2-nn-1pzp′′z=z-nGz±n-1nHz-G2z,
where
(3)Gz=p′zpz,Hz=G2z-p′′zpz,
and where the signs are chosen so as to maximize the modulus of the denominators.


### 2.1. Known Results

It is known that Laguerre’s method exhibits cubic convergence to a simple root and linear convergence to a multiple root [2, 3]. It is also known that for a real polynomial with real roots, the method converges to a root from any initial guess z0∈R [3]. A particular feature of interest is that even if the initial guess is a real number, convergence to a complex root can occur due to the square root in the denominator of (2). In many cases, the method seems to converge to a root from any initial guess in the complex plane, although this is not the case in general [7]. For example, consider the polynomial pn(z)=zn-1 with n≥3, for which both the first and the second derivative vanish at z=0, and L(0) is undefined (in what follows, we will consider the extended complex plane C^=C∪{∞} so that L(0)=∞ and L(∞)=0, and {0,∞} forms a two-cycle of the method). It is also known [10] that if p(z) is a polynomial of degree n and z∈C, then there exists a root z* of p such that |z-z*|≤n|z-L(z)|.The Laguerre iteration function (2) is sometimes claimed to be invariant under Möbius transformations [2, 11], although the correct, weaker statement is given and proved in [7]. For the classes of quadratics and cubics of the form pc(z)=z2+c and pλ(z)=(z-1)(z2+z+λ), respectively, with c,λ∈C, the Laguerre iteration function (2) can be shown to not have any free critical points [11], and a generalization to all complex quadratics and cubics is suggested based on the invariance under Möbius transformations.


### 2.2.  Roots of Unity

When applied to the polynomialpn(z)=zn-1, n≥2, the Laguerre iteration function (2) for z≠0 simplifies to
(4)Lz=zz-n/2±n-1zn/2±n-1,
where again the sign is chosen to maximize the modulus of the denominator. Using the principal square root of zn, which will result in an expression with a nonnegative real part, we can rewrite L(z) as Lp(z) given by
(5)Lpz=z1/zn+n-1zn+n-1.We note that the roots ofpn are exactly the fixed points of Lp, and it is easy to check that the derivative of Lp vanishes at the roots, so they are attracting fixed points, and each has an open neighborhood contained in its immediate basin of attraction.It is straightforward to check that in the casen=2 the method converges in one iteration for any initial guess z0∈C. If Re(z0)>0, or if Re(z0)=0 and Im⁡(z0)≥0, then Lp(z0)=1; otherwise Lp(z0)=-1.In the cases withn≥3, the method has a two-cycle consisting of 0 and ∞ in the extended complex plane C^. Other than this two-cycle, the method is globally convergent for n=3,4 [7, 8].The behavior of Laguerre’s method is quite different in the cases withn≥5 and is the subject of our interest. In the following sections, we closely follow the analysis of Curry and Fiedler [8], which in turn is based on the work of Ray [7]. We provide additional insights and graphical illustrations for some of the results. While the main focus will be on the cases with n≥5, if a result applies more generally, we will state so.For future reference, we note that forr>0, we have [8]
(6)Lpreiθ2=1rn-21+n-12rn+2n-1cos⁡nθ/2rn/2rn+n-12+2n-1cos⁡nθ/2rn/2.


## 2.1. Known Results

It is known that Laguerre’s method exhibits cubic convergence to a simple root and linear convergence to a multiple root [2, 3]. It is also known that for a real polynomial with real roots, the method converges to a root from any initial guess z0∈R [3]. A particular feature of interest is that even if the initial guess is a real number, convergence to a complex root can occur due to the square root in the denominator of (2). In many cases, the method seems to converge to a root from any initial guess in the complex plane, although this is not the case in general [7]. For example, consider the polynomial pn(z)=zn-1 with n≥3, for which both the first and the second derivative vanish at z=0, and L(0) is undefined (in what follows, we will consider the extended complex plane C^=C∪{∞} so that L(0)=∞ and L(∞)=0, and {0,∞} forms a two-cycle of the method). It is also known [10] that if p(z) is a polynomial of degree n and z∈C, then there exists a root z* of p such that |z-z*|≤n|z-L(z)|.The Laguerre iteration function (2) is sometimes claimed to be invariant under Möbius transformations [2, 11], although the correct, weaker statement is given and proved in [7]. For the classes of quadratics and cubics of the form pc(z)=z2+c and pλ(z)=(z-1)(z2+z+λ), respectively, with c,λ∈C, the Laguerre iteration function (2) can be shown to not have any free critical points [11], and a generalization to all complex quadratics and cubics is suggested based on the invariance under Möbius transformations.


## 2.2.  Roots of Unity

When applied to the polynomialpn(z)=zn-1, n≥2, the Laguerre iteration function (2) for z≠0 simplifies to
(4)Lz=zz-n/2±n-1zn/2±n-1,
where again the sign is chosen to maximize the modulus of the denominator. Using the principal square root of zn, which will result in an expression with a nonnegative real part, we can rewrite L(z) as Lp(z) given by
(5)Lpz=z1/zn+n-1zn+n-1.We note that the roots ofpn are exactly the fixed points of Lp, and it is easy to check that the derivative of Lp vanishes at the roots, so they are attracting fixed points, and each has an open neighborhood contained in its immediate basin of attraction.It is straightforward to check that in the casen=2 the method converges in one iteration for any initial guess z0∈C. If Re(z0)>0, or if Re(z0)=0 and Im⁡(z0)≥0, then Lp(z0)=1; otherwise Lp(z0)=-1.In the cases withn≥3, the method has a two-cycle consisting of 0 and ∞ in the extended complex plane C^. Other than this two-cycle, the method is globally convergent for n=3,4 [7, 8].The behavior of Laguerre’s method is quite different in the cases withn≥5 and is the subject of our interest. In the following sections, we closely follow the analysis of Curry and Fiedler [8], which in turn is based on the work of Ray [7]. We provide additional insights and graphical illustrations for some of the results. While the main focus will be on the cases with n≥5, if a result applies more generally, we will state so.For future reference, we note that forr>0, we have [8]
(6)Lpreiθ2=1rn-21+n-12rn+2n-1cos⁡nθ/2rn/2rn+n-12+2n-1cos⁡nθ/2rn/2.


## 3. Symmetry Properties of the Laguerre Iteration Function

When applied to the polynomialspn(z)=zn-1, n≥2, the Laguerre iteration function (5) has several symmetry properties that simplify the analysis of the method in the extended complex plane C^. In particular, the function possesses an n-fold rotational symmetry around the origin, a symmetry with respect to the real axis, and also an inversion symmetry with respect to the unit circle. In Propositions 1–3 we provide the precise statements.We will use the slightly imprecise notation of [8] and denote by θ0 and θ1 any of the following angles for k=0,…,n-1:
(7)θ0=2kπn,θ1=2k+1πn.
In addition, we define the rays
(8)Θ0=reiθ0∈C:r>0,Θ1=reiθ1∈C:r>0.
Note that the roots of pn lie on the rays Θ0, while the rays Θ1 divide the complex plane into n congruent sectors bisected by the rays Θ0.The following proposition implies that it suffices to study the behavior ofLp in the sector {z∈C:-π/n<argz≤π/n}, that is, between two consecutive rays Θ1, and the rest follows by rotational symmetry. This is a special case of the invariance of the method with respect to certain Möbius transformations [2, 7].Proposition 1.
Forn≥2, the Laguerre iteration function Lp defined in (5) commutes with the rotation by an angle α=2π/n about the origin.Proof.
LetTα denote the rotation by an angle α=2π/n about the origin; that is, Tα(z)=eiαz. Since Tα(z)n=zn, substituting into (5), we get for any z∈C^(9)LpTαz=eiαz1/zn+n-1zn+n-1=eiαLpz=TαLpz,
and the result follows.The following proposition implies that the behavior ofLp in the sector {z∈C:-π/n<argz<π/n} is symmetric with respect to the real axis. In the case when arg(z)=θ1, Proposition 1 applies.Proposition 2.
Forn≥2 and z∈C with argz≠θ1, the Laguerre iteration function Lp defined in (5) commutes with the complex conjugation z↦z¯.Proof.
Ifargz≠θ1, then (z¯)n=zn¯. Consequently, Lp(z¯)=Lp(z)¯, and the result follows.Finally, the Laguerre iteration function (5) also exhibits inversion symmetry with respect to the unit circle as shown in the next proposition.Proposition 3.
Forn≥2, the Laguerre iteration function Lp defined in (5) commutes with the inversion with respect to the unit circle S1={z∈C:|z|=1}; that is, Lp1/z¯=1/Lp(z)¯.Proof.
Consider firstz∈C with argz≠θ1. Using the same conjugation properties as in the proof of Proposition 2, we have
(10)Lp1z¯=1z¯1/1/z¯n+n-11/z¯n+n-1=1Lpz¯=1Lpz¯.
We can then check by direct substitution that the same result holds also when arg(z)=θ1, and the conclusion of the proposition follows.In summary, it is enough to study the behavior of the method in the set{reiθ:0≤r≤1,0≤θ≤π/n}, since the rest follows by the symmetries above.


## 4. Significant Sets in the Complex Plane

Consider from now on the polynomialpn(z)=zn-1 with n≥5 and the corresponding Laguerre iteration function Lp given by (5). Following [8], we start by defining several sets in the extended complex plane C^ relevant to the study of the dynamics of Laguerre’s method. We will provide relevant results, some of which are proved in [8].It is stated in [8] that the sets in (11) below “contain all the dynamics” of (5). This is not quite true, as will be shown in Section 6, although these sets are of significance in the analysis. They divide C∖{0} into disjoint subsets and are defined as
(11)D=z∈C:0<z<1,Lpz>1z,∂D=z∈C:0<z<1,Lpz=1z,K0=z∈C:0<z<1,Lpz<1z,S1=z∈C:z=1,K1=z∈C:z>1,Lpz>1z,∂E=z∈C:z>1,Lpz=1z,E=z∈C:z>1,Lpz<1z.
Note that, due to the use of the principal square root in (5), Lp is continuous everywhere in C∖{0} except across the rays Θ1; however, |Lp| is continuous across Θ1, so the notations ∂D and ∂E are justified, since ∂D and ∂E are the boundaries of D and E, respectively, in C∖{0}. For future reference we note that Lp is “counter-clockwise” continuous across the rays Θ1. That is, if z→reiθ1 with argz<θ1, then Lp(z)→Lp(reiθ1). This is not the case in the “clockwise” direction.As in [7, 8], we next focus on the algebraic characterization of ∂D and ∂E. This will lead to a definition and study of a “characteristic function” (14) below that will allow us to determine the shapes of the boundary curves as shown in Figure 1. The figure provides an illustration of the sets in (8) and (11) for n=16; the cases with other values of n are similar. In the figure, the three thick solid curves correspond to the solutions of (13) below and are, in the order of increasing distance from the origin, ∂D, S1, and ∂E. They divide C∖{0} into four regions: D, K0, K1, and E (innermost to outermost). The dots indicate the positions of the roots of pn. The thick dashed lines are the rays Θ1, while the thin dotted lines are the rays Θ0. The thin dashed circles have radii s0<r0<1/r0<1/s0 as defined in (18) in Remark 5 below.Writingz=reiθ, 0<r<∞, we note that both ∂D and ∂E are characterized by the same equation:
(12)Lpz=1zorLpreiθ=1r.
Using (6), (12) is equivalent to [7, 8]
(13)fnr,θ=0,
where the “characteristic function” fn is defined as
(14)fnr,θ=r2n-4+2n-1cos⁡nθ2rn/2rn-4-1-n-12rn+n-12rn-4-1.We summarize relevant results (some stated in [8]) in the following theorem.Theorem 4.
Letn≥5, z=reiθ with 0<r<∞, and let fn(r,θ) be defined as in (14). One then has the following.(1)
For everyθ∈R, (13) has exactly three positive zeroes, rD, 1, and rE, such that rD<1<rE=1/rD. In addition, rE<n-12/(n-4), so the zeroes converge to 1 as n→∞.(2)
Each of the sets in (11) corresponds to a particular sign of fn:
(15)fnr,θ=0⟺Lpz=1z⟺z∈∂D∪S1∪∂E,fnr,θ<0⟺Lpz>1z⟺z∈D∪K1,fnr,θ>0⟺Lpz<1z⟺z∈K0∪E.(3)
The boundaries∂D and ∂E correspond to polar curves of the form r=rD(θ) and r=rE(θ). The function rD(θ) is maximized at any θ=θ0 and minimized at any θ=θ1, while the function rE(θ) is minimized at any θ=θ0 and maximized at any θ=θ1. In addition, both rD(θ) and rE(θ) are monotonic between any two consecutive angles θ0 and θ1 (see Figure 1).Proof.
(1) Letn≥5, θ∈R, and define f(r)=fn(r,θ). Note that f is a differentiable function and
(16)f0=-1,f1=0,lim⁡r→+∞fr=+∞,f′1<0.
It is easy to show that f′(1)≤-2n2. This implies that f has at least three positive zeroes. From (12) and Proposition 3 it follows that, other than 1, the zeroes of f come in reciprocal pairs, so the actual number of zeroes is an odd number greater than or equal to 3. As in [7, 8], we will invoke Descartes’ rule of signs. When n is even, f is a polynomial, so the rule can be applied directly. When n is odd, we can apply it to g(r)=f(r2), which is a polynomial that also satisfies (16) with f(r) replaced by g(r). Hence, we focus on f with the understanding that g is handled exactly the same way. Note that f can be expanded to contain at most 6 terms with different powers of r; hence, there are at most 5 sign changes, and f has at most 5 positive zeroes. From (16) it now follows that if f had 5 zeroes, two of them would have to have multiplicity greater than 1 and f′ would have to have at least 6 positive zeroes (4 between the zeroes of f and at least 2 more from the multiple roots of f). This is, however, impossible, since f′ is another polynomial with at most 5 terms of different powers of r; hence Descartes’ rule of signs implies that f′ has at most 4 positive zeroes. Consequently, f has exactly 3 simple positive zeroes as stated in the theorem.
Finally, a straightforward computation with(n-1)2/(n-4)>1 shows that
(17)fn-12/(n-4)=n-14-1+2nn-2×n-1(2n-4)/(n-4)cos⁡nθ2>0,
so, since f is negative for 1<r<rE and positive for r>rE, we have that (n-1)2/(n-4)>rE. Application of L’Hôpital’s rule shows that (n-1)2/(n-4)→1 as n→∞.
(2) This part follows from the definition of the relevant sets in (11) and from replacing the equality in (12) by inequalities, which results in inequalities in (13) [8].
(3) Since for everyθ∈R there are unique values of rD and rE, we can think of ∂D and ∂E as polar curves. To prove all of the remaining statements in this part, it is enough to consider rE(θ) for 0≤θ≤π/n, since the rest follows by the symmetries discussed earlier. Note that the cosine term in (14) is the largest for θ=0, so on the circle r=rE(0)>1, as a function of θ, fn(rE(0),θ) is the largest (and equal to 0) exactly when θ=θ0. Thus, fn is negative on the circle for every θ≠θ0, and it follows that rE(θ)≥rE(θ0) for all θ∈R. Similarly, the cosine term is the smallest when θ=π/n, and by a similar argument we get rE(θ)≤rE(θ1) for all θ∈R. Finally, to prove the last assertion, we implicitly differentiate (13) with respect to θ and observe that drE/dθ=-(∂fn/∂θ)/(∂fn/∂r) vanishes only when θ=θ0 and does not exist only when θ=θ1, since the numerator contains a factor sin(nθ/2) and the denominator is positive on rE(θ) as the proof of part (1) implies. This concludes the proof of the theorem.Remark 5.
As in [8], we define the values 0<s0<r0<1 by
(18)s0=rDθ1=min⁡0≤θ<2πrDθ,r0=rDθ0=max⁡0≤θ<2πrDθ.
The four circles with radii s0<r0<1/r0<1/s0 are shown in Figure 1 as dashed circles, and the annuli {s0<r<r0} and {1/r0<r<1/s0} are shaded gray.


## 5. Dynamics of the Laguerre Iteration Function

### 5.1. Dynamics on the Unit Circle

In this section, we study the dynamics on the unit circle,S1. As a consequence of Theorem 4, part (1), we have that the unit circle, S1, is invariant under the Laguerre iteration function (see also [8]). This follows from (13) and (12) with r=1. However, more can be said about the behavior of Lp on S1.Proposition 6.
Letn≥5. If z0∈S1∖Θ1, then the sequence of iterates of Laguerre’s method, {Lpk(z0)}, converges monotonically to the nearest root of pn(z)=zn-1 in the sense that |Lpk(z0)|=1 and the arguments of Lpk(z0) monotonically approach the argument of the nearest root as k→∞. If z0∈S1∩Θ1, then the iterates converge monotonically to the nearest root of pn in the clockwise direction.Proof.
Due to the symmetry properties ofLp (Propositions 1 and 2), it is enough to assume z=eiθ with 0<θ≤π/n and show that Lp(z)=eiθ~ with 0<θ~<θ. Since the sequence of arguments generated by the method will then be a decreasing sequence bounded below by 0, it will converge, and the corresponding sequence of points on S1 will converge to a fixed point of Lp, that is, to a root of pn by the continuity of Lp away from Θ1. The limiting root will have to be 1 and both assertions of the proposition will follow.
To prove that0<θ~<θ, we first note that
(19)Lpz=eiθe-inθ/2+n-1einθ/2+n-1,
where the numerator and the denominator are conjugates of each other and nθ/2≤π/2. Thus the whole fraction results in an expression of the form e-2iθ^ with 0<θ^<π/2, where
(20)θ^=argeinθ/2+n-1=arctansinnθ/2cos⁡nθ/2+n-1.
Consequently, Lp(z)=ei(θ-2θ^) and it remains to show that θ-2θ^>0. Consider the function
(21)gθ=θ-2θ^=θ-2arctansinnθ/2cos⁡nθ/2+n-1,0≤θ≤πn.
One can verify that g(0)=0 and since
(22)g′θ=2n-1n-2sin2nθ/4cos⁡nθ/2+n-12+sin2nθ/2>0,
we conclude that g(θ)>0 for 0<θ≤π/n.


### 5.2.  Dynamics of the Two-Cycle{0,∞}

As we mentioned earlier, the Laguerre iteration function (5) has a two-cycle {0,∞} for n≥3. We now show that this two-cycle is attracting for n≥5 and its basin of attraction contains a significant portion of D∪E. We will demonstrate later in Section 6 that the basin of attraction can be quite complicated and appears to have a fractal boundary. For the rest of Section 5 we assume n≥5.The following proposition appears in [8]. It shows that the innermost and the outermost white regions in Figure 1 belong to the basin of attraction of the two-cycle. We provide our own proof for the second part of the proposition, as the original proof in [8] appears to assume the continuity of the Laguerre iteration function Lp throughout the complex plane.Proposition 7.
Lets0 be as defined in (18). Let Ds0={z∈C∖{0}:|z|<s0} and Es0={z∈C:|z|>1/s0}. Then Lp(Ds0)⊂Es0 and Lp(Es0)⊂Ds0. Moreover, Ds0∪Es0 is contained in the basin of attraction of the two-cycle {0,∞}.Proof.
The proof of the first part follows that of [8]. Note first that Theorem 4 implies that Ds0⊂D and Es0⊂E. Hence, if z∈Ds0, then |Lp(z)|>1/|z|>1/s0 and Lp(z)∈Es0. Similarly, if z∈Es0, then |Lp(z)|<1/|z|<s0 and Lp(z)∈Ds0.
To prove the second part, it is enough to show that the basin of attraction of the two-cycle{0,∞} contains Ds0. It follows from the previous part that if z∈Ds0, then |Lp(z)|>1/|z| and |Lp2(z)|<1/|Lp(z)|, and, consequently, |Lp2(z)|<|z|. Similarly, if z∈Es0, we have |Lp2(z)|>|z|. We will show that for z∈Ds0 the even terms of the sequence {Lpk(z)} converge to 0 and the odd ones to ∞. To this end, we observe that {|Lp2k(z)|} is a decreasing, bounded, and therefore convergent sequence. If its limit is 0, we are done, since |Lp2k(z)|→0 and |Lp2k+1(z)|>1/|Lp2k(z)|→∞ as k→∞.
Assume now thatlim⁡k→∞⁡|Lp2k(z)|=b>0 and, using the Bolzano-Weierstrass theorem, consider a convergent subsequence of {Lp2nk(z)} and its limit, say, z~∈Ds0. We then have that if z~ is not in Θ1, or if z~∈Θ1 and {Lp2nk(z)} approaches it counter-clockwise, then, by the continuity of Lp and |Lp|, we have b=lim⁡k→∞⁡|Lp2(Lp2nk(z))|=|Lp2(z~)|<|z~|=b, a contradiction. The only remaining possibility is that z~∈Θ1 and it is not possible to extract a subsequence approaching it counter-clockwise. In that case z~ is (eventually) approached clockwise, and we can consider a sequence symmetric via a reflection through Θ1 (Propositions 1 and 2). We then obtain a contradiction for this new sequence as in the previous case.Remark 8.
The regionsDs0 and Es0 defined in Proposition 7 can be seen in Figure 1: Ds0 is the open ball not containing 0 bounded by the smaller gray annulus, while Es0 is the region on the outside of the larger gray annulus.Although the basin of attraction of the two-cycle{0,∞} is significantly larger than Ds0∪Es0 (see Section 6), we can immediately extend it in the following sense.Corollary 9.
The sets{|z|=s0}∩D and {|z|=1/s0}∩E are contained in the basin of attraction of the two-cycle {0,∞}.Proof.
From the definitions ofD and E in (11) it is clear that any point in {|z|=s0}∩D or {|z|=1/s0}∩E gets mapped into Ds0∪Es0, and the claim follows.We believe that the pointss0eiθ1 and (1/s0)eiθ1 also converge to the {0,∞} two-cycle. Since these points belong to the set ∂D∪∂E, their images under the Laguerre iteration map (5) lie on the circles with radii 1/s0 and s0, respectively, so it suffices to show that their arguments are different from θ1. We have not been able to find a simple proof for this statement.


### 5.3.  Dynamics of the Basins of Convergence

In Proposition10 we state a result [8] that shows that the open annulus bounded by the gray annuli in Figure 1 belongs to the basin of attraction of the roots of pn(z)=zn-1. Again, it turns out that the basin is actually larger than the annulus (see Section 6). We provide an elementary proof of the final statement of Proposition 10, since in the proof in [8] a reference is made to [6], which does not appear relevant to the proof.Proposition 10.
Letr0 be defined as in (18). Let K^0={z∈C:r0<|z|<1}⊂K0 and K^1={z∈C:1<|z|<1/r0}⊂K1. Then Lp(K^0∪K^1∪S1)⊂K^0∪K^1∪S1, and the sequence {Lpk(z)} with z∈K^0∪K^1∪S1 converges to a root of pn(z)=zn-1.Proof.
We provide a proof along the lines of [8]. First, if z=reiθ∈K^0⊂K0, then |Lp(z)|<1/r<1/r0 from the definition of K0. Using (6) and r<1, we obtain |Lp(z)|>r>r0 (see [8] for details), so we can conclude that Lp(z)∈K^0∪K^1. In exactly the same fashion, for z=reiθ∈K^1 we obtain r0<1/r<|Lp(z)|<r<1/r0, and, again, Lp(z)∈K^0∪K^1. In view of Proposition 6, we can conclude that Lp(z)∈K^0∪K^1∪S1 for any z∈K^0∪K^1∪S1.
We know from Proposition6 that if z∈S1, then {Lpk(z)} converges to a root of pn. It follows from the above inequalities that for z∈K^0∪K^1 we have
(23)min⁡z,1z<Lpz<max⁡z,1z,min⁡z,1z<1Lpz<max⁡z,1z,
and, consequently, the sequence Lpkz-1/Lpkz is decreasing and convergent. This sequence converges to 0 (and lim⁡k→∞|Lpk(z)|=1), since otherwise we can consider a subsequence (not relabeled) such that |Lpk(z)|→b≠1, extract a further subsequence such that Lpnk(z)→z~, and argue as in the proof of Proposition 7 that |Lp(z~)|=|z~|=b, contradicting the inequalities in (23).
Finally, forz∈K^0∪K^1 and the sequence {Lpk(z)}, consider a convergent subsequence {Lpnk(z)} and its limit z~∈S1. If z~∈S1∖Θ1, then the sequence {Lpj(z~)} converges to a root z* of pn by Proposition 6. By the continuity of Lp and the fact that {Lpj(z~)} converges to z* monotonically in the sense of Proposition 6, we have lim⁡k→∞Lpnk+j(z)→Lpj(z~) for any j≥0. This implies that there exist a large enough k and a large enough j such that Lpnk+j(z) is in the basin of attraction of the root z*, and, therefore, the whole sequence {Lpk(z)} converges to z*. In particular, z~=z*.
The remaining case with the limit of the subsequence{Lpnk(z)} satisfying z~∈S1∩Θ1 can be treated as in the proof of Proposition 7 by considering further subsequences approaching z~ clockwise or counter-clockwise; in either cases we obtain a contradiction, since arguing as in the previous paragraph we conclude that z~ has to be a root of pn.We again have an extension of the above proposition, arguing as in the proof of Corollary9.Corollary 11.
The sets{|z|=r0}∩K0 and {|z|=1/r0}∩K1 are contained in the basin of attraction of the roots of unity.However, the remaining points on the circles{|z|=r0} and {|z|=1/r0} form nontrivial, finite two-cycles [7, 8].Proposition 12.
For everyθ0∈Θ0, the set {r0eiθ0,(1/r0)eiθ0} with r0 defined in (18) is a two-cycle for the Laguerre iteration function (5).Proof.
By Proposition1, we can assume θ0=0. From (5) we have that Lp maps real, positive numbers to real, positive numbers, so Lp(r0)=1/r0 since r0∈∂D. Similarly, Lp(1/r0)=r0 since 1/r0∈∂E.For completeness, we state the following result that completes the dynamics onΘ0.Proposition 13.
For everyθ0∈Θ0, the set {reiθ0:0<r<r0or1/r0<r} belongs to the basin of attraction of the two-cycle {0,∞} for the Laguerre iteration function (5).Proof.
The proof is similar to the proof of the second part of Proposition7. For 0<r<r0, we get 0<Lp2(r)<r, so lim⁡k→∞Lp2k(r)=r~ with 0≤r~<r0. Now, if r~>0, we would have the contraction Lp2(r~)<r~ and we would also obtain Lp2(r~)=r~ by the continuity of Lp. Therefore, r~=0, and the rest follows by the symmetry properties of the Laguerre iteration function.Finally, the following result clearly demonstrates that Laguerre’s method is not suitable for finding roots of unity for large-degree polynomials [7].Proposition 14.
Lets0 be as defined in (18). The set of all points in C for which Laguerre’s method (1) converges to a root of pn(z)=zn-1, n≥5, is contained in the annulus {z∈C:s0≤|z|≤1/s0}, whose Lebesgue measure tends to 0 as n→∞.Proof.
The claim follows from Proposition7 and Theorem 4, part (1).


## 5.1. Dynamics on the Unit Circle

In this section, we study the dynamics on the unit circle,S1. As a consequence of Theorem 4, part (1), we have that the unit circle, S1, is invariant under the Laguerre iteration function (see also [8]). This follows from (13) and (12) with r=1. However, more can be said about the behavior of Lp on S1.Proposition 6.
Letn≥5. If z0∈S1∖Θ1, then the sequence of iterates of Laguerre’s method, {Lpk(z0)}, converges monotonically to the nearest root of pn(z)=zn-1 in the sense that |Lpk(z0)|=1 and the arguments of Lpk(z0) monotonically approach the argument of the nearest root as k→∞. If z0∈S1∩Θ1, then the iterates converge monotonically to the nearest root of pn in the clockwise direction.Proof.
Due to the symmetry properties ofLp (Propositions 1 and 2), it is enough to assume z=eiθ with 0<θ≤π/n and show that Lp(z)=eiθ~ with 0<θ~<θ. Since the sequence of arguments generated by the method will then be a decreasing sequence bounded below by 0, it will converge, and the corresponding sequence of points on S1 will converge to a fixed point of Lp, that is, to a root of pn by the continuity of Lp away from Θ1. The limiting root will have to be 1 and both assertions of the proposition will follow.
To prove that0<θ~<θ, we first note that
(19)Lpz=eiθe-inθ/2+n-1einθ/2+n-1,
where the numerator and the denominator are conjugates of each other and nθ/2≤π/2. Thus the whole fraction results in an expression of the form e-2iθ^ with 0<θ^<π/2, where
(20)θ^=argeinθ/2+n-1=arctansinnθ/2cos⁡nθ/2+n-1.
Consequently, Lp(z)=ei(θ-2θ^) and it remains to show that θ-2θ^>0. Consider the function
(21)gθ=θ-2θ^=θ-2arctansinnθ/2cos⁡nθ/2+n-1,0≤θ≤πn.
One can verify that g(0)=0 and since
(22)g′θ=2n-1n-2sin2nθ/4cos⁡nθ/2+n-12+sin2nθ/2>0,
we conclude that g(θ)>0 for 0<θ≤π/n.


## 5.2.  Dynamics of the Two-Cycle{0,∞}

As we mentioned earlier, the Laguerre iteration function (5) has a two-cycle {0,∞} for n≥3. We now show that this two-cycle is attracting for n≥5 and its basin of attraction contains a significant portion of D∪E. We will demonstrate later in Section 6 that the basin of attraction can be quite complicated and appears to have a fractal boundary. For the rest of Section 5 we assume n≥5.The following proposition appears in [8]. It shows that the innermost and the outermost white regions in Figure 1 belong to the basin of attraction of the two-cycle. We provide our own proof for the second part of the proposition, as the original proof in [8] appears to assume the continuity of the Laguerre iteration function Lp throughout the complex plane.Proposition 7.
Lets0 be as defined in (18). Let Ds0={z∈C∖{0}:|z|<s0} and Es0={z∈C:|z|>1/s0}. Then Lp(Ds0)⊂Es0 and Lp(Es0)⊂Ds0. Moreover, Ds0∪Es0 is contained in the basin of attraction of the two-cycle {0,∞}.Proof.
The proof of the first part follows that of [8]. Note first that Theorem 4 implies that Ds0⊂D and Es0⊂E. Hence, if z∈Ds0, then |Lp(z)|>1/|z|>1/s0 and Lp(z)∈Es0. Similarly, if z∈Es0, then |Lp(z)|<1/|z|<s0 and Lp(z)∈Ds0.
To prove the second part, it is enough to show that the basin of attraction of the two-cycle{0,∞} contains Ds0. It follows from the previous part that if z∈Ds0, then |Lp(z)|>1/|z| and |Lp2(z)|<1/|Lp(z)|, and, consequently, |Lp2(z)|<|z|. Similarly, if z∈Es0, we have |Lp2(z)|>|z|. We will show that for z∈Ds0 the even terms of the sequence {Lpk(z)} converge to 0 and the odd ones to ∞. To this end, we observe that {|Lp2k(z)|} is a decreasing, bounded, and therefore convergent sequence. If its limit is 0, we are done, since |Lp2k(z)|→0 and |Lp2k+1(z)|>1/|Lp2k(z)|→∞ as k→∞.
Assume now thatlim⁡k→∞⁡|Lp2k(z)|=b>0 and, using the Bolzano-Weierstrass theorem, consider a convergent subsequence of {Lp2nk(z)} and its limit, say, z~∈Ds0. We then have that if z~ is not in Θ1, or if z~∈Θ1 and {Lp2nk(z)} approaches it counter-clockwise, then, by the continuity of Lp and |Lp|, we have b=lim⁡k→∞⁡|Lp2(Lp2nk(z))|=|Lp2(z~)|<|z~|=b, a contradiction. The only remaining possibility is that z~∈Θ1 and it is not possible to extract a subsequence approaching it counter-clockwise. In that case z~ is (eventually) approached clockwise, and we can consider a sequence symmetric via a reflection through Θ1 (Propositions 1 and 2). We then obtain a contradiction for this new sequence as in the previous case.Remark 8.
The regionsDs0 and Es0 defined in Proposition 7 can be seen in Figure 1: Ds0 is the open ball not containing 0 bounded by the smaller gray annulus, while Es0 is the region on the outside of the larger gray annulus.Although the basin of attraction of the two-cycle{0,∞} is significantly larger than Ds0∪Es0 (see Section 6), we can immediately extend it in the following sense.Corollary 9.
The sets{|z|=s0}∩D and {|z|=1/s0}∩E are contained in the basin of attraction of the two-cycle {0,∞}.Proof.
From the definitions ofD and E in (11) it is clear that any point in {|z|=s0}∩D or {|z|=1/s0}∩E gets mapped into Ds0∪Es0, and the claim follows.We believe that the pointss0eiθ1 and (1/s0)eiθ1 also converge to the {0,∞} two-cycle. Since these points belong to the set ∂D∪∂E, their images under the Laguerre iteration map (5) lie on the circles with radii 1/s0 and s0, respectively, so it suffices to show that their arguments are different from θ1. We have not been able to find a simple proof for this statement.


## 5.3.  Dynamics of the Basins of Convergence

In Proposition10 we state a result [8] that shows that the open annulus bounded by the gray annuli in Figure 1 belongs to the basin of attraction of the roots of pn(z)=zn-1. Again, it turns out that the basin is actually larger than the annulus (see Section 6). We provide an elementary proof of the final statement of Proposition 10, since in the proof in [8] a reference is made to [6], which does not appear relevant to the proof.Proposition 10.
Letr0 be defined as in (18). Let K^0={z∈C:r0<|z|<1}⊂K0 and K^1={z∈C:1<|z|<1/r0}⊂K1. Then Lp(K^0∪K^1∪S1)⊂K^0∪K^1∪S1, and the sequence {Lpk(z)} with z∈K^0∪K^1∪S1 converges to a root of pn(z)=zn-1.Proof.
We provide a proof along the lines of [8]. First, if z=reiθ∈K^0⊂K0, then |Lp(z)|<1/r<1/r0 from the definition of K0. Using (6) and r<1, we obtain |Lp(z)|>r>r0 (see [8] for details), so we can conclude that Lp(z)∈K^0∪K^1. In exactly the same fashion, for z=reiθ∈K^1 we obtain r0<1/r<|Lp(z)|<r<1/r0, and, again, Lp(z)∈K^0∪K^1. In view of Proposition 6, we can conclude that Lp(z)∈K^0∪K^1∪S1 for any z∈K^0∪K^1∪S1.
We know from Proposition6 that if z∈S1, then {Lpk(z)} converges to a root of pn. It follows from the above inequalities that for z∈K^0∪K^1 we have
(23)min⁡z,1z<Lpz<max⁡z,1z,min⁡z,1z<1Lpz<max⁡z,1z,
and, consequently, the sequence Lpkz-1/Lpkz is decreasing and convergent. This sequence converges to 0 (and lim⁡k→∞|Lpk(z)|=1), since otherwise we can consider a subsequence (not relabeled) such that |Lpk(z)|→b≠1, extract a further subsequence such that Lpnk(z)→z~, and argue as in the proof of Proposition 7 that |Lp(z~)|=|z~|=b, contradicting the inequalities in (23).
Finally, forz∈K^0∪K^1 and the sequence {Lpk(z)}, consider a convergent subsequence {Lpnk(z)} and its limit z~∈S1. If z~∈S1∖Θ1, then the sequence {Lpj(z~)} converges to a root z* of pn by Proposition 6. By the continuity of Lp and the fact that {Lpj(z~)} converges to z* monotonically in the sense of Proposition 6, we have lim⁡k→∞Lpnk+j(z)→Lpj(z~) for any j≥0. This implies that there exist a large enough k and a large enough j such that Lpnk+j(z) is in the basin of attraction of the root z*, and, therefore, the whole sequence {Lpk(z)} converges to z*. In particular, z~=z*.
The remaining case with the limit of the subsequence{Lpnk(z)} satisfying z~∈S1∩Θ1 can be treated as in the proof of Proposition 7 by considering further subsequences approaching z~ clockwise or counter-clockwise; in either cases we obtain a contradiction, since arguing as in the previous paragraph we conclude that z~ has to be a root of pn.We again have an extension of the above proposition, arguing as in the proof of Corollary9.Corollary 11.
The sets{|z|=r0}∩K0 and {|z|=1/r0}∩K1 are contained in the basin of attraction of the roots of unity.However, the remaining points on the circles{|z|=r0} and {|z|=1/r0} form nontrivial, finite two-cycles [7, 8].Proposition 12.
For everyθ0∈Θ0, the set {r0eiθ0,(1/r0)eiθ0} with r0 defined in (18) is a two-cycle for the Laguerre iteration function (5).Proof.
By Proposition1, we can assume θ0=0. From (5) we have that Lp maps real, positive numbers to real, positive numbers, so Lp(r0)=1/r0 since r0∈∂D. Similarly, Lp(1/r0)=r0 since 1/r0∈∂E.For completeness, we state the following result that completes the dynamics onΘ0.Proposition 13.
For everyθ0∈Θ0, the set {reiθ0:0<r<r0or1/r0<r} belongs to the basin of attraction of the two-cycle {0,∞} for the Laguerre iteration function (5).Proof.
The proof is similar to the proof of the second part of Proposition7. For 0<r<r0, we get 0<Lp2(r)<r, so lim⁡k→∞Lp2k(r)=r~ with 0≤r~<r0. Now, if r~>0, we would have the contraction Lp2(r~)<r~ and we would also obtain Lp2(r~)=r~ by the continuity of Lp. Therefore, r~=0, and the rest follows by the symmetry properties of the Laguerre iteration function.Finally, the following result clearly demonstrates that Laguerre’s method is not suitable for finding roots of unity for large-degree polynomials [7].Proposition 14.
Lets0 be as defined in (18). The set of all points in C for which Laguerre’s method (1) converges to a root of pn(z)=zn-1, n≥5, is contained in the annulus {z∈C:s0≤|z|≤1/s0}, whose Lebesgue measure tends to 0 as n→∞.Proof.
The claim follows from Proposition7 and Theorem 4, part (1).


## 6. The Basins of Convergence and Their Boundaries

In this section we present primarily computational results that address the structure of the basins of attraction of Laguerre’s method (1) applied to pn(z)=zn-1 with n≥5. All numerical results have been generated using the free software package GNU Octave [12, 13]. These results show that the basins of attraction do not coincide with the sets defined in (11), and they raise additional questions that we summarize in the next section.We mentioned earlier that forn=2 it takes one iteration to get to a root of p2 from any initial guess. It is also known that for n=3 and 4 the method is globally convergent to a root of pn (except for when the initial guess z0=0) [7, 8, 11]. However, from the above analysis it follows that for n≥5 this is no longer true; more specifically, the basin of attraction for each n≥5 is contained in the annulus {s0≤|z|≤1/s0} with s0 given in (18). Since s0 is not easily computable, we can use the upper bound 1/s0<(n-1)2/(n-4) (see Theorem 4). In Figures 2 and 3, we present examples of the basins of attraction for n=5,…,8 (Figure 2) and n=10, 12, 14, and 16 (Figure 3). These are plotted on the squares [-(n-1)2/(n-4),(n-1)2/(n-4)]×[-(n-1)2/(n-4),(n-1)2/(n-4)] and show that the upper bound is a good estimate of 1/s0. Also plotted are the curves ∂D and ∂E and we see that the basins of attraction do not coincide with any of the sets of significance defined in (11). Also note how, in accordance with Theorem 4, the basin of convergence shrinks as n increases. This is demonstrated in Figure 4, where the basins for n=5, 8, 12, and 16 are plotted on the same scale.Numerically computed basins of attraction of Laguerre’s method applied to the polynomialspn(z)=zn-1 with n=5, 6, 7, and 8 (row-wise, left to right). Each color corresponds to a basin of attraction of a root in the basin. The two black curves in each image are ∂D and ∂E, and the dots represent the roots of pn. Note how the boundary of the basin of attraction tracks but does not coincide with ∂D∪∂E and appears fractal.
(a)
(b)
(c)
(d)Numerically computed basins of attraction of Laguerre’s method applied to the polynomialspn with n=10, 12, 14, and 16 (row-wise, left to right).
(a)
(b)
(c)
(d)Numerically computed basins of attraction of Laguerre’s method applied to the polynomialspn with n=5, 8, 12, and 16 (row-wise, left to right) shown on the same [-16,16]×[-16,16] square.
(a)
(b)
(c)
(d)The boundary of the basin of convergence appears fractal (see, e.g., [14] for more on fractals). We demonstrate this in Figure 5, where we show parts of the external boundary of the basins of convergence in the sectors with π(n-1)/n<θ<π(n+1)/n for n=8, 16, 24, and 32. By the rotational symmetry, Proposition 1, the other parts of the external boundary are congruent to the displayed ones.Parts of the basins of convergence to roots ofpn(z)=zn-1 for n=8, 16, 24, and 32. They correspond to the sectors with π(n-1)/n<θ<π(n+1)/n and indicate that the boundaries of the basins of convergence are fractal.
(a)
(b)
(c)
(d)The boundaries displayed in Figure5 appear self-similar, but they are only quasi-self-similar (see, e.g., [14, 15] for more on quasi-self-similarity). We demonstrate this observation in Figure 6, where we can see slight changes of shape as we zoom in and also as we more carefully examine the shapes within each figure.Figure 6
Three consecutive zoom levels into a part of the boundary forn=32 clearly demonstrate that the boundary of the basin of convergence is not self-similar only quasi-self-similar.In addition, it came to us as quite a surprise; it seems that the basins of convergence as shown in color in Figures2 and 3 are not, in general, (disregarding the “hole” in the middle) simply connected or even connected! In Figures 7 and 8 we present results with n=128 and n=1024, respectively, and several consecutive zooms into the “gray area” {1/r0<|z|<1/s0} shown in Figure 1. Note the intricate structure that becomes more prominent for larger values of n. Both figures clearly demonstrate the disconnectedness of the basin of attraction of the roots of pn. We chose the values of n=128 and n=1024 since the “holes’’ become detectable with a naked eye around n=120 and we could zoom into them, and the larger value to demonstrate how much more the structure develops as n increases.Figure 7
Several consecutive zooms into two parts of the boundary forn=128. Note that the basin of convergence is not either connected or simply connected. In particular, it appears that the basin of attraction of the roots consists of infinitely many (quasi-) self-similar disconnected sets (zooms on the left) and infinitely many (quasi-) self-similar “holes” corresponding to basins of attraction of the two-cycle {0,∞} (zooms on the right).Figure 8
Several consecutive zooms into two parts of the boundary forn=1024. Much more structure and disconnectedness becomes visible compared to the case with n=128 (Figure 7). Note how the basins of convergence to the two-cycle {0,∞} (in white) extend through the “gray areas” 1/r0<|z|<1/s0 and also note the (quasi-) self-similarity throughout.


## 7. Conclusions and Outstanding Questions

In the previous sections we have analyzed the behavior of Laguerre’s method applied to the polynomialspn(z)=zn-1 in the extended complex plane and provided computational results demonstrating the interesting behavior of the method. We now have an almost complete understanding of the behavior of the method outside of the two gray areas that contain the boundary of the basin of convergence. We concluded that for initial guesses in K^0∪K^1∪S1 the method converges to a root of pn (Proposition 10), and for initial guesses in Ds0∪Es0 the method converges to the two-cycle {0,∞} (Proposition 7).The numerical results indicate that the basin of attraction of the roots and the basin of attraction of the two-cycle share a common boundary, which should then be an invariant set under the Laguerre iteration function (5) and consist only of finite cycles and infinite orbits. We have not pursued this direction in great depth, as it would likely require extending the theory of Julia and Fatou sets [16] to functions that are not rational. Note that the Laguerre iteration function (5) is not rational even if n is even due to the choice of sign in the denominator of the method. We have, however, attempted to find some short cycles, other than those given in Proposition 12, numerically in the following way. First, we used the computational software programMathematica to generate the contour plots of ReLpk(z)-z=0 and Im⁡Lpk(z)-z=0 in the sector 0<θ<π/n (recall the symmetries in Propositions 1–3), and used the visually discovered points of intersection as initial guesses for the command FindRoot inMathematica applied to Lpk(z)-z. This way we have been able to find some 2-, 4-, and 6-cycles for polynomials of low degrees. In particular, it appears that 2-cycles in the sector 0<θ<π/n only exist for n≥10 with p10–p16 having one such 2-cycle each; p17–p26 having two; p27–p38 having three, and so forth. Regarding 4-cycles, we found two for n=5,6,7; four for n=8; eight for n=9; nine for n=10; ten for n=11 and 12, and so forth. Finally, 6-cycles appear to start at n=6; we found ten of them for n=6, twelve for n=7, and twenty-three for n=8. Not surprisingly, we have not found any short odd-cycles, which seems reasonable due to the expected behavior of points near ∂D getting mapped close to ∂E and vice versa. We list the found 4- and 6-cycles for n=5,6,7,8 in Table 1, where all numbers have been computed to 16 significant digits accuracy.Table 1
Period four and period six cycles in the sectors0<θ<π/n for n=5,6,7,8. All numbers computed to 16-significant-digit accuracy.
n
Four cycles in0<θ<π/n
Six cycles in0<θ<π/n
5
14.76136221056119
+
6.053684491748273
i
13.34758676939078
+
8.758987500188936
i
6
4.749579144551457
+
1.098207699050568
i
4.809680273550060
+
0.2938473062700105
i
4.462144769610253
+
2.042313839245265
i
4.807845850061632
+
0.5532613795970850
i
4.791479366250020
+
0.7926029359282372
i
4.758607318036074
+
1.041475486533466
i
4.703162128954519
+
1.307935002359033
i
4.660756967199228
+
1.487046196784297
i
4.587335089636846
+
1.730901724312133
i
4.504230549742958
+
1.940512624824430
i
4.394056696857116
+
2.184780604963821
i
4.271115104571219
+
2.408180892551038
i
7
3.102711305833646
+
0.4791536373837452
i
3.086956249849817
+
0.09918082640500742
i
3.005076854712194
+
1.041210971892816
i
3.098674298771984
+
0.2141440467880112
i
3.108949745463634
+
0.2853986438548191
i
3.105161257066959
+
0.3575768153296901
i
3.103107584356313
+
0.4651267058741789
i
3.096111405599539
+
0.5516620616566748
i
3.104755891427699
+
0.6231011218949135
i
3.069516544423272
+
0.7787753426450393
i
3.013630591486307
+
1.011069152189774
i
2.988317222029729
+
1.090657585339925
i
2.947434684423189
+
1.193708033582317
i
2.917334700654045
+
1.353477443986847
i
8
2.452675491472578
+
0.2785857657502200
i
2.424861149787357
+
0.04867681760903371
i
2.475125064051807
+
0.4260510136323984
i
2.433534405337240
+
0.07300790020468901
i
2.419209618854812
+
0.6711649955368295
i
2.436567623533557
+
0.1147077080457789
i
2.403834152721369
+
0.9295918014456642
i
2.443481963307878
+
0.1425019298788600
i
2.453807739243897
+
0.1734183047708730
i
2.448811352673064
+
0.2130028821893788
i
2.452347914830289
+
0.2731330464450077
i
2.452422308102194
+
0.3140142922891776
i
2.460907150206826
+
0.3413782443508301
i
2.475788631367756
+
0.3743161467144843
i
2.478533197214976
+
0.3940810991477981
i
2.474834833464490
+
0.4192210929378601
i
2.452717379844995
+
0.4708078573787699
i
2.445815983913505
+
0.5121550600972321
i
2.446892544221102
+
0.5361638213148769
i
2.421772891898377
+
0.6579277753771876
i
2.413249889360346
+
0.6953853836452080
i
2.395254878356101
+
0.7555517867904204
i
2.393829791477975
+
0.8012023541812359
i
2.395554660155073
+
0.8271069757313417
i
2.405037612365332
+
0.9182940336703574
i
2.396106513659878
+
0.9454683171801179
i
2.394665948621691
+
0.9684820140915532
iMany questions remain. What is the shape of the boundary of the basin of convergence? We see in Figures2 and 3 that the boundary appears to track ∂D and ∂E, but it does not coincide with these sets. The boundary is fractal (Figures 5 and 6) and, moreover, has many other components in the annuli determined by r0 and s0 (Figures 7 and 8). It may be of interest to see whether a fractal dimension of the boundary has a simple dependence on n. We speculate that the dimension might grow from 1 to 2 as n increases from 5 to ∞, but we have not pursued this idea further.It would also be interesting to see if other families of polynomials exhibit similar features to those observed forpn(z)=zn-1. In particular, what determines the size and shape of the basins of convergence to the roots? Is it due to the symmetry of the roots that the measure of the basins of convergence tends to zero? If so, would other symmetric arrangements of the roots yield similar results? Perhaps the questions should be reversed. Are there families of polynomials for which Laguerre’s method converges to a root except if starting from a set of zero measure? If so, what are they? We intend to look into some of these questions in future work.We conclude with the following interesting observation. The fact that the method theoretically converges only in the small annulus in the neighborhood of the unit circleS1 suggests that Laguerre’s method is unsuitable practically and raises a valid concern for general polynomials. On the other hand, when the method is implemented in its general formulation (2) and applied to polynomials pn(z)=zn-1, the resulting image of the basins of attraction may look like Figure 9, in which the basin of attraction of the roots of p7 is shown as computed on a 1000×1000 grid of points. Note that visually the method appears to converge from any point in the displayed squares, which is not the case when the mathematically equivalent formulation (5) is used. We allow the iterations to run to convergence (or a prescribed maximum number of iterations, 100 in this computation) and observe convergence to apparently random roots even for initial guesses in the set of theoretical convergence to the two-cycle {0,∞} (compare to Figure 2(c), where the basin of attraction of {0,∞} is colored white). The reason for this peculiar behavior is the loss of significance in the computation of the expression (n-1)2p′z2-nn-1pzp′′(z) in the denominator of (2). Note that both terms in the difference have leading terms n2(n-1)2z2n-2, and the actual difference should be equal to n2(n-1)2zn-2. We therefore see that, for large |z|, significant errors will occur in the computation of the square root in (2). In fact, the relative error in the computation of the square root is roughly proportional to ɛ(1+|z|n), where ɛ is the machine epsilon, so, for example, with n=8 and the usual 64-bit double precision, the relative error is on the order of 1 with |z| as small as 100. Such errors then lead to the subsequent iterates attaining values from which convergence occurs. We also note that such loss of significance will occur for any polynomial p(z) of degree n and |z| large enough, since for a general polynomial of degree n the difference (n-1)2p′z2-nn-1pzp′′(z) will have a leading term of order z2n-4, two orders of magnitude smaller than the leading terms of (n-1)2p′(z)2 and nn-1pzp′′(z). Perhaps this observation helps explain the popular notion that Laguerre’s method seems to converge to a root from almost any initial guess.Three levels of zoom into the computed basin of attraction forp7(z)=z7-1 using the general formulation of the method (2). (b) corresponds to Figure 2(c), (a) is a zoom into the center part of (b), and (c) is a zoom out to a 40×40 square.
(a)
(b)
(c)



---

*Source: 321585-2014-11-26.xml*