Abstract
Carstensen’s results from 1991, connected with Gerschgorin’s disks, are used to establish a theorem concerning the localization of polynomial zeros and to derive an a posteriori error bound method. The presented quasi-interval method possesses useful property of inclusion methods to produce disks containing all simple zeros of a polynomial. The centers of these disks behave as approximations generated by a cubic derivative free method where the use of quantities already calculated in the previous iterative step decreases the computational cost. We state initial convergence conditions that guarantee the convergence of error bound method and prove that the method has the order of convergence three. Initial conditions are computationally verifiable since they depend only on the polynomial coefficients, its degree and initial approximations. Some computational aspects and the possibility of implementation on parallel computers are considered, including two numerical examples.
Similar content being viewed by others
References
Alefeld, G., Herzberger, J.: Introduction to Interval Computation. Academic Press, New York (1983)
Börsch-Supan, W.: A posteriori error bounds for the zeros of polynomials. Numer. Math. 5, 380–398 (1963)
Braess, D., Hadeler, K.P.: Simultaneous inclusion of the zeros of a polynomial. Numer. Math. 21, 161–165 (1973)
Carstensen, C.: Anwendungen von Begleitmatrizen. Z. Angew. Math. Mech. 71, 809–812 (1991)
Carstensen, C.: Inclusion of the roots of a polynomial based on Gerschgorin’s theorem. Numer. Math. 59, 349–360 (1991)
Cosnard, M., Fraigniaud, P.: Asynchronous Durand–Kerner and Aberth polynomial root finding methods on a distributed memory multicomputer. Parallel Comput. 9, 79–84 (1989)
Cosnard, M., Fraigniaud, P.: Finding the roots of a polynomial on an MIMD multicomputer. Parallel Comput. 15, 75–85 (1990)
Durand, E.: Solution numériques des équations algébraiques, Tom. I: Équations du Type F(x)=0; Racines d’un Polynôme (Masson, Paris 1960)
Elsner, L.: Remark on simultaneous inclusion of the zeros of a polynomial by Gerschgorin’s theorem. Numer. Math. 21, 425–427 (1973)
Freeman, T.L.: Calculating polynomial zeros on a local memory parallel computer. Parallel Comput. 12, 351–358 (1989)
Gargantini, I., Henrici, P.: Circular arithmetic and the determination of polynomial zeros. Numer. Math. 18, 305–320 (1972)
Henrici, P.: Applied and Computational Complex Analysis, Vol. I. Wiley, New York (1974)
Kerner, I.O.: Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen. Numer. Math. 8, 290–294 (1966)
Marden, M.: The Geometry of Polynomials. Mathematical surveys, American Mathematical Society, Providence, Rhode Island (1966)
Petković, M.S.: On an iterative method for simultaneous inclusion of polynomial complex zeros. J. Comput. Appl. Math. 1, 51–56 (1982)
Petković, M.S.: Iterative Methods for Simultaneous Inclusion of Polynomial Zeros. Springer, Berlin Heidelberg New York (1989)
Petković, M.S., Herceg, Đ.: Börsch–Supan-like methods: Point estimation and parallel implementation. Int. J. Comput. Math. 64, 327–341 (1997)
Petković, M.S., Herceg, Đ.: Point estimation of simultaneous methods for solving polynomial equations: A survey. J. Comput. Appl. Math. 136, 183–207 (2001)
Petković, M.S., Herceg, Đ. Ilić, S.M.: Point Estimation Theory and its Applications. Institute of Mathematics, Novi Sad (1997)
Petković, M.S., Milošević, D.: A higher order family for the simultaneous inclusion of multiple zeros of polynomials. Numer. Algorithms 39, 415–435 (2005)
Petković, M.S., Petković, L.D.: Complex Interval Arithmetic and its Applications. Wiley-VCH, Berlin–Weinhein–New York (1998)
Petković, M.S., Petković, L.D.: On a cubically convergent root finding method (submitted)
Petković, M.S., Tričković, S., Herceg, Đ.: On Euler-like methods for the simultaneous approximation of polynomial zeros. Jpn. J. Ind. Appl. Math. 15, 295–315 (1998)
Smale, S.: The fundamental theorem of algebra and complexity theory. Bull. Am. Math. Soc. 4, 1–35 (1981)
Smith, B.T.: Error bounds for zeros of a polynomial based upon Gerschgorin’s theorem. J. Assoc. Comput. Mach. 17, 661–674 (1970)
Wang, D., Zhao, F.: The theory of Smale’s point estimation and its application. J. Comput. Appl. Math. 60, 253–269 (1995)
Wang, X., Zheng, S.: The quasi-Newton method in parallel circular iteration. J. Comput. Math. 4, 305–309 (1984)
Weierstrass, K.: Neuer Beweis des Satzes, dass jede ganze rationale Funktion einer Veränderlichen dargestellt werden kann als ein Product aus linearen Funktionen derselben Verändelichen, Ges. Werke 3, 251–269 (1903) (Johnson Reprint Corp., New York 1967)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Ljiljana Cvetković.
In honor of Professor Richard S. Varga.
Rights and permissions
About this article
Cite this article
Petković, M.S., Petković, L.D. On the convergence of the sequences of Gerschgorin-like disks. Numer Algor 42, 363–377 (2006). https://doi.org/10.1007/s11075-006-9040-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-006-9040-8
Keywords
- polynomial zeros
- localization of zeros
- a posteriori error bounds
- inclusion methods
- parallel implementation