Diverging orbits for the Ehrlich–Aberth and the Weierstrass root finders

Reinke, Bernhard

doi:10.1090/proc/15715

Diverging orbits for the Ehrlich–Aberth and the Weierstrass root finders
HTML articles powered by AMS MathViewer

by Bernhard Reinke PDF

Proc. Amer. Math. Soc. 150 (2022), 1287-1300 Request permission

Abstract:

We show that several well known higher dimensional methods for finding roots of univariate polynomials have infinite orbits that diverge to infinity: in particular, the “Weierstrass” (Durand–Kerner) and the “Ehrlich–Aberth” methods. This is possible for the Jacobi update scheme (all coordinates are updated in parallel) as well as Gauss–Seidel (any coordinate update is used for all subsequent coordinates).

These root finding methods are in active use in practice, but very little is known about their global dynamical properties, and diverging orbits were discovered only recently for one of them. Our results are established by a combination of methods from dynamical systems and computer algebra.

References

Oliver Aberth, Iteration methods for finding all zeros of a polynomial simultaneously, Math. Comp. 27 (1973), 339–344. MR 329236, DOI 10.1090/S0025-5718-1973-0329236-7
Todor Bilarev, Magnus Aspenberg, and Dierk Schleicher, On the speed of convergence of Newton’s method for complex polynomials, Math. Comp. 85 (2016), no. 298, 693–705. MR 3434876, DOI 10.1090/mcom/2985
Béla Bollobás, Malte Lackmann, and Dierk Schleicher, A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton’s method, Math. Comp. 82 (2013), no. 281, 443–457. MR 2983031, DOI 10.1090/S0025-5718-2012-02640-8
Wolfram Decker, Gert-Martin Greuel, Gerhard Pfister, and Hans Schönemann, Singular 4-1-3 — a computer algebra system for polynomial computations, 2020.
E. Durand, Solutions numériques des équations algébriques. Tome I: Équations du type $F(x)=0$; racines d’un polynôme, Masson et Cie, Éditeurs, Paris, 1960 (French). MR 0121987
L. W. Ehrlich, A modified Newton method for polynomials, Commun. ACM 10 (1967), no. 2, 107–108 (en).
John Hubbard, Dierk Schleicher, and Scott Sutherland, How to find all roots of complex polynomials by Newton’s method, Invent. Math. 146 (2001), no. 1, 1–33. MR 1859017, DOI 10.1007/s002220100149
Immo O. Kerner, Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen, Numer. Math. 8 (1966), 290–294 (German). MR 203931, DOI 10.1007/BF02162564
Maxima, Maxima, a computer algebra system, version 5.44.0, 2020.
Victor Y. Pan, Solving a polynomial equation: some history and recent progress, SIAM Rev. 39 (1997), no. 2, 187–220. MR 1453318, DOI 10.1137/S0036144595288554
Jacob Palis Jr. and Welington de Melo, Geometric theory of dynamical systems, Springer-Verlag, New York-Berlin, 1982. An introduction; Translated from the Portuguese by A. K. Manning. MR 669541
Miodrag Petković, Iterative methods for simultaneous inclusion of polynomial zeros, Lecture Notes in Mathematics, vol. 1387, Springer-Verlag, Berlin, 1989. MR 1013787, DOI 10.1007/BFb0083599
Bernhard Reinke, Dierk Schleicher, and Michael Stoll, The Weierstrass root finder is not generally convergent, arXiv:2004.04777, April 2020.
Sage Developers, Sagemath, the Sage Mathematics Software System (version 9.1), 2020, https://www.sagemath.org.
Karl Weierstraß, Neuer Beweis des Satzes, dass jede ganze rationale Function einer Veränderlichen dargestellt werden kann als ein Product aus linearen Functionen derselben Veränderlichen, Sitzungsberichte der königlich preussischen Akademie der Wissenschaften zu Berlin, 1085–1101.