×

Inverse power and Durand-Kerner iterations for univariate polynomial root-finding. (English) Zbl 1054.65046

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.

MSC:

65H05 Numerical computation of solutions to single equations
65H17 Numerical solution of nonlinear eigenvalue and eigenvector problems
12Y05 Computational aspects of field theory and polynomials (MSC2010)
26C10 Real polynomials: location of zeros
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)

Software:

na20; na10; mctoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] McNamee, J. M., Bibliography on roots of polynomials, J. Comp. Appl. Math., 47, 391-394 (1993) · Zbl 0788.65056
[2] McNamee, J. M., A supplementary bibliography on roots of polynomials, J. Computational Applied Mathematics, 78, 1 (1997) · Zbl 0973.65501
[3] Pan, V. Y., Solving a polynomial equation: Some history and recent progress, SIAM Review, 39, 2, 187-220 (1997) · Zbl 0873.65050
[4] Pan, V. Y., Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros, (Proc. 27th Ann. ACM Symp. on Theory of Computing (May 1995), ACM Press: ACM Press New York), 741-750 · Zbl 0942.68796
[5] Pan, V. Y., Univariate polynomials: Nearly optimal algorithms for factorization and rootfinding, (Proc. Intern. Symposium on Symbolic and Algorithmic Computation (ISSAC ‘01) (2001), ACM Press: ACM Press New York), 253-267 · Zbl 1356.65125
[6] Pan, V. Y., Univariate polynomials: Nearly optimal algorithms for factorization and rootfinding, Journal of Symbolic Computations, 33, 5, 701-733 (2002) · Zbl 1004.65061
[7] Petkovic, M. S.; Herceg, D.; Illic, S., Safe convergence of simultaneous method for polynomials zeros, Numer. Algorithms, 17, 313-331 (1998) · Zbl 0908.65027
[8] Fiedler, M., Expressing a polynomial as the characteristic polynomial of a symmetric matrix, Linear Algebra Appl., 141, 265-270 (1990) · Zbl 0721.15005
[9] Toh, K. C.; Trefethen, L. N., Pseudozeros of polynomials and pseudospectra of companion matrices, Numerische Math., 68, 403-425 (1994) · Zbl 0808.65053
[10] Edelman, A.; Murakami, H., Polynomial roots from companion matrix eigenvalues, Mathematics of Computation, 64, 763-776 (1995) · Zbl 0833.65041
[11] Malek, F.; Vaillancourt, R., Polynomial zerofinding iterative matrix algorithms, Computers Math. Applic., 29, 1, 1-13 (1995) · Zbl 0812.65039
[12] Malek, F.; Vaillancourt, R., A composite polynomial zerofinding matrix algorithm, Computers Math. Applic., 30, 2, 37-47 (1995) · Zbl 0846.65021
[13] Fortune, S., Polynomial root finding using iterated eigenvalue computation, (Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC ‘01) (2001), ACM Press: ACM Press New York), 121-128 · Zbl 1356.65121
[14] Barnett, S., Congenial matrices, Linear Algebra Appl., 41, 277-298 (1981) · Zbl 0479.15012
[15] Carstensen, C., On a linear construction of companion matrices, Linear Algebra Appl., 149, 191-214 (1991) · Zbl 0717.15011
[16] Carstensen, C., Inclusion of the roots of a polynomial based on Gershgorin’s theorem, Numerische Math., 59, 349-360 (1991) · Zbl 0726.65053
[17] Bini, D. A., Numerical computation of polynomial zeros by means of Aberth’s method, Numerical Algorithms, 13, 3-4, 179-200 (1996) · Zbl 0869.65034
[18] Bini, D. A.; Fiorentino, G., Design, analysis, and implementation of a multiprecision polynomial rootfinder, Numerical Algorithms, 23, 127-173 (2000) · Zbl 1018.65061
[19] Kim, M.-hi; Sutherland, S., Polynomial root-finding algorithms and branched covers, SIAM J. on Computing, 23, 2, 415-436 (1994) · Zbl 0803.65066
[20] Hubbard, J.; Schleicher, D.; Sutherland, S., How to find all roots of complex polynomials by Newton’s method, Inventiones Math., 146, 1-33 (2001) · Zbl 1048.37046
[21] D.A. Bini, V.Y. Pan, Polynomial and Matrix Computations, Volume 2: Fundamental and Practical Algorithms; D.A. Bini, V.Y. Pan, Polynomial and Matrix Computations, Volume 2: Fundamental and Practical Algorithms · Zbl 0809.65012
[22] Elsner, L., A remark on simultaneous inclusions of the zeros of a polynomial by Gershgorin theorem, Numer. Math., 21, 425-427 (1973) · Zbl 0267.65037
[23] Carstensen, C., On Grau’s method for simultaneous factorization of polynomials, SIAM J. of Numerical Analysis, 29, 2, 601-613 (1992) · Zbl 0756.65072
[24] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD · Zbl 0865.65009
[25] Eidelman, Y.; Gohberg, I., Inversion formulas and linear complexity algorithm for diagonal plus semiseparable matrices, Computers Math. Applic., 33, 4, 69-79 (1997) · Zbl 0870.65020
[26] Mastronardi, N.; Chandrasekaran, S.; Van Huffel, S., Fast and stable two-way algorithm for diagonal plus semi-separable systems of linear equations, Numer. Linear Algebra Appl., 8, 1, 7-12 (2001) · Zbl 1051.65021
[27] Wilkinson, J. H., Rounding Errors in Algebraic Processes, Notes on Applied Science No. 32 (1963), Her Majesty’s Stationery Office: Her Majesty’s Stationery Office London, Prentince-Hall, Englewood Cliffs, NJ, U.S.A.
[28] Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), SIAM: SIAM Philadelphia, PA · Zbl 1011.65010
[29] Bini, D. A.; Gemignani, L.; Meini, B., Computations with infinite Toeplitz matrices and polynomials, Linear Algebra Appl., 343/344, 21-61 (2002) · Zbl 0999.65025
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.