ON THE SHIFTED QR ITERATION APPLIED TO COMPANION MATRICES
Dario A. Bini, Francesco Daddi, Luca Gemignani · 2004
Abstract. We show that the shifted QR iteration applied to a companion matrix F maintains the weakly semiseparable structure of F. More precisely, if Ai − αiI = QiRi, Ai+1: = RiQi + αiI, i = 0, 1,..., where A0 = F, then we prove that Qi, Ri and Ai are semiseparable matrices having semiseparability rank at most 1, 4 and 3, respectively. This structural property is used to design an algorithm for performing a single step of the QR iteration in just O(n) flops. The robustness and reliability of this algorithm is discussed. Applications to approximating polynomial roots are shown.