##plugins.themes.bootstrap3.article.main##

There are two objectives for this paper. Firstly, we shall introduce the Thukral-determinantal formula, and secondly, we shall demonstrate the similarities between the well-established algorithms, namely the Aitkin Δ2 algorithm and the Durbin sequence transformation. In fact, we have found that the solution of the Thukral-determinantal formula is equivalent to the Thukral-sequence transformation formula.

Introduction

In almost all areas of numerical mathematics, there are convergence problems. In such cases, either the convergence is slow or even divergence is observed and accordingly many techniques for accelerating convergence have been devised. For example; Aitkin Δ2 algorithm, ε-algorithm, θ-algorithm, Lubkin transformation, Levin-type transformation, and many others may be found in [1], [2]. Whereas Durbin’s sequence transformation and Brezinski-Durbin-Redivo-Zaglia’s sequence transformation may be found in [3], [4]. It is well-established that the Durbin sequence transformation cannot be expressed as a ratio of two determinants [5], [6], and it has been a long quest to find this representation. Hence, the prime motive for the introduction of the Thukral-determinantal formula was to establish that the Durbin sequence transformation can be represented as a ratio of two determinants. Furthermore, we shall verify that the Thukral-determinantal formula produces an equivalent equation to the Thukral-sequence transformation, and there is a particular connection between the Brezinski-Durbin-Redivo-Zaglia’s sequence transformation.

The structure of this paper is as follows: In Section 2, we state the essential definitions relevant to the present work. In Section 3, we shall define the Thukral-determinantal formula, and in process we will demonstrate the similarities between the Aitkin Δ2 algorithm, the Durbin sequence transformation, and the Thukral-sequence transformation. In order to construct the new determinantal formula, the following proposition is essential.

Preliminaries

In order to construct an iterative scheme, the following assumptions are essential and are given in [1], [2].

Let us assume that is a slowly convergent or divergent sequence, whose elements sn are the partial sum of an infinite series, give as

s = i = 0 c i ,
s n = i = 0 n c i .

The basic assumption of all sequence transformation is that a sequence element sn can be for all indices n0 to be partitioned into a limit s a truncation error en according to

s n = s + e n .

The conventional approach of evaluating an infinite series consists of adding up so many terms that the error en ultimately becomes zero. Unfortunately, this is not always possible because of obvious practical limitations. Moreover, adding up further terms does not work in the case of a divergent series. Therefore, the development of new techniques plays an important role.

Furthermore, let us assume the two sequences |sn| and |sn| both converge to the same limit s. Another condition of the sequence |sn| converges more rapidly than |sn| then

lim n s n s s n s = 0.

Construction of the Thukral-Determinant Formula

In this section, we shall define the Thukral-determinantal formula for accelerating the convergence of sequences. In the process, we shall demonstrate that the Thukral-determinantal formula is in fact equivalent to the Thukral-sequence transformation formula and show a connection with the Brezinski-Durbin-Redivo-Zaglia [3], [4]. Hence, we shall show the similarities for the first five cases and then define the Thukral-determinantal formula as a general form. We begin with the Brezinski-Durbin-Redivo-Zaglia formula, where n, k, Δ operates, now and in sequel, on the variable n. For example,

B D R Z n = i = 0 k ( 1 ) i ( k i ) s n + i Δ s n + k i i = 0 k ( 1 ) i ( k i ) Δ s n + k i ,
Δ s n = ( s n + 1 s n ) .

In order to obtain the identical results between the Thukral-determinantal formula and the Thukral-sequence transformation we will modify the Brezinski-Durbin-Redivo-Zaglia formula, and define a new version, namely Thukral-sequence transformation as

t n = i = 0 k ( 1 ) i ( k i ) s n + i + 1 Δ s n + k i i = 0 k ( 1 ) i ( k i ) Δ s n + k i .

We shall demonstrate the similarities between the Thukral-determinantal formula and Thukral-sequence transformation for several values of k.

For case k=1:

T 1 = ( 1 ) 1 | 1 Δ s n 1 Δ s n + 1 s n + 1 s n | | 1 Δ s n + 1 1 Δ s n 1 1 | = ( s n Δ s n + 1 s n + 1 Δ s n ) ( Δ s n + 1 Δ s n ) 1 ( Δ s n Δ s n + 1 ) ( Δ s n + 1 Δ s n ) 1 .

By cancelling common factors and simplifying (7), we get

T 1 = ( s n + 2 s n s n + 1 2 ) ( s n + 2 2 s n + 1 + s n ) .

Using the Thukral-sequence transformation Formula (6) for case k=1, we obtain

