Valid to use all Wynn-extrapolated values?

Question

Hi,

I have a question about Wynn's epsilon algorithm for extrapolation of sequences. Say I have a list of N sequences, with each sequence being of length M. The goal is to evaluate the extrapolated value --- S[i], i = {1, 2, ... N} --- for each of the N sequences, which should give the dependence S[i] as a function of i.

The concern is this: the Wynn extrapolation on each sequence, after say k iterations (with k < M), gives us M - k extrapolated values and it is not clear which of these M - k values one should choose as the final S[i]. It may so happen that for the sequence i, it is the j -th value (j <= M - k) that converges whereas for the sequence i' it is the j'-th value, with j' != j. By "converges", I mean the result S[i] must be a smooth curve between i and i' without sharp awkward jumps. My question is: is there any theorem for this extrapolation technique which states that if it is the j-th value that converges for a given sequence, it must only be the j-th value that also converges for a closely related (in terms of arising from a given unknown function) sequence?

Note that it is neither always helpful nor possible to always choose k such that k = M - 1 because only every even-numbered iteration gives a converged list of M - k values.

Thanks, VKV

Answer 1

There really isn't a theorem you can use, since most of the applicable theory is for sequences with known asymptotic behavior. For "in the wild" sequences, you can do no better than to check that the results of the $\varepsilon$-algorithm remain sensible as you proceed. As a general rule however, for the recursion

$$\varepsilon_{k+1}^{(n)}=\varepsilon_{k-1}^{(n+1)}+\frac1{\varepsilon_{k}^{(n+1)}-\varepsilon_{k}^{(n)}}$$

the so-called "diagonal approximations" (borrowing from the theory of Padé approximants) $\varepsilon_m^{(0)}$ or $\varepsilon_m^{(1)}$, depending on which diagonal of the table you're already in, would be the most accurate approximations for the limit of your sequence. Still, for these algorithms, the human eye is a better judge of convergence than the computer, so have your Wynn routine print out the entire array if it can.

For more practical advice, have a look at E.J. Weniger's survey paper.

Answer 2

The issue is that for my problem at hand. $N$ --- the number of sequences --- can be over a thousand. It might be impracticable to print out such a table and inspect it visually every time. But yes, $\epsilon_{m}^{(0)}$ or $\epsilon_{m}^{(1)}$ tend to perform better. I still have to "experimentally" choose one of the two; just wondering if it is "legal" to mix-and-match between the two for the same underlying function.

As a practical note for computer implementation, it is preferable to use the progressive form of the Wynn algorithm i.e.

$\epsilon_{k+1}^{(n+1)} = \epsilon_{k+1}^{(n)} + \frac{1}{\epsilon_{k+2}^{(n)} - \epsilon_{k}^{(n+1)}}$

"Extrapolation methods" by Brezinski and Zaglia should give more details on this, though I should confess that I'm still in the process of demystifying the method of implementing this alternative route to myself.