Extrapolating a limit from finite numerical data

extrapolationlimitsnumerical methodssequences-and-series

Simply for fun, I'm wondering if there are techniques (rigourous or not) for estimating a sequential limit from finitely many terms

(under certain niceness assumptions, e.g., there is only negligible transient behaviour).

For definiteness, consider the following setting:

A toy problem

I have two sequences, $(a_n)_{n=1}^∞$ and $(b_n)_{n=1}^∞$ for which I have only been able to calculate the first 8 terms.

Here's what is known:

  • $a_n \leq b_n$ for all $n$.
  • $(a_n)$ increasing.
  • $(b_n)$ decreasing.
  • $(b_n-a_n) → 0$.

I.e., they converge and have the same limit, sandwiched between the two sequences.

Numerically,

  • $(a_n)_{n=1}^8 \approx (0.7767, 0.7863, 0.7940, 0.7995, 0.8034, 0.8062, 0.8081,
    0.8095)$    .
  • $(b_n)_{n=1}^8 \approx (0.8760, 0.8582, 0.8443, 0.8350, 0.82895, 0.8248, 0.8222,
    0.8202)$    .

Here is a plot:

Graph of sequences

So the shared limit is likely between 0.81 and 0.82.

The question: if a gun was placed to your head and you were told to guess the limit, what would you guess, and why?

(Or a probability density, if you prefer.)

Naive idea

One naive idea, focusing on each sequence individually, would be to try to approximate each data set with a converging curve. E.g., for some $N$, choose $(λ_n)_{n=1}^N$ so that

$$ a_n \approx \sum_{k=0}^N λ_k n^{-k}$$

in some fashion, and take $λ_0$ as the candidate limit. (And similarly for $(b_n)$.)

There are plenty of problems with this, with the arbitrariness of polynomial terms in the sum and the choice of fitting.

With the probably-poor choice of least-squares fitting, the following happens with the estimate when we vary $N$:

  • The estimates from each sequence mostly disagree!
  • Most estimates lie outside the admissible window.
  • In particular, for $N≥7$, the value bifurcates and settles down onto a totally wrong estimate.

These estimates are depicted in the following graph. (For larger $N$, it continues to settle down to the wrong value.)
lambda_0 as a function of N

Subquestion (optional): Can this naive method be improved, e.g., with a different choice of fitting functions and fitting method?

Best Answer

You're looking for series/sequence acceleration, such as Aitken's method. If you interpret another sequence as

$$x_{2n}=a_n,\quad x_{2n-1}=b_n$$

then you may also get accelerated convergence by applying the Van Wijngaarden transformation, which essentially suggests you should be looking at the averages of $a_n$ and $b_n$.

For your data set, the averages of the last three $a_n$ and $b_n$ are

$$\left(\frac{a_n+b_n}2\right)_{n=6}^8=(0.81550, 0.81515, 0.81485)$$

and the Aitken acceleration applied to those terms yields $0.81305$.

Related Question