

@defun
def richardson(ctx, seq):
    '\n    Given a list ``seq`` of the first `N` elements of a slowly convergent\n    infinite sequence, :func:`~mpmath.richardson` computes the `N`-term\n    Richardson extrapolate for the limit.\n\n    :func:`~mpmath.richardson` returns `(v, c)` where `v` is the estimated\n    limit and `c` is the magnitude of the largest weight used during the\n    computation. The weight provides an estimate of the precision\n    lost to cancellation. Due to cancellation effects, the sequence must\n    be typically be computed at a much higher precision than the target\n    accuracy of the extrapolation.\n\n    **Applicability and issues**\n\n    The `N`-step Richardson extrapolation algorithm used by\n    :func:`~mpmath.richardson` is described in [1].\n\n    Richardson extrapolation only works for a specific type of sequence,\n    namely one converging like partial sums of\n    `P(1)/Q(1) + P(2)/Q(2) + \\ldots` where `P` and `Q` are polynomials.\n    When the sequence does not convergence at such a rate\n    :func:`~mpmath.richardson` generally produces garbage.\n\n    Richardson extrapolation has the advantage of being fast: the `N`-term\n    extrapolate requires only `O(N)` arithmetic operations, and usually\n    produces an estimate that is accurate to `O(N)` digits. Contrast with\n    the Shanks transformation (see :func:`~mpmath.shanks`), which requires\n    `O(N^2)` operations.\n\n    :func:`~mpmath.richardson` is unable to produce an estimate for the\n    approximation error. One way to estimate the error is to perform\n    two extrapolations with slightly different `N` and comparing the\n    results.\n\n    Richardson extrapolation does not work for oscillating sequences.\n    As a simple workaround, :func:`~mpmath.richardson` detects if the last\n    three elements do not differ monotonically, and in that case\n    applies extrapolation only to the even-index elements.\n\n    **Example**\n\n    Applying Richardson extrapolation to the Leibniz series for `\\pi`::\n\n        >>> from mpmath import *\n        >>> mp.dps = 30; mp.pretty = True\n        >>> S = [4*sum(mpf(-1)**n/(2*n+1) for n in range(m))\n        ...     for m in range(1,30)]\n        >>> v, c = richardson(S[:10])\n        >>> v\n        3.2126984126984126984126984127\n        >>> nprint([v-pi, c])\n        [0.0711058, 2.0]\n\n        >>> v, c = richardson(S[:30])\n        >>> v\n        3.14159265468624052829954206226\n        >>> nprint([v-pi, c])\n        [1.09645e-9, 20833.3]\n\n    **References**\n\n    1. [BenderOrszag]_ pp. 375-376\n\n    '
    if (len(seq) < 3):
        raise ValueError('seq should be of minimum length 3')
    if (ctx.sign((seq[(- 1)] - seq[(- 2)])) != ctx.sign((seq[(- 2)] - seq[(- 3)]))):
        seq = seq[::2]
    N = ((len(seq) // 2) - 1)
    s = ctx.zero
    c = ((((- 1) ** N) * (N ** N)) / ctx.mpf(ctx._ifac(N)))
    maxc = 1
    for k in xrange((N + 1)):
        s += (c * seq[(N + k)])
        maxc = max(abs(c), maxc)
        c *= ((k - N) * (ctx.mpf(((seq + N) + 1)) ** N))
        c /= ((1 + k) * (ctx.mpf((k + N)) ** N))
    return (s, maxc)

dataset/ETHPy150Open fredrik-johansson/mpmath/mpmath/calculus/extrapolation.py richardson/VarMisuse@212/1301 `k`->`seq`