On using symmetric polynomials for constructing root finding methods
HTML articles powered by AMS MathViewer
- by Dmitry I. Khomovsky;
- Math. Comp. 89 (2020), 2321-2331
- DOI: https://doi.org/10.1090/mcom/3531
- Published electronically: April 6, 2020
- HTML | PDF | 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 121987
- 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 388759
- 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 127525
- 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 218196
Bibliographic Information
- Dmitry I. Khomovsky
- Affiliation: Faculty of Physics, Lomonosov Moscow State University, 1-2 Leninskie Gory, 119991 Moscow, Russia
- MR Author ID: 1067846
- Email: khomovskij@physics.msu.ru
- Received by editor(s): June 16, 2018
- Received by editor(s) in revised form: June 23, 2018, August 2, 2019, and January 13, 2020
- Published electronically: April 6, 2020
- © Copyright 2020 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 2321-2331
- MSC (2010): Primary 30C15, 65H05
- DOI: https://doi.org/10.1090/mcom/3531
- MathSciNet review: 4109568