A Guide to the Acceleration of Iterative Methods Whose Iteration Matrix is Nonnegative and Convergent

For an $n \times n$ nonnegative matrix B whose spectral radius is less than unity we consider the acceleration of the fixed-point iteration scheme \[ (1) \qquad x_{j + 1} = Bx_j + c \] by two parameter-dependent techniques: the extrapolation method \[ (2) \qquad z_{j + 1} = [ \omega B + ( 1 - \omega )B ] z_j + \omega c \] and the second-degree stationary method \[ (3) \qquad u_{j + 1} = \omega Bu_j + ( 1 - \omega )u_{j - 1} + \omega c. \] It is shown whether, when B is (also) irreducible, it is possible to accelerate (1) and, if so, whether technique (2) or (3) provides the best acceleration, which is largely determined by the cyclicity p of B. In this paper all possible values of p are analyzed. In the case when B is reducible, the possibilities for accelerating (1) can be determined with the aid of the Frobenius normal form of B. Actually, one motivation for the present work is an observation that if B is an $n \times n$ nonnegative matrix whose spectral radius is less than 1, then for no decomposition of B into $B = B_1 + B_2 $ , where both $B_1 $ and $B_2 $ are nonnegative matrices, does the second-degree iterative method \[ w_{j + 1} = B_1 w_j + B_2 w_{j - 1} + c \] attain a convergence rate superior to the scheme in (1).