On using symmetric polynomials for constructing root finding methods

Khomovsky, Dmitry

doi:10.1090/mcom/3531

On using symmetric polynomials for constructing root finding methods
HTML articles powered by AMS MathViewer

by Dmitry I. Khomovsky HTML | PDF

Math. Comp. 89 (2020), 2321-2331 Request permission

Abstract:

We propose an approach to constructing iterative methods for finding polynomial roots simultaneously. One feature of this approach is using the fundamental theorem of symmetric polynomials. Within this framework, we reconstruct many of the existing root finding methods. The new results presented in this paper are some modifications of the Durand–Kerner method.

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
Dario Andrea Bini, Numerical computation of polynomial zeros by means of Aberth’s method, Numer. Algorithms 13 (1996), no. 3-4, 179–200 (1997). MR 1430518, DOI 10.1007/BF02207694
D. A. Bini, L. Gemignani, and V. Y. Pan, Inverse power and Durand-Kerner iterations for univariate polynomial root-finding, Comput. Math. Appl. 47 (2004), no. 2-3, 447–459. MR 2048196, DOI 10.1016/S0898-1221(04)90037-5
S. I. Cholakov, Local and semilocal convergence of Wang-Zheng’s method for simultaneous finding polynomial zeros, Symmetry, 11.6 (2019), 736.
K. Dochev, Modified Newton’s method for simultaneous computation of all the roots of a given algebraic equation (Bulgarian), Phys. Mat. J. Bulg. Acad. Sci. 5 (1962), 136–139.
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, Communications of the ACM 10.2 (1967), 107–108.
Walter Gander, On Halley’s iteration method, Amer. Math. Monthly 92 (1985), no. 2, 131–134. MR 777559, DOI 10.2307/2322644
Irene Gargantini, Parallel laguerre iterations: The complex case, Numer. Math. 26 (1976), no. 3, 317–323. MR 1553988, DOI 10.1007/BF01395948
A. S. Householder, The numerical treatment of a single nonlinear equation, International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York-Düsseldorf-London, 1970. MR 0388759
Immo O. Kerner, Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen, Numer. Math. 8 (1966), 290–294 (German). MR 203931, DOI 10.1007/BF02162564
Hans J. Maehly, Zur iterativen Auflösung algebraischer Gleichungen, Z. Angew. Math. Phys. 5 (1954), 260–263 (German). MR 63146, DOI 10.1007/bf01600333
J. M. McNamee and V. Y. Pan, Numerical methods for roots of polynomials. Part II, Studies in Computational Mathematics, vol. 16, Elsevier/Academic Press, Amsterdam, 2013. MR 3293902
D. G. Mead, Newton’s identities, Amer. Math. Monthly 99 (1992), no. 8, 749–751. MR 1186460, DOI 10.2307/2324242
G. V. Milovanović and M. S. Petković, On the convergence order of a modified method for simultaneous finding polynomial zeros, Computing 30 (1983), no. 2, 171–178 (English, with German summary). MR 698128, DOI 10.1007/BF02280787
Gradimir V. Milovanović and Miodrag S. Petković, Computational efficiency of the simultaneous methods for finding polynomial zeros: estimation of efficiency, Numerical methods and approximation theory, II (Novi Sad, 1985) Univ. Novi Sad, Novi Sad, 1985, pp. 83–87 (English, with Serbo-Croatian summary). MR 822487
A. M. Ostrowski, Solution of equations and systems of equations, Pure and Applied Mathematics, Vol. IX, Academic Press, New York-London, 1960. MR 0127525
M. S. Petković, Generalised root iterations for the simultaneous determination of multiple complex zeros, Z. Angew. Math. Mech. 62 (1982), no. 11, 627–630. MR 694063, DOI 10.1002/zamm.19820621109
Miodrag Petković, Point estimation of root finding methods, Lecture Notes in Mathematics, vol. 1933, Springer-Verlag, Berlin, 2008. MR 2442063, DOI 10.1007/978-3-540-77851-6
Miodrag S. Petković and Đorđe D. Herceg, On the convergence of Wang-Zheng’s method, J. Comput. Appl. Math. 91 (1998), no. 1, 123–135. MR 1626593, DOI 10.1016/S0377-0427(98)00034-X
M. S. Petković and G. V. Milovanović, A note on some improvements of the simultaneous methods for determination of polynomial zeros, J. Comput. Appl. Math. 9 (1983), no. 1, 65–69. MR 702231, DOI 10.1016/0377-0427(83)90028-6
M. S. Petković, G. V. Milovanović, and L. V. Stefanović, Some higher-order methods for the simultaneous approximation of multiple polynomial zeros, Comput. Math. Appl. Ser. A 12 (1986), no. 9, 951–962. MR 861672
M. S. Petković and L. V. Stefanović, On some improvements of square root iteration for polynomial complex zeros, J. Comput. Appl. Math. 15 (1986), no. 1, 13–25. MR 843708, DOI 10.1016/0377-0427(86)90235-9
Bl. Sendov, A. Andreev, and N. Kjurkchiev, Numerical solution of polynomial equations, Handbook of numerical analysis, Vol. III, Handb. Numer. Anal., III, North-Holland, Amsterdam, 1994, pp. 625–778. MR 1307411, DOI 10.1016/S1570-8659(05)80019-5
Xing Hua Wang and Shi Ming Zheng, A family of parallel and interval iterations for finding simultaneously all roots of a polynomial with rapid convergence. II, Math. Numer. Sinica 7 (1985), no. 4, 433–444 (Chinese, with English summary). MR 849937
Karl Weierstrass, Mathematische Werke. VI. Vorlesungen über Anwendung der elliptischen Funktionen, Georg Olms Verlagsbuchhandlung, Hildesheim; Johnson Reprint Corp., New York, 1967 (German). MR 0218196