Computing Characteristic Polynomials from Eigenvalues
Computing Characteristic Polynomials from Eigenvalues
复制标题
DOI：
10.1137/100788392
复制
发表时间：
2011-02
期刊：
影响因子：
--
通讯作者：
Rizwana Rehman;Ilse C. F. Ipsen
中科院分区：
文献类型：
--
作者：
Rizwana Rehman;Ilse C. F. Ipsen
本文讨论了真实的或复矩阵A的特征多项式系数C_k的计算。我们分析了前向误差系数$c_k$时，他们计算的特征值$A$，是由MATLAB的多功能。特别是，我们推导出绝对和相对扰动边界的基本对称函数，我们反过来使用推导出扰动边界的系数$c_k$关于绝对和相对变化的特征值$\lambda_j$的$A$。我们提出了所谓的求和算法，用于从特征值$\lambda_j$计算系数$c_k$，这基本上是poly使用的算法。我们推导出求和算法的循环误差界和运行误差界。该算法具有前向稳定性，并具有一定的误差界。运行误差界可用于估计“动态”计算系数的准确性，并且它们往往比循环误差界不那么悲观。数值实验表明，我们的界限给出了有用的估计的精度系数$c_k$。特别是，边界确认，如果特征值是正的，并给予高的相对精度，聚计算系数$c_k$高的相对精度。
This paper concerns the computation of the coefficients $c_k$ of the characteristic polynomial of a real or complex matrix $A$. We analyze the forward error in the coefficients $c_k$ when they are computed from the eigenvalues of $A$, as is done by MATLAB's poly function. In particular, we derive absolute and relative perturbation bounds for elementary symmetric functions, which we use in turn to derive perturbation bounds for the coefficients $c_k$ with regard to absolute and relative changes in the eigenvalues $\lambda_j$ of $A$. We present the so-called Summation Algorithm for computing the coefficients $c_k$ from the eigenvalues $\lambda_j$, which is essentially the algorithm used by poly. We derive roundoff error bounds and running error bounds for the Summation Algorithm. The roundoff error bounds imply that the Summation Algorithm is forward stable. The running error bounds can be used to estimate the accuracy of the computed coefficients “on the fly,” and they tend to be less pessimistic than the roundoff error bounds. Numerical experiments illustrate that our bounds give useful estimates for the accuracy of the coefficients $c_k$. In particular, the bounds confirm that poly computes the coefficients $c_k$ to high relative accuracy if the eigenvalues are positive and given to high relative accuracy.