Page 72 - Textos de Matemática Vol. 44

62
M. E. HOCHSTENBACH, D. A. SINGER AND P. F. ZACHLIN
FOV approximations
3 2 1 0
−1 −2 −3
3 2 1 0
−1 −2 −3
−2 0 2 4
Real
−2 0 2 4
Real(z)
(a) (b)
Figure 1. (a) Eigenvalues (dots) and W(A) (solid) of the 256×256 grcar matrix. (b) Approximations of W (A) using dif- ferent Krylov subspaces for each of the 32 angles (dashed), re- spectively one Krylov subspace for all angles (solid). All Krylov spaces have dimension k = 10.
In the following result, we see that the approximations may be even exactly the same for some combinations of matrices and initial vectors.
Proposition 2.3. Let A be an n × n tridiagonal matrix such that the subdi- agonal entries of A and eiαA + (eiαA)∗, for each α ∈ {α1, . . . , αm}, do not vanish. Suppose that b = e1 is the initial vector of the Krylov space. Then the following two approximation methods to W(A) produce exactly the same result.
(a) Run k steps of Arnoldi (2.2) on A and approximate W(A) ≈ W(Hk),
where W(Hk) on its turn is approximated by a set of angles {α1,...,αm}.
(b) For each angle α ∈ {α1,...,αm}, run k steps of Lanczos on 1(eiαA+ 2
(eiαA)∗) resulting in k × k tridiagonal matrices Tk(α), determine the maximal and minimal eigenvalues λmax(α) and λmin(α) of the Tk(α), and approximate W(A) by the intersection of all half planes of the form {z : λmin(α) ≤ e−iα Re(z) ≤ λmax(α)}.
Proof. The crucial observation is that, because of the assumptions of the nonzero subdiagonal elements, the Krylov spaces generated in both cases:
Imag
Imag(z)