1977 Articles

Asymptotic behavior of vector recurrences with applications

Feldstein, Alan; Traub, Joseph F.

The behavior of the vector recurrence y_(n + 1) = My_n + w_(n + 1) is studied under very weak assumptions. Let λ(M) denote the spectral radius of M and let λ(M) ≥ 1. Then if the w_n are bounded in norm and a certain subspace hypothesis holds, the root order of the y_n is shown to be λ(M). If one additional hypothesis on the dimension of the principal Jordan blocks of M holds, then the quotient order of the y_n is also λ(M). The behavior of the homogeneous recurrence is studied for all values of λ(M). These results are applied to the analysis of (1) Nonlinear iteration with application to iteration with memory and to parallel iteration algorithms. (2) Order and efficiency of composite iteration.