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.


  • thumnail for S0025-5718-1977-0426464-0.pdf S0025-5718-1977-0426464-0.pdf application/pdf 926 KB Download File

Also Published In

Mathematics of Computation

More About This Work

Academic Units
Computer Science
Published Here
September 16, 2013