Rigorous Proof of Cubic Convergence for the dqds Algorithm for Singular Values
Aishima, Kensuke ; Matsuo, Takayasu ; Murota, Kazuo
Japan J. Indust. Appl. Math., Tome 25 (2008) no. 1, p. 65-81 / Harvested from Project Euclid
Fernando and Parlett observed that the dqds algorithm for singular values can be made extremely efficient with Rutishauser's choice of shift; in particular it enjoys ``local'' (or one-step) cubic convergence at the final stage of iteration, where a certain condition is to be satisfied. Their analysis is, however, rather heuristic and what has been shown is not sufficient to ensure asymptotic cubic convergence in the strict sense of the word. The objective of this paper is to specify a concrete procedure for the shift strategy and to prove with mathematical rigor that the algorithm with this shift strategy always reaches the ``final stage'' and enjoys asymptotic cubic convergence.
Publié le : 2008-02-15
Classification:  singular value,  bidiagonal matrix,  dqds algorithm
@article{1208196865,
     author = {Aishima, Kensuke and Matsuo, Takayasu and Murota, Kazuo},
     title = {Rigorous Proof of Cubic Convergence for the dqds Algorithm for Singular Values},
     journal = {Japan J. Indust. Appl. Math.},
     volume = {25},
     number = {1},
     year = {2008},
     pages = { 65-81},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1208196865}
}
Aishima, Kensuke; Matsuo, Takayasu; Murota, Kazuo. Rigorous Proof of Cubic Convergence for the dqds Algorithm for Singular Values. Japan J. Indust. Appl. Math., Tome 25 (2008) no. 1, pp.  65-81. http://gdmltest.u-ga.fr/item/1208196865/