  The roots of a monic polynomial expressed in a Chebyshev basis are known to
be the eigenvalues of the so-called colleague matrix, which is a Hessenberg
matrix that is the sum of a symmetric tridiagonal matrix and a rank-1 matrix.
The rootfinding problem is thus reformulated as an eigenproblem, making the
computation of the eigenvalues of such matrices a subject of significant
practical importance. In this manuscript, we describe an $O(n^2)$ explicit
structured QR algorithm for colleague matrices and prove that it is
componentwise backward stable, in the sense that the backward error in the
colleague matrix can be represented as relative perturbations to its
components. A recent result of Noferini, Robol, and Vandebril shows that
componentwise backward stability implies that the backward error $\delta c$ in
the vector $c$ of Chebyshev expansion coefficients of the polynomial has the
bound $\lVert \delta c \rVert \lesssim \lVert c \rVert u$, where $u$ is machine
precision. Thus, the algorithm we describe has both the optimal backward error
in the coefficients and the optimal cost $O(n^2)$. We illustrate the
performance of the algorithm with several numerical examples.
