Error bounds for linear recurrence relations
Author:
F. W. J. Olver
Journal:
Math. Comp. 50 (1988), 481499
MSC:
Primary 65Q05; Secondary 39A10, 65G05
MathSciNet review:
929547
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Recurrence relations of the form are examined in two cases: (A) oscillatory systems, for which ; (B) monotonic systems, for which . In both cases, a posteriori methods are supplied for constructing strict and realistic error bounds in arithmetic operations. A priori bounds, also requiring arithmetic operations, are supplied in Case B. Several illustrative numerical examples are included.
 [1]
J.
R. Cash, Stable recursions, Academic Press [Harcourt Brace
Jovanovich, Publishers], LondonNew YorkToronto, Ont., 1979. With
applications to the numerical solution of stiff systems; Computational
Mathematics and Applications. MR 570113
(81j:65099)
 [2]
Walter
Gautschi, Computational aspects of threeterm recurrence
relations, SIAM Rev. 9 (1967), 24–82. MR 0213062
(35 #3927)
 [3]
W.
Gautschi, Zur Numerik rekurrenter Relationen, Computing (Arch.
Elektron. Rechnen) 9 (1972), 107–126 (German, with
English summary). MR 0312714
(47 #1270)
 [4]
Walter
Gautschi, Computational methods in special functions—a
survey, Theory and application of special functions (Proc. Advanced
Sem., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1975) Academic
Press, New York, 1975, pp. 1–98. Math. Res. Center, Univ.
Wisconsin Publ., No. 35. MR 0391476
(52 #12297)
 [5]
Nicholas
J. Higham, Efficient algorithms for computing the condition number
of a tridiagonal matrix, SIAM J. Sci. Statist. Comput.
7 (1986), no. 1, 150–165. MR 819464
(87b:65053), http://dx.doi.org/10.1137/0907011
 [6]
R.
M. M. Mattheij, Accurate estimates of solutions of second order
recursions, Linear Algebra and Appl. 12 (1975),
no. 1, 29–54. MR 0375812
(51 #12002)
 [7]
R.
M. M. Mattheij and A.
van der Sluis, Error estimates for Miller’s algorithm,
Numer. Math. 26 (1976), no. 1, 61–78. MR 0438745
(55 #11652)
 [8]
Ramon
E. Moore, Methods and applications of interval analysis, SIAM
Studies in Applied Mathematics, vol. 2, Society for Industrial and
Applied Mathematics (SIAM), Philadelphia, Pa., 1979. MR 551212
(81b:65040)
 [9]
F.
W. J. Olver, Error analysis of Miller’s
recurrence algorithm, Math. Comp. 18 (1964), 65–74. MR 0169406
(29 #6656), http://dx.doi.org/10.1090/S00255718196401694069
 [10]
F.
W. J. Olver, Numerical solution of secondorder linear difference
equations, J. Res. Nat. Bur. Standards Sect. B 71B
(1967), 111–129. MR 0221789
(36 #4841)
 [11]
F.
W. J. Olver, Bounds for the solutions of secondorder linear
difference equations, J. Res. Nat. Bur. Standards Sect. B
71B (1967), 161–166. MR 0229407
(37 #4981)
 [12]
F.
W. J. Olver, Further developments of rp and ap error analysis,
IMA J. Numer. Anal. 2 (1982), no. 3, 249–274.
MR 678016
(84c:65073), http://dx.doi.org/10.1093/imanum/2.3.249
 [13]
F.
W. J. Olver and J.
H. Wilkinson, A posteriori error bounds for Gaussian
elimination, IMA J. Numer. Anal. 2 (1982),
no. 4, 377–406. MR 692286
(84m:65044), http://dx.doi.org/10.1093/imanum/2.4.377
 [14]
Siegfried
M. Rump, Solving algebraic problems with high accuracy,
Parallel and largescale computers: performance, architecture, applications
(Montreal, Que., 1982) IMACS Trans. Sci. Comput., II, IMACS, New
Brunswick, NJ, 1983, pp. 299–300. MR
751813
 [15]
A.
van der Sluis, Estimating the solutions of slowly varying
recursions, SIAM J. Math. Anal. 7 (1976), no. 5,
662–695. MR 0421114
(54 #9119)
 [16]
R.
Tait, Error analysis of recurrence
equations, Math. Comp. 21 (1967), 629–638. MR 0221736
(36 #4788), http://dx.doi.org/10.1090/S00255718196702217360
 [17]
Peter
R. Turner, The distribution of leading significant digits, IMA
J. Numer. Anal. 2 (1982), no. 4, 407–412. MR 692287
(84f:65038), http://dx.doi.org/10.1093/imanum/2.4.407
 [18]
J.
H. Wilkinson, Rounding errors in algebraic processes,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
(28 #4661)
 [19]
Jet
Wimp, Computation with recurrence relations, Applicable
Mathematics Series, Pitman (Advanced Publishing Program), Boston, MA, 1984.
MR 727118
(85f:65001)
 [1]
 J. R. Cash, Stable Recursions, Academic Press, London, 1979. MR 570113 (81j:65099)
 [2]
 W. Gautschi, "Computational aspects of threeterm recurrence relations," SIAM Rev., v. 9, 1967, pp. 2482. MR 0213062 (35:3927)
 [3]
 W. Gautschi, "Zur Numerik rekurrenter Relationen," Computing, v. 9, 1972, pp. 107126. [Translated as Report ARL 730005, Aerospace Research Laboratories, WrightPatterson Air Force Base, Ohio, 1973.] MR 0312714 (47:1270)
 [4]
 W. Gautschi, "Computational methods in special functionsa survey," in Theory and Application of Special Functions (R. A. Askey, ed.), Academic Press, New York, 1975, pp. 198. MR 0391476 (52:12297)
 [5]
 N. J. Higham, "Efficient algorithms for computing the condition number of a tridiagonal matrix," SIAM J. Sci. Statist. Comput., v. 7, 1986, pp. 150165. MR 819464 (87b:65053)
 [6]
 R. M. M. Mattheij, "Accurate estimates of solutions of second order recursions," Linear Algebra Appl., v. 12, 1975, pp. 2954. MR 0375812 (51:12002)
 [7]
 R. M. M. Mattheij & A. Van Der Sluis, "Error estimates for Miller's algorithm," Numer. Math., v. 26, 1976, pp. 6178. MR 0438745 (55:11652)
 [8]
 R. E. Moore, Methods and Applications of Interval Analysis, Society for Industrial and Applied Mathematics, Philadelphia, 1979. MR 551212 (81b:65040)
 [9]
 F. W. J. Olver, "Error analysis of Miller's recurrence algorithm," Math. Comp., v. 18, 1964, pp. 6574. MR 0169406 (29:6656)
 [10]
 F. W. J. Olver, "Numerical solution of secondorder linear difference equations," J. Res. Nat. Bur. Standards Sect. B, v. 71, 1967, pp. 111129. MR 0221789 (36:4841)
 [11]
 F. W. J. Olver, "Bounds for the solutions of secondorder linear difference equations," J. Res. Nat. Bur. Standards Sect. B, v. 71, 1967, pp. 161166. MR 0229407 (37:4981)
 [12]
 F. W. J. Olver, "Further developments of rp and ap error analysis, " IMA J. Numer. Anal., v. 2, 1982, pp. 249274. MR 678016 (84c:65073)
 [13]
 F. W. J. Olver & J. H. Wilkinson, "A posteriori error bounds for Gaussian elimination," IMA J. Numer. Anal., v. 2, 1982, pp. 377406. MR 692286 (84m:65044)
 [14]
 S. M. Rump, "Solving algebraic problems with high accuracy," in A New Approach to Scientific Computation (U. W. Kulisch and W. L. Miranker, eds.), Academic Press, New York, 1983, pp. 51120. MR 751813
 [15]
 A. Var Der Sluis, "Estimating the solutions of slowly varying recursions," SIAM J. Math. Anal., v. 7, 1976, pp. 662695. MR 0421114 (54:9119)
 [16]
 R. Tait, "Error analysis of recurrence relations," Math. Comp., v. 21, 1967, pp. 629638. MR 0221736 (36:4788)
 [17]
 P. R. Turner, "The distribution of leading significant digits," IMA J. Numer. Anal., v. 2, 1982, pp. 407412. MR 692287 (84f:65038)
 [18]
 J. H. Wilkinson, Rounding Errors in Algebraic Processes, National Physical Laboratory Notes on Applied Science No. 32, Her Majesty's Stationery Office, London, 1963. MR 0161456 (28:4661)
 [19]
 J. Wimp, Computation with Recurrence Relations, Pitman, Boston, 1984. MR 727118 (85f:65001)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65Q05,
39A10,
65G05
Retrieve articles in all journals
with MSC:
65Q05,
39A10,
65G05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198809295479
PII:
S 00255718(1988)09295479
Article copyright:
© Copyright 1988
American Mathematical Society
