Asymptotic behavior of vector recurrences with applications
Authors:
Alan Feldstein and J. F. Traub
Journal:
Math. Comp. 31 (1977), 180192
MSC:
Primary 65Q05
MathSciNet review:
0426464
Fulltext 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. 147155.
 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, CarnegieMellon 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
(52 #16005)
 [A]
A.
C. Hindmarsh, Optimality in a class of rootfinding algorithms,
SIAM J. Numer. Anal. 9 (1972), 205–214. MR 0312719
(47 #1275)
 [H]
H.
T. Kung and J.
F. Traub, Computational complexity of onepoint and multipoint
iteration, Complexity of computation (Proc. Sympos., New York, 1973)
Amer. Math. Soc., Providence, R.I., 1974, pp. 149–160. SIAMAMS
Proc., Vol. VII. MR 0366095
(51 #2345)
 [W]
W.
L. Miranker, Parallel methods for approximating the root of a
function, IBM J. Res. Develop. 13 (1969),
297–301. MR 0239752
(39 #1109)
 [J]
John
R. Rice, Matrix representations of nonlinear
equation iterations—Application to parallel computation, Math. Comp. 25 (1971), 639–647. MR 0303714
(46 #2850), http://dx.doi.org/10.1090/S00255718197103037147
 [G]
G.
S. Shedler, Parallel numerical methods for the solution of
equations, Comm. ACM 10 (1967), 286–291. MR 0240976
(39 #2321)
 [J]
J.
F. Traub, Iterative methods for the solution of equations,
PrenticeHall Series in Automatic Computation, PrenticeHall, Inc.,
Englewood Cliffs, N.J., 1964. MR 0169356
(29 #6607)
 [J]
J.
F. Traub and H.
Woźniakowski, Strict lower and upper bounds on iterative
computational complexity, Analytic computational complexity (Proc.
Sympos., CarnegieMellon Univ., Pittsburgh, Pa., 1975) Academic Press,
New York, 1976, pp. 15–34. MR 0431786
(55 #4781)
 [R]
Richard
S. Varga, Matrix iterative analysis, PrenticeHall, Inc.,
Englewood Cliffs, N.J., 1962. MR 0158502
(28 #1725)
 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. 147155.
 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, CarnegieMellon Univ., December 1974.
 [J]
 HERZBERGER [74], "Über Matrixdarstellungen für Iterationsverfahren bei nichtlinearen Gleichungen," Computing, v. 12, 1974, pp. 215222. MR 0395207 (52:16005)
 [A]
 C. HINDMARSH [72], "Optimality in a class of rootfinding algorithms," SIAM J. Numer. Anal., v. 9, 1972, pp. 205214. MR 47 # 1275. MR 0312719 (47:1275)
 [H]
 T. KUNG & J. F. TRAUB [74], "Computational complexity of onepoint and multipoint iteration," Complexity of Computation, (SIAMAMS Proceedings, vol. 7), edited by R. M. Karp, Amer. Math. Soc., Providence, R. I., 1974, pp. 149160. 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. 297301. MR 39 # 1109. MR 0239752 (39:1109)
 [J]
 R. RICE [71], "Matrix representations of nonlinear equation iterationsApplication to parallel computation," Math. Comp., v. 25, 1971, pp. 639647. 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. 286291. MR 39 # 2321. MR 0240976 (39:2321)
 [J]
 F. TRAUB [64], Iterative Methods for the Solution of Equations, PrenticeHall, 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, PrenticeHall, 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:
http://dx.doi.org/10.1090/S00255718197704264640
PII:
S 00255718(1977)04264640
Article copyright:
© Copyright 1977
American Mathematical Society
