On the stability of computing polynomial roots via confederate linearizations (Q2814445)

The authors are primarily interested in the normwise stability of linearization-based root finding methods for polynomials expressed in certain nonmonomial bases (Chebyshev basis or general orthogonal polynomial basis). The paper has three main goals. First, the authors prove normwise stability when the polynomial is properly scaled and the QZ algorithm is applied to a comrade pencil associated with a Jacobi orthogonal polynomial. This study is compared with the more commonly used QR algorithm. Second, they extend a result by Arnold that leads to a first-order expansion of the backward error when the eigenvalues are computed via QR, which shows that the method can be unstable. Based on the analysis they suggest how to choose between QR and QZ. Finally, they focus on the special case of the Chebyshev basis and on the problem of finding real roots of a general function on an interval. In addition, they discuss how to compute accurate roots.