On Computing an Eigenvector of a Tridiagonal Matrix. Part I: Basic Results

We consider the solution of the homogeneous equation $(J-\lambda I) x =0$, where J is a tridiagonal matrix, $\lambda$ is a known eigenvalue, and x is the unknown eigenvector corresponding to $\lambda$. Since the system is underdetermined, x could be obtained by setting xk=1 and solving for the rest of the elements of x. This method is not entirely new, and it can be traced back to the times of Cauchy [Oeuvres Complétes IIe Série, Vol. 9, Gauthier--Villars, Paris, 1841]. In 1958, Wilkinson demonstrated that, in finite-precision arithmetic, the computed x is highly sensitive to the choice of k; the traditional practice of setting k=1 or k=n can lead to disastrous results. We develop algorithms to find optimal k which require an LDU and a UDL factorization (where L is lower bidiagonal, D is diagonal, and U is upper bidiagonal) of $J-\lambda I$ and are based on the theory developed by Fernando [On a Classical Method for Computing Eigenvectors, Numerical Algorithms Group Ltd, Oxford, 1995] for general matrices. We have also discovered new formulae (valid also for more general Hessenberg matrices) for the determinant of $J-\tau I$, which give better numerical results when the shifted matrix is nearly singular. These formulae could be used to compute eigenvalues (or to improve the accuracy of known estimates) based on standard zero finders such as Newton and Laguerre methods. The accuracy of the computed eigenvalues is crucial for obtaining small residuals for the computed eigenvectors. The algorithms for solving eigenproblems are embarrassingly parallel and hence suitable for modern architectures.