# 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
##### Software:
Chebfun; JDQR; JDQZ; lobpcg.m; PRIMME; PRIMME_SVDS
Full Text:
##### References:
  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  Davis, Chandler; Kahan, W. M., The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal., 7, 1-46 (1970) · Zbl 0198.47201  chebfunguide T. A. Driscoll, N. Hale, and L. N. Trefethen. \newblock \em Chebfun Guide. \newblock Pafnuty Publications, 2014.  \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,  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  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  Horn, Roger A.; Johnson, Charles R., Topics in matrix analysis, viii+607 pp. (1991), Cambridge University Press, Cambridge · Zbl 0729.15001  Hunter, John K.; Nachtergaele, Bruno, Applied Analysis, xiv+439 pp. (2001), World Scientific Publishing Co., Inc., River Edge, NJ · Zbl 0981.46002  Kato, Tosio, Perturbation Theory for Linear Operators, Classics in Mathematics, xxii+619 pp. (1995), Springer-Verlag, Berlin · Zbl 0836.47009  Knyazev, Andrew V., New estimates for Ritz vectors, Math. Comp., 66, 219, 985-995 (1997) · Zbl 0870.65045  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  Li, Chi-Kwong; Li, Ren-Cang, A note on eigenvalues of perturbed Hermitian matrices, Linear Algebra Appl., 395, 183-190 (2005) · Zbl 1068.15027  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  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  Nakatsukasa, Yuji, Accuracy of singular vectors obtained by projection-based SVD methods, BIT, 57, 4, 1137-1152 (2017) · Zbl 1386.65116  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  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  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  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  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  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.