Volume 18, pp. 137-152, 2004.

On the shifted QR iteration applied to companion matrices

Dario A. Bini, Francesco Daddi, and Luca Gemignani

Abstract

We show that the shifted QR iteration applied to a companion matrix $F$ maintains the weakly semiseparable structure of $F$. More precisely, if $A_i-\alpha_i I=Q_iR_i$, $A_{i+1}:=R_iQ_i+\alpha_iI$, $i=0,1,\ldots$, where $A_0=F$, then we prove that $Q_i$, $R_i$ and $A_i$ 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.

Full Text (PDF) [180 KB], BibTeX

Key words

companion matrices, QR factorization, QR iteration, semiseparable matrices, eigenvalues, polynomial roots.

AMS subject classifications

65F15, 15A18, 65H17.

ETNA articles which cite this article

Vol. 30 (2008), pp. 144-167 Raf Vandebril, Marc Van Barel, and Nicola Mastronardi: A parallel QR-factorization/solver of quasiseparable matrices

Vol. 33 (2008-2009), pp. 126-150 Raf Vandebril, Marc Van Barel, and Nicola Mastronardi: A new iteration for computing the eigenvalues of semiseparable (plus diagonal) matrices