4.3 Algebraic and Numerical Methods

In this section, we first consider the task of constructing continued- fraction representations from power series. This is the topic which we considered from a theoretical viewpoint in the previous section. Second, we discuss methods by which the continued fractions which we have con­structed, or derived, should be evaluated numerically.

 

Viskovatov's method [1803] is a handy method for constructing contin- ued-fraction expansions, or equivalently staircase sequences of Pade ap­proximants, from the given power series. It avoids having to reciprocate any series numerically, as was part of the construction of (2.2) and (2.3). It is a labor saving device which is as useful for people as for computers. The method is based on the formal identity

(3.1)

Viskovatov's method is best described by an illustrative example.

 

 

 

 

 

 

 

 

 

 

 

 

 

(3.2)Thus the generation of staircase sequences of Pade approximants is abso­lutely straightforward in the nondegenerate case. The other straightforward method of economical construction of continued fractions from power series is the Q.D. algorithm, which we treat fully in the next section.

 

The other main question we consider in this section is that of how to evaluate a fraction such as (3.2) numerically. There does not seem to be an agreed best method of computing continued fractions, and so we state three principal methods without making any clear recommendation about which is "best". The problem is, given the elements a,, ft, and a value of the variable z, to compute which we assume to be a convergent fraction.

Forward recurrence method. The numerators At-(z) and denomina­tors 5,(z) are calculated from the recurrence relation (2.7). Because of the ease of computing the values of successive convergents, the forward recur­rence method is the standard method for computing continued fractions.

 

It is sometimes the case in practice that the crude approximation

(3.4)

gives a rough and ready estimate of the rate of growth of An and Bn. Equation (3.4) is exact in the special case that the coefficients an ft, in (2.7) are constant. If |'"i|>|'2|, the Y terms are the dominant components and the /2,5 terms become less significant as oo. Such considerations assist in the understanding of the following numerical hazards of the forward recurrence method.

Floating point overflow of A n, Bn. If |r, |> 1, floating-point overflow may occur at some point during the actual computation. Rescaling of An, An_\, Bn, and Bn , at the critical point in the obvious way is recommended. Underflow must likewise be anticipated.

Suppression of required solution by a dominant solution. If the true solutions An, Bn of the exact recurrence relation (2.7) are the subdominant solutions, they may be suppressed numerically. Other solutions, An, Bn, generated by different initial conditions (e.g. A0 ^A0) for which An/An —>0, B„/B„ —>0, exist in this case. Rounding error introduced in the initial stages always becomes a dominant effect in such calculations. The connection with the concepts of Miller's backward recurrence algorithm is obvious.

(c) Accumulation of roundoff error in a dominant solution. If \An\ and \Bn\ are decreasing sequences, rounding error may accumulate using the forward recurrence method. This has been discovered empirically [Jones and Thron, 1974] for the following continued fraction:

 

 

 

 

evaluated at

 

using fixed decimal precision in the floating point

operations. (Why would binary operations be different.') the traction is being evaluated on the edge of its domain of convergence, and so it is a natural prototype for investigation of the buildup of roundoff error.

 

Backward recurrence method. This method of evaluating the wth convergent of (3.3) starts at the "tail" end of the convergent. We define

 

 

 

 

 

 

 

 

 

and then

 

is the wth convergent of f(z). The major drawback of this

method is that ot deciding in advance which is the appropriate value of n to choose so that the wth convergent is an adequate approximation to f(z).

Summation formula. The wth convergent of (3.3) is given by the formula

 

 

where the quantities p,, p2, p3,..., p„ are defined in terms of the elements of the continued fraction by

 

 

and recursively by

 

 

Proof. We construct a summation formula by using the identity

 

 

 

 

 

a formula equivalent to (3.10) is derived as (7.6). A comparison of Equa­tions (3.7), (3.10) leads us to define

 

 

Equation (3.8) defines the first two convergents correctly. To establish (3.9). we use the recurrence relation

 

 

to prove that

 

 

and the recurrence

 

 

to prove that

 

 

Equation (3.9) is proved by multiplying (3.12) and (3.13).

 

which is a representation of (5.55)

A consequence of (3.8), (3.9) and the equivalence transformation (1.6) is the new representation

 

The summation formula expressed by (3.7)-(3.9) has the advantage that it is suitable for iterative computation, which is important if the rate of convergence is not known a priori.

For further details of the numerical methods, and especially for error estimates, we refer to Jones and Thron's companion volume [1980], to Blanch [1964], and to Gautschi [1967].

Exercise 1. Prove that the value of the repeating fraction (assumed conver-

 

gent

 

 

 

 

satisfies the equation

 

 

Deduce the value of the fraction. Pringsheim [1910] gives a full discussion of the evaluation of periodic continued fractions.

Exercise 2. Solve the recurrence relation for the numerators and de­nominators of the fraction

 

deduce that

 

and