# 4 Extrapolation Methods for Orthogonal Expansions

For extrapolation of expansions in orthogonal polynomials of the form

with partial sums

not many methods are known to work well. Besides the well-known algorithm of Wynn and the transformations [130], there are methods based on the acceleration of related complex power series [121], [124], [125]. If one does not like to work with complex arithmetics, one may use also the so-called transformation [120]. The transformation may be regarded as a generalization of the transformation that has proved to be useful for trigonometric Fourier series [119], [123]. Both transformations are obtained by iteration of a simple transformation.

We sketch the main ideas that lead to the transformation.

Consider the sequence of the partial sums to be extrapolated as given in Eq. (27), and write it in terms of the limit s and a tail as

By using the usual three-term recurrence relation of the orthogonal polynomials repeatedly, one may express the tail as

One may express as linear combination of and with x-dependent coefficients.

Remark
This is always possible in the cases of interest, at least asymptotically for large n. For example, specializing to Legendre functions and that satisfy the recurrence relation with the initial conditions , , , , one has the asymptotic relation[130] for large n where k is a constant. An easy calculation then shows for large n.

Using this method, it is possible to rewrite the tails as

Assuming that the leading behavior of and for large n is up to constants c and d given by remainder estimates , model sequences of the form

are obtained where the and obey the three-term recursion

where the coefficients for j=0, 1, 2 are x dependent. Rewriting this as

and applying the recursion relation (32) to both sides of the equation, one obtains

This may be solved for s. Then, we obtain

i.e., we can calculate the exact limit s for model sequences of the form (31). If a given sequence differs from this model, one cannot expect to calculate the limit exactly by this simple formula, but applying it is expected to yield a sequence of approximations that is closer to the limit if the problem sequence is ``close'' to the model. Thus, one obtains a sequence transformation given by the expression

We say that this transformation is exact for model sequences of the form (31) since it allows to calculate the exact limit s for such model sequences. This is the simple sequence transformation mentioned above that is to be iterated.

Iteration leads to the recursive scheme

that defines the transformation. Here, the are auxiliary quantities. This transformation is a nonlinear sequence transformation, if the depend on the .

We make the important observation that in each step of the iteration numbered by k, a new sequence of remainder estimates is used according to , and that the lower index of the recursion coefficients is shifted by k. Note that the remainder estimates depend only on the original remainder estimates and the auxiliary quantities . Note that the recursion relations for the numerators and denominators are nothing but the application of the three-term recurrence relation for (up to a scaling inducing by the ). Thus, the sequence transformation eliminates approximately contributions of orthogonal functions (and ) for successive higher values of n.

We specialize to the case of expansions in Legendre polynomials. Here, the input sequence of partial sums (27) is transformed into a new sequence

with , and . The latter correspond to the three-recurrence relation for . By we denote the integer part of x.

The transformed sequence converges normally much faster than the original one if the coefficients in (26) do not oscillate itself, and also considerably faster than the estimates obtained using the algorithm. [120] For further information on the extrapolation of orthogonal expansions see also [131], [121].

If the maximal value of n is 2N, i.e., if only partial sum up to are available, then is a polynomial of degree 2N in x. In this case, the transformed quantities are a rational function in x of the form

where is a polynomial of degree 2N and is a polynomial of degree N. For instance, for , , and N=2 we have

and

If the evaluation of the expansion at many values of x is required, then it pays to compute the coefficients of numerator and denominator polynomial once and for all from the known coefficients , and then, the additional numerical effort in comparison to the term-wise summation of the expansion is the additional evaluation of a polynomial of degree N. As we will see, the resulting expression is much more accurate than . For instance, is often 1000fold more accurate than .

Although this approach of fixing the maximum value of n throughout is very cost-effective, it has some disadvantages: The accuracy is not uniform, ie., not the same for all angles. Further, as seen from the explicit expression for , there are some values of for which the denominator polynomial vanishes. These angles may easily be identified in advance. In the vicinity of these angles either the explicit summation or linear convergence [132], [133] acceleration may be used. Then, however, convergence is much slower usually. Thus, a hybrid algorithm would have to be designed. Alternatively, by using the whole sequence of the as computed via the recursive scheme defining the transformation, one can stop the calculation when the difference between consecutive approximations lies below a threshold. This method will result in more uniform approximations. Also, for nonlinear convergence accelerators, one may use progressive forms and particular rules to avoid the rare cases that the denominators vanish (cp. [131], and [134] and references therein). Alternatively, the simple device to replace an accidentally vanishing denominator by a small number near the smallest floating point number and simply to go on with the recursive algorithm, has proven to work surprisingly well. [135] The latter approach can also be implemented in the programs for the transformation that were used in the present work.

We further remark that in the vicinity of the singularities of the Legendre series the convergence of the original series may become exceedingly slow (like for small ). In this case, convergence acceleration is especially desirable. Straightforward application of nonlinear convergence accelerators is not the best way to evaluate the sum of the orthogonal series. Instead, it is much better to use the fold frequency approach. ( : "tau") This is essentially the application of a convergence acceleration method to the sequence for some suitable integer . In the case of the transformation, this produces approximations

using , , and corresponding to the three-term recurrence relation of Legendre polynomials at the argument

One may choose the remainder estimated in this approach for instance as , i.e., as suitable coefficients of the Legendre series. For further details of the fold frequency approach, the interested reader is referred to the literature [121], [122], [123], [124], [125]. We are not going to use this approach in the following for simplicity.

Next: 5 A Simple Example Up: On Convergence Acceleration of Previous: 3 Three-center Nuclear Attraction

Herbert H. H. Homeier (herbert.homeier@na-net.ornl.gov)