A globally convergent method for simultaneously finding polynomial roots

Pasquini, L.; Trigiante, D.

doi:10.1090/S0025-5718-1985-0771036-6

A globally convergent method for simultaneously finding polynomial roots

Authors: L. Pasquini and D. Trigiante
Journal: Math. Comp. 44 (1985), 135-149
MSC: Primary 65H05
DOI: https://doi.org/10.1090/S0025-5718-1985-0771036-6
MathSciNet review: 771036
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A new method for the simultaneous approximation of all the roots of a polynomial is given. The method converges for almost every initial approximation, the set of the exceptional starting points being a closed set of measure zero, at least if all the polynomial roots are real and simple. The method exhibits quadratic convergence not only to simple, but also to multiple roots.

[1] M. W. Green, A. J. Korsak & M. C. Pease, "Simultaneous iteration towards all roots of a complex polynomial," SIAM Rev., v. 18, 1976, pp. 501-502.
[2] Immo O. Kerner, Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen, Numer. Math. 8 (1966), 290–294 (German). MR 203931, https://doi.org/10.1007/BF02162564
[3] I. O. Kerner, "Algorithm 283," Comm. ACM, v. 9, 1966, p. 273.
[4] E. Durand, Solution Numérique des Equations Algébriques, Tome I, Masson, Paris, 1968.
[5] L. W. Ehrlich, "A modified Newton method for polynomials," Comm. ACM, v. 10, 1967, pp. 107-109.
[6] Oliver Aberth, Iteration methods for finding all zeros of a polynomial simultaneously, Math. Comp. 27 (1973), 339–344. MR 329236, https://doi.org/10.1090/S0025-5718-1973-0329236-7
[7] L. Pasquini & D. Trigiante, "Il metodo di continuazione e l'approssimazione simultanea degli zeri di un polinomio," Seminario dell'Ist. di Mat. Appl., Fac.di Ing., Univ. di Roma, 1981, pp. 128-146.
[8] M. L. Locascio, L. Pasquini & D. Trigiante, "Un polialgoritmo a convergenza rapida per la determinazione simultanea degli zeri reali di un polinomio e delle loro molteplicità," Monografie di Soft. Matem., N. 30, Pubbl. dell'IAC, 1984.
[9] Carl de Boor, A practical guide to splines, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York-Berlin, 1978. MR 507062
[10] L. B. Rall, Convergence of the Newton process to multiple solutions, Numer. Math. 9 (1966), 23–37. MR 210316, https://doi.org/10.1007/BF02165226
[11] Béla Barna, Über die Divergenzpunkte des Newtonschen Verfahrens zur Bestimmung von Wurzeln algebraischen Gleichungen. II, Publ. Math. Debrecen 4 (1956), 384–397 (German). MR 78956
[12] Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, https://doi.org/10.1090/S0273-0979-1981-14858-8