Skip to main content
Springer Nature Link
Log in

On the convergence of the sequences of Gerschgorin-like disks

  • Published:
Numerical Algorithms Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alefeld, G., Herzberger, J.: Introduction to Interval Computation. Academic Press, New York (1983)

    Google Scholar 

  2. Börsch-Supan, W.: A posteriori error bounds for the zeros of polynomials. Numer. Math. 5, 380–398 (1963)

    Article  MathSciNet  Google Scholar 

  3. Braess, D., Hadeler, K.P.: Simultaneous inclusion of the zeros of a polynomial. Numer. Math. 21, 161–165 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  4. Carstensen, C.: Anwendungen von Begleitmatrizen. Z. Angew. Math. Mech. 71, 809–812 (1991)

    MathSciNet  Google Scholar 

  5. Carstensen, C.: Inclusion of the roots of a polynomial based on Gerschgorin’s theorem. Numer. Math. 59, 349–360 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  6. Cosnard, M., Fraigniaud, P.: Asynchronous Durand–Kerner and Aberth polynomial root finding methods on a distributed memory multicomputer. Parallel Comput. 9, 79–84 (1989)

    Article  Google Scholar 

  7. Cosnard, M., Fraigniaud, P.: Finding the roots of a polynomial on an MIMD multicomputer. Parallel Comput. 15, 75–85 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  8. 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)

  9. Elsner, L.: Remark on simultaneous inclusion of the zeros of a polynomial by Gerschgorin’s theorem. Numer. Math. 21, 425–427 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  10. Freeman, T.L.: Calculating polynomial zeros on a local memory parallel computer. Parallel Comput. 12, 351–358 (1989)

    Article  MATH  Google Scholar 

  11. Gargantini, I., Henrici, P.: Circular arithmetic and the determination of polynomial zeros. Numer. Math. 18, 305–320 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  12. Henrici, P.: Applied and Computational Complex Analysis, Vol. I. Wiley, New York (1974)

    Google Scholar 

  13. Kerner, I.O.: Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen. Numer. Math. 8, 290–294 (1966)

    Article  MATH  MathSciNet  Google Scholar 

  14. Marden, M.: The Geometry of Polynomials. Mathematical surveys, American Mathematical Society, Providence, Rhode Island (1966)

    Google Scholar 

  15. Petković, M.S.: On an iterative method for simultaneous inclusion of polynomial complex zeros. J. Comput. Appl. Math. 1, 51–56 (1982)

    Article  Google Scholar 

  16. Petković, M.S.: Iterative Methods for Simultaneous Inclusion of Polynomial Zeros. Springer, Berlin Heidelberg New York (1989)

    MATH  Google Scholar 

  17. Petković, M.S., Herceg, Đ.: Börsch–Supan-like methods: Point estimation and parallel implementation. Int. J. Comput. Math. 64, 327–341 (1997)

    MathSciNet  MATH  Google Scholar 

  18. Petković, M.S., Herceg, Đ.: Point estimation of simultaneous methods for solving polynomial equations: A survey. J. Comput. Appl. Math. 136, 183–207 (2001)

    Google Scholar 

  19. Petković, M.S., Herceg, Đ. Ilić, S.M.: Point Estimation Theory and its Applications. Institute of Mathematics, Novi Sad (1997)

    MATH  Google Scholar 

  20. 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)

    Article  MathSciNet  MATH  Google Scholar 

  21. Petković, M.S., Petković, L.D.: Complex Interval Arithmetic and its Applications. Wiley-VCH, Berlin–Weinhein–New York (1998)

    MATH  Google Scholar 

  22. Petković, M.S., Petković, L.D.: On a cubically convergent root finding method (submitted)

  23. 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)

    Article  MATH  Google Scholar 

  24. Smale, S.: The fundamental theorem of algebra and complexity theory. Bull. Am. Math. Soc. 4, 1–35 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  25. Smith, B.T.: Error bounds for zeros of a polynomial based upon Gerschgorin’s theorem. J. Assoc. Comput. Mach. 17, 661–674 (1970)

    MATH  MathSciNet  Google Scholar 

  26. Wang, D., Zhao, F.: The theory of Smale’s point estimation and its application. J. Comput. Appl. Math. 60, 253–269 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  27. Wang, X., Zheng, S.: The quasi-Newton method in parallel circular iteration. J. Comput. Math. 4, 305–309 (1984)

    MathSciNet  Google Scholar 

  28. 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)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Electronic Engineering, University of Niš, 18 000, Niš, Serbia and Montenegro

    Miodrag S. Petković

  2. Faculty of Mechanical Engineering, University of Niš, 18 000, Niš, Serbia and Montenegro

    Ljiljana D. Petković

Authors
  1. Miodrag S. Petković
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ljiljana D. Petković
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Miodrag S. Petković.

Additional information

Communicated by Ljiljana Cvetković.

In honor of Professor Richard S. Varga.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-006-9040-8

Keywords

AMS(MOS) Subject Classifications

Search

Navigation