Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I had a monotonically increasing sequence $\{d_{n}\}$ which is also bounded above. The $d_{n}$'s satisfy a given recurrence, however computationally they tend very slowly to the limit. What are some ways which I can use to speed up the convergence of this sequence computationally? I am computing these $d_{n}$ in PARI/GP if that is useful information.

share|improve this question
    
What kind of recurrence do the $d_n$ satisfy? Have you checked out: mathworld.wolfram.com/ConvergenceImprovement.html which might have some ideas you could use... –  Aryabhata Jun 23 '11 at 22:03
    
I expect that there is no single technique that will speed up the computation of the limit of an arbitrary increasing, bounded, recursively defined sequence. (Although I would be fascinated if I'm wrong about this!) Maybe you should explain how your particular sequence is defined? –  mac Jun 23 '11 at 22:04
    
As mentioned in the previous comments, you should give the exact recurrence of your sequence for us to help you. –  Beni Bogosel Jun 23 '11 at 22:21
    
The chosen method will vary badly on which sequence you are considering, because some sequence satisfy some powerful relations which allows to speed up convergence, while some other might not. If your convergence is not that bad to being with and you just want a few extra digits, you could simply compute by hand the recurrence formula for three or four extra terms instead of just one or two by hand, and then plug it in the computer... which would give you a linear increase in speed, but usually that is not what you're looking for. Shoot the formula and we can help more. –  Patrick Da Silva Jun 23 '11 at 22:29
    
@mac: It is indeed true; there are so called "logarithmic sequences" (sequences that satisfy $\lim\limits_{n\to\infty}\frac{s_{n+1}-s}{s_n-s}=1$ where $s_n$ is the sequence and $s$ is the limit) that no sequence transformation could ever hope to accelerate properly... –  J. M. Jul 24 '11 at 0:10

2 Answers 2

up vote 3 down vote accepted

*cracks knuckles*

Okay, first off, on the matter of picking sequence transformation methods, one would do well to read Appendix A of The SIAM 100-Digit Challenge: A Study in High-Accuracy Numerical Computing by Dirk Laurie, as well as the (long!) survey article Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series by Ernst Joachim Weniger. (There are in fact books on this subject, but they're not too "beginner-friendly" methinks.)

Having gotten those recommendations out of the way, here's advice: it's a good idea to at the very least estimate the asymptotic behavior of your sequence; most of the methods in practice make (sometimes unwarranted!) assumptions on the asymptotic behavior of the sequence.

In the answer to this particular problem, I mentioned two of the most common workhorses for the purpose of extrapolating a sequence to its limit (and in some cases to its antilimit, if need be): Richardson extrapolation and the Shanks transformation (I mentioned them also here.). I've given the formulae for Richardson extrapolation in the first link; I'll just say here that Richardson essentially fits an interpolating polynomial to your sequence along with an auxiliary sequence tending to 0 as abscissas, and then evaluating the polynomial at 0. On the other hand, the Shanks transformation assumes that the given sequence is in fact the values of the partial sums of a power series, and then tries to find the corresponding values of successive Padé approximants (the rational function whose first few terms matches the given power series) of the assumed series.

There are also specialized methods, if for instance your sequence was generated as the partial sums of an alternating series, or as the output of a fixed point iteration $x_{i+1}=f(x_i)$. In the first case, one of the simpler methods is the method of Cohen, Rodriguez Villegas, and Zagier (this is one of the methods used internally by PARI/GP for summing alternating series); briefly, it exploits the properties of Chebyshev polynomials to construct a rational approximation to the alternating series. The Levin transformation (which I discussed briefly here), on the other hand, uses forward differences successively to remove error terms of an alternating series.

I've only given four of the algorithms I've used; the thing you should take away here is that either you should figure out your sequence's asymptotic behavior, or you'll have to experiment with not just one, but several sequence transformations if you're unable or unwilling to diagnose asymptotic behavior. As I said, a convergence acceleration method can fail spectacularly if its assumptions aren't applicable to the input sequence.

share|improve this answer
    
Maybe I'll edit this later to be a tad more helpful than it currently is, without making it textbook-long... –  J. M. Aug 23 '11 at 7:41

This should go as comment, but I want to add an example, so I need more space.
But first: I second the other comments, that your question should give more context and characteristics of your sequence.
Now here is an example of a quick&dirty-procedure: it's an Euler-summation with negative order. Euler-summation works best with series of alternating sign and roughly geometric growth. If we have nonalternating increasing series/sequences, then it slows the convergence down. But negative order is a possibility in a certain, however, small range of parameters. To have an example I use the sequence $p_k$ of partial sums of the $\zeta(2)$: it is increasing and bounded. Then, because Euler-summation sums a series, we use the differences $p_k-p_{k-1}$ which are just the reciprocal squares, and get the terms $e_k$ of the accelerated sequence. Here are the three example rows. (My codeexample in Pari/GP using own basic vector/matrixfunctions):

 Gp:> Mat([Z(2),DrPow(1.0)*Z(2),ESum(-0.43)*Z(2.0)])

 diff   p_k       Eulersummed e_k
 ---------------------------------
     1          1  1.0000000
   1/4  1.2500000  1.4385965
   1/9  1.3611111  1.4497110
  1/16  1.4236111  1.5208230
  1/25  1.4636111  1.5315428
  1/36  1.4913889  1.5569019
  1/49  1.5117971  1.5648384
  1/64  1.5274221  1.5770663
  ...     ...       ... 
1/3136  1.6272354  1.6348067
1/3249  1.6275432  1.6349835
1/3364  1.6278405  1.6351543
1/3481  1.6281277  1.6353192
1/3600  1.6284055  1.6354787
1/3721  1.6286743  1.6356330
1/3844  1.6289344  1.6357824
1/3969  1.6291864  1.6359270
1/4096  1.6294305  1.6360671

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.