Geodesic
On the shifted QR iteration applied to companion matrices
Electronic transactions on numerical analysis, Tome 18 (2004), pp. 137-152
We show that the shifted QR iteration applied to a companion matrix F maintains the weakly semiseparable structure of F . More precisely, if Ai - $\alpha $iI = QiRi, Ai+1 := $RiQi + \alpha $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.
Classification : 65F15, 15A18, 65H17
Keywords: companion matrices, QR factorization, QR iteration, semiseparable matrices, eigenvalues, polynomial roots 
@article{ETNA_2004__18__a4,
     author = {Bini,  Dario A. and Daddi,  Francesco and Gemignani,  Luca},
     title = {On the shifted {QR} iteration applied to companion matrices},
     journal = {Electronic transactions on numerical analysis},
     pages = {137--152},
     year = {2004},
     volume = {18},
     zbl = {1066.65039},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2004__18__a4/}
}
TY  - JOUR
AU  - Bini,  Dario A.
AU  - Daddi,  Francesco
AU  - Gemignani,  Luca
TI  - On the shifted QR iteration applied to companion matrices
JO  - Electronic transactions on numerical analysis
PY  - 2004
SP  - 137
EP  - 152
VL  - 18
UR  - http://geodesic.mathdoc.fr/item/ETNA_2004__18__a4/
LA  - en
ID  - ETNA_2004__18__a4
ER  - 
%0 Journal Article
%A Bini,  Dario A.
%A Daddi,  Francesco
%A Gemignani,  Luca
%T On the shifted QR iteration applied to companion matrices
%J Electronic transactions on numerical analysis
%D 2004
%P 137-152
%V 18
%U http://geodesic.mathdoc.fr/item/ETNA_2004__18__a4/
%G en
%F ETNA_2004__18__a4
Bini,  Dario A.; Daddi,  Francesco; Gemignani,  Luca. On the shifted QR iteration applied to companion matrices. Electronic transactions on numerical analysis, Tome 18 (2004), pp. 137-152. http://geodesic.mathdoc.fr/item/ETNA_2004__18__a4/