These methods are similar to Algorithm 11.5 in the previous subsection, but the shifts are chosen in the process of iterations and do not require knowledge of any bounds. Historically, preconditioned steepest descent/ascent methods for eigenproblems were suggested earlier (see [225,393,365]) than the power method with an a priori choice of the shift of the previous subsection.
Here, we present the single-vector version of the preconditioned steepest ascent for the pencil in Algorithm 11.6. For , , the method becomes a steepest descent method for .
We note that the shift can be determined with the Rayleigh-Ritz method for the pencil on the trial subspace . As the trial space is two-dimensional, the projection problem can be solved as a quadratic equation. Thus, one can derive explicit formulas for as roots of a quadratic polynomial.
By construction, the steepest ascent (descent) method provides maximization (minimization) of the Rayleigh quotient on every iteration as compared with the corresponding iterative Algorithm 11.5. Therefore, the convergence results from the previous section can be applied without any changes, and similar observations can be made.
We have collected the dominant costs per iteration for Algorithm 11.6 in terms of storage, and floating point operations in the following two tables, respectively:
|Temporary vectors||3-5 -vectors|
|Rayleigh-Ritz method||dots and matrix-vector products|
|Residual||matrix-vector products, update|
|Preconditioned residual||Depends on preconditioner|
The main advantages of the preconditioned steepest descent/ascent method are its relative simplicity and a minimal cost of every iteration compared to other preconditioned eigensolvers considered below. Using the Rayleigh-Ritz method instead of an a priori chosen shift does not require knowledge of any bounds. On the negative side, every iteration may cost about twice that of Algorithm 11.5. Though convergence is usually better than that of Algorithm 11.5 it is still worse than linear convergence of other preconditioned eigensolvers we consider below.