Page 71 - Textos de Matemática Vol. 44

FIELD OF VALUES OF A MATRIX INVERSE 61
As originally suggested by Manteuffel and Starke [8] one can approximate W(A) by W(Uk∗AUk) = W(Hk). This approximation has the following pleasant monotonic inclusion property.
Proposition 2.1.
W(Hk) ⊆ W(Hk+1) ⊆ W(A). Proof. This follows from the observation
W(Uk∗AUk) = {c∗Uk∗AUkc : c ∈ Ck, ∥c∥ = 1} = {x∗Ax : x ∈ Uk, ∥x∥ = 1}
and the fact that Uk ⊂ Uk+1.
From this proposition it follows that the convex set W(Hk) = W(Uk∗AUk) may be interpreted as the field of values of A restricted to the Krylov subspace Uk. In particular, we know that after k steps W(Hk), and therefore also W(A), contains the convex hull of the eigenvalues of Hk, which are called the Ritz values of A with respect to Uk. Since k is assumed to be much smaller than n (the main idea of a subspace method), determining W(Hk) is computationally very efficient, for instance by the method proposed by Johnson.
We note that this second approach via a single Arnoldi decomposition is in practice often very sensible. While a different search space per α may often give a (slightly) better result (that is, a larger maximal eigenvalue per angle and hence a larger approximate field of values which is still included in the true W(A)), both approaches may give nearly the same approximation, as for instance in the following example.
Example 2.2. As a first example, consider for A the 256×256 grcar matrix [9],
which is banded upper Hessenberg; this example is also used in [8]. The eigenval-
ues (dots) and W (A) are depicted in Figure 1(a). We approximate W (A) by 10-
dimensional Krylov subspaces, with a random initial vector b. From Figure 1(b),
we see that taking different Krylov subspaces Kk 1 (eiα A + e−iα A∗ ), b for each 2
of the 32 angles (dashed) instead of one Krylov subspace Kk (A, b) for all angles (solid) hardly improves the numerical approximation to W(A), while the first approach is much more expensive.