On Convergence of the Inexact Rayleigh Quotient Iteration without and with MINRES
Zhongxiao Jia · arXiv (Cornell University) · 2009
For the Hermitian inexact Rayleigh quotient iteration (RQI), we present general convergence results, independent of iterative solvers for inner linear systems. We prove that the method converges quadratically at least under a new condition, called the uniform positiveness condition. This condition can be much weaker than the commonly used one that at outer iteration k, requires the relative residual norm ξk (inner tolerance) of the inner linear system to be smaller than one considerably and may allow ξk ≥ 1. Our focus is on the inexact RQI with MINRES used for solving the linear systems. We derive some subtle and attractive properties of the residuals obtained by MINRES. Based on these properties and the new general convergence results, we establish a number of insightful convergence results. Let ‖rk ‖ be the residual norm of approximating eigenpair at outer iteration k. Fundamentally different from the existing results that cubic and quadratic convergence requires ξk = O(‖rk‖) and ξk ≤ ξ ≪ 1 with ξ fixed, respectively, our new results remarkably show that the inexact RQI with MINRES generally converges cubically, quadratically and linearly provided that ξk ≤ ξ with ξ fixed not near one, ξk = 1 − O(‖rk‖) and ξk = 1 − O(‖rk ‖ 2), respectively. Since we always have ξk ≤ 1 in MINRES for any inner iteration steps, the results mean that the inexact RQI with MINRES can achieve cubic, quadratic and linear convergence by solving the linear systems only with very low accuracy and very little accuracy, respectively. New theory can be used to design much more effective implementations of the method than ever before. The results also suggest that we implement the method with fixed small inner iteration steps. Numerical experiments confirm our results and demonstrate much higher effectiveness of the new implementations.