标题： 近似特征值和奇异值的子空间方法的误差界 显示英文标题

标题： Sharp error bounds for approximate eigenvalues and singular values from subspace methods

摘要： 子空间方法常用于寻找大规模矩阵的近似特征值和奇异值。 一旦找到子空间，Rayleigh-Ritz 方法（针对对称特征值问题）和 Petrov-Galerkin 投影（针对奇异值）便是提取特征值和奇异值的实际方法。 在这项工作中，我们推导了通过 Rayleigh-Ritz 过程获得的近似特征值的二次误差界。 我们的界利用了极值特征对通常比其余部分更快收敛的事实，因此具有更小的残差 $\|A\widehat x_i-\theta_i\widehat x_i\|_2$，其中 $(\theta_i,\widehat x_i)$ 是一个 Ritz 对（近似特征对）。 证明使用了 Rayleigh-Ritz 方法背后的扰动矩阵的结构来限制其特征向量的分量。 这样，我们得到了一种形式的界 $c\frac{\|A\widehat x_i-\theta_i\widehat x_i\|_2^2}{\eta_i}$，其中 $\eta_i$ 大致是第 $i$个 Ritz 值与未被 Ritz 过程近似的特征值之间的间隙，而 $c> 1$ 是一个适度的标量。 我们的界适应每个 Ritz 值，并且对聚类的 Ritz 值具有鲁棒性，这是现有结果的关键改进。 我们进一步表明该界是渐近精确的，并将其推广到任意实矩阵的奇异值。 最后，我们将这些界应用于计算特征值和奇异值的几种方法，并在多种计算环境中展示我们界的确切性，包括 Krylov 方法和随机算法。 显示英文摘要

摘要： Subspace methods are commonly used for finding approximate eigenvalues and singular values of large-scale matrices. Once a subspace is found, the Rayleigh-Ritz method (for symmetric eigenvalue problems) and Petrov-Galerkin projection (for singular values) are the de facto method for extraction of eigenvalues and singular values. In this work we derive quadratic error bounds for approximate eigenvalues obtained via the Rayleigh-Ritz process. Our bounds take advantage of the fact that extremal eigenpairs tend to converge faster than the rest, hence having smaller residuals $\|A\widehat x_i-\theta_i\widehat x_i\|_2$, where $(\theta_i,\widehat x_i)$ is a Ritz pair (approximate eigenpair). The proof uses the structure of the perturbation matrix underlying the Rayleigh-Ritz method to bound the components of its eigenvectors. In this way, we obtain a bound of the form $c\frac{\|A\widehat x_i-\theta_i\widehat x_i\|_2^2}{\eta_i}$, where $\eta_i$ is roughly the gap between the $i$th Ritz value and the eigenvalues that are not approximated by the Ritz process, and $c> 1$ is a modest scalar. Our bound is adapted to each Ritz value and is robust to clustered Ritz values, which is a key improvement over existing results. We further show that the bound is asymptotically sharp, and generalize it to singular values of arbitrary real matrices. Finally, we apply these bounds to several methods for computing eigenvalues and singular values, and illustrate the sharpness of our bounds in a number of computational settings, including Krylov methods and randomized algorithms.