General subspace iteration theory related to $GR$-algorithms

A more elaborate study on this subject can be found in [9,4].

Subspace iteration can be seen as the following iteration:

$$\mathcal{S}_i = p_i(A) \mathcal{S}_{i-1},$$

starting from an initial subspace $\mathcal{S}_0=\mathcal{S}$. The $p_i(\lambda)$ are suitably chosen polynomials (or rational functions in our case), in order to speed up the convergence. Under some mild constraints this will converge to an invariant subspace. Defining $\hat{p}_i(\lambda)=p_i(\lambda)\ldots p_2(\lambda)p_1(\lambda)$, we also have

$$\mathcal{S}_i = \hat{p}_i(A) \mathcal{S}_{0}.$$

A $GR$-method, in which $R$ defines an upper triangular matrix, and $G$ is an invertible transformation matrix is based on transformations of the following form: $p_i(A^{(i)})=G^{(i)}R^{(i)},$ where the new iterate is defined as follows:

$$A^{(i+1)}={G^{(i)}}^{-1} A^{(i)} G^{(i)}.$$ (5)

This can easily be interpreted as a subspace iteration step, followed by a coordinate transformation. Namely first a subspace iteration step is performed onto $\langle \mathbf{e}_1,\ldots,\mathbf{e}_k \rangle$ (for all $1\leq k\leq n$ at the same time):

$$p_i(A^{(i)})\langle \mathbf{e}_1,\ldots,\mathbf{e}_k \rangle = \langle \mathbf{g}_1,\ldots,\mathbf{g}_k \rangle,$$

where the $\mathbf{g}_i$ are the columns of the matrix $G^{(i)}$, which means that $G^{(i)}=[\mathbf{g}_1,\ldots,\mathbf{g}_n]$.

To conclude a coordinate transformation has to be performed, defined by Equation (5). This maps the subspace $\langle \mathbf{g}_1,\ldots,\mathbf{g}_k \rangle$ back to the subspace $\langle \mathbf{e}_1,\ldots,\mathbf{e}_k \rangle$.

Hence, in case of a $GR$-method, one does not work with a sequence of changing subspaces, but with a sequence of changing matrices. Gradually the lower triangular part of the matrices $A^{(i)}$ should converge to zero, thereby revealing the eigenvalues on the diagonal of the matrix $A^{(i)}$.

We did not yet specify the $p_i(\lambda)$ in this case. Considering Equation (5), one can easily see that for the standard $QR$-method one considers in every step $p_i(\lambda)=\lambda-\sigma_i$. Where $\sigma_i$ is a suitable chosen shift, e.g., the Rayleigh or the Wilkinson shift. In our case the considered rational functions are of the form $p_i(\lambda)=(\lambda-\sigma_i)(\lambda-\kappa_i)$.