Structured backward error for palindromic polynomial eigenvalue problems. (English) Zbl 1213.65063
For given \(n\times n\) matrices \(A_j\), a palindromic matrix polynomial takes the form
\[ P(\lambda) = \sum_{\ell = 0}^d \lambda^\ell A_\ell \quad A_{d-\ell} = \varepsilon A_\ell^\star, \quad \ell = 0,1,\dots,\lfloor d/2\rfloor, \]
where \(\star\) denotes the transpose or conjugate transpose of a matrix and \(\varepsilon \in \{+1,-1\}\). If \(P(\lambda)x =0\) for \(x \not = 0\) then \((\lambda,x)\) is called an eigenpair of \(P\). The paper is concerned with the following structured backward error problem: Given a pair \((\mu,z)\), determine the norm of the minimal perturbation \(\triangle P\) such that \(P + \triangle P\) remains palindromic and \((\mu,z)\) becomes an eigenpair of \(P + \triangle P\). Here, the norm of \(\triangle P\) is understood as a weighted spectral or Frobenius norm of its coefficient matrices. Computable expressions for the structured backward error for all instances of palindromic matrix polynomials are provided. Moreover, numerical experiments highlight the critical cases \(|\mu| = 1\) (when \(\star\) denotes the conjugate transpose) and \(\mu = \pm 1\) (when \(\star\) denotes the transpose).
\[ P(\lambda) = \sum_{\ell = 0}^d \lambda^\ell A_\ell \quad A_{d-\ell} = \varepsilon A_\ell^\star, \quad \ell = 0,1,\dots,\lfloor d/2\rfloor, \]
where \(\star\) denotes the transpose or conjugate transpose of a matrix and \(\varepsilon \in \{+1,-1\}\). If \(P(\lambda)x =0\) for \(x \not = 0\) then \((\lambda,x)\) is called an eigenpair of \(P\). The paper is concerned with the following structured backward error problem: Given a pair \((\mu,z)\), determine the norm of the minimal perturbation \(\triangle P\) such that \(P + \triangle P\) remains palindromic and \((\mu,z)\) becomes an eigenpair of \(P + \triangle P\). Here, the norm of \(\triangle P\) is understood as a weighted spectral or Frobenius norm of its coefficient matrices. Computable expressions for the structured backward error for all instances of palindromic matrix polynomials are provided. Moreover, numerical experiments highlight the critical cases \(|\mu| = 1\) (when \(\star\) denotes the conjugate transpose) and \(\mu = \pm 1\) (when \(\star\) denotes the transpose).
Reviewer: Daniel Kressner (Lausanne)
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 15A54 | Matrices over function rings in one or more variables |
References:
| [1] | Bora S.: Structured eigenvalue condition number and backward error of a class of polynomial eigenvalue problems. SIAM J. Matrix Anal. Appl. 31(3), 900–917 (2009) · Zbl 1201.65083 · doi:10.1137/060675769 |
| [2] | Bunch J.R., Demmel J., Van Loan C.F.: The strong stability of algorithms for solving symmetric linear systems. SIAM J. Matrix Anal. Appl. 10(4), 494–499 (1989) · Zbl 0687.65021 · doi:10.1137/0610035 |
| [3] | Byers, R., Mackey, D.S., Mehrmann, V., Xu, H.: Symplectic, BVD, and palindromic approaches to discrete-time control problems. Technical report, Preprint 14-2008, Institute of Mathematics, Technische Universität Berlin, 2008 |
| [4] | Chu E.K.-W., Hwang T.-M., Lin W.-W., Wu C.-T.: Vibration of fast trains, palindromic eigenvalue problems and structure-preserving doubling algorithms. J. Comput. Appl. Math. 229, 237–252 (2008) · Zbl 1141.74025 · doi:10.1016/j.cam.2007.07.016 |
| [5] | Higham D.J., Higham N.J.: Backward error and condition of structured linear systems. SIAM J. Matrix Anal. Appl. 13(1), 162–175 (1992) · Zbl 0747.65028 · doi:10.1137/0613014 |
| [6] | Higham D.J., Higham N.J.: Structured backward error and condition of generalized eigenvalue problems. SIAM J. Matrix Anal. Appl. 20(2), 493–512 (1998) · Zbl 0935.65032 · doi:10.1137/S0895479896313188 |
| [7] | Higham N.J., Tisseur F., Van Dooren P.: Detecting a definite Hermitian pair and a hyperbolic or elliptic quadratic eigenvalue problem, and associated nearness problems. Linear Algebra Appl. 351–352, 455–474 (2002) · Zbl 1004.65045 · doi:10.1016/S0024-3795(02)00281-1 |
| [8] | Hilliges, A.: Numerische Lösung von quadratischen Eigenwertproblemen mit Anwendungen in der Schiendynamik. Master’s thesis, Technical University Berlin, Germany, July 2004 |
| [9] | Hilliges, A., Mehl, C., Mehrmann, V.: On the solution of palindramic eigenvalue problems. In: Proceedings of 4th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS), Jyväskylä, Finland, 2004 |
| [10] | Hochstenbach M.E., Plestenjak B.: Backward error, condition numbers, and pseudospectra for the multiparameter eigenvalue problem. Linear Algebra Appl. 375, 63–81 (2003) · Zbl 1048.65034 · doi:10.1016/S0024-3795(03)00613-X |
| [11] | Huang T.-M., Lin W.-W., Qian J.: Numerically stable, structure-preserving algorithms for palindromic quadratic eigenvalue problems arising from vibration of fast trains. SIAM J. Matrix Anal. Appl. 30(4), 1566–1592 (2009) · Zbl 1180.65043 · doi:10.1137/080713550 |
| [12] | Ipsen I.C.F.: Accurate eigenvalues for fast trains. SIAM News 37, 1–2 (2004) |
| [13] | Liu X.-G., Wang Z.-X.: A note on the backward errors for Hermite eigenvalue problems. Appl. Math. Comput. 165(2), 405–417 (2005) · Zbl 1072.65055 · doi:10.1016/j.amc.2004.06.020 |
| [14] | Mackey D.S., Mackey N., Mehl C., Mehrmann V.: Structured polynomial eigenvalue problems: good vibrations from good linearizations. SIAM J. Matrix Anal. Appl. 28, 1029–1051 (2006) · Zbl 1132.65028 · doi:10.1137/050628362 |
| [15] | Mackey D.S., Mackey N., Mehl C., Mehrmann V.: Vector spaces of linearizations for matrix polynomials. SIAM J. Matrix Anal. Appl. 28, 971–1004 (2006) · Zbl 1132.65027 · doi:10.1137/050628350 |
| [16] | Schröder, C.: A QR-like algorithm for the palindromic eigenvalue problem. Technical report, Preprint 388, TU Berlin, Matheon, Germany, 2007 |
| [17] | Schröder, C.: URV decomposition based structured methods for palindromic and even eigenvalue problems. Technical report, Preprint 375, TU Berlin, MATHEON, Germany, 2007 |
| [18] | Tisseur F.: Backward error and condition of polynomial eigenvalue problems. Linear Algebra Appl. 309, 339–361 (2000) · Zbl 0955.65027 · doi:10.1016/S0024-3795(99)00063-4 |
| [19] | Tisseur F.: Stability of structured Hamiltonian eigensolvers. SIAM J. Matrix Anal. Appl. 23(1), 103–125 (2001) · Zbl 0996.65041 · doi:10.1137/S0895479800368007 |
| [20] | Tisseur F., Meerbergen K.: The quadratic eigenvalue problem. SIAM Rev. 43, 235–386 (2001) · Zbl 0985.65028 · doi:10.1137/S0036144500381988 |
| [21] | Xu H.: On equivalence of pencils from discrete-time and continuous-time control. Linear Algebra Appl. 414, 97–124 (2006) · Zbl 1134.15300 · doi:10.1016/j.laa.2005.09.015 |
| [22] | Zaglmayr, S.: Eigenvalue problems in saw-filter simulations. Diplomarbeit, Institute of Computational Mathematics, Johannes Kepler University Linz, Linz, Austria, 2002 |
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.
