next up previous external

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

4 Extrapolation Methods for Orthogonal Expansions

  For extrapolation of expansions in orthogonal polynomials of the form

  equation480

with partial sums

  equation486

not many methods are known to work well. Besides the well-known tex2html_wrap_inline2576 algorithm of Wynn and the tex2html_wrap_inline2582 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 tex2html_wrap_inline2584 transformation [120]. The tex2html_wrap_inline2584 transformation may be regarded as a generalization of the tex2html_wrap_inline2588 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 tex2html_wrap_inline2584 transformation.

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

equation505

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

equation509

One may express tex2html_wrap_inline2600 as linear combination of tex2html_wrap_inline2602 and tex2html_wrap_inline2604 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 tex2html_wrap_inline2598 and tex2html_wrap_inline2612 that satisfy the recurrence relation tex2html_wrap_inline2614 with the initial conditions tex2html_wrap_inline2616 , tex2html_wrap_inline2618 , tex2html_wrap_inline2620 , tex2html_wrap_inline2622 , one has the asymptotic relation[130] tex2html_wrap_inline2624 for large n where k is a constant. An easy calculation then shows tex2html_wrap_inline2630 for large n.

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

equation532

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

  equation540

are obtained where the tex2html_wrap_inline2646 and tex2html_wrap_inline2648 obey the three-term recursion

  equation546

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

equation560

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

equation566

This may be solved for s. Then, we obtain

equation580

i.e., we can calculate the exact limit s for model sequences of the form (31). If a given sequence tex2html_wrap_inline2592 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

equation607

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

  equation635

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

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 tex2html_wrap_inline2674 , and that the lower index of the recursion coefficients tex2html_wrap_inline2650 is shifted by k. Note that the remainder estimates tex2html_wrap_inline2680 depend only on the original remainder estimates tex2html_wrap_inline2682 and the auxiliary quantities tex2html_wrap_inline2666 . Note that the recursion relations for the numerators and denominators are nothing but the application of the three-term recurrence relation for tex2html_wrap_inline2686 (up to a scaling inducing by the tex2html_wrap_inline2666 ). Thus, the sequence transformation eliminates approximately contributions of orthogonal functions tex2html_wrap_inline2598 (and tex2html_wrap_inline2612 ) for successive higher values of n.

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

  equation707

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

The transformed sequence converges normally much faster than the original one if the coefficients tex2html_wrap_inline2710 in (26) do not oscillate itself, and also considerably faster than the estimates obtained using the tex2html_wrap_inline2576 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 tex2html_wrap_inline2718 are available, then tex2html_wrap_inline2718 is a polynomial of degree 2N in x. In this case, the transformed quantities tex2html_wrap_inline2726 are a rational function in x of the form

equation734

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

eqnarray743

and

displaymath2578

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 tex2html_wrap_inline2710 , 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 tex2html_wrap_inline2750 is much more accurate than tex2html_wrap_inline2718 . For instance, tex2html_wrap_inline2754 is often 1000fold more accurate than tex2html_wrap_inline2756 .

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 tex2html_wrap_inline2754 , there are some values of tex2html_wrap_inline2762 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 tex2html_wrap_inline2764 as computed via the recursive scheme defining the tex2html_wrap_inline2584 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 tex2html_wrap_inline2584 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 tex2html_wrap_inline2770 for small tex2html_wrap_inline2448 ). 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 tex2html_wrap_inline2774 fold frequency approach. ( tex2html_wrap_inline2776 : "tau") This is essentially the application of a convergence acceleration method to the sequence tex2html_wrap_inline2778 for some suitable integer tex2html_wrap_inline2780 . In the case of the tex2html_wrap_inline2584 transformation, this produces approximations

equation893

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

  equation909

One may choose the remainder estimated in this approach for instance as tex2html_wrap_inline2790 , i.e., as suitable coefficients of the Legendre series. For further details of the tex2html_wrap_inline2774 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 up previous external
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)