Aitken's transformation

Introduction

Continuous fractions

The basic hypothesis

About proofs

Euler's constant

ZIP-files

The sum of any line is value of that final expression 

from which expansion this line is appeared

Leonard Euler

Introduction

I do not know, how you, and me for a long time irritated, that a line

1 + z + z^2 + z^3 + z^4 + z^5 + z^6+... ( z - complex, that there )

yields excellent results at | z | < 1 under the formula S = 1 / ( 1 - z ) also does not work at | z | >= 1. 

I still understand about a point z = 1, but that that prevents the rests? - Ah, a circle of convergence...  Let's consider the symbolical partial sums

A₀( z ) = 1

A₁( z ) = 1 + z

A₂( z ) = 1 + z + z^2

A₃( z ) = 1 + z + z^2 + z^3

A₄( z ) = 1 + z + z^2 + z^3 + z^4

Let's calculate a certain combination from these sums

B₂( z ) = ( A₂ * A₀ - A₁^2 ) / ( A₂ + A₀ - A₁*2 ) = 1 / ( 1 - z )

B₃( z ) = ( A₃ * A₁ - A₂^2 ) / ( A₃ + A₁ - A₂*2 ) = 1 / ( 1 - z )

B₄( z ) = ( A₄ * A₂ - A₃^2 ) / ( A₄ + A₂ - A₃*2 ) = 1 / ( 1 - z )

Our sums were stabilized, and on the formula of the sum of a geometrical progression. And any problems at transition through a circle | z | = 1 this formula will not meet.

These formulas

also refer to as Aitken's transformation.

It well copes with geometrical progressions, and as numerical instability on a computer, as a rule, is connected to such progressions this transformation is used at calculations.

What makes this transformation with the partial sums of sedate lines? - Will transform them to rational function P_n( z ) / Q_m( z ). Really, from what we have taken, what exactly polynoms in the best way describe meeting functions?

Continuous fractions

Such approach investigated in 1892 french mathematician Pade. Polynoms A_i - these are pieces of MacLoren's line, their derivatives in zero down to i-th the order coincide with derivatives of initial function. A polynom A_i has i+1 factor. It is natural to demand, that fraction P_n( z ) / Q_m( z ), approximating A_i had as much factors (so to say to balance number of adjusted parameters ). From here m+1+n+1-1 = i+1 (one factor can be saved, having reduced fraction on the senior factor of a denominator). And all these fractions should keep constant the first i derivatives. Pade has written out the whole matrix of such fractions (n - on a vertical, m - across).

Later the formula for factors of polynoms has been deduced P_n( z ) and Q_m( z ), also it is proved, that the best speed of convergence at fractions, where m=n and m=n-1 (diagonals of the Pade-table) - these fractions are representatives of a class of continuous fractions.

The continuous fraction is a way of record of the lines, alternative to a polynom. An example

Beautifully, is not that so?

Not less beautifully, than Ln(1 + z) = 0 + z / 1 - z^2 / 2 + z^3 / 3 - z^4 / 4 + z^5 / 5 - z^6 / 6 + ...

The basic hypothesis

And sedate line and continuous fractions allow to receive brief (a minimum of factors) the formula keeping in zero the same derivatives, as from initial function. Aitken's transformation also keeps these derivatives.

Aitken's transformation which has been carried out once (from polynoms A_i to receive fractions B_i), results in the first column of the Pade-table (fraction of a kind P_i-1( z ) / Q₁( z )). But, Aitken's transformation can be applied and to B_i, having transformed them in C_i ( i=4, ... ), and to C_i, having transformed them in D_i ( i=6, ... ), and so on.

Here already about minimization of number of factors to speak it is not necessary - the degree of a denominator grows: a line C_i these are fractions of a kind P_i-1( z ) / Q₃( z ), a line D_i these are fractions of a kind P_i-1( z ) / Q₅( z ). I.e. the parity is broken m+n = i. It is too much adjusted parameters, but they are selected automatically and efficiently!

Let's compare quality of approximation of initial function ( Ln(1 + z ) ) in three ways: a sedate line, in continuous fraction, in Aitken's transformation. For concreteness I was limited to values of first six derivatives and examined a circle | z | < 2. The white circle is a border of a circle of convergence | z | = 1. As we see on a logarithmic scale,

Aitken's transformation provides the best convergence, than even the continuous fraction.

 About proofs

As well as everybody, I am able to prove, that Aitken's transformation does not spoil corresponding number of the first derivatives. 

The unique example when Aitken's transformation precisely converges to the necessary result is degenerated case of a geometrical progression.

I do not know any proof of convergence of Aitken's transformations for any other function. On a computer I have touched very many functions: EXP(z), SIN(z), COS(z), SH(z), CH(z), TG(z), arc SIN(z), arc TG(z), arc SH(z), arc TH(z), 1/(1-z) + 1/(1-2*z), (1-z+z^3)/(1-2*z+z^2) /Gregg, 1972/ and everywhere observed this result - the best convergence.

And, apparently, "counterexample". F( z ) = ( 1 + z + z^2 ) / ( 1 + z + z^2 + z^3 ).

A₀( z ) = 1

A₁( z ) = 1

A₂( z ) = 1

A₃( z ) = 1 - z^3

A₄( z ) = 1 - z^3

A₅( z ) = 1 - z^3 + z^4

Very hardly for Aitken's transformation to go on such in part to constant members of line. But... C₅( z ) = ( 1 + z + z^2 ) / ( 1 + z^2 ) / ( 1 + z ) = F( z ).

Euler's constant

I began L.Ejler's citation and I shall finish him line with zero radius of convergence (i.e. sedate line misses everywhere except for zero).

It is known, that 1 + z + 2! * z^2 + 3! * z^3 + 4! * z^4 + 5! * z^5 + ... @ 0.5963 at z = -1. Let's apply Aitken's transformation directly to a line from numbers

ZIP-files

Aitken_Ln.bmp(16Kb)