ABSTRACT

At most one solution can increase exponentially with increasing n, and at most one solution can increase exponentially with decreasing n.

Let Un and Dn be the two solutions to equation (27), with the former increasing exponentially with increasing n, and the latter, with decreasing n. Suppose that Dn is the one we want. So we start by evaluating D0 and D1, and then calculating D2, D3,

..., from equation (27). However, any calculation contains some roundoff error, so what we really calculate is not exactly D2, but D2+e2U2, and then D3+e3U3, …. Because the Un increase exponentially with increasing n, the small errors e2, e3, …, grow and quickly swamp Dn, the desired solution. Calculating Dn by forward

recursion-in order of increasing n-is unstable under these circumstances. The way around this problem is to calculate them by backward recursion. If the

Un increase exponentially with increasing n, then they decrease exponentially with

decreasing n. If the recursion is unstable for calculating the Dn in the direction of increasing n, it will be stable in the other direction. There-

fore, pick a large integer N, and set D'N+1=0 and D'N=1. Then use equation (27) to

evaluate D'N-1, …, D'0. If a is any scalar, the set of aDn is a solution to equation (27) whenever the Dn are. We have evaluated D'n=aDn; we find the value of a by calculating the value of D0 and

If we have chosen N large enough, the error made by assuming that D'N+1=0 and D'

N=1 will be negligible. This topic is discussed more fully by Abramowitz and Stegun (1968), and by

Press et al(1992, pp 172 ff). The latter authors give several theorems about recursion. They also give a simple method for telling whether recursion in a given direction is stable. Given a recursion relation like equation (27), test it in the forward direction by taking D0=0, D1=1, and then calculating the first 30 or so of the Dn. If they all

remain about order unity, then the recursion is stable; if they grow wildly, it is not.