3.2 Acceleration and Overacceleration of Convergence

It is natural to ask how the accelerated sequence derived from Aitken's A2 method may be improved upon. The natural answer is to iterate Aitken's method. This answer is not entirely satisfactory, because of the lack of justification based on principle, as the following remarks will make clear.

Aitken's scheme works well if the original sequence converges geometri­cally; the accelerated sequence takes full account of the dominant terms in the original sequence, and one should wonder what is the reason for accelerating again. Let us suppose that the original sequence is a geometric sequence rounded to given accuracy. Then the accelerated sequence, accord­ing to (1.4), is the limit but contains the small rounding errors. Further acceleration by Aitken's method (and the Pade method for that matter) requires differencing, and consequently, the results depend entirely on rounding errors in the original sequence. Thus, some sort of theoretical basis or an empirical numerical criterion is an essential prerequisite before iterating acceleration schemes. It is all too tempting to try to extract too much information by accelerating a few terms of a sequence too fast.

 (Note the trivial variation on the

method described in Sections 3.1, and 1.1, where the approximants are evaluated at z= 1.) Working to first order in e in (1.1.8) and (1.1.9), we find the error bounds

 

 

showing that this approximant is sensitive, but not unduly sensitive, to rounding errors in the data coefficients. However, when we come to consider the [2/2] Padé approximant, we find that

 

 

to first order. We see that the value of Q{2/2\z) is completely controlled by rounding error in this case; the zeros of Q[2/2\z), which are the poles of the approximant, are distributed all over the complex plane. (We do not suggest that the distribution is random, and we would expect more zeros of Q'2/21(z) near \z\ — \ than near z = 0, for example.) Since the value of the [2/2] Padé approximant depends primarily on rounding error, whereas the [1/1] approximant is accurate within errors, use of the [2/2] approximant is an example of overacceleration of convergence. In this case, the moral is that we should use the lower-order approximant.

The Padé method has the following interpretation (among others): the given sequence has a certain number of geometric components which dominate. Let us suppose that with a^O, |a|<l, |/?|< 1, and « = 0,1,2,.... This expression may be rewritten as much smaller terms.

 

(2.2)

Note that Sn is derived from the series much smaller term, much smaller terms,divergent sequences, such as (2.1) with |

The third row of the Padé table takes account of the explicit leading terms in (2.1), (2.2), and (2.3), whereas direct calculation shows that the once iterated Aitken method does not. We assumed in (2.1) that a^O and so that there are genuinely two geometric components which dominate the remainder, and this assumption is crucial. We are a bit vague about the size of the remainder terms, so as not to prejudice the development, and to admit possibilities such as for which the odd terms vanish.

We assume that |a|<l and |/?|<1 which is conventional but not entirely necessary. The Padé method does make sense of well-posed problems with corresponding to a divergent sequence with one component derived from an arithmetic progression, the Padé method gives 5= oo with an obvious interpretation.

As in Section 1.3, to justify the Padé method, we form the function which we wish to evaluate at z=\. Formation of [L/2] approximants is suggested by the explicit dominant terms of (2.4), and we apply de Montessus's theorem. Borrowing from Section 6.2, we quote the theorem in context here.

 

 

 

 

 

 

 

 

 

[L/2] approximants converge for sequences such as (2.1) or series such as (2.3), with the stated hypothesis about the residuals.