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]**HERZBERGER [74], "Über Matrixdarstellungen für Iterationsverfahren bei nichtlinearen Gleichungen,"*Computing*, v. 12, 1974, pp. 215-222. MR**0395207 (52:16005)****[A]**C. HINDMARSH [72], "Optimality in a class of root-finding algorithms,"*SIAM J. Numer. Anal.*, v. 9, 1972, pp. 205-214. MR**47**# 1275. MR**0312719 (47:1275)****[H]**T. KUNG & J. F. TRAUB [74], "Computational complexity of one-point and multi-point iteration,"*Complexity of Computation*, (SIAM-AMS Proceedings, vol. 7), edited by R. M. Karp, Amer. Math. Soc., Providence, R. I., 1974, pp. 149-160. MR**0366095 (51:2345)****[W]**L. MIRANKER [69], "Parallel methods for approximating the root of a function,"*IBM J. Res. Develop.*, v. 13, 1969, pp. 297-301. MR**39**# 1109. MR**0239752 (39:1109)****[J]**R. RICE [71], "Matrix representations of nonlinear equation iterations--Application to parallel computation,"*Math. Comp.*, v. 25, 1971, pp. 639-647. MR**46**# 2850. MR**0303714 (46:2850)****[G]**S. SHEDLER [67], "Parallel numerical methods for the solution of equations,"*Comm. ACM*, v. 10, 1967, pp. 286-291. MR**39**# 2321. MR**0240976 (39:2321)****[J]**F. TRAUB [64],*Iterative Methods for the Solution of Equations*, Prentice-Hall, Englewood Cliffs, N. J., 1964. MR**29**# 6607. MR**0169356 (29:6607)****[J]**F. TRAUB & H. WOZNIAKOWSKI [76], "Strict lower and upper bounds on iterative computational complexity,"*Analytic Computational Complexity*, edited by J. F. Traub, Academic Press, New York, 1976. MR**0431786 (55:4781)****[R]**S. VARGA [62],*Matrix Iterative Analysis*, Prentice-Hall, Englewood Cliffs, N. J., 1962. MR**28**# 1725. MR**0158502 (28:1725)**

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