Min-max elementwise backward error for roots of polynomials and a corresponding backward stable root finder

Abstract A new measure called min-max elementwise backward error is introduced for approximate roots of scalar polynomials p ( z ) . Compared with the elementwise relative backward error, this new measure allows for larger relative perturbations on the coefficients of p ( z ) that do not participate much in the overall backward error. By how much these coefficients can be perturbed is determined via 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 − z B of p ( z ) to which we added an extra zero leading coefficient, and an appropriate two-sided diagonal scaling that balances A and makes B graded in particular when there is variation in the magnitude of the coefficients of p ( z ) . An implementation of the QZ algorithm with a strict deflation criterion for eigenvalues 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 a graded backward error when B is graded, we prove that our new algorithm is min-max elementwise backward stable. Several numerical experiments show the superior performance of the new algorithm compared with the MATLAB roots function. Extending the algorithm to polynomial eigenvalue problems leads to a new polynomial eigensolver that exhibits excellent numerical behaviour compared with other existing polynomial eigensolvers, as illustrated by many numerical tests.