×

zbMATH — the first resource for mathematics

Sharp error bounds for Ritz vectors and approximate singular vectors. (English) Zbl 1441.65038
Let \(A\in\mathbb{C}^{n\times n}\) be Hermitian with an eigenpair \((\lambda,x)\) and its approximation \((\hat{\lambda},\hat{x})\), \(\|\hat{x}\|=1\), where \(\|\cdot\|\) denotes the Euclidean norm. Define \[ r=A\hat{x}-\hat{\lambda}\hat{x},\quad\mathrm{gap}_c=\min_{\lambda\ne\mu\in\sigma(A)}|\mu-\hat{\lambda}|, \] where \(\sigma(A)\) stands for the spectrum of \(A\). C. Davis and W. M. Kahan [SIAM J. Numer. Anal. 7, 1–46 (1970; Zbl 0198.47201)] proved that the angle between \(x\) and \(\hat{x}\) satisfies \[ \sin\angle(x,\hat{x})\le\frac{\|r\|}{\mathrm{gap}_c}. \] This bound for \(\sin\angle(x,\hat{x})\) is the best possible using only \(\|r\|\) and \(\mathrm{gap}_c\). If \(\|r\|\ge\mathrm{gap}_c\), then these quantities therefore tell nothing about the accuracy of \(\hat{x}\).
However, suppose that \((\hat{\lambda},\hat{x})\) has been computed by the Rayleigh-Ritz process (RR in short). Using this additional information, the author improves the Davis-Kahan bound, obtaining nontrivial bounds in all cases. He also pursues this topic further in three directions. First, to find error bounds for angles between invariant subspaces computed by RR. Second, to present their variants concerning the accuracy of singular vectors and singular subspaces of \(A\in\mathbb{C}^{m\times n}\), \(m\ge n\), computed by the Petrov-Galerkin projection method. Third, to extend the discussion to self-adjoint operators on a Hilbert space.
MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
15A42 Inequalities involving eigenvalues and eigenvectors
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Templates for the Solution of Algebraic Eigenvalue Problems, A practical guide, Software, Environments, and Tools 11, xxx+410 pp. (2000), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 0965.65058
[2] Davis, Chandler; Kahan, W. M., The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal., 7, 1-46 (1970) · Zbl 0198.47201
[3] chebfunguide T. A. Driscoll, N. Hale, and L. N. Trefethen. \newblock \em Chebfun Guide. \newblock Pafnuty Publications, 2014.
[4] \bibfolland1992fourierbook author=Folland, Gerald B., title=Fourier Analysis and its Applications, series=The Wadsworth & Brooks/Cole Mathematics Series, pages=x+433, publisher=Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, date=1992, isbn=0-534-17094-3, review=\MR1145236,
[5] Golub, Gene H.; Van Loan, Charles F., Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences, xiv+756 pp. (2013), Johns Hopkins University Press, Baltimore, MD · Zbl 1268.65037
[6] Halko, N.; Martinsson, P. G.; Tropp, J. A., Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53, 2, 217-288 (2011) · Zbl 1269.65043
[7] Horn, Roger A.; Johnson, Charles R., Topics in matrix analysis, viii+607 pp. (1991), Cambridge University Press, Cambridge · Zbl 0729.15001
[8] Hunter, John K.; Nachtergaele, Bruno, Applied Analysis, xiv+439 pp. (2001), World Scientific Publishing Co., Inc., River Edge, NJ · Zbl 0981.46002
[9] Kato, Tosio, Perturbation Theory for Linear Operators, Classics in Mathematics, xxii+619 pp. (1995), Springer-Verlag, Berlin · Zbl 0836.47009
[10] Knyazev, Andrew V., New estimates for Ritz vectors, Math. Comp., 66, 219, 985-995 (1997) · Zbl 0870.65045
[11] Knyazev, Andrew V., Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23, 2, 517-541 (2001) · Zbl 0992.65028
[12] Li, Chi-Kwong; Li, Ren-Cang, A note on eigenvalues of perturbed Hermitian matrices, Linear Algebra Appl., 395, 183-190 (2005) · Zbl 1068.15027
[13] Li, Ruipeng; Xi, Yuanzhe; Vecharynski, Eugene; Yang, Chao; Saad, Yousef, A thick-restart Lanczos algorithm with polynomial filtering for Hermitian eigenvalue problems, SIAM J. Sci. Comput., 38, 4, A2512-A2534 (2016) · Zbl 1348.65071
[14] Li, Ren-Cang; Zhang, Lei-Hong, Convergence of the block Lanczos method for eigenvalue clusters, Numer. Math., 131, 1, 83-113 (2015) · Zbl 1334.65073
[15] Nakatsukasa, Yuji, Accuracy of singular vectors obtained by projection-based SVD methods, BIT, 57, 4, 1137-1152 (2017) · Zbl 1386.65116
[16] Ovtchinnikov, E., Cluster robust error estimates for the Rayleigh-Ritz approximation. I. Estimates for invariant subspaces, Linear Algebra Appl., 415, 1, 167-187 (2006) · Zbl 1157.65350
[17] Parlett, Beresford N., The Symmetric Eigenvalue Problem, Classics in Applied Mathematics 20, xxiv+398 pp. (1998), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 0885.65039
[18] Saad, Yousef, Numerical Methods for Large Eigenvalue Problems, Classics in Applied Mathematics 66, xvi+276 pp. (2011), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1242.65068
[19] Stewart, G. W.; Sun, Ji Guang, Matrix Perturbation Theory, Computer Science and Scientific Computing, xvi+365 pp. (1990), Academic Press, Inc., Boston, MA · Zbl 0706.65013
[20] Trefethen, Lloyd N.; Bau, David, III, Numerical Linear Algebra, xii+361 pp. (1997), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 0874.65013
[21] Wu, Lingfei; Romero, Eloy; Stathopoulos, Andreas, \(PRIMME_-\) SVDS: a high-performance preconditioned SVD solver for accurate large-scale computations, SIAM J. Sci. Comput., 39, 5, S248-S271 (2017) · Zbl 1392.65100
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.