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]

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

< Back