< Terug naar vorige pagina


Min-Max Elementwise Backward Error for Roots of Polynomials and a Corresponding Backward Stable Root Finder

Tijdschriftbijdrage - Tijdschriftartikel

A new measure called min-max elementwise backward error is introducedfor approximate roots of scalar polynomials $p(z)$.Compared with the elementwise relative backward error, this new measure allows forlarger relative perturbations on the coefficients of $p(z)$ that do not participate muchin the overall backward error.By how much these coefficients can be perturbed is determinedvia an associated max-times polynomial and its tropical roots.An algorithm is designed for computing the roots of $p(z)$.It uses a companion linearization $C(z) = A-zB$ of $p(z)$ to which weadded an extra zero leading coefficient, andan appropriate two-sided diagonal scaling that balances $A$ and makes $B$graded in particular when there is variation in the magnitudeof the coefficients of $p(z)$.An implementation of the QZ algorithm with a strict deflation criterion foreigenvalues at infinity is then used to obtain approximations to the roots of $p(z)$.Under the assumption that this implementation of the QZ algorithm exhibits agraded backward error when $B$ is graded,we prove that our newalgorithm is min-max elementwise backward stable.Several numerical experiments show the superior performance of the new algorithmcompared with the MATLAB \texttt{roots} function.Extending the algorithm to polynomial eigenvalue problems leads toa new polynomial eigensolverthat exhibits excellent numerical behaviour compared with other existingpolynomial eigensolvers, as illustrated by many numerical tests.
Tijdschrift: Linear Algebra and Its Applications
ISSN: 0024-3795
Volume: 623
Pagina's: 454 - 477
Jaar van publicatie:2021