×

zbMATH — the first resource for mathematics

The Laguerre-and-sums-of-powers algorithm for the efficient and reliable approximation of all polynomial roots. (English. Russian original) Zbl 1351.65027
Probl. Inf. Transm. 51, No. 4, 361-370 (2015); translation from Probl. Peredachi Inf. 51, No. 4, 60-70 (2015).
Summary: We prove the first sufficient convergence criterion for Laguerre’s root-finding algorithm, which by empirical evidence is highly efficient. The criterion is applicable to simple roots of polynomials with degree greater than 3. The “sums of powers algorithm” (SPA), which is a reliable iterative root-finding method, can be used to fulfill the condition for each root. Therefore, Laguerre’s method together with the SPA is now an efficient and reliable algorithm (LaSPA). In computational mathematics these results solve a central task which was first attacked by L. Euler 266 years ago.
MSC:
65H04 Numerical computation of roots of polynomial equations
Software:
SPAViews
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Möller, H., Convergence and Visualization of Laguerre’s Rootfinding Algorithm, arXiv:1501.02168 [math.NA], 2015.
[2] Mekwi, W.R., Iterative Methods for Roots of Polynomials, Master Thesis, Univ. of Oxford, UK, 2001.
[3] Press, W.H., Teukolsky, S.A., Vetterling, W.T., and Flannery, B.P., Numerical Recipes: The Art of Scientific Computing, New York: Cambridge Univ. Press, 2007, 3rd ed. · Zbl 1132.65001
[4] Laguerre, E., OEuvres, vol. 1, Paris: Gauthier-Villars, 1898.
[5] Möller, H., An efficient reliable algorithm for the approximation of all polynomial roots based on the method of D. Bernoulli, Sovr. Probl. Matem., 16, 52-65, (2012)
[6] Möller, H., Algorithmische Lineare Algebra, Braunschweig/Wiesbaden: Vieweg, 1997. Available at http: //wwwmath.uni-muenster.de/u/mollerh/data/AlLiAlC.pdf.
[7] Möller, H., Report on the Visualization of Laguerre’s Method, 2014. Available at http://wwwmath. uni-muenster.de/u/mollerh/data/VisReport.pdf.
[8] Möller, H., Visualization of the First Stage of the SPA, 2012. Available at http://wwwmath. uni-muenster.de/u/mollerh/data/SPAview.pdf.
[9] Turán, P., On a New Method of Analysis and Its Applications, New York: Wiley, 1978.
[10] Euler, L., Introductio in analysin infinitorum, lausannae: M.-M. bousquet, 1748, (1988), Berlin
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.