t 1 = i = 0 1 ( 1 ) i ( 1 i ) s n + i + 1 Δ s n + 1 i i = 0 1 ( 1 ) i ( 1 i ) Δ s n + 1 i = s n Δ s n + 1 s n + 1 Δ s n Δ s n + 1 Δ s n .

Expanding and simplifying (9), we obtain

t 1 = ( s n + 2 s n s n + 1 2 ) ( s n + 2 2 s n + 1 + s n ) .

The Aitkin Δ2 algorithm is a well-known technique for accelerating the convergence of sequences and in fact, there are many versions of the algorithm [1]–[3], [7], the Eq. (10) is one of many versions of the Aitkin Δ2 algorithm. Therefore, it is apparent that (8) and (10) are equivalent and is one of the versions of the Aitken process.

We progress to k=2:

T 2 = ( 1 ) 2 | 1 Δ s n 1 Δ s n + 1 1 Δ s n + 2 n Δ s n n + 1 Δ s n + 1 n + 2 Δ s n + 2 s n + 2 s n + 1 s n | | 1 Δ s n + 2 1 Δ s n + 1 1 Δ s n n Δ s n + 2 n + 1 Δ s n + 1 n + 2 Δ s n 1 1 1 | = ( s n Δ s n + 2 2 s n + 1 Δ s n + 1 + s n + 2 Δ s n ) ( Δ s n + 2 Δ s n + 1 Δ s n ) 1 ( Δ s n 2 Δ s n + 1 + Δ s n + 2 ) ( Δ s n + 2 Δ s n + 1 Δ s n ) 1 .

Expanding the numerator and denominator of (11), we get

T 2 = ( s n Δ s n + 2 2 s n + 1 Δ s n + 1 + s n + 2 Δ s n ) ( Δ s n + 2 Δ s n + 1 Δ s n ) 1 ( Δ s n 2 Δ s n + 1 + Δ s n + 2 ) ( Δ s n + 2 Δ s n + 1 Δ s n ) 1 .

Again, we cancel the common factors and simplify (12), which yields

T 2 = ( s n Δ s n + 2 2 s n + 1 Δ s n + 1 + s n + 3 Δ s n ) ( Δ s n 2 Δ s n + 1 + Δ s n + 2 ) .

The second scheme of the Thukral-sequence transformation Formula (6) is given as

t 2 = i = 0 2 ( 1 ) i ( 2 i ) s n + i + 1 Δ s n + 2 i i = 0 2 ( 1 ) i ( 2 i ) Δ s n + 2 i .

The Eq. (14) is simplified as

t 2 = ( s n Δ s n + 2 2 s n + 1 Δ s n + 1 + s n + 2 Δ s n ) ( Δ s n 2 Δ s n + 1 + Δ s n + 2 ) .

Here also we find that the expressions (13) and (15) are identical.

For the purpose and motivation of this paper, we shall demonstrate similarities between the Thukral-determinantal formula and the Durbin sequence transformation for the next case.

When k=3, the Thukral-determinantal formula is given as

T 3 = ( 1 ) 3 | 1 Δ s n 1 Δ s n + 1 1 Δ s n + 2 1 Δ s n + 3 n Δ s n n 2 Δ s n n + 1 Δ s n + 1 n + 2 Δ s n + 2 ( n + 1 ) 2 Δ s n + 1 ( n + 2 ) 2 Δ s n + 2 n + 3 Δ s n + 3 ( n + 3 ) 2 Δ s n + 3 s n + 3 s n + 2 s n + 1 s n | | 1 Δ s n + 3 1 Δ s n + 2 1 Δ s n + 1 1 Δ s n n Δ s n + 3 n 2 Δ s n + 3 1 n + 1 Δ s n + 2 n + 2 Δ s n + 1 ( n + 1 ) 2 Δ s n + 2 ( n + 2 ) 2 Δ s n + 1 1 1 n + 3 Δ s n ( n + 3 ) 2 Δ s n 1 |

Evaluating the above equation, we get

T 3 = 2 ( s n Δ s n + 3 + 3 s n + 1 Δ s n + 2 + 3 s n + 2 Δ s n + 1 s n + 3 Δ s n ) ( Δ s n + 3 Δ s n + 2 Δ s n + 1 Δ s n ) 1 2 ( Δ s n 3 Δ s n + 1 + 3 Δ s n + 2 Δ s n + 3 ) ( Δ s n + 3 Δ s n + 2 Δ s n + 1 Δ s n ) 1 .

As before, we cancel the common factors of (17) and obtain

