Fernandoʹs solution to Wilkinsonʹs problem: An application of double factorization

Suppose that one knows a very accurate approximation σ to an eigenvalue λ of a symmetric tridiagonal matrix T. A good way to approximate the eigenvector x is to discard an appropriate equation, say the rth, from the system (T − σI)x = 0 and then to solve the resulting underdetermined system in any of several stable ways. However the output x can be completely inaccurate if r is chosen poorly, and in the absence of a quick and reliable way to choose r, this method has lain neglected for over 35 years. Experts in boundary value problems have known about the special structure of the inverse of a tridiagonal matrix since the 1960s, and their double triangular factorization technique (down and up) gives directly the redundancy of each equation and so reveals the set of good choices for r. The relation of double factorization to the eigenvector algorithm of Godunov and his collaborators is described. The results extend to band matrices and to zero entries in eigenvectors, and have uses beyond eigenvector computation.