A quadratically convergent algorithm based on matrix equations for inverse eigenvalue problems
A quadratically convergent algorithm based on matrix equations for inverse eigenvalue problems
复制标题
DOI：
10.1016/j.laa.2017.05.019
复制
发表时间：
2017-05
影响因子：
1.1
通讯作者：
Kensuke Aishima
中科院分区：
文献类型：
--
作者：
Kensuke Aishima
提出了一种求解矩阵方程反对称特征值问题的二次收敛算法。基本思想是在最近的一项研究中看到的Ogita和Aishima，而他们得出一个有效的迭代细化算法的对称特征值问题使用特殊的矩阵方程。换句话说，本研究被解释为基于矩阵方程的特征值问题和逆特征值问题的二次收敛算法的统一观点。据我们所知，这种统一的算法开发是第一次提供。由于所提出的特征值反问题的算法可以看作是求解矩阵方程的牛顿法，因此很自然地证明了算法的二次收敛性。我们的算法被解释为一个改进的版本的凯莱变换方法的逆特征值问题。虽然凯莱变换方法是有效的迭代方法之一，凯莱变换需要O（n3）的算术运算，以产生一个正交矩阵使用反对称矩阵在每次迭代。我们的算法可以细化正交性，而无需凯莱变换，这减少了每次迭代中的操作。值得注意的是，我们的方法克服了Cayley变换方法的限制，反标准特征值问题，从而在广义特征值反问题的扩展。
We propose a quadratically convergent algorithm for inverse symmetric eigenvalue problems based on matrix equations. The basic idea is seen in a recent study by Ogita and Aishima, while they derive an efficient iterative refinement algorithm for symmetric eigenvalue problems using special matrix equations. In other words, this study is interpreted as a unified view on quadratically convergent algorithms for eigenvalue problems and inverse eigenvalue problems based on matrix equations. To the best of our knowledge, such a unified development of algorithms is provided for the first time. Since the proposed algorithm for the inverse eigenvalue problems can be regarded as the Newton's method for the matrix equations, the quadratic convergence is naturally proved. Our algorithm is interpreted as an improved version of the Cayley transform method for the inverse eigenvalue problems. Although the Cayley transform method is one of the effective iterative methods, the Cayley transform takes O (n 3) arithmetic operations to produce an orthogonal matrix using a skew-symmetric matrix in each iteration. Our algorithm can refine orthogonality without the Cayley transform, which reduces the operations in each iteration. It is worth noting that our approach overcomes the limitation of the Cayley transform method to the inverse standard eigenvalue problems, resulting in an extension to inverse generalized eigenvalue problems.