Error analysis for matrix eigenvalue algorithm based on the discrete hungry Toda equation
Error analysis for matrix eigenvalue algorithm based on the discrete hungry Toda equation
复制标题
基于离散饥饿Toda方程的矩阵特征值算法误差分析
DOI：
10.1007/s11075-012-9606-6
复制
发表时间：
2012
影响因子：
2.1
通讯作者：
E. Ishiwata and Y. Nakamura
中科院分区：
文献类型：
--
作者：
A. Fukuda;Y. Yamamoto;M. Iwasaki;E. Ishiwata and Y. Nakamura
基于可积离散饥饿户田（dh户田）方程，设计了一类完全非负矩阵特征值的计算算法（AnnMatPura Appl，doi： 10.1007/s10231-011-0231-0 ).这被命名为dhToda算法，并且可以被视为众所周知的qd算法的扩展。通过引入原点移位，设计了移位的dhToda算法，以加快收敛速度。在本文中，我们首先提出了移位dhToda算法的微分形式，通过参考的qds（dqds）算法。减法运算的次数减少了，浮点运算中的抵消效应也降到了最低。其次，从混合误差分析的角度，我们研究了该算法在浮点运算中的数值稳定性。在此基础上，给出了新算法计算特征值的相对扰动界。从而验证了该算法计算的特征值具有较高的相对精度。数值例子与我们对算法的误差分析相一致。
Based on the integrable discrete hungry Toda (dhToda) equation, the authors designed an algorithm for computing eigenvalues of a class of totally nonnegative matrices (Ann Mat Pura Appl, doi: 10.1007/s10231-011-0231-0 ). This is named the dhToda algorithm, and can be regarded as an extension of the well-known qd algorithm. The shifted dhToda algorithm has been also designed by introducing the origin shift in order to accelerate the convergence. In this paper, we first propose the differential form of the shifted dhToda algorithm, by referring to that of the qds (dqds) algorithm. The number of subtractions is then reduced and the effect of cancellation in floating point arithmetic is minimized. Next, from the viewpoint of mixed error analysis, we investigate numerical stability of the proposed algorithm in floating point arithmetic. Based on this result, we give a relative perturbation bound for eigenvalues computed by the new algorithm. Thus it is verified that the eigenvalues computed by the proposed algorithm have high relative accuracy. Numerical examples agree with our error analysis for the algorithm.