T 3 = ( s n Δ s n + 3 + 3 s n + 1 Δ s n + 2 3 s n + 2 Δ s n + 1 + s n + 3 Δ s n ) ( Δ s n 3 Δ s n + 1 + 3 Δ s n + 2 Δ s n + 3 ) .

We expand (18) and show the similarities between the Thukral-determinantal formula and the Durbin sequence transformation, thus becomes

T 3 = ( s n ( s n + 4 s n + 3 ) 3 s n + 1 ( s n + 3 s n + 2 ) + 3 s n + 2 ( s n + 2 s n + 1 ) s n + 3 ( s n + 1 s n ) ) ( ( s n + 1 s n ) + 3 ( s n + 2 s n + 1 ) 3 ( s n + 3 s n + 2 ) + ( s n + 4 s n + 3 ) ) .

By cancelling similar terms and simplifying (19), we get

T 3 = ( 3 s n + 2 2 4 s n + 1 s n + 3 + s n s n + 4 ) ( 6 s n + 2 4 ( s n + 1 + s n + 3 ) + ( s n + s n + 4 ) )

Which is identical to the Durbin sequence transformation [1], [3], [5]. Moreover, from the Thukral-sequence transformation Formula (6), for k=3, yields

t 3 = i = 0 3 ( 1 ) i ( 3 i ) s n + i Δ s n + 3 i i = 0 3 ( 1 ) i ( 3 i ) Δ s n + 3 i ,
t 3 = ( s n Δ s n + 3 3 s n + 1 Δ s n + 2 + 3 s n + 2 Δ s n + 1 s n + 3 Δ s n ) ( Δ s n + 3 3 Δ s n + 2 + 3 Δ s n + 1 Δ s n ) .

Expanding and simplifying (22), we obtain

t 3 = ( 3 s n + 2 2 4 s n + 1 s n + 3 + 3 s n + 2 s n + 4 + s n s n + 4 ) ( 6 s n + 4 4 ( s n + 1 s n + 1 ) + 3 ( s n + 3 s n + 2 ) ) .

Consequently, for k=3 we have demonstrated that the Thukral-determinantal formula, the Durbin sequence transformation and the Thukral-sequence transformation formula produce identical results.

The Thukral-determinantal formula for k=4:

T 4 = ( 1 ) 4 | 1 Δ s n 1 Δ s n + 1 1 Δ s n + 2 1 Δ s n + 3 1 Δ s n + 4 n Δ s n n 2 Δ s n n 3 Δ s n s n + 4 n + 1 Δ s n + 1 n + 2 Δ s n + 2 n + 3 Δ s n + 3 ( n + 1 ) 2 Δ s n + 1 ( n + 2 ) 2 Δ s n + 2 ( n + 3 ) 2 Δ s n + 3 ( n + 1 ) 3 Δ s n + 1 ( n + 2 ) 3 Δ s n + 2 ( n + 3 ) 3 Δ s n + 3 s n + 3 s n + 2 s n + 1 n + 4 Δ s n + 4 ( n + 4 ) 2 Δ s n + 4 ( n + 4 ) 3 Δ s n + 4 s n | | 1 Δ s n + 4 1 Δ s n + 3 1 Δ s n + 2 1 Δ s n + 1 1 Δ s n n Δ s n + 4 n 2 Δ s n + 4 n 3 Δ s n + 4 1 n + 1 Δ s n + 3 n + 2 Δ s n + 2 n + 3 Δ s n + 1 ( n + 1 ) 2 Δ s n + 3 ( n + 2 ) 2 Δ s n + 2 ( n + 3 ) 2 Δ s n + 1 ( n + 1 ) 3 Δ s n + 3 ( n + 2 ) 3 Δ s n + 2 ( n + 3 ) 3 Δ s n + 1 1 1 1 n + 4 Δ s n ( n + 4 ) 2 Δ s n ( n + 4 ) 3 Δ s n 1 | .

Expanding (24), we obtain

T 4 = 12 ( s n Δ s n + 4 4 s n + 1 Δ s n + 3 + 6 s n + 2 Δ s n + 2 4 s n + 3 Δ s n + 1 + s n + 4 Δ s n ) ( Δ s n + 4 Δ s n + 3 Δ s n + 2 Δ s n + 1 Δ s n ) 1 12 ( Δ s n 4 Δ s n + 1 + 6 Δ s n + 2 4 Δ s n + 3 + Δ s n + 4 ) ( Δ s n + 4 Δ s n + 3 Δ s n + 2 Δ s n + 1 Δ s n ) 1 .

Eliminating the common factors and simplifying (25), we get

