An algorithm for nondominant solutions of linear second-order inhomogeneous difference equations

Authors:
Takemitsu Hasegawa and Tatsuo Torii

Journal:
Math. Comp. **64** (1995), 1199-1214

MSC:
Primary 65Q05; Secondary 65F05

DOI:
https://doi.org/10.1090/S0025-5718-1995-1284668-2

MathSciNet review:
1284668

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: An algorithm is given for computing a weighted sum of a nondominant solution of a linear second-order inhomogeneous difference equation to a prescribed accuracy by estimating the truncation error. The present method is an extension of both the stable numerical method due to Olver and Sookne and a summation technique due to Deuflhard for computing minimal solutions of a homogeneous difference equation. The method is illustrated by numerical examples.

**[1]**M. Branders and R. Piessens,*An extension of Clenshaw-Curtis quadrature*, J. Comput. Appl. Math.**1**(1975), 55-65. MR**0371022 (51:7245)****[2]**J. R. Cash,*An extension of Olver's method for the numerical solution of linear recurrence relations*, Math. Comp.**32**(1978), 497-510. MR**0483578 (58:3570)****[3]**-,*A note on the numerical solution of linear recurrence relations*, Numer. Math.**34**(1980), 371-386. MR**577404 (81g:65174)****[4]**C. W. Clenshaw and A. R. Curtis,*A method for numerical integration on an automatic computer*, Numer. Math.**2**(1960), 197-205. MR**0117885 (22:8659)****[5]**P. Deuflhard,*A summation technique for minimal solutions of linear homogeneous difference equations*, Computing**18**(1977), 1-13. MR**0433927 (55:6897)****[6]**W. Gautschi,*Computational aspects of three-term recurrence relations*, SIAM Rev.**9**(1967), 24-82. MR**0213062 (35:3927)****[7]**W. M. Gentleman,*Implementing Clenshaw-Curtis quadrature*II.*Computing the cosine transformation*, Comm. ACM**15**(1972), 343-346. MR**0327002 (48:5344)****[8]**G. H. Golub and C. F. Van Loan,*Matrix computations*, 2nd ed., The Johns Hopkins University Press, Baltimore, 1989. MR**1002570 (90d:65055)****[9]**T. Hasegawa and T. Torii,*A stable algorithm for numerical solutions of second-order linear difference equations*, J. Inform. Process.**23**(1982), 583-590 (in Japanese).**[10]**-,*Indefinite integration of oscillatory functions by the Chebyshev series expansion*, J. Comput. Appl. Math.**17**(1987), 21-29. MR**884258 (88d:65039)****[11]**T. Hasegawa, T. Torii, and H. Sugiura,*An algorithm based on the FFT for a generalized Chebyshev interpolation*, Math. Comp.**54**(1990), 195-210. MR**990599 (91c:65009)****[12]**T. Hasegawa and A. Sidi,*An automatic integration procedure for infinite range integrals involving oscillatory kernels*, submitted.**[13]**W. B. Jones and W. J. Thron,*Continued fractions*:*analytic theory and applications*, Addison-Wesley, Reading, MA, 1980. MR**595864 (82c:30001)****[14]**P. Levrie and A. Bultheel,*Convergence acceleration for the numerical solution of second-order linear recurrence relations*, SIAM J. Numer. Anal.**27**(1990), 166-177. MR**1034927 (91a:65244)****[15]**D. W. Lozier,*Numerical solution of linear difference equations*, report NBSIR 80-1976, NBS, Washington, 1980.**[16]**J. Oliver,*Numerical solution of linear recurrence relations*, Numer. Math.**11**(1968), 349-360. MR**0226893 (37:2479)****[17]**-,*An extension of Olver's error estimation technique for linear recurrence relations*, Numer. Math.**12**(1968), 459-467. MR**0239782 (39:1139)****[18]**F. W. J. Olver,*Numerical solution of second-order linear difference equations*, J. Res. NBS**71 (B)**(1967), 111-129. MR**0221789 (36:4841)****[19]**-,*Error bounds for linear recurrence relations*, Math. Comp.**50**(1988), 481-499. MR**929547 (89e:65146)****[20]**F. W. J. Olver and D. J. Sookne,*Note on backward recurrence algorithms*, Math. Comp.**26**(1972), 941-947. MR**0331826 (48:10158)****[21]**R. Piessens, E. deDoncker-Kapenga, C. W. Überhuber, and D. K. Kahaner,*QUADPACK, A subroutine package for automatic integration*, Springer-Verlag, Berlin-Heidelberg-New York-Tokyo, 1983. MR**712135 (85b:65022)****[22]**P. Van der Cruyssen,*A reformulation of Olver's algorithm for the numerical solution of second-order linear difference equations*, Numer. Math.**32**(1979), 159-166. MR**529906 (80c:65241)****[23]**J. Wimp,*Computation with recurrence relations*, Pitman, Boston, 1984. MR**727118 (85f:65001)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65Q05,
65F05

Retrieve articles in all journals with MSC: 65Q05, 65F05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1995-1284668-2

Keywords:
Three-term recurrence relation,
nondominant solution,
numerical instability,
LU factorization,
rank-one updating

Article copyright:
© Copyright 1995
American Mathematical Society