A positivity preserving inexact Noda iteration for computing the smallest eigenpair of a large irreducible M-matrix
A positivity preserving inexact Noda iteration for computing the smallest eigenpair of a large irreducible M-matrix
复制标题
用于计算大型不可约 M 矩阵的最小特征对的正性保留不精确 Noda 迭代
DOI：
10.1007/s00211-014-0677-2
复制
发表时间：
2015
影响因子：
2.1
通讯作者：
Liu Ching-Sung
中科院分区：
文献类型：
--
作者：
Jia Zhongxiao;Lin Wen-Wei;Liu Ching-Sung
本文在Noda迭代的基础上，提出了求大型不可约非奇异矩阵的最小特征值和相应的正特征向量的不精确Noda迭代(INI)。近似值的正性在应用中是至关重要的，如果近似值失去正性，则它们可能没有意义，无法解释。对于所涉及的内线性方程组，我们提出了两种不同的内容差策略，并证明了所得到的INI算法的收敛阶分别是全局线性和超线性的。所提出的INI算法是结构保持的，并且保持了近似特征向量的正性。我们还重温了精确的Noda迭代，并建立了一个新的二次收敛结果。首先对不可约非负矩阵的Perron根和正Perron向量的计算问题进行了研究，然后将其应用于不可约非奇异矩阵的最小特征对的计算。数值算例表明，所提出的INI算法是实用的，并且它们始终保持近似特征向量的正性。我们将它们与Jacobi-Davidson方法、隐式重新开始的Arnoldi方法和显式重新开始的Krylov-Schur方法进行了比较，这些方法都不能保证近似特征向量的正性，说明了INI算法的整体效率与后三种方法相当，并且可以显著高于后三种方法。
In this paper, based on the Noda iteration, we present inexact Noda iterations (INI), to find the smallest eigenvalue and the associated positive eigenvector of a large irreducible nonsingular-matrix. The positivity of approximations is critical in applications, and if the approximations lose the positivity then they may be meaningless and could not be interpreted. We propose two different inner tolerance strategies for solving the inner linear systems involved, and prove that the convergence of resulting INI algorithms is globally linear and superlinear with the convergence order, respectively. The proposed INI algorithms are structure preserving and maintains the positivity of approximate eigenvectors. We also revisit the exact Noda iteration and establish a new quadratic convergence result. All the above is first done for the problem of computing the Perron root and the positive Perron vector of an irreducible nonnegative matrix and is then adapted to computing the smallest eigenpair of the irreducible nonsingular-matrix. Numerical examples illustrate that the proposed INI algorithms are practical, and they always preserve the positivity of approximate eigenvectors. We compare them with the Jacobi–Davidson method, the implicitly restarted Arnoldi method and the explicitly restarted Krylov–Schur method, all of which cannot guarantee the positivity of approximate eigenvectors, and illustrate that the overall efficiency of the INI algorithms is competitive with and can be considerably higher than the latter three methods.