Asymptotic behavior of vector recurrences with applications

Abstract:

The behavior of the vector recurrence ${{\mathbf {y}}_{n + 1}} = M{{\mathbf {y}}_n} + {{\mathbf {w}}_{n + 1}}$ is studied under very weak assumptions. Let $\lambda (M)$ denote the spectral radius of M and let $\lambda (M) \geqslant 1$. Then if the ${{\mathbf {w}}_n}$ are bounded in norm and a certain subspace hypothesis holds, the root order of the ${{\mathbf {y}}_n}$ is shown to be $\lambda (M)$. If one additional hypothesis on the dimension of the principal Jordan blocks of M holds, then the quotient order of the ${{\mathbf {y}}_n}$ is also $\lambda (M)$. The behavior of the homogeneous recurrence is studied for all values of $\lambda (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.