TOPICS
Search

Wynn's Epsilon Method


Wynn's epsilon method is a recursive algorithm for computing Shanks' transformation of a sequence. It is used for numerical sums and products by transforming their partial sums or partial products.

In particular, the method provides an efficient algorithm for implementing transformations of the form

 T(S_n)=(S_(n+1)S_(n-1)-S_n^2)/(S_(n+1)-2S_n+S_(n-1)),

where S_n=sum_(k=0)^(n)a_k is the nth partial sum of a sequence {a_k}_(k=0)^infty, with n>=1 and nonzero transformation denominator. The transformation can yield convergence improvement (Hamming 1986, p. 205). Set epsilon_0(S_n)=S_n, epsilon_(-1)(S_n)=0, and use

 epsilon_(r+1)(S_n)=epsilon_(r-1)(S_(n+1))+1/(epsilon_r(S_(n+1))-epsilon_r(S_n))

for r=0, 1, ..., wherever the denominator is nonzero. For a positive integer k, the values epsilon_(2k)(S_n) give Shanks' transformation of order k, based on S_n, ..., S_(n+2k). The case k=1 gives Aitken's delta-squared process, with epsilon_2(S_n)=T(S_(n+1)). Higher orders generally differ from repeated applications of Aitken's delta-squared process.

Wynn's epsilon method can be invoked in numerical summation and multiplication using Method -> "WynnEpsilon" in the Wolfram Language's NSum and NProduct commands. It is also utilized in the routine NLimit[expr, x -> x0] in the Wolfram Language package NumericalCalculus` .

Wynn's epsilon method is a member of a large family of similar so-called lozenge, or rhombus, transformations (Hamming 1986, p. 207).

Generalizations include a one-parameter family connecting the original epsilon table with iterated Aitken's delta-squared process (Vanden Broeck and Schwartz 1979), an adaptable scalar summation algorithm (Killingbeck 1988), and simplified topological epsilon algorithms for vector sequences (Brezinski and Redivo-Zaglia 2017). These extensions use different transformations and should not be identified with repeated application of the original scalar recurrence.

The related Wynn's rho algorithm replaces the numerator 1 in the recurrence by a difference of interpolation nodes. Its rational-extrapolation model differs from the model underlying Shanks' transformation.


See also

Aitken's Delta-Squared Process, Convergence Improvement, Euler-Maclaurin Integration Formulas, Shanks' Transformation, Wynn's Rho Algorithm

Explore with Wolfram|Alpha

References

Brezinski, C. "Convergence Acceleration during the 20th Century." J. Comput. Appl. Math. 122, 1-21, 2000. https://doi.org/10.1016/S0377-0427(00)00360-5.Brezinski, C.; Norman, F. A.; and Redivo-Zaglia, M. "The Legacy of Peter Wynn." Mathematics 9, 1240, 2021. https://doi.org/10.3390/math9111240.Brezinski, C. and Redivo Zaglia, M. "Scalar Extrapolation Algorithms." In Extrapolation Methods: Theory and Practice. Amsterdam, Netherlands: North-Holland, pp. 55-143, 1991. https://doi.org/10.1016/B978-0-444-88814-3.50006-4.Brezinski, C. and Redivo-Zaglia, M. "The Simplified Topological epsilon-Algorithms: Software and Applications." Numer. Algorithms 74, 1237-1260, 2017. https://doi.org/10.1007/s11075-016-0238-0.Hamming, R. W. Numerical Methods for Scientists and Engineers, 2nd ed. New York: Dover, pp. 206-207, 1986.Killingbeck, J. "An Adaptable Summation Algorithm." Phys. Lett. A 132, 223-225, 1988. https://doi.org/10.1016/0375-9601(88)90552-X.National Institute of Standards and Technology. "Acceleration of Convergence." §3.9 in NIST Digital Library of Mathematical Functions. https://dlmf.nist.gov/3.9.Shanks, D. "Nonlinear Transformations of Divergent and Slowly Convergent Sequences." J. Math. Phys. 34, 1-42, 1955. https://doi.org/10.1002/sapm19553411.Vanden Broeck, J.-M. and Schwartz, L. W. "A One-Parameter Family of Sequence Transformations." SIAM J. Math. Anal. 10, 658-666, 1979. https://doi.org/10.1137/0510061.Weniger, E. J. "Nonlinear Sequence Transformations for the Acceleration of Convergence and the Summation of Divergent Series." Comput. Phys. Rep. 10, 189-371, 1989. https://doi.org/10.1016/0167-7977(89)90011-7. https://arxiv.org/abs/math/0306302.Wynn, P. "On a Device for Computing the e_m(S_n) Transformation." Math. Tables Aids Comput. 10, 91-96, 1956. https://doi.org/10.1090/S0025-5718-1956-0084056-6.Wynn, P. "Acceleration Techniques in Numerical Analysis, with Particular Reference to Problems in One Independent Variable." Proc. IFIPS, Munich. Munich, Germany, pp. 149-156, 1962.Wynn, P. "The Epsilon Algorithm and Operational Formulas of Numerical Analysis." Math. Comput. 15, 151-158, 1961. https://doi.org/10.1090/S0025-5718-1961-0158513-X.

Referenced on Wolfram|Alpha

Wynn's Epsilon Method

Cite this as:

Weisstein, Eric W. "Wynn's Epsilon Method." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/WynnsEpsilonMethod.html

Subject classifications