A note on the convergence theorem of the tridiagonal QR algorithm with Wilkinson's shift

作者：Aishima Kensuke^*

来源：Japan Journal of Industrial and Applied Mathematics, 2015, 32(2): 465-487.

DOI：10.1007/s13160-015-0171-y

• Numerical linear algebra
• Eigensolver
• QR algorithm
• Symmetric tridiagonal matrices
• Wilkinson's shift
• Convergence rate

We discuss the convergence rate of the QR algorithm with Wilkinson's shift for tridiagonal symmetric eigenvalue problems. It is well known that the convergence rate is theoretically at least quadratic, and practically better than cubic for most matrices. In an effort to derive the convergence rate, the limiting patterns of some lower right submatrices have been intensively investigated. In this paper, we first describe a new limiting pattern of the lower right 3-by-3 submatrix with a concrete example, and then prove that the convergence rate of this new pattern is strictly cubic. In addition, we stress that our analysis identifies three classes of the limiting patterns of the tridiagonal QR algorithm with Wilkinson's shift.

• 出版日期2015-7