3.1 Aitken's A2 Method as [L/l] Padé Approximants

One of the best-known and simplest techniques of accelerating the convergence of a sequence is Aitken's A2 method. Given a sequence of real or complex numbers, such that

As converges faster to 5.

It is clear from (1.2) why Aitken's method is called the A2 method. There are many reasons for expecting in general that converges to a limit, that this

limit is S, and that convergence has been accelerated. But we must add an early word of caution: Aitken's method does not work for any arbitrary convergent sequence S. Like all algorithms of numerical analysis, Aitken's method has its own domain of validity, and in certain circumstances it should not be used. An important example is where all the Sn are identical, so that the Tn are undefined. A more insidious example is the one in which the Sn are equal up to rounding errors, so that the Tn are meaningless noise. This is a notorious situation to beware of. But, in general, the method is safe if it is empirically convergent, and it has wide applicability.

Basically, Aitken's method [1926] is designed to treat sequences with geometric convergence.

We see that in this case, Aitken's method yields the exact answer at every stage. More generally, for a sequence ? which is dominated by one geomet­rically convergent component, we expect that Aitken's method accelerates convergence by "taking out the geometrically convergent part".

 

As a practical example (see Part II, Section 3.1) we consider the numerical evaluation of

(1.5)

The integrand of (5) is infinite at the end points, but the integral is well defined. We define Sn as the value of the integral obtained by using 2" equally spaced integration points. These Riemann sums, obtained by dou­bling the number of integration points at each successive evaluation, con­verge to S and are obtained with great ease. It turns out that Aitken's algorithm is a very effective technique of estimating S.

The connection between Pade approximants and Aitken's A2 method is made, as in Section 1.3, by using the series derived from the sequence. Define It follows that Sn are the partial sums of the series, and of course the series converges to S. We form the power series

(1.7)

The previous theorem makes quite precise the statement that Aitken's method and the [L/\] Pade method accelerate convergence of a sequence dominated by a geometrically convergent component, of the type given by (1.9). In the next section we turn our attention to generalizing these basic ideas. For further details of the general theory, we refer to Brezinski [1977].

If both sequences S and 5" given by (1.1) and (1.2) converge, then they converge to the same limit [Lubkin, 1952]. For an account of recent progress with convergence theory, we refer to Cordellier [1979a] and Germain-Bonne [1979].

Exercise 1. Show that Newton's method of finding a zero of a function 4>(z) takes the form (1.9), with the one-point iteration function

 

 

Exercise 2. Is it a good idea to accelerate convergence of the sequence generated by Newton's method of the previous exercise if

z0 is a simple root of cj>(z)?

Hence

zQ is a multiple root of <j>(z)?

 

 

 

and

Exercise 3. Consider the series

 

 

where

[Marx, 1963]. Define

and Tn by (1.2). Prove

 

for m— 1,2,3,...

that

 

 

 

 

 

 

Notice the implication that converges, yet {Tn} diverges by oscillation.