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

Previous analyses of Laguerre’s iteration method have provided results on the behavior of this popular method when applied to the polynomials , . 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 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 . 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 . We also numerically find some short finite cycles on the boundary of the basin of convergence for . 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) , 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