论文标题
精确计算赫米尔矩阵特征值的数值方法和一般矩阵的奇异值
Numerical methods for accurate computation of the eigenvalues of Hermitian matrices and the singular values of general matrices
论文作者
论文摘要
本文综述了用于计算Hermitian矩阵特征值以及一般值和某些结构化矩阵的奇异值的数值方法。重点是方法背后的主要原理，即使在常规方法不适合条件的情况下，也可以保证高精度。首先，结果表明，在有限的精度实现算法中，误差的特定结构可以更好地衡量灵敏度，尽管经典条件号很大，但仍可以高精度地计算。有限精确计算产生的这种结构化误差在某些算法中，例如从入口或列的小，这比通常在Frobenius矩阵标准中测量的通常所考虑的误差要好得多。针对Hermitian矩阵的这种结构化扰动的特殊量身定制的扰动理论可确保计算出的特征值的相对误差更好。 ％ 其次，我们回顾了一种非常规的方法，可以准确计算一些臭名昭著的结构化矩阵（例如，例如Cauchy，Vandermonde和Hankel矩阵。精确算法的独特特征是使用定义此类矩阵以获得非正交分解的固有参数，例如\ textsf {ldu}分解，然后计算如此计算的因子的产物的奇异值。也讨论了最新软件的状态。
This paper offers a review of numerical methods for computation of the eigenvalues of Hermitian matrices and the singular values of general and some classes of structured matrices. The focus is on the main principles behind the methods that guarantee high accuracy even in the cases that are ill-conditioned for the conventional methods. First, it is shown that a particular structure of the errors in a finite precision implementation of an algorithm allows for a much better measure of sensitivity and that computation with high accuracy is possible despite a large classical condition number. Such structured errors incurred by finite precision computation are in some algorithms e.g. entry-wise or column-wise small, which is much better than the usually considered errors that are in general small only when measured in the Frobenius matrix norm. Specially tailored perturbation theory for such structured perturbations of Hermitian matrices guarantees much better bounds for the relative errors in the computed eigenvalues. % Secondly, we review an unconventional approach to accurate computation of the singular values and eigenvalues of some notoriously ill-conditioned structured matrices, such as e.g. Cauchy, Vandermonde and Hankel matrices. The distinctive feature of accurate algorithms is using the intrinsic parameters that define such matrices to obtain a non-orthogonal factorization, such as the \textsf{LDU} factorization, and then computing the singular values of the product of thus computed factors. The state of the art software is discussed as well.
