An acceleration theorem for the \(\rho\)-algorithm (Q1923302)

The \(\rho\)-algorithm is a sequence transformation introduced by the reviewer [Proc. Camb. Phil. Soc., 52, 663-671 (1956; Zbl 0072.33802)] which involves the construction of numbers \(\rho (m,r)\) \((r>0\), \(m\geq 0)\) form the initial values \(\rho (m,-1)=0\) \((m >0)\), \(\rho(m,0) = S(m)\) \((m\geq 0)\) by use of the recursion \(\rho (m,r+1) = \rho (m+1,r-1)+ (r+ 1)/ \{\rho (m+1,r)-\rho (m,r)\}\) \((r,m\geq 0)\); it is often found that a number of the form \(\rho (m, 2r)\) is a better approximation to \(S= \lim S(m)\) \((m\to\infty)\) than any of the sequence members, \(S(\omega)\) \((m\leq\omega \leq m+2r)\), from which the number is derived, and that this is uniformly true for \(r>0\), \(m\geq 0\). The author shows that if \(S(m)\sim S+m^\theta \{\sum c(\omega) m^{-\omega} \mid\omega \geq 0\}\) for large \(m\) and \(\theta=-k\) is a negative integer, then \(\lim\{\rho (m,2k)-S\}/ \{S(m+2k)-S\} = \mu\) \((m\to\infty)\) where \(\mu=0\) and in this sense the \(\rho\)-algorithm accelerates convergence; if \(\text{Re} (\theta)<0\) and \(\theta\) is not a negative integer, \(\mu\neq 0\) for \(k=1,2,\dots\) and in this sense it does not. A similar negative conclusion is arrived at with respect to sequences for which \(S(m+1)-S = \{\lambda +e(m)\}\) \(\{S(m)-S\}\) where \(-1\leq \lambda<1\) \((\lambda\neq 0)\) and \(\lim e(m)=0\) \((m\to\infty)\). The numerical performance of the \(\rho\)-algorithm is contrasted with that of other algorithms in selected cases and it is in this connection that attention is unwiltingly drawn to a characteristic of the algorithms concerned: all of them (the \(\rho\)-algorithm included) are, used as convergence acceleration devices, afflicted by pronounced growth of rounding error. Thus it would appear from Table IV on p. 530, for example, that as \(r\) increases, with \(m\) fixed, the discrepancies \(|S-\rho(m,2r)|\) decrease initially and then remain constant or even increase slightly. This is not so. During computation rounding errors grow and become as large as the discrepancies are \(|S-\rho (m,2r)|\); the computations then become swamped by noise. This happens with regard to all methods considered. This crucial matter is not dealt with in the paper by \textit{D. A. Smith} and \textit{W. F. Ford} [SIAM J. Numer. Anal., 16, 223-240 (1979; Zbl 0407.65002)] and in the book of \textit{C. Brezinski} and \textit{M. Redivo Zaglia} [Extrapolation methods. Theory and practice. North Holland, Amsterdam (1991; Zbl 0744.65004)] both referred to by the author. The most effective method of treating the monotonic sequences considered is by use of the Euler-Maclaurin sum formula, since the semi-infinite integrals involved are easily evaluated; an oscillating series involving derivatives is then transformed by repeated application of the \(\varepsilon\)-algorithm which, used in this way, is stable. Cases in which the semi-infinite integral involved is approximated in terms of integrand derivatives at the finite end point have been treated by the reviewer [see p. 87 et seq. of: Calcolo 15, No. 4, Suppl. 1-103 (1978; Zbl 0531.40002) and Section 10 of: The transformation of series by the use of Padé quotients and more general approximants; in: Padé and ration. Approx. (Eds. Saff E. B. and R. S. Varga) 121-144 (1977; Zbl 0368.41004)].