Global bounds of backward errors of polynomial eigenvalue problem solved by a companion linearization

被引：0
作者：
Ziyin Yang [1 ]
Zekun Wang [1 ]
Zongqi Cao [1 ]
Xiang Wang [1 ]
机构：
[1] School of Mathematics and Computer Science, Nanchang University, Jiangxi, Nanchang
来源：
Computational and Applied Mathematics | 2025年 / 44卷 / 4期
基金：
中国国家自然科学基金;
关键词：
Backward error; Linearization; Matrix polynomial; Scaling;
D O I：
10.1007/s40314-025-03168-0
中图分类号：
学科分类号：
摘要：
One common way to solve the polynomial eigenvalue problem (PEP) is to recast it by linearization, as a generalized eigenvalue problem (GEP) which can be solved by a backward stable algorithm such as QZ algorithm. QZ algorithm is backward stable for GEP, but may be backward unstable for PEP when the norms of the coefficient matrices for PEP vary widely. To improve the backward stability of PEP solved by a companion linearization, we combine the linearization with tropical scaling, and we also investigate the backward error of approximate eigenvalues of PEP via the tropically scaled linearization. Furthermore, we derive global upper bounds for the backward errors of approximate eigenvalues of PEP via the companion linearization without and with tropical scaling. In numerical experiments, we illustrate that the backward errors of the computed eigenvalues can be successfully improved by tropical scaling and well predicted by the global upper bounds. © The Author(s) under exclusive licence to Sociedade Brasileira de Matemática Aplicada e Computacional 2025.
引用
收藏
相关论文
共 17 条
  • [1] Bai Z., Demmel J., Dongarra J., Ruhe A., van der Vorst H., Templates for the solution of algebraic eigenvalue problems: a practical guide, (2000)
  • [2] Betcke T., Higham N.J., Mehrmann V., Schroder C., Tisseur F., Nlevp: a collection of nonlinear eigenvalue problems, ACM Trans Math Softw (TOMS), 39, pp. 1-28, (2013)
  • [3] Chen H., Meng J., Sakurai T., Wang X., Backward error analysis for linearizations in heavily damped quadratic eigenvalue problem, Numer Linear Algebra Appl, 26, (2019)
  • [4] Chen H., Wang T., Zhang C.-H., Wang X., Solving the quadratic eigenvalue problem expressed in non-monomial bases by the tropical scaling, Adv Comput Math, 50, pp. 1-28, (2024)
  • [5] Chen M., Ling L., Yun D., Proving the stability estimates of variational least-squares kernel-based methods, Comput Math Appl, 180, pp. 46-60, (2025)
  • [6] Fan H.-Y., Lin W.-W., Van Dooren P., Normwise scaling of second order polynomial matrices, SIAM J Matrix Anal Appl, 26, pp. 252-256, (2004)
  • [7] Gaubert S., Sharify M., Tropical scaling of polynomial matrices, Positive systems: proceedings of the third multidisciplinary international symposium on positive systems: theory and applications (POSTA 2009) Valencia, Spain, September 2-4, 2009, pp. 291-303, (2009)
  • [8] Higham D.J., Higham N.J., Structured backward error and condition of generalized eigenvalue problems, SIAM J Matrix Anal Appl, 20, pp. 493-512, (1998)
  • [9] Higham N.J., Li R.-C., Tisseur F., Backward error of polynomial eigenproblems solved by linearization, SIAM J Matrix Anal Appl, 29, pp. 1218-1241, (2008)
  • [10] Lancaster P., Tismenetsky M., The theory of matrices: with applications, (1985)
12