Page 70 - Textos de Matemática Vol. 44

60 M. E. HOCHSTENBACH, D. A. SINGER AND P. F. ZACHLIN
2. Krylov approximations to the field of values
An attractive aspect of W(A) is the availability of efficient numerical meth- ods to approximate this set, both for small and large matrices. For small ma- trices, Johnson [7] pointed out that W(A) may be efficiently approximated by computing the maximal and minimal eigenvalue of the Hermitian part of eiαA:
1 (eiαA + (eiαA)∗) 2
for a number of angles α ∈ [0, π). Hereby the equalities
(2.1)
max
z∈W (A) min
z∈W (A)
Re(e−iαz) = 1 λmax(eiαA + (eiαA)∗), 2
Re(e−iαz) = 1 λmin(eiαA + (eiαA)∗) 2
are used for every angle α. Here, Re denotes the real part of a complex number, and λmax and λmin are the largest and smallest eigenvalue of a Hermitian matrix.
For matrices of large dimension, we may use the Lanczos method (see, e.g., [15]) to approximate the largest and smallest eigenvalue of the Hermitian matri- ces eiαA + (eiαA)∗. This method generates a low-dimensional Krylov subspace to approximate eigenpairs of large (sparse) matrices. The Lanczos method gen- erally approximates the extremal eigenvalues well, particularly the largest and smallest eigenvalue. We may run a new Lanczos process for every α in a cho- sen discrete set; for each angle α the largest eigenpair will be approximated using a different Krylov subspace, generated by a different matrix of the form eiαA + (eiαA)∗ and an initial vector, for instance a random vector, or the approximate eigenvector for a previous value of α.
We would like to point out that there is a computationally less expensive alternative using only a single Krylov subspace for all angles α as follows. We may perform a single run of the Arnoldi process (see, e.g., [15]) on A (or on eiαA for any fixed angle α) and an initial vector u1 of unit length (for instance a random vector). Let
Uk = Kk(A, u1) = span(u1, Au1, . . . , Ak−1u1)
be the Krylov space of dimension k generated by A and u1. Performing k steps
of Arnoldi yields the decomposition
(2.2) AUk = Uk Hk + hk+1,k uk+1 e∗k = Uk+1 Hk,
where the columns of Uk form an orthonormal basis for Uk with u1 as its first column, Hk is an upper Hessenberg matrix, ek is the kth canonical basis vector,
Hk
and Hk = hk+1,k e∗ is a (k + 1) × k upper Hessenberg matrix with an extra
row.
k