Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Asymptotic behavior of vector recurrences with applications

Authors: Alan Feldstein and J. F. Traub
Journal: Math. Comp. 31 (1977), 180-192
MSC: Primary 65Q05
MathSciNet review: 0426464
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

  • 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
  • [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
  • [J] John R. Rice, Matrix representations of nonlinear equation iterations—Application to parallel computation, Math. Comp. 25 (1971), 639–647. MR 0303714, 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
  • [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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65Q05

Retrieve articles in all journals with MSC: 65Q05

Additional Information

Article copyright: © Copyright 1977 American Mathematical Society