Inner and Outer Iterations for the Chebyshev Algorithm

We analyze the preconditioned Chebyshev iteration in which at each step the linear system involving the preconditioner is solved inexactly by an inner iteration. We allow the tolerance used in the inner iteration to decrease from one outer iteration to the next. When the tolerance converges to zero, the asymptotic convergence rateis the same as for the exact method. Motivated by this result, we seek the sequence of tolerance values that yields the lowest cost to achieve a specified accuracy. We find that among all sequences of slowly varying tolerances, a constant one is optimal. Numerical calculations that verify our results are presented. Asymptotic methods, such as the W.K.B. method for linear recurrence equations, are used with an estimate of the accuracy of the asymptotic result.