TABLE OF CONTENTS The convergence behavior of the different algorithms seen in this chapter can be analyzed by exploiting optimality properties whenever such properties exist. This is the case for the CG and the GMRES algorithms. On the other hand, the nonoptimal algorithms such as FOM, IOM, and QGMRES will be harder to analyze.
One of the main tools in the analysis of these methods is the use of Chebyshev polynomials. These polynomials are useful both in theory, when studying convergence, and in practice, as a mean of accelerating single-vector iterations or projection processes. In the following, real and complex Chebyshev polynomials are discussed separately.
The Chebyshev polynomial of the first kind of degree k is defined by
That this is a polynomial with respect to t can be shown easily by induction from the trigonometric relation
and the fact that C 1 (t) = t, C 0 (t) = 1. Incidentally, this also shows the important three-term recurrence relation
The definition (6.109) can be extended to cases where t > 1 with the help of the following formula:
This is readily seen by passing to complex variables and using the definition cos ? = ( e i ? + e ? i ?)/2. As a result of (6.110), the following expression can be derived:
which is valid for t ? 1 but can also be extended to the case of t
