The convergence behavior of Ritz values in the presence of close eigenvalues (Q1095582): Difference between revisions

Let A be a symmetric \(n\times n\) matrix, w a vector in \(E^ n\), and \(K_ i=span(w,Aw,...,A^{i-1}w)\subset E^ n\). Let \(T_ i\) mean the orthogonal projection upon \(K_ i\) and \(A| K_ i\) the restriction of A to \(K_ i\). Then, as known, the eigenvalues \(\theta_ 1^{(i)},...,\theta_ i^{(i)}\) of the matrix \(A_ i=T_ iA| K_ i,\) called Ritz values of degree i, approximate the corresponding eigenvalues \(\lambda_ 1,...,\lambda_ n\) of A and converge to them as i increases. However, in the case that A has almost multiple eigenvalues the convergence behavior of the Ritz values can be ``rather bizarre''. The desire to analyze this phenomenon theoretically has motivated the present paper. The authors start by making a numerical experiment which corresponds to the case that an almost double eigenvalue occurs at the beginning of the spectrum. One then observes that \(\theta_ 1^{(i)}\) first seems to converge to the cluster, stays in its immediate vicinity for quite a while, moving with very small steps, starts moving again and quite fast, to \(\lambda_ 1\). \(\theta_ 2^{(i)}\) first seems to converge to \(\lambda_ 3\) and achieves its immediate vicinity, but about at the same time that \(\theta_ 1^{(i)}\) resumes its march to \(\lambda_ 1\), \(\theta_ 2^{(i)}\) does so to \(\lambda_ 2\), and quite soon afterwards we have \(\theta_ 1^{(i)}-\lambda_ 1\approx \theta_ 2^{(i)}-\lambda_ 2\). As soon as \(\theta_ 2^{(i)}\) leaves the vicinity of \(\lambda_ 3\) its place is occupied by \(\theta_ 3^{(i)}.\) Sections 7-10 are devoted to explain theoretically the above observations, to find quantitative estimates for the local behavior of the rate of convergence and to compare the results with experimental observations. Since the known Kaniel-Paige-Saad a priori upper bounds do not reflect the local convergence behavior, another approach is needed. All the new results obtained are based on the orthogonality of the so- called Ritz polynomials. The definition and properties of these polynomials and the minimum properties of Ritz values are given in Sec. 5. However, the Kaniel-Paige-Saad approach cannot be replaced by that of the authors, since the latter does not have the a priori character of the former. Finally, in Sec. 12, a theorem is given in order to explain the ``superlinear convergence'' of Ritz values. This phenomenon occurs by large values of i. Every section contains a long discussion.