accelerating convergence of a class of sequences

Question

Do any of the standard methods of acceleration convergence of series, when applied to the series $1 - 1 + 1/2 - 1/2 + 1/3 - 1/3 + ...$, give convergence to 0 with error $o(1/n)$?

I tried applying Euler's method to the series, and found that the estimates fall like $1/n$; in fact, the $n$th estimate seems to be to $2/n + o(1/n)$ (e.g., for $n=500$, the $n$th Euler's method estimate is about 1.992 over 500). There are better methods of accelerating convergence, but I don't know much about them.

More broadly, I am looking for a method of accelerating convergence of sequences in which the $n$th term is the mean of the first $n$ terms of a bounded almost periodic sequence. (E.g., in the case where the almost periodic sequence is the periodic sequence $1,-1,1,-1,1,-1,...$, the sequence of averages is $1/1,0/2,1/3,0/4,1/5,0/6,...$, which corresponds to the series $1/1-1/1+1/3-1/3+1/5-1/5+...$.)

Answer 1

The Aitken delta squared method gives $O(1/n^2)$.

Answer 2

This is perhaps naive, but your sequence of partial sums is squeezed between an upper and a lower series. Why privilege one over the other? I assume (perhaps incorrectly) that any standard convergence method applied to the harmonic sequence converges to $0$ with error $O(1/n)$.

Together with your sequence of partial sums $\mathbf{a}= 1 ,0 ,1/2, 0, 1/3, 0 \cdots$ consider the companion sequence $\mathbf{b}= 0, 1, 0, 1/2, 0, 1/3 \cdots.$ You want to have that after acceleration $\mathbf{a}$ and $\mathbf{b}$ converges to $0$ with error $o(1/n)$. This seems problematic if the acceleration has $\mathbf{a}+\mathbf{b}=1,1,1/2,1/2,1/3,1/3,\cdots$ converge to zero with error $O(1/n).$ Also, if the new value at each index depends only on the terms up to that point then whatever it gives for $\mathbf{a}$ after $10$ terms should be no less than what it gives for $1/5,0,1/5,0,1/5,0,1/5,0.$

With an eye to methods tuned to this particular situation, let me see if I understand. You have sequences such as the fibonnacci word $0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 \cdots$ obtained by starting with $0$ and then repeatedly replacing $0 \to 0 1$ and $1 \to 0$ so the averages go to $\frac{\sqrt(5)-1}{2}$ and also the sequence with $n$th term $2/3+\cos(n)$ with averages converging to $2/3.$ So there are several of these, perhaps even infintely many all added together. We are given only the combined series (or, equivalently, the sequence of partial sums) and the knowledge that it arose this way and want to converge to the average value as rapidly as possible. Is that correct?

Answer 3

Since we know the setup, we can assume that we have the sequence of running totals or the original almost periodic sequence as we choose. Suppose I tell you ahead of time that I am working with a sequence taking only two integer values $p-1$ and $p$ and formed by choosing a positive real $p-1 \lt r \lt p$ and taking the values $\lfloor nr \rfloor-\lfloor (n-1)r \rfloor$. Then the averages converge to $r$ and the partial sums are $a_n=\lfloor nr \rfloor.$ Given this extra information you will have at each step a nondecreasing lower and a nonincreasing upper bound for $r.$ I can't see anything better to do than to take the average as an estimate. Only rarely are we unable to predict $a_n$ so the bounds only change infrequently. For example in the case $r=\frac{\sqrt{5}-1}{2}$ , which may be about the worst irrational case, when we find out that $a_{144}=88$ we know that $\frac{55}{89} \lt r \lt \frac{89}{144}.$ This gives an error of about $\frac{0.3618}{n^2}$. Then no new information arises as far as $a_{232}$ when the error is the same but now is about $\frac{0.947}{n^2}.$ Then $a_{233}=144$ improves the lower bound to $\frac{144}{233} \lt r \lt \frac{89}{144}$ which is again an error of about $\frac{0.3618}{n^2}$. So this is $O(\frac{1}{n^2})$ but I can't see $o(\frac{1}{n^2}).$

A slightly more problematic case is if I inform you that my chosen number is either $r=1$ or $r=\frac{M+1}{M}$ for some (maybe huge) $M$. Then if you ever see $a_n=n+1$ you will know exactly what $r$ is. But if you have gotten as far as $a_n=n$ (So forever if I actually chose $r=1$) you will only know that $1 \le r \le 1+\frac{1}{n+1}$

A related scheme is where I tell you that I have chosen a real $0 \lt r \lt 1$ which is to be the limiting average of the $0,1$ sequence formed as follows: I take the binary expansion $r=\sum\frac{b_i}{2^i}$ and use the sequence $b_1,b_2,b_1,b_3,b_1,b_2,b_1,b_4,\cdots$ which takes the value $b_i$ at all positions $(2m+1)2^{i-1}$. I imagine that would qualify as almost periodic. Choose $r$ a dyadic rational for a purely periodic sequence (whose period we will never know for sure in finite time). The only new information comes at positions of the form $2^i$ when we have an upper and lower bound which differ by $\frac{1}{2^i}$. If $r$ really is a dyadic rational and we decree the terminating binary expansion and we use the lower bound as our estimate, then eventually we will have perfect accuracy, but we won't know when it happens. If we use the midpoint then we will have an error which is $O(\frac{1}{n})$.

You might need some control of the "almost period". I'm not sure exactly what I mean by that but consider the case that I assure you that I have a purely periodic $0,1$ sequence with a finite (but potentially astronomical) period. Consider the rule: "choose the shortest initial segment which is not ruled out as one full period and use the average of that." After some finite stage it will be exactly the limit. However you will never know when that is and I can push the running averages back and forth between $0$ and $1$ as I please (as long as I stop before the end of time.)

Returning to the first example, which is especially well behaved, if we have a sum like $\lfloor nr \rfloor + \lfloor ns \rfloor$ we might, if we knoew this exact form, be able to sense the two kinds of jumps and seperately get estimates for $r,s.$ But for the running average of $r+s$, which is what we want, the numbers we get are within one of $\lfloor n(r+s) \rfloor$ so the error is about the same. I don't see that positive combinations like $ u\lfloor nr \rfloor + v\lfloor ns \rfloor$, even with more terms, would be that different (although it would take longer before things settled down.)

So here is a proposed method , somewhat vague, which might work well for certain almost periodic sequences with both positive and negative integer values (for convenience, rule out zero values): Split into two sequences, one non-negative and one non-positive whose termwise sum is the given sequence. For the non-negative sequence keep a fictional real $r$ in mind and pretend that the running totals should be $\lfloor rn \rfloor.$ At each stage we have a provisional lower bound and upper bound for $r$. If the actual total at stage $n$ is $a_n$ then consider the predicted values of this integer using the upper and lower bounds in $\lfloor rn \rfloor$. If these two integers are the same as each other and as $a_n$ then keep the bounds the same. If they differ and $a_n$ is between them then lower the upper bound or raise the lower bound as appropriate. However, if $a_n$ is outside the range then move the lower bound down or upper bound up.Perhaps these will pull togeteher even though they stagger on the way there. Do the same thing for the non-positive sequence and combine the bounds somehow. Perhaps it is better to only consider adjusting the bounds for each sequence when the running total changes.