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

Citations Over TimeTop 10% of 1979 papers

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.

Related Papers

• → Deconvolutions based on singular value decomposition and the pseudoinverse: a guide for beginners(1994)211 cited
• → On Accuracy Properties of One-Sided Bidiagonalization Algorithm and Its Applications(2005)3 cited
• → Fast truncated SVD of sparse and dense matrices on graphics processors(2023)1 cited
• P.C. Iterative Format of Newton Method(2002)
• → Appendix B: Singular Value Decomposition (SVD)(2017)