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
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 $ {{\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] 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)

Similar Articles

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

American Mathematical Society