Page 79 - Textos de Matemática Vol. 44

FIELD OF VALUES OF A MATRIX INVERSE 69
Part (a) states that the field of values of H−1 is the true field of values of a k
perturbed matrix A−1 + Ek = A−1(I + Fk), restricted to the Krylov subspace
Uk. Here, the backward error Ek is a (hopefully small) rank-one update matrix.
In particular ∥Ek∥ will be small if Uk is almost an invariant subspace, which
means that |hk+1,k| is small. Item (b) is similar but uses a multiplicative (rel-
ative) perturbation. Part (c) means that every point of W(H−1) is at most k
|hk+1,k|∥U∗A−1uk+1∥∥H−∗ek∥ away from W(U∗A−1Uk), a projected field of kkk
values of A−1 which is included in the sought set W(A−1).
In summary, when we compare (5.1) with (5.2), the advantage of the for-
mer is that this approximation is a proper inclusion. However, a strength of (5.2) over (5.1) is that this method employs a projection that works solely with Uk: (5.2) approximates a projection of A−1 onto the space Uk, and not onto the space AUk. The space AUk may be seen as biased, as by the mul- tiplication with A the smallest eigenmodes will have been (greatly) reduced. Therefore, we expect that (5.2) may often yield a better approximation, espe- cially if |hk+1,k| ∥U∗A−1uk+1∥ ∥H−∗ek∥ is reasonably small.
We now continue with an illustrative numerical example.
Example 5.3. In Figure 2 the eigenvalues (dots) and field of values of A−1
(solid) are plotted, where A is the 256 × 256 grcar matrix. We take for
U a 16-dimensional Krylov space generated using a random starting vector.
We plot two approximations to W(A−1): W(R−∗H∗R−1) ((5.1), dash), and kkk
W(H−1) ((5.2), solid). Although it is not guaranteed that W(H−1) is a subset kk
of W(A−1), it is the case here; moreover, we see that W(H−1) is a much better k
approximation to W(A−1) than W(R−∗H∗R−1). Indeed, W(R−∗H∗R−1) con- kkk kkk
tains only a small portion of the eigenvalues of A−1, while W(H−1) contains
kk
the entire spectrum of A−1.
6. Concluding remarks
k
We have approximated the field of values of the inverse of a large sparse matrix by subspace methods, in particular the Arnoldi process. To this aim, we have introduced a viable alternative for a method proposed by Manteuffel and Starke [8].
The Arnoldi procedure can be used to give an approximation to the field of values of A and of its inverse. As the Ritz values of A with respect to search space Uk are always in W(A), the inverses of the harmonic Ritz val- ues are guaranteed to be in W(A−∗). As we can use the Ritz matrix Hk = Uk∗AUk to approximate W(A), we can use the harmonic Ritz matrix, H k = (Uk∗A∗Uk)−1Uk∗A∗AUk, of which the harmonic Ritz values are the eigenvalues,