Inverse power and Durand-Kerner iterations for univariate polynomial root-finding
type: Item
instance of: scholarly article
title: Inverse power and Durand-Kerner iterations for univariate polynomial root-finding
zbMATH Open document ID: 1054.65046
DOI: 10.1016/S0898-1221(04)90037-5
publication date: 2004-06-15T00:00:00Z
review text: The paper is devoted to the study of a special class of iterative methods for simultaneous approximations of all roots of a given polynomial, known as Weierstrass (Durand-Kerner), briefly W(D-K), iterations. After a unifying derivation of the W(D-K) algorithm and its higher-order extensions (in Section 2) and some considerations regarding the choice of initial approximations, when applying these methods (Section 3), the rest of the paper focusses on the inverse power method for finding the eigenvalues of a generalized companion matrix of a polynomial. This is an alternative approach to root finding, based on the fact that the method for finding all roots reduces to the corresponding problem of computing all eigenvalues of the companion matrix. Numerical experiments are also considered in order to show the effectiveness of the algorithms.
Mathematics Subject Classification ID: 65H05
Mathematics Subject Classification ID: 65H17
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 26C10
Mathematics Subject Classification ID: 30C15
zbMATH DE Number: 2075472
zbMATH Keywords: polynomial root-finding
zbMATH Keywords: Weierstrass (Durand-Kerner) algorithm
zbMATH Keywords: generalized companion matrix
zbMATH Keywords: eigenvalue
zbMATH Keywords: inverse power iteration
zbMATH Keywords: numerical experiments
zbMATH Keywords: algorithm
zbMATH Keywords: matrix methods
author: Dario A. Bini
author: L. Gemignani
author: Victor Y. Pan
reviewed by: Vasile Berinde
describes a project that uses: na20
describes a project that uses: na10
describes a project that uses: mctoolbox
MaRDI profile type: Publication
cites work: A bibliography on roots of polynomials
cites work: A supplementary bibliography: on roots of polynomials
cites work: Solving a Polynomial Equation: Some History and Recent Progress
cites work: Q4234125
cites work: Univariate polynomials
cites work: Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
cites work: Safe convergence of simultaneous methods for polynomial zeros
cites work: Expressing a polynomial as the characteristic polynomial of a symmetric matrix
cites work: Pseudozeros of polynomials and pseudospectra of companion matrices
cites work: Polynomial Roots from Companion Matrix Eigenvalues
cites work: Polynomial zerofinding iterative matrix algorithms
cites work: A composite polynomial zerofinding matrix algorithm
cites work: Polynomial root finding using iterated Eigenvalue computation
cites work: Congenial matrices
cites work: Linear construction of companion matrices
cites work: Inclusion of the roots of a polynomial based on Gerschgorin's theorem
cites work: Numerical computation of polynomial zeros by means of Aberth's method
cites work: Design, analysis, and implementation of a multiprecision polynomial rootfinder
cites work: Polynomial Root-Finding Algorithms and Branched Covers
cites work: How to find all roots of complex polynomials by Newton's method.
cites work: Q4314299
cites work: A remark on simultaneous inclusions of the zeros of a polynomial by Gershgorin's theorem
cites work: On Grau’s Method for Simultaneous Factorization of Polynomials
cites work: Q5689624
cites work: Inversion formulas and linear complexity algorithm for diagonal plus semiseparable matrices
cites work: Q4814569
cites work: Q4342463
cites work: Accuracy and Stability of Numerical Algorithms
cites work: Computations with infinite Toeplitz matrices and polynomials
full work available at URL: s0898-1221(04)90037-5
OpenAlex ID: W1995134626
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 2075472