Inexact inverse iteration for symmetric matrices
Inexact inverse iteration for symmetric matrices
复制标题
DOI：
10.1016/j.laa.2005.11.019
复制
发表时间：
2006-07
影响因子：
1.1
通讯作者：
Jörg Berns-Müller;I. Graham;A. Spence
中科院分区：
文献类型：
--
作者：
Jörg Berns-Müller;I. Graham;A. Spence
本文分析了实对称特征值问题Av=λv的不精确逆迭代，我们的分析适用于当A大且稀疏时的情形，其中使用迭代方法来求解所产生的移位线性方程组(A−σi)y=x。我们提出了一个与所使用的不精确求解器的性质无关的收敛理论，尽管强调了瑞利商的使用，但我们的分析也扩展到了对移位和不精确求解器策略的非常一般的选择。此外，收敛框架允许我们既处理标准的预条件，又提出对Simoncini和Eldén引入的变化的新分析(BIT，第42卷，第159-182页，2002年)。此外，我们还分析了使用预条件MinRes作为非精确求解器时内迭代解的性能。这一分析提供了描述性的界限，被证明可以很好地预测在实践中观察到的实际行为。此外，还解释了Simoncini和Eldén提出的修正在性能上比标准预条件形式的改进。重要的是，我们的分析表明，让移位趋于特征值，就像使用瑞利商的情况一样，不会显著损害移位系统的迭代方法的性能。文中给出的数值结果说明了理论的正确性。
In this paper we analyse inexact inverse iteration for the real symmetric eigenvalue problem Av=λv. Our analysis is designed to apply to the case when A is large and sparse and where iterative methods are used to solve the shifted linear systems (A−σI)y=x which arise. We present a convergence theory that is independent of the nature of the inexact solver used, and, though the use of the Rayleigh quotient is emphasised, our analysis also extends to quite general choices for shift and inexact solver strategies. Additionally, the convergence framework allows us to treat both standard preconditioning and to present a new analysis of the variation introduced by Simoncini and Eldén (BIT, vol. 42, pp.159–182, 2002). Also, we provide an analysis of the performance of inner iteration solves when preconditioned MINRES is used as the inexact solver. This analysis provides descriptive bounds which are shown to predict well the actual behaviour observed in practice. Also, it explains the improvement in performance of the modification introduced by Simoncini and Eldén over the standard preconditioned form. Importantly, our analysis shows that letting the shift tend to the eigenvalue, as is the case if the Rayleigh quotient is used, does not harm significantly the performance of the iterative method for the shifted systems. Throughout the paper numerical results are given to illustrate the theory.