Order of Vector Recurrences with Application to Nonlinear Iteration, Parallel Algorithms, and the Power Method,
Abstract
The behavior of the vector recurrence y sub (n+1) = M(y sub n) + w sub (n+1) is studied under very weak assumptions. Let lambda (M) denote the spectral radius of M and let lambda (M) > or = 1. Then if the w sub n are bounded in norm and a certain subspace hypothesis holds, the root order of the (y sub 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 (y sub 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: Nonlinear iteration with application to iteration with memory and to parallel iteration algorithms; Order and efficiency of composite iteration; The power method.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1974
- Accession Number
- ADA006864
Entities
People
- Alan Feldstein
- Joseph F. Traub
Organizations
- Carnegie Mellon University