Perturbation bounds for polynomials. (English) Zbl 1140.65037
Authors’ summary: Using two different elementary approaches we derive a global and a local perturbation theorem on polynomial zeros that significantly improve the results of A. Ostrowski [Acta Math 72, 99–257 (1940; Zbl 0023.33403)], and R. Bhatia, L. Elsner and G. Krause [Linear Algebra Appl 142, 195–209 (1990; Zbl 0713.15005)]. A comparison of different perturbation bounds shows that our results are better in many cases than the similar local result of B. Beauzamy [Can. Math. Bull. 42, No. 1, 3–12 (1999; Zbl 0930.30008)]. Using the matrix theoretical approach we also improve the backward stability result of A. Edelman and H. Murakami [Proceedings of the Fifth SIAM Conference on Applied Linear Algebra, SIAM, Philapdelphia, 1994; Math Comput 64, No. 210, 763–776 (1995; Zbl 0833.65041)].
Reviewer: Jiří Vaníček (Praha)
MSC:
| 65H05 | Numerical computation of solutions to single equations |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 15A12 | Conditioning of matrices |
| 65J20 | Numerical solutions of ill-posed problems in abstract spaces; regularization |
Software:
mctoolboxReferences:
| [1] | Anderson J. (1996). A secular equation for the eigenvalues of a diagonal matrix perturbation. Linear Algebra Appl. 246: 49–70 · Zbl 0861.15006 · doi:10.1016/0024-3795(94)00314-9 |
| [2] | Arnold V.I. (1971). On the matrices depending on parameters. Russ. Math. Surv. 26: 29–43 · Zbl 0259.15011 · doi:10.1070/RM1971v026n02ABEH003827 |
| [3] | Baumgartel H. (1985). Analytic Perturbation Theory for Matrices and Operators. Birkhauser Verlag, Budapest |
| [4] | Bauer F.L. and Fike C.T. (1960). Norms and exclusion theorems. Numer. Math. 2: 137–144 · Zbl 0101.25503 · doi:10.1007/BF01386217 |
| [5] | Beauzamy B. (1999). How the roots of a polynomial vary with its coefficients: a local quantitative result. Can. Math. Bull. 42(1): 3–12 · Zbl 0930.30008 · doi:10.4153/CMB-1999-001-6 |
| [6] | Beauzamy B. (2000). Finding the roots of polynomial equations: an algorithm with linear command. Revista Matemática Complutense 13(2): 305–323 · Zbl 0976.05007 |
| [7] | Beckermann B. (2000). The condition number of real Vandermonde, Krylov and positive definite Hankel matrices. Numer. Math. 85: 553–577 · Zbl 0965.15003 · doi:10.1007/PL00005392 |
| [8] | Bhatia R., Elsner L. and Krause G. (1990). Bounds for the variation of the roots of a polynomial and the eigenvalues of a matrix. Linear Algebra Appl. 142: 195–209 · Zbl 0713.15005 · doi:10.1016/0024-3795(90)90267-G |
| [9] | Bhatia R. (1997). Matrix Analysis. Springer, Heidelberg · Zbl 0863.15001 |
| [10] | Björck A. and Pereyra V. (1970). Solution of Vandermonde systems of equations. Math. Comp. 24: 893–903 · Zbl 0221.65054 |
| [11] | Bunch J.R., Nielsen C.P. and Sorensen D.C. (1978). Rank-one modification of the symmetric eigenproblem. Numer. Math. 31: 31–48 · Zbl 0369.65007 · doi:10.1007/BF01396012 |
| [12] | Chatelin F. (1993). Eigenvalues of Matrices. Wiley, New York · Zbl 0783.65031 |
| [13] | Chu E.K. (1986). Generalization of the Bauer-Fike Theorem. Numer. Math. 49: 685–691 · doi:10.1007/BF01389736 |
| [14] | Córdova A., Gautschi W. and Ruschewey S. (1990). Vandermonde matrices on the circle: spectral properties and conditioning. Numer. Math. 57: 577–591 · Zbl 0728.15003 · doi:10.1007/BF01386429 |
| [15] | Csáki, F.G.: Some notes on the inverse of the confluent Vandermonde matrices. IEEE Trans. Autom. Control, February, pp. 154–157 (1975) |
| [16] | Ćurgus B. and Mascioni V. (2006). Roots and polynomials as homeomorphic spaces. Expos. Math. 24: 81–95 · Zbl 1101.30008 |
| [17] | Deif A.S. (1995). Rigorous perturbation bounds for eigenvalues and eigenvectors of a matrix. J. Comp. Appl. Math. 57: 403–412 · Zbl 0823.15017 · doi:10.1016/0377-0427(93)E0208-4 |
| [18] | Demmel J.W. (1987). On condition numbers and the distance to the nearest ill-posed problem. Numer. Math. 51: 251–289 · Zbl 0597.65036 · doi:10.1007/BF01400115 |
| [19] | Edelman A. and Murakami H. (1994). Polynomial roots from companion matrix eigenvalues. In: Lewis, J.G. (eds) Proceedings of the Fifth SIAM Conference on Applied Linear Algebra., pp 326–330. SIAM, Philapdelphia · Zbl 0819.65086 |
| [20] | Edelman A. and Murakami H. (1995). Polynomial roots from companion matrix eigenvalues. Math. Comput. 64(210): 763–776 · Zbl 0833.65041 · doi:10.1090/S0025-5718-1995-1262279-2 |
| [21] | Freedman D.Z. (2004). Perturbation bounds for the joint spectrum of commuting matrices. Linear Algebra Appl. 387: 29–40 · Zbl 1067.15015 · doi:10.1016/j.laa.2003.12.012 |
| [22] | Gautschi W. (1962). On inverses of Vandermonde and confluent Vandermonde matrices. Numer. Math. 4: 117–123 · Zbl 0108.12501 · doi:10.1007/BF01386302 |
| [23] | Gautschi W. (1963). On inverses of Vandermonde and confluent Vandermonde matrices II. Numer. Math. 5: 425–430 · Zbl 0115.34303 · doi:10.1007/BF01385906 |
| [24] | Gautschi W. (1973). On the condition of algebraic equations. Numer. Math. 21: 405–424 · Zbl 0278.65044 · doi:10.1007/BF01436491 |
| [25] | Gautschi W. (1975). Norm estimates for inverses of Vandermonde matrices. Numer. Math. 23: 337–347 · Zbl 0304.65031 · doi:10.1007/BF01438260 |
| [26] | Gautschi W. (1975). Optimally conditioned Vandermonde matrices. Numer. Math. 24: 1–12 · Zbl 0316.65005 · doi:10.1007/BF01437212 |
| [27] | Gautschi W. (1978). On inverses of Vandermonde and confluent Vandermonde matrices III. Numer. Math. 29: 445–450 · Zbl 0362.15002 · doi:10.1007/BF01432880 |
| [28] | Gautschi W. (1979). The condition of polynomial in power form. Math. Comput. 33: 343–352 · Zbl 0399.41002 · doi:10.1090/S0025-5718-1979-0514830-6 |
| [29] | Gautschi W. and Inglese G. (1988). Lower bounds for the condition number of Vandermonde matrices. Numer. Math. 52: 241–250 · Zbl 0646.15003 · doi:10.1007/BF01398878 |
| [30] | Gilbert R.C. (1988). Companion matrices with integer entries and integer eigenvalues and eigenvectors. Am. Math. Monthly 95: 947–950 · Zbl 0667.15011 · doi:10.2307/2322394 |
| [31] | Golub G.H. (1973). Some modified matrix eigenvalue problem. SIAM Rev. 15: 318–334 · Zbl 0254.65027 · doi:10.1137/1015032 |
| [32] | Golub G. and Van Loan C. (1983). Matrix Computations. The Johns Hopkins University Press, Baltimore · Zbl 0559.65011 |
| [33] | Harville D. (1997). Matrix Algebra from a Statistician’s Perspective. Springer, Heidelberg · Zbl 0881.15001 |
| [34] | Henrici P. (1962). Bounds for iterates, inverses, spectral variation and fields of values of non-normal matrices. Numer. Math. 4: 24–40 · Zbl 0102.01502 · doi:10.1007/BF01386294 |
| [35] | Higham N.J. (1996). Accuracy and Stability of Numerical Algorithms. SIAM, Philapdelphia · Zbl 0847.65010 |
| [36] | Hoffman A.J. and Wielandt H.W. (1953). The variation of the spectrum of a normal matrix. Duke Math. J. 20: 37–39 · Zbl 0051.00903 · doi:10.1215/S0012-7094-53-02004-3 |
| [37] | Horn R. and Johnson C. (1985). Matrix Analysis. Cambridge University Press, Cambridge · Zbl 0576.15001 |
| [38] | Jiang E. (1998). Challenging eigenvalue perturbation problems. Linear Algebra Appl. 278: 303–307 · Zbl 0933.15031 · doi:10.1016/S0024-3795(97)10086-6 |
| [39] | Kato T. (1966). Perturbation Theory for Linear Operators. Springer, Heidelberg · Zbl 0148.12601 |
| [40] | Kittaneh F. (1995). Singular values of companion matrices and bounds on zeros of polynomials. SIAM J. Matrix Anal. Appl. 16: 333–340 · Zbl 0819.15014 · doi:10.1137/S0895479893260139 |
| [41] | Laguerre E.N. (1881). Sur les équations algébriques de la forme \({\frac{A_{0}}{x-a_{0}} + \frac{A_{1}}{x-a_{1}} + \cdots + \frac{A_{n}} {x-a_{n}} = 0}\) . Comptes rendus des séances de l”Académie des Sciences 93: 156–157 |
| [42] | Li, R.-C.: Lower bounds for the condition number of a real confluent Vandermonde matrix. Technical Report 2004–10, Department of Mathematics, University of Kentucky, available at http://www.ms.uky.edu/\(\sim\)math/MAreport/PDF/2004-10.pdf (2004) |
| [43] | Macon N. and Spitzbart A. (1958). Inverse of Vandermonde matrices. Am. Math. Monthly 65: 95–100 · Zbl 0081.01503 · doi:10.2307/2308881 |
| [44] | Marden M. (1949). The Geometry of the Zeros of a Polynomial in a Complex Variable. AMS, New York · Zbl 0038.15303 |
| [45] | Melman A. (1995). Numerical solution of a secular equation. Numer. Math. 69: 483–493 · Zbl 0821.65020 · doi:10.1007/s002110050104 |
| [46] | Mitrinović D.S. (1970). Analytic Inequalities. Springer, Heidelberg · Zbl 0199.38101 |
| [47] | Ostrowski A. (1940). Recherches sur la méthode de Gräffe et les zeros des polynômes et des series de Laurent. Acta Math. 72: 99–257 · Zbl 0023.33403 · doi:10.1007/BF02546329 |
| [48] | Ostrowski A. (1957). Über die Stetigkeit von charakteristischen Wurzeln in Abhängigkeit von den Matrizenelementen. Jahresber. deut. Mat.-Ver. 60: 40–42 · Zbl 0077.02302 |
| [49] | Ostrowski A. (1960). Solution of Equations and Systems of Equations. Academic, New York · Zbl 0115.11201 |
| [50] | Pap M. and Schipp F. (2004). Interpolation by rational functions. Ann. Univ. Sci. Bp. Sect. Comp. 24: 223–237 · Zbl 1108.41010 |
| [51] | Parlett B. (1967). Canonical decomposition of Hessenberg matrices. Math. Comput. 21(98): 223–227 · Zbl 0159.20501 · doi:10.1090/S0025-5718-1967-0228519-6 |
| [52] | Pellet M.A. (1881). Sur une mode de séparation des racines des équations et la formule de Lagrange. Bull. Sci. Math. 5: 393–395 · JFM 13.0074.01 |
| [53] | Reichel L. and Opfer G. (1990). Chebyshev-Vandermonde systems. Math. Comp. 57: 703–721 · Zbl 0755.65032 · doi:10.1090/S0025-5718-1991-1094957-9 |
| [54] | Robbins H. (1955). A remark on Stirling formula. Am. Math. Monthly 62: 26–29 · Zbl 0068.05404 · doi:10.2307/2308012 |
| [55] | Roberts L.G. (1972). Higher derivations and the Jordan canonical form of the companion matrix. Can. Math. Bull. 15(1): 143–144 · Zbl 0239.15009 · doi:10.4153/CMB-1972-027-6 |
| [56] | Rump M.S. (2003). Ten methods to bound multiple roots of polynomials. J. Comput. Appl. Math. 156: 403–432 · Zbl 1030.65046 · doi:10.1016/S0377-0427(03)00381-9 |
| [57] | Schappelle, R.H.: The inverse of the confluent Vandermonde matrix. IEEE Trans. Autom. Control, October, pp. 724–725 (1972) |
| [58] | Schönhage, A.: The fundamental theorem of algebra in terms of computational complexity. Technical report, Mathematisches Institut der Universität Tübingen, August, 1982, revised in July, 2004 |
| [59] | Smith B.T. (1970). Error bounds for zeros of a polynomial based upon Gerschgorin’s theorem. JACM 17(4): 661–674 · Zbl 0215.27305 · doi:10.1145/321607.321615 |
| [60] | Song Y. (2002). A note on the variation of the spectrum of an arbitrary matrix. Linear Algebra Appl. 342: 41–46 · Zbl 0995.15014 · doi:10.1016/S0024-3795(01)00447-5 |
| [61] | Stewart G. and Sun J. (1990). Matrix Perturbation Theory. Academic, New York · Zbl 0706.65013 |
| [62] | Sun J. (1996). On the variation of the spectrum of a normal matrix. Linear Algebra Appl. 246: 215–223 · Zbl 0867.15012 · doi:10.1016/0024-3795(94)00354-8 |
| [63] | Toh K. and Trefethen L.N. (1994). Pseudozeros of polynomials and pseudospectra of companion matrices. Numer. Math. 68: 403–425 · Zbl 0808.65053 · doi:10.1007/s002110050069 |
| [64] | Turnbull H.W. and Aitken A.C. (1952). An Introduction to the Theory of Canonical Matrices. Blackie, Glasgow · Zbl 0005.19303 |
| [65] | Tyrtyshnikov E.E. (1994). How bad are Hankel matrices?. Numer. Math. 67: 261–269 · Zbl 0797.65039 · doi:10.1007/s002110050027 |
| [66] | Verde-Star L. (1988). Inverses of generalized Vandermonde matrices. J. Math. Anal. Appl. 131: 341–353 · Zbl 0642.15005 · doi:10.1016/0022-247X(88)90210-7 |
| [67] | Wilf H.S. (1960). Almost diagonal matrices. Am. Math. Monthly 67: 431–434 · Zbl 0093.01603 · doi:10.2307/2309289 |
| [68] | Wilkinson J.H. (1965). The Algebraic Eigenvalue Problem. Oxford University Press, Oxford · Zbl 0258.65037 |
| [69] | Wilkinson J.H (1994). Rounding Errors in Algebraic Processes. Dover, New York · Zbl 0868.65027 |
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.
