Accelerating Convergence of a Sequence

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.

*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.