---
tag: 827RWYT7Q6
kind: definition
name: Levin-type transformations
msc: [65B10, 65B05, 40A25]
defines: 1P47PCRVTZ
uses: [0JH4MN4K1C, 0NB643K60Q, 092GEF38YD, 90ANMX55DP]
sources:
  - url: https://en.wikipedia.org/wiki/Series_acceleration
---

## Definition

Let $\sum_{j \ge 0} a_j$ be a [[series|0JH4MN4K1C]] with [[partial sums|0NB643K60Q]] $s_n = \sum_{j=0}^{n} a_j$.
Let $(\omega_n)$ be a sequence of nonzero numbers, the remainder estimates, let $\beta > 0$, and let $k \ge 1$ be an integer.
The *Levin transformation* is
$$\mathcal{L}_k^{(n)} = \frac{\displaystyle\sum_{j=0}^{k} (-1)^j \binom{k}{j} (\beta + n + j)^{k-1} \frac{s_{n+j}}{\omega_{n+j}}}{\displaystyle\sum_{j=0}^{k} (-1)^j \binom{k}{j} (\beta + n + j)^{k-1} \frac{1}{\omega_{n+j}}},$$
defined when the denominator is not $0$.
The choice $\omega_n = a_n$ gives Levin's $t$-transformation, and $\omega_n = (\beta + n) a_n$ gives Levin's $u$-transformation.
Transformations of the same construction with other choices of remainder estimates or of the factors $(\beta + n + j)^{k-1}$ are called *Levin-type transformations*.

## Remarks

The formula is exact for the model sequences
$$s_n = s + \omega_n \sum_{i=0}^{k-1} \frac{c_i}{(\beta + n)^i}.$$
Indeed, $(\beta + n)^{k-1}(s_n - s)/\omega_n$ is then a polynomial in $n$ of degree at most $k - 1$, so its $k$-th difference vanishes.
Solving this for $s$ gives $\mathcal{L}_k^{(n)} = s$.
Example: for $a_j = x^j$ with $x \ne 0, 1$, one has $s_n - \frac{1}{1-x} = a_n \cdot \frac{-x}{1 - x}$, so the $t$-transformation with $k = 1$ returns $\frac{1}{1-x}$ for every $n$.
Non-example: if some term $a_{n+j}$ is $0$, the remainder estimate $\omega_{n+j} = a_{n+j}$ is $0$ and the $t$-transformation is not defined there.

## Explanations

### L1 human

The transformation divides out a guess of the error, removes a polynomial correction by taking differences, and reads off the sum.