Error bounds for linear recurrence relations
HTML articles powered by AMS MathViewer
- by F. W. J. Olver PDF
- Math. Comp. 50 (1988), 481-499 Request permission
Abstract:
Recurrence relations of the form \[ {a_r}{p_{r + 1}} = {b_r}{p_r} + {c_r}{p_{r - 1}}\] are examined in two cases: (A) oscillatory systems, for which $b_r^2 + 4{a_r}{c_r} < 0$; (B) monotonic systems, for which $b_r^2 + 4{a_r}{c_r} \geq 0$. In both cases, a posteriori methods are supplied for constructing strict and realistic error bounds in $O(r)$ arithmetic operations. A priori bounds, also requiring $O(r)$ arithmetic operations, are supplied in Case B. Several illustrative numerical examples are included.References
- J. R. Cash, Stable recursions, Computational Mathematics and Applications, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York-Toronto, Ont., 1979. With applications to the numerical solution of stiff systems. MR 570113
- Walter Gautschi, Computational aspects of three-term recurrence relations, SIAM Rev. 9 (1967), 24–82. MR 213062, DOI 10.1137/1009002
- W. Gautschi, Zur Numerik rekurrenter Relationen, Computing (Arch. Elektron. Rechnen) 9 (1972), 107–126 (German, with English summary). MR 312714, DOI 10.1007/bf02236961
- 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) Math. Res. Center, Univ. Wisconsin, Publ. No. 35, Academic Press, New York, 1975, pp. 1–98. MR 0391476
- 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, DOI 10.1137/0907011
- R. M. M. Mattheij, Accurate estimates of solutions of second order recursions, Linear Algebra Appl. 12 (1975), no. 1, 29–54. MR 375812, DOI 10.1016/0024-3795(75)90125-1
- R. M. M. Mattheij and A. van der Sluis, Error estimates for Miller’s algorithm, Numer. Math. 26 (1976), no. 1, 61–78. MR 438745, DOI 10.1007/BF01396566
- 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
- F. W. J. Olver, Error analysis of Miller’s recurrence algorithm, Math. Comp. 18 (1964), 65–74. MR 169406, DOI 10.1090/S0025-5718-1964-0169406-9
- F. W. J. Olver, Numerical solution of second-order linear difference equations, J. Res. Nat. Bur. Standards Sect. B 71B (1967), 111–129. MR 221789
- F. W. J. Olver, Bounds for the solutions of second-order linear difference equations, J. Res. Nat. Bur. Standards Sect. B 71B (1967), 161–166. MR 229407
- F. W. J. Olver, Further developments of rp and ap error analysis, IMA J. Numer. Anal. 2 (1982), no. 3, 249–274. MR 678016, DOI 10.1093/imanum/2.3.249
- 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, DOI 10.1093/imanum/2.4.377
- Siegfried M. Rump, Solving algebraic problems with high accuracy, Parallel and large-scale computers: performance, architecture, applications (Montreal, Que., 1982) IMACS Trans. Sci. Comput., II, IMACS, New Brunswick, NJ, 1983, pp. 299–300. MR 751813
- A. van der Sluis, Estimating the solutions of slowly varying recursions, SIAM J. Math. Anal. 7 (1976), no. 5, 662–695. MR 421114, DOI 10.1137/0507051
- R. Tait, Error analysis of recurrence equations, Math. Comp. 21 (1967), 629–638. MR 221736, DOI 10.1090/S0025-5718-1967-0221736-0
- Peter R. Turner, The distribution of leading significant digits, IMA J. Numer. Anal. 2 (1982), no. 4, 407–412. MR 692287, DOI 10.1093/imanum/2.4.407
- J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
- Jet Wimp, Computation with recurrence relations, Applicable Mathematics Series, Pitman (Advanced Publishing Program), Boston, MA, 1984. MR 727118
Additional Information
- © Copyright 1988 American Mathematical Society
- Journal: Math. Comp. 50 (1988), 481-499
- MSC: Primary 65Q05; Secondary 39A10, 65G05
- DOI: https://doi.org/10.1090/S0025-5718-1988-0929547-9
- MathSciNet review: 929547