A note on the dqds algorithm with Rutishauser's shift for singular values

作者：Aishima Kensuke^*; Matsuo Takayasu; Murota Kazuo

来源：Japan Journal of Industrial and Applied Mathematics, 2011, 28(2): 251-262.

DOI：10.1007/s13160-011-0037-x

• Numerical linear algebra
• Singular value
• Iterative method

We consider the behavior of the dqds algorithm with Rutishauser's shift for computing singular values of matrices. In our previous paper Aishima et al. (Jpn J Ind Appl Math 25:65-81, 2008), it has been proved that the algorithm asymptotically achieves cubic convergence; i.e., possibly after some "transient" period with seemingly random shift choices, the system finally reaches its final phase of convergence, where Rutishauser's shift is chosen continuously and the convergence becomes cubic. In actual numerical examples, however, often the situation is far simpler. Once Rutishauser's shift becomes valid, it is continuously chosen, and we find no such "transient" phase in practice. In this paper we give a theoretical explanation for the phenomenon, to fill the gap between the numerical observation and the theory.

• 出版日期2011