Partial problem of eigen values

The problem of calculating one or a few eigen values of a square matrix, usually real or complex, as well as the corresponding eigen vectors.

The following variants of the partial problem of eigen values are encountered most often in practice: 1) find the groups of in absolute value smallest (or largest) eigen values; 2) find the groups of eigen values closest to a given number $ a $; and 3) find the points of the spectrum that lie in a given interval $ ( \alpha , \beta ) $( for a symmetric or Hermitian matrix).

The majority of methods for solving the partial problem of eigen values for general matrices are based on the idea of power iteration or on a variant of it — inverse iteration (cf. Iteration methods for the solution of matrix eigen value problems): If a matrix $ A $ has an eigen value $ \lambda _ \max $ that is dominating in absolute value and if $ x _ \max $ is the corresponding eigen vector, then for almost any vector $ v $ the sequence $ v , A v , A ^ {2} v \dots $ converges to $ x _ \max $. If the eigen value that is smallest in absolute value is required (problem 1), then power iteration is carried out on the matrix $ A ^ {-} 1 $( the method of inverse iteration); to find an eigen value closest to $ a $( problem 2), use the matrix $ ( A - aI ) ^ {-} 1 $( the method of inverse iteration with a shift).

The most important special case of the partial problem of eigen values is that of computing the eigen values and corresponding eigen vectors of a real symmetric or complex Hermitian matrix $ A $. Here there are many effective numerical methods for solving the partial problem of eigen values, based on entirely different ideas (cf. [1]). Among these are: methods that use the extremal properties of the Rayleigh functional (the greatest and the smallest eigen values of $ A $ realize, respectively, the maximum and minimum of the Rayleigh quotient $ \phi ( A , z ) = ( A z , z ) / ( z , z ) $, $ z \neq 0 $; these extremes are achieved on the corresponding eigen vectors); methods that apply Silvester's law of inertia (the method of Sturm sequences and, more generally, spectral-division methods); and finally, methods based on the approximation properties of Krylov subspaces, that is, of the linear spans of systems of the form $ v , A v \dots A ^ {k-} 1 v $( the Lanczos method and its variants). The choice of which method to use will depend on such considerations as the order of the problem, the degree of the matrix, the availability of a band structure, accessible information about the spectrum, etc.

Methods for solving the partial problem of eigen values, both in the general and in the Hermitian case, can be divided into group methods and sequential methods. Group methods are characterized by the fact that the desired eigen values (and the corresponding eigen vectors) are calculated to some extent in parallel. These include numerous methods of simultaneous iteration, the Lanczos method and spectral-division methods.

In sequential methods the eigen values are determined one-by-one. Here, from the second eigen value onwards it becomes necessary to ensure that the iterations do not converge to solutions that have already been found. Related to this there are different methods of exhaustion (or deflation) [2]. In some cases the exhaustion leads to the construction of a matrix $ \widetilde{A} $ in which the eigen values of $ A $ that have already been calculated correspond to zero; up to those eigen values the spectra of the two matrices coincide, as do their eigen vectors. In other cases the result of the exhaustion is a splitting of the matrix, after which the subsequent eigen values may be obtained using matrices of smaller order. In yet others the iteration method is carried out on a non-modified matrix $ A $, while orthogonalization is carried out with respect to the previously-calculated eigen vectors. Exhaustion techniques can also be used with group methods.

References

[1]	B.N. Parlett, "The symmetric eigenvalue problem" , Prentice-Hall (1980)
[2]	J.H. Wilkinson, "The algebraic eigenvalue problem" , Oxford Univ. Press (1969)

Comments

Cf. also Complete problem of eigen values.

References

[a1]	G.H. Golub, C.F. van Loan, "Matrix computations" , Johns Hopkins Univ. Press (1983)