Page 74 - Textos de Matemática Vol. 44

64 M. E. HOCHSTENBACH, D. A. SINGER AND P. F. ZACHLIN
we have the upper bound
∥rMR∥ k/2 k ≤ 1 − ν(A) ν(A−1)
Note in particular that the right-hand side is independent of the choice of the initial guess and the resulting Krylov search space.
Moreover, we have the following property. Since xk ∈ Kk(A,b), we can write xk = qk−1(A) b for a certain polynomial qk−1 of degree k − 1, and rk = pk (A) b for a certain polynomial pk of degree k. Then the zeros ζ of the GMRES polynomial pk satisfy ζ−1 ∈ W(A−1), see [8] and also below.
In fact, these zeros are the harmonic Ritz values [10, 3]. The harmonic Rayleigh–Ritz approach, which was introduced in [10], is a popular tool for the numerical computation of interior eigenvalues close to a given target τ. Note that these eigenvalues are exterior eigenvalues of the shifted and inverted matrix (A − τI)−1, where I denotes the identity matrix. For subspace meth- ods it is often easier to compute exterior eigenvalues, as compared to interior eigenvalues. Given a search space Uk for the eigenvector, this suggests to de- termine (or extract) approximate eigenpairs (θ,u), where u ∈ Uk, by imposing the Galerkin condition
(A − τI)−1u − (θ − τ)−1u ⊥ Uk.
∥r0∥
.
Here Uk is a test space; to avoid working with the inverse of a large sparse matrix the harmonic Rayleigh–Ritz approach takes U k = (A−τI)∗(A−τI)Uk. In this case the subspace extraction is determined by the projected (and hence low-dimensional) generalized eigenvalue problem
U k∗ ( A − τ I ) ∗ ( A − τ I ) U k c = ( θ − τ ) U k∗ ( A − τ I ) ∗ U k c ,
where we write u = Ukc, with c ∈ Ck. The pair (θ,u) = (θ,Ukc) is called a harmonic Ritz pair. For eigenpair approximations, one is interested in the pair with the harmonic Ritz value θ closest to τ, see, e.g., [13]. Given a harmonic Ritz vector u, the corresponding harmonic Ritz value is given by
u∗(A−τI)∗(A−τI)u. u∗(A − τI)∗u
The roots of the GMRES polynomial are the harmonic Ritz values with target τ = 0 [10, 3]. By the equalities
−1 x∗A−1x y∗A∗y W(A )= x∗x :x̸=0 = y∗A∗Ay:y̸=0
we see that the inverses of these harmonic Ritz values are in W(A−1). These equalities may also be interpreted as: W(A−1) is the set of the inverses of