T 4 = ( s n Δ s n + 4 4 s n + 1 Δ s n + 3 + 6 s n + 2 Δ s n + 2 4 s n + 3 Δ s n + 1 + s n + 4 Δ s n ) ( Δ s n 4 Δ s n + 1 + 6 Δ s n + 2 4 Δ s n + 3 + Δ s n + 4 ) .

The Thukral-sequence transformation Formula (6), for k=4 is given as

t 4 = i = 0 4 ( 1 ) i ( 4 i ) s n + i + 1 Δ s n + 4 i i = 0 4 ( 1 ) i ( 4 i ) Δ s n + 4 i ,
t 4 = ( s n Δ s n + 4 4 s n + 1 Δ s n + 3 + 6 s n + 2 Δ s n + 2 4 s n + 3 Δ s n + 1 + s n + 4 Δ s n ) ( Δ s n + 4 4 Δ s n + 3 + 6 Δ s n + 2 4 Δ s n + 1 + Δ s n ) .

It is apparent that (26) and (28) are identical and hence the Thukral-determinantal formula and the Thukral-sequence transformation formula produce identical results.

The Thukral-determinantal formula for k=5:

T 5 = ( 1 ) 5 | 1 Δ s n 1 Δ s n + 1 1 Δ s n + 2 1 Δ s n + 3 1 Δ s n + 4 1 Δ s n + 5 n Δ s n n 2 Δ s n n 3 Δ s n n + 1 Δ s n + 1 n + 2 Δ s n + 2 n + 3 Δ s n + 3 ( n + 1 ) 2 Δ s n + 1 ( n + 2 ) 2 Δ s n + 2 ( n + 3 ) 2 Δ s n + 3 ( n + 1 ) 3 Δ s n + 1 ( n + 2 ) 3 Δ s n + 2 ( n + 3 ) 3 Δ s n + 3 n + 4 Δ s n + 4 n + 5 Δ s n + 5 ( n + 4 ) 2 Δ s n + 4 ( n + 5 ) 2 Δ s n + 5 ( n + 4 ) 3 Δ s n + 4 ( n + 5 ) 3 Δ s n + 5 n 4 Δ s n s n + 5 ( n + 1 ) 4 Δ s n + 1 s n + 4 ( n + 2 ) 4 Δ s n + 2 s n + 3 ( n + 3 ) 4 Δ s n + 3 s n + 2 ( n + 4 ) 4 Δ s n + 4 ( n + 5 ) 4 Δ s n + 5 s n + 1 s n | | 1 Δ s n + 5 1 Δ s n + 4 1 Δ s n + 3 1 Δ s n + 2 1 Δ s n + 1 1 Δ s n n Δ s n + 5 n 2 Δ s n + 5 n 3 Δ s n + 5 n + 1 Δ s n + 4 n + 2 Δ s n + 3 n + 3 Δ s n + 2 ( n + 1 ) 2 Δ s n + 4 ( n + 2 ) 2 Δ s n + 3 ( n + 3 ) 2 Δ s n + 2 ( n + 1 ) 3 Δ s n + 4 ( n + 2 ) 3 Δ s n + 3 ( n + 3 ) 3 Δ s n + 2 n + 4 Δ s n + 1 n + 5 Δ s n ( n + 4 ) 2 Δ s n + 1 ( n + 5 ) 2 Δ s n ( n + 4 ) 3 Δ s n + 1 ( n + 5 ) 3 Δ s n n 4 Δ s n + 5 1 ( n + 1 ) 4 Δ s n + 4 1 ( n + 2 ) 4 Δ s n + 3 1 ( n + 3 ) 4 Δ s n + 2 1 ( n + 4 ) 4 Δ s n + 1 ( n + 5 ) 4 Δ s n 1 1 | .

Similarly, we expand (29) and obtain where the common factors of the numerator and the dominator of (30) are denoted as

T 5 = ( s n Δ s n + 5 5 s n + 1 Δ s n + 4 + 10 s n + 2 Δ s n + 3 10 s n + 3 Δ s n + 2 + 5 s n + 4 Δ s n + 1 s n + 5 Δ s n ) R 5 ( Δ s n 5 Δ s n + 1 + 10 Δ s n + 2 10 Δ s n + 3 + 5 Δ s n + 4 Δ s n + 5 ) R 5 ,
R 5 = 288 ( Δ s n + 5 Δ s n + 4 Δ s n + 3 Δ s n + 2 Δ s n + 1 Δ s n ) 1 .

By cancelling these factors and simplifying (31), we get

