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

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*.

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 2*N*, i.e., if only partial sum up to
are
available, then is a polynomial of degree 2*N* in *x*. In this case, the
transformed quantities are a
rational function in *x* of the form

where is a polynomial of degree 2*N* 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.