Acceleration via smoothing - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T08:55:11Z http://mathoverflow.net/feeds/question/74976 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/74976/acceleration-via-smoothing Acceleration via smoothing James Propp 2011-09-09T05:54:47Z 2011-12-18T19:22:12Z <p>Is the following approach to accelerating the rate of convergence of $(1+1/2+\dots+1/n)- \ln n$ (with $n=1,2,3,\dots$), and other sequences like it, in the literature?</p> <p>Let $f(t)=(\sum_{1 \leq n \leq t} 1/n) - \ln t$ for $t \geq 0$, so that $f(t)$ tends to Euler's constant $\gamma$ as $t \rightarrow \infty$. It follows that the continuous piecewise-differentiable function $F(t) := \int_0^t f(s) \: ds$ grows like $\gamma t$ so that $F(t)/t \rightarrow \gamma$. Note that $F(t)= (\sum_{1 \leq n \leq t} (t-n)/n) - t \ln t + t$ so that $F(n)/n$ is about as easy to compute as $f(n)$.</p> <p>(1) Can someone provide asymptotic estimates for $f(n)-\gamma$ and $F(n)/n-\gamma$? The former is undoubtedly classical (and, I suspect, easy), but I don't know if anyone's looked at the latter (though it's probably not too hard). It appears empirically that $F(n)/n$ converges to $\gamma$ faster than $f(n)$. </p> <p>(2) Is this "smoothing" approach to acceleration of sequence-convergence discussed in the literature? (I don't know any numerical analysis; maybe this trick is "well-known to those who know it".)</p> <p>(3) The smoothing method can be iterated, but there often comes a point of diminishing returns. Is anything known about the optimal amount of smoothing to apply? (Is it related to the rate of decay of the coefficients of some Fourier series or something like that?)</p> <p>Of course there are much better ways to estimate Euler's constant than smoothing, and for sequences in general there are much better ways to accelerate convergence. What's distinctive about the above method is that it's linear.</p> <p>The method is related to "smoothed summation" (as described in <a href="http://www.tricki.org/article/Smoothing_sums" rel="nofollow">http://www.tricki.org/article/Smoothing_sums</a> for instance) via integration by parts. Specifically, $(n+1)$-fold iteration of the operation $f \mapsto F$ gives the function $\int_0^t [(t-s)^n/n!] f(s) \: ds$, which can be viewed as the convolution of $f(t)$ with the kernel $t^n/n!$. In some contexts this kind of convolution is called "filtering". Perhaps there's more to be said about these connections.</p> <p>I also have a feeling that the method is related to Cesaro summation. Can anyone provide details of the relation?</p> http://mathoverflow.net/questions/74976/acceleration-via-smoothing/75148#75148 Answer by James Propp for Acceleration via smoothing James Propp 2011-09-11T16:21:30Z 2011-09-11T16:21:30Z <p>Andrew is 100% correct; $f(n)$ and $F(n)$ are equal! There are examples where the kind of filtering I described can improve convergence of a sequence, but this isn't one of them. I'm going to close this thread and open a new one once I've figured out what I should say. Apologies to those who spent time reading the thread; I should've spend more time reading it myself before I posted.</p>