|
""" |
|
Convergence acceleration / extrapolation methods for series and |
|
sequences. |
|
|
|
References: |
|
Carl M. Bender & Steven A. Orszag, "Advanced Mathematical Methods for |
|
Scientists and Engineers: Asymptotic Methods and Perturbation Theory", |
|
Springer 1999. (Shanks transformation: pp. 368-375, Richardson |
|
extrapolation: pp. 375-377.) |
|
""" |
|
|
|
from sympy.core.numbers import Integer |
|
from sympy.core.singleton import S |
|
from sympy.functions.combinatorial.factorials import factorial |
|
|
|
|
|
def richardson(A, k, n, N): |
|
""" |
|
Calculate an approximation for lim k->oo A(k) using Richardson |
|
extrapolation with the terms A(n), A(n+1), ..., A(n+N+1). |
|
Choosing N ~= 2*n often gives good results. |
|
|
|
Examples |
|
======== |
|
|
|
A simple example is to calculate exp(1) using the limit definition. |
|
This limit converges slowly; n = 100 only produces two accurate |
|
digits: |
|
|
|
>>> from sympy.abc import n |
|
>>> e = (1 + 1/n)**n |
|
>>> print(round(e.subs(n, 100).evalf(), 10)) |
|
2.7048138294 |
|
|
|
Richardson extrapolation with 11 appropriately chosen terms gives |
|
a value that is accurate to the indicated precision: |
|
|
|
>>> from sympy import E |
|
>>> from sympy.series.acceleration import richardson |
|
>>> print(round(richardson(e, n, 10, 20).evalf(), 10)) |
|
2.7182818285 |
|
>>> print(round(E.evalf(), 10)) |
|
2.7182818285 |
|
|
|
Another useful application is to speed up convergence of series. |
|
Computing 100 terms of the zeta(2) series 1/k**2 yields only |
|
two accurate digits: |
|
|
|
>>> from sympy.abc import k, n |
|
>>> from sympy import Sum |
|
>>> A = Sum(k**-2, (k, 1, n)) |
|
>>> print(round(A.subs(n, 100).evalf(), 10)) |
|
1.6349839002 |
|
|
|
Richardson extrapolation performs much better: |
|
|
|
>>> from sympy import pi |
|
>>> print(round(richardson(A, n, 10, 20).evalf(), 10)) |
|
1.6449340668 |
|
>>> print(round(((pi**2)/6).evalf(), 10)) # Exact value |
|
1.6449340668 |
|
|
|
""" |
|
s = S.Zero |
|
for j in range(0, N + 1): |
|
s += (A.subs(k, Integer(n + j)).doit() * (n + j)**N * |
|
S.NegativeOne**(j + N) / (factorial(j) * factorial(N - j))) |
|
return s |
|
|
|
|
|
def shanks(A, k, n, m=1): |
|
""" |
|
Calculate an approximation for lim k->oo A(k) using the n-term Shanks |
|
transformation S(A)(n). With m > 1, calculate the m-fold recursive |
|
Shanks transformation S(S(...S(A)...))(n). |
|
|
|
The Shanks transformation is useful for summing Taylor series that |
|
converge slowly near a pole or singularity, e.g. for log(2): |
|
|
|
>>> from sympy.abc import k, n |
|
>>> from sympy import Sum, Integer |
|
>>> from sympy.series.acceleration import shanks |
|
>>> A = Sum(Integer(-1)**(k+1) / k, (k, 1, n)) |
|
>>> print(round(A.subs(n, 100).doit().evalf(), 10)) |
|
0.6881721793 |
|
>>> print(round(shanks(A, n, 25).evalf(), 10)) |
|
0.6931396564 |
|
>>> print(round(shanks(A, n, 25, 5).evalf(), 10)) |
|
0.6931471806 |
|
|
|
The correct value is 0.6931471805599453094172321215. |
|
""" |
|
table = [A.subs(k, Integer(j)).doit() for j in range(n + m + 2)] |
|
table2 = table.copy() |
|
|
|
for i in range(1, m + 1): |
|
for j in range(i, n + m + 1): |
|
x, y, z = table[j - 1], table[j], table[j + 1] |
|
table2[j] = (z*x - y**2) / (z + x - 2*y) |
|
table = table2.copy() |
|
return table[n] |
|
|