A New Algorithm for the Higher-Order $G$-Transformation
Provides a more efficient numerical method for computing infinite-range integrals and sequence transformations, benefiting computational scientists.
This work develops the FS/qd-algorithm for computing the higher-order G-transformation, which reduces operation count compared to the rs-algorithm and also efficiently implements the Shanks transformation, outperforming the ε-algorithm.
Let the scalars $A^{(j)}_n$ be defined via the linear equations $$A_l=A^{(j)}_n+\sum^n_{k=1}\barα_ku_{k+l-1},\ \ l=j,j+1,\ldots,j+n\ .$$ Here the $A_i$ and $u_i$ are known and the $\barα_k$ are additional unknowns, and the quantities of interest are the $A^{(j)}_n$. 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^{(j)}_n$ 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 $\varepsilon$-algorithm of Wynn that is normally used for this purpose.