Inverse Iteration, Ill-Conditioned Equations and Newton’s Method

Abstract

Inverse iteration is one of the most widely used algorithms in practical linear algebra but an understanding of its main numerical properties has developed piecemeal over the last thirty years: a major source of misunderstanding is that it requires the solution of very ill-conditioned systems of equations. We describe closely related algorithms which avoid these ill-conditioned systems and explain why the standard inverse iteration algorithm may nevertheless be preferable. The discussion covers the generalized problems $Ax - \lambda Bx$ and $(A_r \lambda ^r + \cdots + A_1 \lambda + A_0 )x = 0$ in addition to the standard problem. The case when $A - \lambda I$ is almost singular to the working accuracy has only recently been understood, mainly through the work of Varah. The final sections give a detailed account of the current state of this work, concluding with an analysis based on the singular value decomposition.