Ten methods to bound multiple roots of polynomials
type: Item
instance of: scholarly article
title: Ten methods to bound multiple roots of polynomials
zbMATH Open document ID: 1030.65046
DOI: 10.1016/S0377-0427(03)00381-9
published in: Journal of Computational and Applied Mathematics
publication date: 2003-08-07T00:00:00Z
review text: Let \(P\in{\mathbb C}[z]\) be a univariate polynomial, and \(\widetilde{z} \in {\mathbb C}\) be such that \(P\) has a \(k\)-fold root cluster near \(\widetilde{z}\). The author examines, for 17 different types of polynomials \(P\), the behavior of nine methods to compute a disc near \(\widetilde{z}\) which contains at least (or, for some methods, exactly) \(k\) roots of \(P\). Most of the methods are known, though some new variations are presented. All possible effects of rounding errors are accounted for in the implementation and testing of each method, and complexity bounds are presented for each as well. Single precision arithmetic is used throughout. Based on the results of the tests, the author derives a tenth, hybrid algorithm which does not require knowledge of \(k\) in advance, and which almost always gives, numerically, nearly optimal discs. This algorithm has been implemented in Matlab 4.0 and is available in the INTLAB toolbox, which can be downloaded (freely, for private and academic purposes) from the author's homepage.
Mathematics Subject Classification ID: 65H05
Mathematics Subject Classification ID: 65G50
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 26C10
Mathematics Subject Classification ID: 30C15
zbMATH DE Number: 1961629
zbMATH Keywords: multiple roots
zbMATH Keywords: univariate polynomials
zbMATH Keywords: bounding roots
zbMATH Keywords: rounding errors
zbMATH Keywords: complexity bounds
zbMATH Keywords: hybrid algorithm
author: Siegfried M. Rump
reviewed by: Alyson Reeves
describes a project that uses: INTLAB
describes a project that uses: Matlab
MaRDI profile type: Publication
cites work: Q3345690
cites work: Gershgorin's Theorem and the Zeros of Polynomials
cites work: Bounds for the variation of the roots of a polynomial and the eigenvalues of a matrix
cites work: Residuenabschätzung für Polynom-Nullstellen mittels Lagrange-Interpolation
cites work: Simultaneous inclusion of the zeros of a polynomial
cites work: Inclusion of the roots of a polynomial based on Gerschgorin's theorem
cites work: Über die Falksche ECP-Transformation und Verallgemeinerungen
cites work: A remark on simultaneous inclusions of the zeros of a polynomial by Gershgorin's theorem
cites work: Q2765413
cites work: Circular arithmetic and the determination of polynomial zeros
cites work: Theorem Proving in Higher Order Logics
cites work: Q4888807
cites work: Q4072022
cites work: Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
cites work: Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken
cites work: Q5546070
cites work: A bibliography on roots of polynomials
cites work: Q5566070
cites work: Enclosing clusters of zeros of polynomials
cites work: An Existence Test for Root Clusters and Multiple Roots
cites work: Interval Methods for Systems of Equations
cites work: Q4060241
cites work: Improving spectral-variation bounds with Chebyshev polynomials
cites work: Automatic differentiation: techniques and applications
cites work: Q4321536
cites work: Q4949347
cites work: Computational error bounds for multiple or nearly multiple eigenvalues
cites work: Self-validating methods
cites work: Quasi-gcd computations
cites work: Error Bounds for Zeros of a Polynomial Based Upon Gerschgorin's Theorems
cites work: Q5566068
cites work: The Lorenz attractor exists
cites work: Upperbounds for roots of polynomials
cites work: Mathematische Deutung des ‘Flat Facet Models’ zur Bildverarbeitung
cites work: Q5674306
Recommended article: Multiplicity hunting and approximating multiple roots of polynomial systems
Recommended article: Q4660677
Recommended article: Computation of bounds for polynomial roots
Recommended article: Q5314686
Recommended article: The computation of multiple roots of a polynomial
Recommended article: On an efficient method for the simultaneous approximation of polynomial multiple roots
Recommended article: On the bounds for the roots of a polynomial
Recommended article: Bounds for the multiplicities of the roots of a complex polynomial
description: scientific article; zbMATH DE number 1961629