The rise and fall of the vector epsilon algorithm (Q1315206)

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.