An extension of Olver's method for the numerical solution of linear recurrence relations
Author:
J. R. Cash
Journal:
Math. Comp. 32 (1978), 497510
MSC:
Primary 65Q05
MathSciNet review:
0483578
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: An algorithm is developed for computing the solution of a class of linear recurrence relations of order greater than two when unstable error propagation prevents the required solution being found by direct forward recurrence. By abandoning an appropriate number of initial conditions the original problem may be replaced by an inexact but wellconditioned boundary value problem, and in certain circumstances the solution of this new problem is a good approximation to the required solution of the original problem. The required solution of this reposed problem is generated using an algorithm based on Gaussian elimination, and a technique developed by Olver is extended to estimate automatically the truncation error of the proposed algorithm.
 [1]
J.
R. Cash, High order methods for the numerical integration of
ordinary differential equations, Numer. Math. 30
(1978), no. 4, 385–409. MR 502523
(80i:65078), http://dx.doi.org/10.1007/BF01398507
 [2]
Walter
Gautschi, Computational aspects of threeterm recurrence
relations, SIAM Rev. 9 (1967), 24–82. MR 0213062
(35 #3927)
 [3]
J.
D. Lambert, Computational methods in ordinary differential
equations, John Wiley & Sons, LondonNew YorkSydney, 1973.
Introductory Mathematics for Scientists and Engineers. MR 0423815
(54 #11789)
 [4]
D. W. LOZIER, A Stable Algorithm for Computing any Solution of an Arbitrary Linear Difference Equation, Ph.D. Thesis, University of Maryland.
 [5]
J. C. P. MILLER, British Association for the Advancement of Science: Bessel Functions, Part II. Mathematical Tables, Vol. 10, Cambridge Univ. Press, Cambridge, 1952.
 [6]
Kenneth
S. Miller, Linear difference equations, W. A. Benjamin, Inc.,
New YorkAmsterdam, 1968. MR 0227644
(37 #3228)
 [7]
J.
Oliver, Relative error propagation in the recursive solution of
linear recurrence relations, Numer. Math. 9
(1966/1967), 323–340. MR 0213064
(35 #3929)
 [8]
J.
Oliver, The numerical solution of linear recurrence relations,
Numer. Math. 11 (1968), 349–360. MR 0226893
(37 #2479)
 [9]
J.
Oliver, An extension of Olver’s error estimation technique
for linear recurrence relations, Numer. Math. 12
(1968), 459–467. MR 0239782
(39 #1139)
 [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]
J.
H. Wilkinson, The algebraic eigenvalue problem, Clarendon
Press, Oxford, 1965. MR 0184422
(32 #1894)
 [13]
R. V. M. ZAHAR, "A mathematical analysis of Miller's algorithm," Numer. Math., v. 27, 1977, pp. 427447.
 [1]
 J. R. CASH, "High order methods for the numerical integration of ordinary differential equations," Numer. Math. (To appear.) MR 502523 (80i:65078)
 [2]
 W. GAUTSCHI. "Computational aspects of threeterm recurrence relations," SIAM Rev., v. 9, 1967, pp. 2482. MR 0213062 (35:3927)
 [3]
 J. D. LAMBERT, Computational Methods in Ordinary Differential Equations, Wiley, London and New York, 1973. MR 0423815 (54:11789)
 [4]
 D. W. LOZIER, A Stable Algorithm for Computing any Solution of an Arbitrary Linear Difference Equation, Ph.D. Thesis, University of Maryland.
 [5]
 J. C. P. MILLER, British Association for the Advancement of Science: Bessel Functions, Part II. Mathematical Tables, Vol. 10, Cambridge Univ. Press, Cambridge, 1952.
 [6]
 K. S. MILLER, Linear Difference Equations, Benjamin, New York, 1968. MR 0227644 (37:3228)
 [7]
 J. OLIVER, "Relative error propagation in the recursive solution of linear recurrence relations," Numer. Math., v. 9, 1967, pp. 323340. MR 0213064 (35:3929)
 [8]
 J. OLIVER, "The numerical solution of linear recurrence relations," Numer. Math., v. 11, 1968, pp. 349360. MR 0226893 (37:2479)
 [9]
 J. OLIVER, "An extension of Olver's error estimation technique for linear recurrence relations," Numer. Math., v. 12, 1968, pp. 459467. MR 0239782 (39:1139)
 [10]
 F. W. J. OLVER, "Numerical solution of second order 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]
 J. H. WILKINSON, The Algebraic Eigenvalue Problem, Oxford Univ. Press, Oxford, 1965. MR 0184422 (32:1894)
 [13]
 R. V. M. ZAHAR, "A mathematical analysis of Miller's algorithm," Numer. Math., v. 27, 1977, pp. 427447.
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/S00255718197804835788
PII:
S 00255718(1978)04835788
Article copyright:
© Copyright 1978 American Mathematical Society
