International Journal of Computational Mathematics

Volume 2014, Issue 1 321585

Research Article

Open Access

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

Pavel Bělík,

Corresponding Author

Pavel Bělík

[email protected]

Mathematics Department, Augsburg College, 2211 Riverside Avenue, Minneapolis, MN 55454, USA augsburg.edu

Search for more papers by this author

HeeChan Kang,

HeeChan Kang

orcid.org/0000-0001-7774-5703

Augsburg College, 2211 Riverside Avenue, Minneapolis, MN 55454, USA augsburg.edu

Search for more papers by this author

Andrew Walsh,

Andrew Walsh

Augsburg College, 2211 Riverside Avenue, Minneapolis, MN 55454, USA augsburg.edu

Search for more papers by this author

Emma Winegar,

Emma Winegar

orcid.org/0000-0002-7677-1667

Augsburg College, 2211 Riverside Avenue, Minneapolis, MN 55454, USA augsburg.edu

Search for more papers by this author

Pavel Bělík,

Corresponding Author

Pavel Bělík

[email protected]

Mathematics Department, Augsburg College, 2211 Riverside Avenue, Minneapolis, MN 55454, USA augsburg.edu

Search for more papers by this author

HeeChan Kang,

HeeChan Kang

orcid.org/0000-0001-7774-5703

Augsburg College, 2211 Riverside Avenue, Minneapolis, MN 55454, USA augsburg.edu

Search for more papers by this author

Andrew Walsh,

Andrew Walsh

Augsburg College, 2211 Riverside Avenue, Minneapolis, MN 55454, USA augsburg.edu

Search for more papers by this author

Emma Winegar,

Emma Winegar

orcid.org/0000-0002-7677-1667

Augsburg College, 2211 Riverside Avenue, Minneapolis, MN 55454, USA augsburg.edu

Search for more papers by this author

First published: 26 November 2014

https://doi.org/10.1155/2014/321585

Citations: 1

Academic Editor: Yaohang Li

Share a link

Email
Wechat
Bluesky

Abstract

Previous analyses of Laguerre’s iteration method have provided results on the behavior of this popular method when applied to the polynomials p_n(z) = zⁿ − 1, . 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.

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 is the golden ratio [3, 4]. Although Laguerre’s method is implemented in Numerical 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 form zⁿ − 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 S¹ 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 p_n (z) = zⁿ − 1. In Section 3, we formulate and prove three propositions regarding the symmetry properties of the iteration function for p_n 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, ∞}.

Details are in the caption following the image — **Figure 1**
Open in figure viewer PowerPoint

Sets of significance for n = 16. The thick solid curves are ∂D, S¹, and ∂E, and they divide into the regions D, K₀, K₁, and E. The dots indicate the positions of the roots, the thick dashed lines are Θ₁, and the thin dotted lines are Θ₀. 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 polynomials p_n (z) = zⁿ − 1 with n ≥ 2 and . We will denote by z^1/2 the set of the two solutions such that w² = z (unless, of course, z = 0, in which case w = 0). We will use the notation for the principal square root of z; that is, if z = re^iθ with r > 0 and −π < θ ≤ π, then 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]

()

where L (z) denotes the Laguerre iteration function [9] given by

()

where

