Relative Perturbation Techniques for Eigenvalue and Singular Value Decompositions

该项目开发了微扰技术，用于推导奇异值和特征值的相对误差界限，以及相对间隙下奇异向量和特征向量的误差角度界限。基于这些边界的紧缩和收敛准则有可能导致高精度和高效的qr型和Jacobi算法用于计算特征值，奇异值和URV分解。在矩阵B的奇异值分解的背景下，研究了一类表示不改变B秩的所有可能的微扰，特别地，它包括双对角和双环矩阵的分量相对微扰，以及在块三角形矩阵中湮灭非对角块的微扰。迄今为止，对于双对角矩阵的奇异值和向量，已有的许多相对摄动界都是由这类摄动的一般结果导出的。对于双环矩阵、三角矩阵和移位三角矩阵的奇异值和奇异向量，也证明了新的摄动结果。这些结果推广到广义特征值问题，以及结构矩阵和非厄米矩阵的特征值问题。

This project develops perturbation techniques for deriving bounds on the relative error of singular values and eigenvalues, as well as bounds on the error angles of singular vectors and eigenvectors in terms of a relative gap. Deflation and convergence criteria based on these bounds have the potential to lead to highly accurate and efficient QR-type and Jacobi algorithms for computing eigenvalue, singular value and URV decompositions. In the context of the singular value decomposition of a matrix B, a class of perturbations is investigated which represents all possible that do not change the rank of B. In particular, it includes componentwise relative perturbations of bidiagonal and biacyclic matrices, and perturbations that annihilate an offdiagonal block in a block triangular matrix. So far, many existing relative perturbations bounds have been derived for singular values and vectors of bidiagonal matrices from general results for this class of perturbations. Also, new perturbation results have been proved for singular values and vectors of biacyclic, triangular and shifted triangular matrices. These results are extended to the generalized eigenvalue problem, and to the eigenvalue problems for structured and non-Hermitian matrices.