T 5 = ( s n Δ s n + 5 5 s n + 1 Δ s n + 4 + 10 s n + 2 Δ s n + 3 10 s n + 3 Δ s n + 2 + 5 s n + 4 Δ s n + 1 s n + 5 Δ s n ) ( Δ s n + 5 5 Δ s n + 4 + 10 Δ s n + 3 10 Δ s n + 2 + 5 Δ s n + 1 Δ s n ) .

Expanding the Thukral-sequence transformation Formula (6) for k=5,

t 5 = i = 0 5 ( 1 ) i ( 5 i ) s n + i + 1 Δ s n + k i i = 0 5 ( 1 ) i ( 5 i ) Δ s n + k i ,
t 5 = ( s n Δ s n + 5 5 s n + 1 Δ s n + 4 + 10 s n + 2 Δ s n + 3 10 s n + 3 Δ s n + 2 + 5 s n + 4 Δ s n + 1 s n + 5 Δ s n ) ( Δ s n + 5 5 Δ s n + 4 + 10 Δ s n + 3 10 Δ s n + 2 + 5 Δ s n + 1 Δ s n ) .

We observe that the equations of the Thukral-determinantal formula and the Thukral-sequence transformation formula given by (32) and (34) respectively are identical.

In general, we define the Thukral-determinantal formula as where n, k, provided the denominator of (35) is a nonzero and sn is given by (2).

T n k = ( 1 ) k | 1 Δ s n 1 Δ s n + k 1 1 Δ s n + k n Δ s n n + 1 Δ s n + k 1 n + k Δ s n + k s n + k s n + k 1 s n | | 1 Δ s n + k 1 Δ s n + k 1 1 Δ s n n Δ s n + k n + k 1 Δ s n + k 1 n + k Δ s n 1 1 1 | ,

Mathematically we have demonstrated that the Thukral-determinantal Formula (35) produces identical results when compared to the Thukral-sequence transformation Formula (6), whereas only the odd values of k are identical to the formula of Brezinski-Durbin-Redivo-Zaglia sequence transformation, given by (5). Therefore, we postulate that the relationship between the two new Thukral’s formulae is given as and we conjecture that the connection between the Thukral-determinantal formula and the Brezinski-Durbin-Redivo-Zaglia’s sequence transformation is

T n k = t n = i = 0 k ( 1 ) i ( k i ) s n + i + 1 Δ s n + k i i = 0 k ( 1 ) i ( k i ) Δ s n + k i ,
T n 2 k 1 = i = 0 2 k 1 ( 1 ) i ( 2 k 1 i ) s n + i Δ s n + 2 k i 1 i = 0 2 k 1 ( 1 ) i ( 2 k 1 i ) Δ s n + 2 k i 1 .

Remarks and Conclusion

In this study, we have introduced the Thukral-determinantal formula and the Thukral-sequence transformation formula for accelerating the convergence of a sequence. It is well established that the Durbin sequence transformation has not been presented in a ratio of two determinants [4]–[6]. Hence, it was of great interest to find a formula. In the process, we have demonstrated the similarities between the Thukral-determinantal formula for the Aitkin Δ2 algorithm and the Durbin sequence transformation for case k=1 and k=3, respectively. Furthermore, we have found that the Thukral-determinantal formula produces mathematically equivalent results to the new Thukral-sequence transformation formula, and only odd values of k results are similar to Brezinski-Durbin-Redivo-Zaglia’s sequence transformation. Finally, further work is in progress to obtain the variants of the Thukral-determinantal formula and establish an efficient convergence accelerator.

References

  1. Sidi A. Practical Extrapolation Methods. Cambridge, England: Cambridge university Press; 2003.
     Google Scholar
  2. Weniger EJ. Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series. Comput Phys Rep. 1989;10:189–371, Los Alamos Preprint math-ph/0306302. Available from: http://arXiv.org.
     Google Scholar
  3. Brezinski C, Redivo-Zaglia M. Generalizations of Aitken’s process for accelerating the convergence of sequences. Comput Appl Maths. 2007;26:171–89.
     Google Scholar
  4. Durbin F. Private communication with Brezinski C, Redivo-Zaglia M. 2003.
     Google Scholar
  5. Chang XK, He Y, Hu XB, Li SH. A new integrable convergence acceleration algorithm for computing Brezinski-Durbin-Redivo-Zaglia’s sequence transformation via pfaffians. Numer Algor. 2018;78:87–106. doi: 10.1007/s11075-017-0368-z.
     Google Scholar
  6. Thukral R. Private communication with Brezinski C. 2024.
     Google Scholar
  7. Aitken AC. On Bernoulli’s numerical solution of algebraic equations. Proc Roy Soc Edinburgh. 1926;46:289–305.
     Google Scholar