8
$\begingroup$

Is there an algorithm that will allow me to numerically compute the limit of a function f(x) in a principled way?

The most naive algorithm would be to continue to compute the function for larger values of x. The first problem is how to figure out the 'large' values for x to compute the function for. How do I know when to stop?

Can we construct some error bars for this calculation perhaps based on some kind of statistical rationale?

Any books for further reading will be much appreciated.

3 Answers 3

5

To expand on T's answer, convergence acceleration methods assume that the error terms of the sequence you are interested in are of a certain form.

One of the general-purpose methods for accelerating the convergence of a sequence is the Shanks transformation. For the case of a sequence of partial sums of a series, the Shanks transformation amounts to constructing a sequence of Padé approximants, which hopefully converge faster to the limit of the sequence of partial sums. (The justly famous Wynn ε algorithm is an efficient realization of the Shanks transformation)

Another popular technique is Richardson extrapolation, which assumes that the error can be expressed as a power series of some form. This is in effect the application of the usual algorithms for polynomial interpolation to estimate the limit of a sequence. (Richardson extrapolation is the machinery behind the Romberg algorithm for accelerating the convergence of the trapezoidal rule, since the error of the trapezoidal rule is expressible as a series in powers of the panel size.)

I have been deliberately vague here since you have given absolutely no information on the nature of your sequence. There are many convergence acceleration methods to choose from (a good reference is Brezinski and Redivo-Zaglia's Extrapolation Methods: Theory and Practice), and the best sequence transformation to use depends a lot on the provenance of your sequence.

  • 0
    As an aside, there is a FORTRAN routine included with Brezinski/Redivo Zaglia for exactly the task of comparing several sequence transformations (as well as the various transformations themselves).2010-10-23
4

You have to assume something about f(x). For the case where the approach to the limit is expected to have an asymptotic expansion:

John Stalker, A convergence speeding algorithm with applications to numerical integration, Advances in Applied Mathematics Volume 22, Issue 1, January 1999, Pages 119-153

0

In many cases you have a good idea of the limiting behavior of the function. For instance, you may have a conjecture and you want to test it. Then you can do some transformation on your function to a convenient form. For example, I have seen people plot $f(1/x)$ with $x\to0$ and guess the shape of $g(x)=f(1/x)$ from there. You can repeat this process to get more and more accurate pictures.