The rise and fall of the vector epsilon algorithm
The vector \(\varepsilon\)-algorithm is widely accepted as a powerful convergence acceleration method. Inevitably the algorithm has occasionally been misapplied and its theory misunderstood and misrepresented. The signal service rendered by the paper under review is to provide, in permanent and pellucid form, an example of such misrepresentation. The scalar \(\varepsilon\)-algorithm over, for example, the real numbers, is a simple recursion involving addition, subtraction and the formation of a reciprocal and is applied to a sequence \(S(m)\) \((m \geq 0)\) to produce further numbers \(\varepsilon (m | r)\) \((m,r \geq 0)\) of which \(\varepsilon (m | 2r)\) \((m,r \geq 0)\) are approximations to a limit associated with \(S\), while \(\varepsilon (m| 2r+1)\) \((m,r \geq 0)\) are auxiliary numbers. Convergence and stability of the algorithm have been investigated by the reviewer [SIAM J. Numer. Anal. 3, 91-122 (1966; Zbl 0299.65003)] and it has been found that, applied to sequences \(S\) of certain classes, convergence of derived sequences \(\varepsilon (m | 2r)\) to an associated limit is dramatically faster than original convergence and that the auxiliary numbers \(\varepsilon (m | 2r+1)\) alone are vitiated by error, the numbers \(\varepsilon(m| 2r)\) remaining unscathed: the process is stable. Applied to sequences \(S\) of other well defined classes, there is no improvement in convergence and error growth is catastrophic. In the context of these two cases, there are either excellent reasons for using the algorithm or compelling ones for not doing so. The \(\varepsilon\)-algorithm is extended to a suitable vector space over a field by replacing the reciprocal involved by an inverse of the form \(v/(v,v)\), the brackets denoting an inner product (which, in the context of a finite dimensional space, it may be advisable to accumulate in double precision arithmetic). The theory of the scalar \(\varepsilon\)- algorithm may be embedded in that of its linear algebra vector counterpart by taking all components to be equal: a special convergence and stability theory of the vector counterpart is immediately available, and further such theories exist. In the paper, the ``rise is a distorted history of the vector \(\varepsilon\)-algorithm containing some misleading statements. The ``fall is in two stages. To cover the first, the authors remark that instability occurs in the determination of the sequence \(\varepsilon (m | 2)\) when the scalar \(\varepsilon\)-algorithm is applied to real sequences for which \((*)\) \(S(m)\sim L+a\lambda^ m\) where \(\lambda = 1 + \delta\), \(\delta>0\) being small. As the above remarks suggest, this was known almost thirty years ago. The second stage is rather amusing. The authors consider a vector \(\varepsilon\)-algorithm variant introduced by the reviewer [Linear Algebra Appl. 1, 357-395 (1968; Zbl 0164.185)] and later considered by him in a more general theoretical setting [The abstract theory of the epsilon algorithm, Centre de rech. math., Univ. de Montréal, CRM-74 (1971)] in which the inner product is an integral, the evaluation of which, at each stage, is of course laborious. The numerical example provided involves the computation of \(\varepsilon (0 | 2)\) from functions \(S(0)\), \(S(1)\), \(S(2)\) alone. The remark (correctly) that for the sequence \(S\) considered, relationship \((*)\) holds \((L\) and \(a\) are now functions) with \(\lambda = 1 - \delta\) and that the determination of \(\varepsilon (m | 2)\) as \(m\) increases is unstable; they then ascribe the discrepancy between \(\varepsilon (0 | 2)\) and \(L=\lim S(m)\) to this instability. It is evidently due to the fact that \(\varepsilon (0 | 2)\) is derived from only three members of the sequence \(S\). The preceding treatment of the vector \(\varepsilon\)-algorithm serves as pattern to introduce a further double sequence of transformations involving not only integration but also evaluation of polynomial roots. The paper contains no proofs of anything; the publications referred to above are not mentioned.
- A note on the \(\epsilon\)-algorithm
- Acceleration Techniques for Iterated Vector and Matrix Problems
- Continued fractions whose coefficients obey a non-commutative law of multiplication
- Degeneracies of generalized inverse, vector-valued Padé approximants
- Extrapolation Methods for Vector Sequences
- Extrapolation methods for vector sequences
- Généralisations de la transformation de Shanks, de la table de Padé et de l'\(\varepsilon\)-algorithme
- scientific article; zbMATH DE number 3215568 (Why is no real title available?)
- Padé-type approximation and general orthogonal polynomials
- Row convergence theorems for generalised inverse vector-valued Padé approximants
- Solution of integral equations using generalised inverse, function-valued Padé approximants. I
- The optimal is not best for the SOR iteration method
- Vector valued rational interpolants. I
- Vector-valued, rational interpolants. III
- A family of the functional epsilon algorithms for accelerating convergence
- A family of Padé-type approximants for accelerating the convergence of sequences
- A review of Padé methods for the acceleration of convergence of a sequence of vectors
- Epsilon-algorithm and eta-algorithm of generalized inverse function-valued Padé approximants using for solution of integral equations
- Introduction to the improved Levin-type algorithms for accelerating convergence of sequence.
- Schwinger-Lanczos algorithm for calculation of off-shell \(T\)-matrix elements and Wynn's epsilon algorithm
- The epsilon algorithm and related topics
- The genesis and early developments of Aitken's process, Shanks' transformation, the \(\varepsilon\)-algorithm, and related fixed point methods
- Matrix completion with \(\varepsilon\)-algorithm. In memory of Peter Wynn (1931--2017)
- Similarities of the integral Padé approximants
- Introduction to the improved functional epsilon algorithm
- A new approach to acceleration of convergence of a sequence of vectors
- An algebraic approach to the vector \(\varepsilon\)-algorithm
- An empirical study of the -algorithm for accelerating numerical sequences
- Confluent form of the multistep -algorithm, and the relevant integrable system
- The vector acceleration algorithm
- scientific article; zbMATH DE number 1452662 (Why is no real title available?)
- Geometric approach to the parallel sum of vectors and application to the vector \(\varepsilon \)-algorithm
- scientific article; zbMATH DE number 822882 (Why is no real title available?)
- Analysis of the ϵ-algorithm to accelerate the convergence
- Solution of integral equations using Padé type approximants
- The vector epsilon algorithm -- a residual approach
- Problems and progress in vector Padé approximation
- Convergence and acceleration properties for the vector \(\epsilon\)- algorithm
- Similarities of the integral Padé approximants. II
This page was built for publication: The rise and fall of the vector epsilon algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1315206)
