Textbook in PDF format

The purpose of this book is to present applied mathematicians, numerical analysts, engineers, physicists and computer scientists with an in-depth study of that vast body of computational techniques based on the use of recurrence relations.
These methods can be traced back to the dawn of mathematics. The Babylonians used such a technique to compute the square root of a positive number, and the Greeks to approximate it. Much later, Lagrange A789) used a computational scheme based on a two-dimensional non-linear recurrence to compute an elliptic integral.
Current interest in the subject, though, can be attributed to some almost offhand remarks made by J.C.P. Miller in an introduction to a table of Bessel functions he had compiled for the British Association for the Advancement of Science. This book, which was published in 1952, coincided with the vaulting growth of large-scale digital computers; although Miller's work was prefigured by some observations of Lord Rayleigh A910) on the calculation of spherical Bessel functions, it was only with the advent of large-scale computers that the great promise of these algorithms could be brought to fruition.
What Miller perceived was that in a second-order linear recurrence which has solutions sufficiently differentiated asymptotically, there is a solution that may be uniquely characterized by one initial value and a knowledge of its growth. This led to an algorithm for computing certain solutions of the equation which required only a scant knowledge of their pointwise values.
List of symbols.
General results on the forward stability of recursion relations.
Background.
Homogeneous systems.
Nonhomogeneous systems.
The first-order scalar case; forward vs. backward recursion.
The computation of successive derivatives.
Scalar equations of higher order: minimal and dominant solutions.
First-order equations used in the backward direction: the Miller algorithm.
Introduction: the algorithm.
Convergence and error analysis.
Second-order homogeneous equations: the Miller algorithm.
The algorithm.
Reduction of the error by the use of asymptotic information.
Error analysis, the simplified algorithm: case of negative coefficients.
Error analysis, the general algorithm.
Algorithms based on continued fractions.
Minimal solutions and orthogonal polynomials.
The Clenshaw averaging process.
Applications of the Miller algorithm to the computation of special functions.
The confluent hypergeometric function I (a, c;x).
The confluent hypergeometric function ty(a,c\x).
The Gaussian hypergeometric function.
Associated Legendre functions.
The Legendre function Q?(z).
The Jacobi polynomials P^T1"iTl)(-itD).
Bessel functions.
Zeros of Bessel functions.
Eigenvalues of Mathieu's equation.
Second-order nonhomogeneous equations: the Olver algorithm.
Introduction: the algorithm.
Solution by forward elimination (Method A).
The method of averaging (Method B).
The LU-decomposition (Method C).
Adaptation to general normalizing conditions.
Conclusions.
Higher-order systems: homogeneous equations.
Observations on higher-order equations.
The Miller algorithm.
The matrix formulation: stability and weak stability.
The Clenshaw averaging process.
Topics for future research: infinite systems:
Basic series for functions satisfying functional equations.
Stieltjes moment integrals.
Higher-order systems (continued): the nonhomogeneous case.
The Wimp-Luke method.
The Lozier algorithm.
The computation of 3F2(1).
The recursion.
The algorithm; truncation error.
Computing the Beta function.
Another 3F2(1).
Computations based on orthogonal polynomials.
Preliminaries: properties of some orthogonal polynomials.
Chebyshev polynomials.
Jacobi polynomials.
Evaluation of finite sums of functions which satisfy a linear homogeneous recurrence.
The algorithm.
Error analysis; three-term recurrence.
Converting one expansion into another.
Series solutions to ordinary differential equations.
Taylor series solutions.
The construction of general recurrence relations for the coefficients of Gegenbauer series.
Introduction and basic formulas.
The algorithms of Clenshaw and Elliott.
The Lewanowicz construction.
Chebyshev series solutions for nonlinear differential equations.
Multidimensional recursion algorithms; general theory.
Background: convergence properties of complex sequences.
Introduction; invariants.
Divergence; strange attractors.
Mean values.
Two-dimensional algorithms.
General remarks: invariant curves.
Evaluation of certain infinite products.
Carlson's results.
An algorithm of Gatteschi.
Tricomi's algorithm.
Solutions of linear functional equations.
Higher-dimensional algorithms.
The computation of a class of trigonometric integrals.
Incomplete elliptic integrals.
Appendix A The general theory of linear difference equations.
Appendix B The asymptotic theory of linear difference equations.
General theory.
The construction of formal series solutions.
The Olver growth theorems.
Appendix C Recursion formulas for hypergeometric functions.
Index of higher mathematical functions discussed