next up previous
Next: About this document Up: 2nd Half Previous: 2nd Half

Impossibility Proof

I first note that there is an analogous construct evalf(Limit(...)) for numerically computing limits in Maple via the Levin's u-transform.

Theorem. Deterministic numerical evaluation of limits is impossible in general.

Remark This obviously implies that numerical calculation of sums is also impossible.

Proof. Suppose we are given an algorithm which purports to evaluate a limit, say to 2 decimal place accuracy, from some finite sample of the sequence (any computer program will have to be content with a finite sample for obvious reasons). Construct the following function:

spy := proc(n) global spylist;
  if type(n, posint) then
    spylist := spylist, n;
spylist := NULL;

(The program is given in Maple syntax for convenience, but this is not restricted to Maple).

This program returns 1, no matter what its input is; thus it reflects the sequence which obviously has limit 1. But it also records the values of n it is called with, for our later perusal. If we run the purported limit algorithm with this function, the algorithm will (quickly, one hopes) return 1 as the limit. We then have a finite list of integers where the algorithm probed the sequence at; now we define a malicious sequence by

Since spylist is finite, this sequence is ultimately 0, and its limit is 0. But the algorithm for accelerating convergence cannot know that, because its probes cannot distinguish this sequence from . Q.E.D.

This proof is a modified version of Kahan's proof that numerical integration is impossible, if the integrator can't look into the subprogram defining the function. There are ways to defeat this proof (by adding randomness, for example) but one could similarly prove that no matter what the program was, there would exist sequences that would fool it.

I leave it as an exercise for the reader to spy on evalf(Sum(...)) to see what it actually does here.

next up previous
Next: About this document Up: 2nd Half Previous: 2nd Half

Robert Corless
Fri Jan 30 13:19:12 EST 1998