Componentes principales

SIAM REVIEW Vol. 42, No. 2, pp. 267–293

c 2000 Society for Industrial and Applied Mathematics

A Jacobi–Davidson Iteration Method for Linear Eigenvalue Problems∗
Gerard L. G. Sleijpen† Henk A. Van der Vorst†
Abstract. In this paper we propose a new method for the iterative computation of a few of the extremal eigenvalues of a symmetric matrix and their associated eigenvectors. The methodis based on an old and almost unknown method of Jacobi. Jacobi’s approach, combined with Davidson’s method, leads to a new method that has improved convergence properties and that may be used for general matrices. We also propose a variant of the new method that may be useful for the computation of nonextremal eigenvalues as well. Key words. eigenvalues and eigenvectors, Davidson’s method, Jacobiiterations, harmonic Ritz values AMS subject classifications. 65F15, 65N25 PII. S0036144599363084

1. Introduction. Suppose we want to compute one or more eigenvalues and their corresponding eigenvectors of the n × n matrix A. Several iterative methods are available: Jacobi’s diagonalization method [9], [23], the power method [9], the method of Lanczos [13], [23], Arnoldi’s method [1], [26], andDavidson’s method [4], [26], [3], [15], [18]. The latter method has been reported to be quite successful, most notably in connection with certain symmetric problems in computational chemistry [4], [5], [32]. The success of the method seems to depend quite heavily on the (strong) diagonal dominance of A. The method of Davidson is commonly seen as an extension to Lanczos’s method, but as Saad [26]points out, from the implementation point of view it is more related to Arnoldi’s method. In spite of these relations, the success of the method is not well understood [26]. Some recent convergence results and improvements, as well as numerical experiments, are reported in [3], [15], [16], [18], [17], [19], [28]. Jacobi [12] proposed a method for eigenvalue approximation that essentially was acombination of (1) Jacobi rotations, (2) Gauss–Jacobi iterations, and (3) an almost forgotten method that we will refer to as Jacobi’s orthogonal component correction (JOCC). Reinvestigation of Jacobi’s ideas leads to another view of Davidson’s method, and this not only helps us explain the behavior of the method, but it also leads to a new and robust method with superior convergence properties fornondiagonally dominant (unsymmetric) matrices as well. Special variants of this method are already known; see [19], [28], and our discussion in section 4.1.
∗ Published electronically April 24, 2000. This paper originally appeared in SIAM Journal on Matrix Analysis and Applications, Volume 17, Number 2, 1996, pages 401–425. http://www.siam.org/journals/sirev/42-2/36308.html † Mathematical Institute,Utrecht University, P.O. Box 80.010, 3508 TA Utrecht, Netherlands (sleijpen@math.uu.nl, vorst@math.uu.nl).

267

268

GERARD L. G. SLEIJPEN AND HENK A. VAN DER VORST

The outline of this paper is as follows. In section 2 we briefly describe the methods of Davidson and Jacobi, and we show that the original Davidson’s method may be viewed as an accelerated Gauss–Jacobi iteration method.Likewise, more recent approaches that include other preconditioners M can be interpreted as accelerated standard iteration methods associated with the splitting A = M − N . In section 3 we propose the new approach, which is essentially a combination of the JOCC approach and Davidson’s method for creating more general subspaces. The difference between this approach and Davidson’s method may seem verysubtle but it is fundamental. Whereas in Davidson’s method accurate preconditioners M (accurate in the sense that they approximate the inverse of the given operator very well) may lead to stagnation or very slow convergence, the new approach takes advantage of such preconditioners, even if they are exact inverses. It should be stressed that in this approach we do not precondition the given...