The convergence of Ritz values for The convergence of Ritz values for sequences of matrices

Bernhard Beckermann

Laboratoire d'Analyse Num'erique et d'Optimisation
UFR IEEA - M3, UST Lille, F-59655 Villeneuve d'Ascq CEDEX, France

While discussing the convergence of the Lanczos method for finding eigenvalues of large symmetric matrices, Trefethen and Bau observed a relationship with electric charge distributions, and claimed that the Lanczos iteration tends to converge to eigenvalues in regions of ``too little charge'' for an equilibrium distribution. Recently, Kuijlaars [1] found a theoretical justification for this phenomenon by considering the Lanczos method applied to a suitable sequence of matrices with similar spectra which may occur for instance in the discretization of PDEs while varying the parameter of discretization. The aim of the present talk is to improve the result of Kuijlaars: we obtain a better rate of convergence under weaker regularity assumptions, and show that this new rate of convergence is sharp [4].

An important tool in our considerations is a constrained energy problem in complex potential theory. This constrained energy problem has been investigated by Rakhmanov (1996), Dragnev-Saff (1997), and several others (see, e.g., [2]) in connection with the asymptotic behavior of discrete orthogonal polynomials. It was shown recently [3] that this constrained energy problem may serve to explain the superlinear convergence of Conjugate Gradients.

In terms of orthogonal polynomials, the eigenvalues of a given matrix may be identified with the abscissa of a given quadrature rule, and the Ritz values obtained by the Lanczos method with the abscissa of an associated lower order Gaussian quadrature formula. In order to estimate the approximation error, we formulate a related polynomial extremal problem, and show that this problem may be asymptotically solved in terms of a constrained energy problem where the constraint is given by the asymptotic distribution of the eigenvalues.


[1] A.B.J. Kuijlaars, Which eigenvalues are found by the Lanczos method? To appear in SIAM J. Matrix Anal. Applics. (2000).

[2] B. Beckermann, On a conjecture of E.A. Rakhmanov. To appear in Constructive Approximation (1999).

[3] B. Beckermann & A.B.J. Kuijlaars, Superlinear Convergence of Conjugate Gradients. Manuscript (1999).

[4] B. Beckermann, A note on the convergence of Ritz values for sequences of matrices. Manuscript (2000).

File translated from TEX by TTH, version 2.27.
On 13 Mar 2000, 15:59.