A New Algorithm for the Higher-Order $G$-Transformation

Abstract

Let the scalars $A_n^{(j)}$ be defined via the linear equations $$A_l=A_n^{(j)}+\sum _{k=1}^n{\bar{\alpha }}_k{u}_{k+l-1},l=j,j+1,\dots ,j+n.$$ Here the $A_i$ and $u_i$ are known and the ${\bar{\alpha }}_k$ are additional unknowns, and the quantities of interest are the $A_n^{(j)}$. This problem arises, for example, when one computes infinite-range integrals by the higher-order $G$-transformation of Gray, Atchison, and McWilliams. One efficient procedure for computing the $A_n^{(j)}$ is the rs-algorithm of Pye and Atchison. In the present work, we develop yet another procedure that combines the FS-algorithm of Ford and Sidi and the qd-algorithm of Rutishauser, and we denote it the FS/qd-algorithm. We show that the FS/qd-algorithm has a smaller operation count than the rs-algorithm. We also show that the FS/qd algorithm can also be used to implement the transformation of Shanks, and compares very favorably with the $\epsilon$-algorithm of Wynn that is normally used for this purpose.