UNIVERSITY OF COLORADO AT DENVER

PLACE: Mathematics Conference Room 626 UCD Building, 1250 14th St., Denver

TIME: NOON (Refreshments served at 11:45 am)

DATE: March 27, 2000

A geometric convergence theory for preconditioned inverse iteration

Dr. Klaus Neymeyr
Mathematisches Institut, Universitaet Tuebingen
Auf der Morgenstelle 10, 72076 Tuebingen
Tel.: +49 (0)7071 29 77596
eMail: neymeyr@na.uni-tuebingen.de

   A new convergence analysis is presented for preconditioned inverse
   iteration, which is a method to determine the smallest eigenvalue together
   with an eigenvector of a symmetric positive definite matrix. Preconditioned
   inverse iteration derives from inverse iteration (also called inverse power
   method) in a way that the occurring system of linear equations is solved
   approximately by using a preconditioner. 
   
   The central result is a sharp convergence estimate for the Rayleigh quotient
   of the iterates. This estimate depends on the spectral radius of the error
   propagation matrix, which describes the quality of the preconditioner,
   as well as on the nearest eigenvalues enclosing the Rayleigh quotient of the
   actual iterate. The estimate does not depend on the largest
   eigenvalue of the given matrix. Hence  multigrid preconditioners can be
   used to solve eigenvalue problems for elliptic differential operators
   efficiently with a grid independent convergence rate.
   
   The convergence analysis of preconditioned inverse iteration
   is based on a predominantly geometric description: a central problem
   is to find the supremum of the Rayleigh quotient on a certain ball of
   iterates, which results from applying preconditioned inverse iteration
   for all admissible preconditioners to a fixed iterate.
   
   The convergence theory can also be extended to a subspace implementation of
   preconditioned inverse iteration. Such a method is designated to determine
   a modest number of the smallest eigenvalues and its corresponding invariant
   subspace of eigenvectors. Sharp convergence estimates are derived for the
   Ritz values associated with the actual iteration subspace.