Structured backward error for palindromic polynomial eigenvalue problems, II: Approximate eigentriplets

Abstract

A detailed structured backward error analysis for four kinds of palindromic polynomial eigenvalue problems (PPEPs)

P(\lambda )\equiv \left({\displaystyle \sum _{l=\mathrm{0}}^d{{\displaystyle A}}_l{\lambda }^l}\right)x=\mathrm{0},{{\displaystyle A}}_{d-l}=\epsilon {{\displaystyle A}}_l^{★},L=\mathrm{0},\mathrm{1},\dots ,\left[{\displaystyle \frac{d}{\mathrm{2}}}\right],

for an approximate eigentriplet is performed, where ★ is one of the two actions: transpose and conjugate transpose, and \epsilon \in \{\pm \mathrm{1}\}. The analysis is concerned with estimating the smallest perturbation to P(\lambda); while preserving the respective palindromic structure, such that the given approximate eigentriplet is an exact eigentriplet of the perturbed PPEP. Previously, R. Li, W. Lin, and C. Wang [Numer. Math., 2010, 116(1): 95–122] had only considered the case of an approximate eigenpair for PPEP but commented that attempt for an approximate eigentriplet was unsuccessful. Indeed, the latter case is much more complicated. We provide computable upper bounds for the structured backward errors. Our main results in this paper are several informative and very sharp upper bounds that are capable of revealing distinctive features of PPEP from general polynomial eigenvalue problems (PEPs). In particular, they reveal the critical cases in which there is no structured backward perturbation such that the given approximate eigentriplet becomes an exact one of any perturbed PPEP, unless further additional conditions are imposed. These critical cases turn out to the same as those from the earlier studies on an approximate eigenpair.

Key words： Palindromic polynomial eigenvalue problem (PPEP); eigentriplet; structured backward error; error bound

References

1 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

2 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, 2008, 219: 237–252

3 Guo C, Lin W W. Solving a structured quadratic eigenvalue problem by a structurepreserving doubling algorithm. SIAM J Matrix Anal Appl, 2010, 31(5): 2784–2801

4 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, 2002, 351-352: 455–474

5 Hilliges A. Numerische Lösung von quadratischen Eigenwertproblemen mit Anwendungen in der Schiendynamik. Master's Thesis, Technical University Berlin, Germany, July 2004

6 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), Jyvaskyla, Finland, 2004

7 Huang T M, Li T, Lin W W, Wu C T. Numerical studies on structure-preserving algorithms for surface acoustic wave simulations. J Comput Appl Math, 2013, 244(1): 140–154

8 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, 2009, 30(4): 1566–1592

9 Huang T M, Lin W W, Su W S. Palindromic quadratization and structure-preserving algorithm for palindromic matrix polynomials of even degree. Numer Math, 2011, 118(4): 713–735

10 Ipsen I C F. Accurate eigenvalues for fast trains. SIAM News, 2004, 37(9)

11 Li R C, Lin W W, Wang C S. Structured backward error for palindromic polynomial eigenvalue problems. Numer Math, 2010, 116(1): 95–122

12 Liu C, Li R C. Structured backward error for palindromic polynomial eigenvalue problems, ii: Approximate eigentriplets. Technical Report 2016-12, Dept Math, Univ of Texas at Arlington, December 2016. www.uta.edu/math/preprint/

13 Liu X G, Wang Z X. A note on the backward errors for Hermite eigenvalue problems. Appl Math Comput, 2005, 165(2): 405–417

14 Lu L, Wang T, Kuo Y C, Li R C, Lin W W. A fast algorithm for fast train palindromic quadratic eigenvalue problems. SIAM J Sci Comput, 2016, 38(6): 3410–3429

15 Lu L, Yuan F, Li R C. A new look at the doubling algorithm for a structured palindromic quadratic eigenvalue problem. Numer Linear Algebra Appl, 2015, 22: 393–409

16 Mackey D S, Mackey N, Mehl C, Mehrmann V. Structured polynomial eigenvalue problems: Good vibrations from good linearizations. SIAM J Matrix Anal Appl, 2006, 28(4): 1029–1051

17 Schroder C. URV decomposition based structured methods for palindromic and even eigenvalue problems. Technical Report, Preprint 375, TU Berlin, Matheon, Germany, 2007

18 Schroder C. A QR-like algorithm for the palindromic eigenvalue problem. Technical Report, Preprint 388, TU Berlin, Matheon, Germany, 2007

19 Tisseur F. Backward error and condition of polynomial eigenvalue problems. Linear Algebra Appl, 2000, 309(1-3): 339–361

20 Xu H. On equivalence of pencils from discrete-time and continuous-time control. Linear Algebra Appl, 2006, 414: 97–124

21 Zaglmayr S, Schöberl J, Langer U. Eigenvalue problems in surface acoustic wave filter simulations. In: Bucchianico A, Mattheij R M M, Peletier M A, eds. Progress in Industrial Mathematics at ECMI 2004. Math Ind, Vol 8. Berlin: Springer, 2006, 74–98