Asymptotic behavior of vector recurrences with applications

Authors:
Alan Feldstein and J. F. Traub

Journal:
Math. Comp. **31** (1977), 180-192

MSC:
Primary 65Q05

DOI:
https://doi.org/10.1090/S0025-5718-1977-0426464-0

MathSciNet review:
0426464

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The behavior of the vector recurrence is studied under very weak assumptions. Let denote the spectral radius of *M* and let . Then if the are bounded in norm and a certain subspace hypothesis holds, the root order of the is shown to be . If one additional hypothesis on the dimension of the principal Jordan blocks of *M* holds, then the quotient order of the is also . The behavior of the homogeneous recurrence is studied for all values of .

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.

**1.**ALAN FELDSTEIN & R. M. FIRESTONE [67],*Hermite Interpolator Iteration Theory and Parallel Numerical Analysis*, Appl. Math. Dept. Report, Brown Univ., October 1967.**2.**ALAN FELDSTEIN & R. M. FIRESTONE [69], "A study of Ostrowski efficiency for composite iteration algorithms,"*Proc. Nat. Conf. Assoc. Comp. Mach.*, 1969, pp. 147-155.**3.**ALAN FELDSTEIN & J. F. TRAUB [74],*Order of Vector Recurrences with Applications to Nonlinear Iteration, Parallel Algorithms, and the Power Method*, Comput. Sci. Dept. Report, Carnegie-Mellon Univ., December 1974.**[J]**J. Herzberger,*Über Matrixdarstellungen für Iterationsverfahren bei nichtlinearen Gleichungen*, Computing (Arch. Elektron. Rechnen)**12**(1974), no. 3, 215–222 (German, with English summary). MR**0395207****[A]**A. C. Hindmarsh,*Optimality in a class of rootfinding algorithms*, SIAM J. Numer. Anal.**9**(1972), 205–214. MR**0312719**, https://doi.org/10.1137/0709019**[H]**H. T. Kung and J. F. Traub,*Computational complexity of one-point and multi-point iteration*, Complexity of computation (Proc. Sympos., New York, 1973) Amer. Math. Soc., Providence, R.I., 1974, pp. 149–160. SIAM-AMS Proc., Vol. VII. MR**0366095****[W]**W. L. Miranker,*Parallel methods for approximating the root of a function*, IBM J. Res. Develop.**13**(1969), 297–301. MR**0239752**, https://doi.org/10.1147/rd.133.0297**[J]**John R. Rice,*Matrix representations of nonlinear equation iterations—Application to parallel computation*, Math. Comp.**25**(1971), 639–647. MR**0303714**, https://doi.org/10.1090/S0025-5718-1971-0303714-7**[G]**G. S. Shedler,*Parallel numerical methods for the solution of equations*, Comm. ACM**10**(1967), 286–291. MR**0240976**, https://doi.org/10.1145/363282.363301**[J]**J. F. Traub,*Iterative methods for the solution of equations*, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR**0169356****[J]**J. F. Traub and H. Woźniakowski,*Strict lower and upper bounds on iterative computational complexity*, Analytic computational complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1975) Academic Press, New York, 1976, pp. 15–34. MR**0431786****[R]**Richard S. Varga,*Matrix iterative analysis*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR**0158502**

Retrieve articles in *Mathematics of Computation*
with MSC:
65Q05

Retrieve articles in all journals with MSC: 65Q05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1977-0426464-0

Article copyright:
© Copyright 1977
American Mathematical Society