Forward Instability of Tridiagonal QR

He QR algorithm is the standard method for finding all the eigenvalues of a symmetric tridiagonal matrix. It produces a sequence of similar tridiagonals. It is well known that the QR transformation from T to $\hat{T} $ is backward stable. That means that the computed $\hat{T} $ is exactly orthogonally similar to a matrix close to T. It is also known that sometimes the computed $\hat{T} $ is not close to the exact $\hat{T} $. This is caused by the occasional extreme sensitivity of $\hat{T} $ to changes in T or the shift, and will be referred to as forward instability of the (computed) QR algorithm. For the purpose of computing eigenvalues the property of backward stability is all that is required. However, the QR transformation has other uses and then forward stability is needed. This paper gives examples, analyzes the forward instability, and shows that it occurs only when the shift causes “premature deflation.” It is shown that forward stability is governed by the size of the last entry in normalized eigenvectors of leading principal submatrices, and the extreme values of the derivative of each entry in $\hat{T} $ as a function of the shift are found.