Refined Projection Methods.

To improve the convergence of the standard Rayleigh-Ritz procedure, a so-called refined projection procedure has been recently proposed. The idea is to retain the selected Ritz values $\tilde{\lambda}$ that approximate desired eigenvalues, but to discard the Ritz vectors. Instead, we seek a new unit length vector $\tilde{u}\in {\cal K}$ that satisfies the optimality condition

$$\Vert(A-\tilde{\lambda}I)\tilde u\Vert _2=\min_{u\in {\cal K},\,\Vert u\Vert _2=1} \Vert(A-\tilde{\lambda}I)u\Vert _2$$ (14)

and to use that vector as a new approximate eigenvector. The vector $\tilde u$ is called a refined Ritz vector or simply a refined approximate eigenvector.

The refined projection procedure is mathematically different from the orthogonal and oblique projection methods described above, because it no longer uses Ritz vectors. In particular, the refined vector is not a Ritz vector if the new residual $(A-\tilde{\lambda}I)\tilde u\neq 0$. The refined residual vector $(A-\tilde{\lambda}I)\tilde u$ is then not orthogonal to either $\KK$ itself or a left subspace $\LL$ such as $A \KK$.

If a conventional SVD algorithm is used to solve the least squares problem (3.11), the computational cost is $O(nm^2)$ floating point operations, which is too expensive. Fortunately, if $\tilde{\lambda}$ is the Ritz value obtained by orthogonal projection methods, the refined approximate eigenvector $\tilde u$ can be computed in $O(m^3)$ floating point operations. Recall that a Rayleigh-Ritz procedure typically requires $O(nm^2)$ floating point operations to produce $V$ and a complete set of $m$ Ritz or harmonic Ritz vectors. Therefore, the cost of computing $\tilde u$ is negligible. Hence, the refined approximate eigenvectors provide a viable alternative for approximating eigenvectors.

Several refined projection algorithms have been developed in [244,245]. Analyses of these methods are presented in [247,246].