Error bounds for linear recurrence relations

Olver, F. W. J.

doi:10.1090/S0025-5718-1988-0929547-9

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