()

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 [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 p_n (z) = zⁿ − 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 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 , then there exists a root z^* of p such that .

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 p_c (z) = z² + c and p_λ (z) = (z − 1) (z² + z + λ), respectively, with , 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 polynomial p_n(z) = zⁿ − 1, n ≥ 2, the Laguerre iteration function (2) for z ≠ 0 simplifies to

()

where again the sign is chosen to maximize the modulus of the denominator. Using the principal square root of zⁿ, which will result in an expression with a nonnegative real part, we can rewrite L (z) as L_p (z) given by

()

We note that the roots of p_n are exactly the fixed points of L_p, and it is easy to check that the derivative of L_p 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 case n = 2 the method converges in one iteration for any initial guess . If Re (z₀) > 0, or if Re (z₀) = 0 and Im⁡ (z₀) ≥ 0, then L_p (z₀) = 1; otherwise L_p (z₀) = −1.

In the cases with n ≥ 3, the method has a two-cycle consisting of 0 and ∞ in the extended complex plane . 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 with n ≥ 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 for r > 0, we have [8]

()

3. Symmetry Properties of the Laguerre Iteration Function

When applied to the polynomials p_n (z) = zⁿ − 1, n ≥ 2, the Laguerre iteration function (5) has several symmetry properties that simplify the analysis of the method in the extended complex plane . 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 θ₀ and θ₁ any of the following angles for k = 0, …, n − 1:

()

In addition, we define the rays

()

Note that the roots of p_n lie on the rays Θ₀, while the rays Θ₁ divide the complex plane into n congruent sectors bisected by the rays Θ₀.

The following proposition implies that it suffices to study the behavior of L_p in the sector , that is, between two consecutive rays Θ₁, 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. For n ≥ 2, the Laguerre iteration function L_p defined in (5) commutes with the rotation by an angle α = 2π/n about the origin.

Proof. Let T_α denote the rotation by an angle α = 2π/n about the origin; that is, T_α (z) = e^iαz. Since , substituting into (5), we get for any

()

and the result follows.

The following proposition implies that the behavior of L_p in the sector is symmetric with respect to the real axis. In the case when arg (z) = θ₁, Proposition 1 applies.

Proposition 2. For n ≥ 2 and with argz ≠ θ₁, the Laguerre iteration function L_p defined in (5) commutes with the complex conjugation .

Proof. If argz ≠ θ₁, then . Consequently, , 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. For n ≥ 2, the Laguerre iteration function L_p defined in (5) commutes with the inversion with respect to the unit circle ; that is, .

Proof. Consider first with argz ≠ θ₁. Using the same conjugation properties as in the proof of Proposition 2, we have

()

We can then check by direct substitution that the same result holds also when arg (z) = θ₁, and the conclusion of the proposition follows.

In summary, it is enough to study the behavior of the method in the set {re^iθ : 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 polynomial p_n (z) = zⁿ − 1 with n ≥ 5 and the corresponding Laguerre iteration function L_p given by (5). Following [8], we start by defining several sets in the extended complex plane 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

into disjoint subsets and are defined as

()

Note that, due to the use of the principal square root in (5), L_p is continuous everywhere in

except across the rays Θ₁; however, |L_p| is continuous across Θ₁, so the notations ∂D and ∂E are justified, since ∂D and ∂E are the boundaries of D and E, respectively, in

. For future reference we note that L_p is “counter-clockwise” continuous across the rays Θ₁. That is, if

with argz < θ₁, then

. 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, S¹, and ∂E. They divide into four regions: D, K₀, K₁, and E (innermost to outermost). The dots indicate the positions of the roots of p_n. The thick dashed lines are the rays Θ₁, while the thin dotted lines are the rays Θ₀. The thin dashed circles have radii s₀ < r₀ < 1/r₀ < 1/s₀ as defined in (18) in Remark 5 below.

Writing z = re^iθ, 0 < r < ∞, we note that both ∂D and ∂E are characterized by the same equation:

()

Using (6), (12) is equivalent to [7, 8]

()

where the “characteristic function” f_n is defined as

()

We summarize relevant results (some stated in [8]) in the following theorem.

Theorem 4. Let n ≥ 5, z = re^iθ with 0 < r < ∞, and let f_n (r, θ) be defined as in (14). One then has the following.

(1)
For every , (13) has exactly three positive zeroes, r_D, 1, and r_E, such that r_D < 1 < r_E = 1/r_D. In addition, r_E < (n − 1)^2/(n−4), so the zeroes converge to 1 as n → ∞.
(2)
Each of the sets in (11) corresponds to a particular sign of f_n:
()
(3)
The boundaries ∂D and ∂E correspond to polar curves of the form r = r_D (θ) and r = r_E (θ). The function r_D (θ) is maximized at any θ = θ₀ and minimized at any θ = θ₁, while the function r_E (θ) is minimized at any θ = θ₀ and maximized at any θ = θ₁. In addition, both r_D (θ) and r_E (θ) are monotonic between any two consecutive angles θ₀ and θ₁ (see Figure 1).

Proof. (1) Let n ≥ 5, , and define f (r) = f_n (r, θ). Note that f is a differentiable function and

()

It is easy to show that f^′ (1)≤−2n². 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 (r²), 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

()

so, since f is negative for 1 < r < r_E and positive for r > r_E, we have that (n − 1) ^2/(n−4) > r_E. 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 there are unique values of r_D and r_E, 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 r_E (θ) 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 = r_E (0) > 1, as a function of θ, f_n (r_E (0), θ) is the largest (and equal to 0) exactly when θ = θ₀. Thus, f_n is negative on the circle for every θ ≠ θ₀, and it follows that r_E (θ) ≥ r_E (θ₀) for all . Similarly, the cosine term is the smallest when θ = π/n, and by a similar argument we get r_E (θ) ≤ r_E (θ₁) for all . Finally, to prove the last assertion, we implicitly differentiate (13) with respect to θ and observe that dr_E/dθ = −(∂f_n/∂θ)/(∂f_n/∂r) vanishes only when θ = θ₀ and does not exist only when θ = θ₁, since the numerator contains a factor sin (nθ/2) and the denominator is positive on r_E (θ) as the proof of part (1) implies. This concludes the proof of the theorem.

Remark 5. As in [8], we define the values 0 < s₀ < r₀ < 1 by

()

The four circles with radii s₀ < r₀ < 1/r₀ < 1/s₀ are shown in Figure 1 as dashed circles, and the annuli {s₀ < r < r₀} and {1/r₀ < r < 1/s₀} 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, S¹. As a consequence of Theorem 4, part (1), we have that the unit circle, S¹, 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 L_p on S¹.

Proposition 6. Let n ≥ 5. If z₀ ∈ S¹∖Θ₁, then the sequence of iterates of Laguerre’s method, , converges monotonically to the nearest root of p_n (z) = zⁿ − 1 in the sense that and the arguments of monotonically approach the argument of the nearest root as k → ∞. If z₀ ∈ S¹∩Θ₁, then the iterates converge monotonically to the nearest root of p_n in the clockwise direction.

Proof. Due to the symmetry properties of L_p (Propositions 1 and 2), it is enough to assume z = e^iθ with 0 < θ ≤ π/n and show that with . 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 S¹ will converge to a fixed point of L_p, that is, to a root of p_n by the continuity of L_p away from Θ₁. The limiting root will have to be 1 and both assertions of the proposition will follow.

To prove that , we first note that

()

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

with

, where

()

Consequently,

and it remains to show that

. Consider the function

()

One can verify that g (0) = 0 and since

()

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 L_p throughout the complex plane.

Proposition 7. Let s₀ be as defined in (18). Let and . Then and . Moreover, 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 and . Hence, if , then |L_p (z)| > 1/|z | > 1/s₀ and . Similarly, if , then |L_p (z)| < 1/|z | < s₀ and .

To prove the second part, it is enough to show that the basin of attraction of the two-cycle {0, ∞} contains . It follows from the previous part that if , then |L_p (z)| > 1/|z| and , and, consequently, . Similarly, if , we have . We will show that for the even terms of the sequence converge to 0 and the odd ones to ∞. To this end, we observe that is a decreasing, bounded, and therefore convergent sequence. If its limit is 0, we are done, since and as k → ∞.

Assume now that and, using the Bolzano-Weierstrass theorem, consider a convergent subsequence of and its limit, say, . We then have that if is not in Θ₁, or if and approaches it counter-clockwise, then, by the continuity of L_p and |L_p|, we have a contradiction. The only remaining possibility is that and it is not possible to extract a subsequence approaching it counter-clockwise. In that case is (eventually) approached clockwise, and we can consider a sequence symmetric via a reflection through Θ₁ (Propositions 1 and 2). We then obtain a contradiction for this new sequence as in the previous case.

Remark 8. The regions and defined in Proposition 7 can be seen in Figure 1: is the open ball not containing 0 bounded by the smaller gray annulus, while 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 (see Section 6), we can immediately extend it in the following sense.

Corollary 9. The sets {|z | = s₀}∩D and {|z | = 1/s₀}∩E are contained in the basin of attraction of the two-cycle {0, ∞}.

Proof. From the definitions of D and E in (11) it is clear that any point in {|z | = s₀}∩D or {|z | = 1/s₀}∩E gets mapped into , and the claim follows.

We believe that the points and 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/s₀ and s₀, respectively, so it suffices to show that their arguments are different from θ₁. We have not been able to find a simple proof for this statement.

5.3. Dynamics of the Basins of Convergence

In Proposition 10 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 p_n (z) = zⁿ − 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. Let r₀ be defined as in (18). Let and . Then , and the sequence with converges to a root of p_n (z) = zⁿ − 1.

Proof. We provide a proof along the lines of [8]. First, if , then |L_p (z)| < 1/r < 1/r₀ from the definition of K₀. Using (6) and r < 1, we obtain |L_p(z)| > r > r₀ (see [8] for details), so we can conclude that . In exactly the same fashion, for we obtain r₀ < 1/r<|L_p (z)| < r < 1/r₀, and, again, . In view of Proposition 6, we can conclude that for any .

We know from Proposition 6 that if z ∈ S¹, then converges to a root of p_n. It follows from the above inequalities that for we have

()

and, consequently, the sequence

is decreasing and convergent. This sequence converges to 0 (and

), since otherwise we can consider a subsequence (not relabeled) such that

, extract a further subsequence such that

, and argue as in the proof of Proposition 7 that

, contradicting the inequalities in (23).

Finally, for and the sequence , consider a convergent subsequence and its limit . If , then the sequence converges to a root z^* of p_n by Proposition 6. By the continuity of L_p and the fact that converges to z^* monotonically in the sense of Proposition 6, we have for any j ≥ 0. This implies that there exist a large enough k and a large enough j such that is in the basin of attraction of the root z^*, and, therefore, the whole sequence converges to z^*. In particular, .

The remaining case with the limit of the subsequence satisfying can be treated as in the proof of Proposition 7 by considering further subsequences approaching clockwise or counter-clockwise; in either cases we obtain a contradiction, since arguing as in the previous paragraph we conclude that has to be a root of p_n.

We again have an extension of the above proposition, arguing as in the proof of Corollary 9.

Corollary 11. The sets {|z | = r₀}∩K₀ and {|z | = 1/r₀}∩K₁ are contained in the basin of attraction of the roots of unity.

However, the remaining points on the circles {|z | = r₀} and {|z | = 1/r₀} form nontrivial, finite two-cycles [7, 8].

Proposition 12. For every θ₀ ∈ Θ₀, the set with r₀ defined in (18) is a two-cycle for the Laguerre iteration function (5).

Proof. By Proposition 1, we can assume θ₀ = 0. From (5) we have that L_p maps real, positive numbers to real, positive numbers, so L_p (r₀) = 1/r₀ since r₀ ∈ ∂D. Similarly, L_p (1/r₀) = r₀ since 1/r₀ ∈ ∂E.

For completeness, we state the following result that completes the dynamics on Θ₀.

Proposition 13. For every θ₀ ∈ Θ₀, the set 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 Proposition 7. For 0 < r < r₀, we get , so with . Now, if , we would have the contraction and we would also obtain by the continuity of L_p. Therefore, , 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. Let s₀ be as defined in (18). The set of all points in for which Laguerre’s method (1) converges to a root of p_n (z) = zⁿ − 1, n ≥ 5, is contained in the annulus , whose Lebesgue measure tends to 0 as n → ∞.

Proof. The claim follows from Proposition 7 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 p_n (z) = zⁿ − 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 for n = 2 it takes one iteration to get to a root of p₂ from any initial guess. It is also known that for n = 3 and 4 the method is globally convergent to a root of p_n (except for when the initial guess z₀ = 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 {s₀≤|z | ≤ 1/s₀} with s₀ given in (18). Since s₀ is not easily computable, we can use the upper bound 1/s₀ < (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/s₀. 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.

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.

The boundaries displayed in Figure 5 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.

In addition, it came to us as quite a surprise; it seems that the basins of convergence as shown in color in Figures 2 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/r₀<|z | < 1/s₀} 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 p_n. 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.

7. Conclusions and Outstanding Questions

In the previous sections we have analyzed the behavior of Laguerre’s method applied to the polynomials p_n (z) = zⁿ − 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 the method converges to a root of p_n (Proposition 10), and for initial guesses in 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 program Mathematica to generate the contour plots of and 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 in Mathematica applied to . 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 p₁₀–p₁₆ having one such 2-cycle each; p₁₇–p₂₆ having two; p₂₇–p₃₈ 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 sectors 0 < θ < π/n for n = 5,6, 7,8. All numbers computed to 16-significant-digit accuracy.

n	Four cycles in 0 < θ < π/n	Six cycles in 0 < θ < π/n
5	14.76136221056119 + 6.053684491748273i
5	13.34758676939078 + 8.758987500188936i

6	4.749579144551457 + 1.098207699050568i	4.809680273550060 + 0.2938473062700105i
	4.462144769610253 + 2.042313839245265i	4.807845850061632 + 0.5532613795970850i
		4.791479366250020 + 0.7926029359282372i
		4.758607318036074 + 1.041475486533466i
		4.703162128954519 + 1.307935002359033i
		4.660756967199228 + 1.487046196784297i
		4.587335089636846 + 1.730901724312133i
		4.504230549742958 + 1.940512624824430i
		4.394056696857116 + 2.184780604963821i
		4.271115104571219 + 2.408180892551038i

7	3.102711305833646 + 0.4791536373837452i	3.086956249849817 + 0.09918082640500742i
	3.005076854712194 + 1.041210971892816i	3.098674298771984 + 0.2141440467880112i
		3.108949745463634 + 0.2853986438548191i
		3.105161257066959 + 0.3575768153296901i
		3.103107584356313 + 0.4651267058741789i
		3.096111405599539 + 0.5516620616566748i
		3.104755891427699 + 0.6231011218949135i
		3.069516544423272 + 0.7787753426450393i
		3.013630591486307 + 1.011069152189774i
		2.988317222029729 + 1.090657585339925i
		2.947434684423189 + 1.193708033582317i
		2.917334700654045 + 1.353477443986847i

8	2.452675491472578 + 0.2785857657502200i	2.424861149787357 + 0.04867681760903371i
	2.475125064051807 + 0.4260510136323984i	2.433534405337240 + 0.07300790020468901i
	2.419209618854812 + 0.6711649955368295i	2.436567623533557 + 0.1147077080457789i
	2.403834152721369 + 0.9295918014456642i	2.443481963307878 + 0.1425019298788600i
		2.453807739243897 + 0.1734183047708730i
		2.448811352673064 + 0.2130028821893788i
		2.452347914830289 + 0.2731330464450077i
		2.452422308102194 + 0.3140142922891776i
		2.460907150206826 + 0.3413782443508301i
		2.475788631367756 + 0.3743161467144843i
		2.478533197214976 + 0.3940810991477981i
		2.474834833464490 + 0.4192210929378601i
		2.452717379844995 + 0.4708078573787699i
		2.445815983913505 + 0.5121550600972321i
		2.446892544221102 + 0.5361638213148769i
		2.421772891898377 + 0.6579277753771876i
		2.413249889360346 + 0.6953853836452080i
		2.395254878356101 + 0.7555517867904204i
		2.393829791477975 + 0.8012023541812359i
		2.395554660155073 + 0.8271069757313417i
		2.405037612365332 + 0.9182940336703574i
		2.396106513659878 + 0.9454683171801179i
		2.394665948621691 + 0.9684820140915532i

Many questions remain. What is the shape of the boundary of the basin of convergence? We see in Figures 2 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 r₀ and s₀ (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 for p_n(z) = zⁿ − 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 circle S¹ 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 p_n(z) = zⁿ − 1, the resulting image of the basins of attraction may look like Figure 9, in which the basin of attraction of the roots of p₇ 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 in the denominator of (2). Note that both terms in the difference have leading terms n² (n − 1) ²z²ⁿ⁻², and the actual difference should be equal to n² (n − 1) ²zⁿ⁻². 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 , 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 will have a leading term of order z²ⁿ⁻⁴, two orders of magnitude smaller than the leading terms of and n (n − 1)p (z)p^′′ (z). Perhaps this observation helps explain the popular notion that Laguerre’s method seems to converge to a root from almost any initial guess.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work was supported in part by the National Science Foundation Grant DMS-0802959 and in part by The Office of Undergraduate Research and Graduate Opportunity at Augsburg College. The authors would also like to thank an anonymous reviewer, whose careful reading of the paper and thoughtful suggestions have improved the exposition of the paper.

References

1 Laguerre E., Sur une méthode pour obtenir par approximation les racines d′une équation algébrique qui a toutes ses racines réelles, Oeuvres de Laguerre. (1898) 1, 87–103.
Google Scholar
2 Parlett B., Laguerre′s method applied to the matrix eigenvalue problem, Mathematics of Computation. (1964) 18, 464–485, MR0165668, ZBL0124.33004.
Google Scholar
3 Ralston A. and Rabinowitz P., A First Course in Numerical Analysis, 2001, 2nd edition, Dover Publications, Mineola, NY, USA, MR1828483.
Google Scholar
4 Ford J. A., A generalization of the Jenkins-Traub method, Mathematics of Computation. (1977) 31, no. 137, 193–203.
Google Scholar
5 Press W. H., Teukolsky S. A., Vetterling W. T., and Flannery B. P., Numerical recipes. The Art of Scientific Computing, 2007, 3rd edition, Cambridge University Press, Cambridge, UK, MR2371990.
Google Scholar
6 Bodewig E., Sur la méthode Laguerre pour l′approximation des racines de certaines équations algébriques et sur la critique d′Hermite, Indagationes Mathematicae. (1946) 49, 570–580.
Google Scholar
7 Ray T. L., Laguerre′s method for finding complex roots [Ph.D. thesis], 1966, Stevens Institute of Technology, Hoboken, NJ, USA.
Google Scholar
8 Curry J. H. and Fiedler S. L., On the dynamics of Laguerre′s iteration: Zⁿ − 1, Physica D. (1988) 30, no. 1-2, 124–134, https://doi.org/10.1016/0167-2789(88)90101-7, MR939270, 2-s2.0-4244121936.
Google Scholar
9 Henrici P., Applied and Computational Complex Analysis, 1974, 1, Wiley- Interscience, New York, NY, USA.
Google Scholar
10 Kahan W., Laguere′s method and a circle which contains at least one zero of a polynomial, SIAM Journal on Numerical Analysis. (1967) 4, no. 3, 474–482, https://doi.org/10.1137/0704042, MR0216743.
Google Scholar
11 Drakopoulos V., Are there any Julia sets for the Laguerre iteration function?, Computers & Mathematics with Applications. (2003) 46, no. 8-9, 1201–1210, https://doi.org/10.1016/S0898-1221(03)90212-4, MR2019677, 2-s2.0-0345328096.
Google Scholar
12 Octave Community, GNU Octave 3.8.1, 2014, http://www.gnu.org/software/octave/.
Google Scholar
13 Eaton J. W., Bateman D., and Hauberg S., Gnu Octave Version 3.0.1 Manual: A High-Level Interactive Language for Numerical Computations, 2009, CreateSpace Independent Publishing Platform, http://www.gnu.org/software/octave/doc/interpreter.
Google Scholar
14 Falconer K., Fractal Geometry: Mathematical Foundations and Applications, 2003, 2nd edition, John Wiley & Sons, https://doi.org/10.1002/0470013850, MR2118797.
10.1002/0470013850
Google Scholar
15 McLaughlin J., A note on Hausdorff measures of quasi-self-similar sets, Proceedings of the American Mathematical Society. (1987) 100, no. 1, 183–186, https://doi.org/10.2307/2046143, MR883425, ZBL0629.28006.
10.1090/S0002-9939-1987-0883425-3
Google Scholar
16 Milnor J., Dynamics in One Complex Variable, 2006, 3rd edition, Princeton University Press, MR2193309.
Google Scholar

Citing Literature

All articles

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

Abstract

1. Introduction