1
$\begingroup$

I have a non-linear equation that converges, and reaches suitable accuracy after around 20 steps, however each step is very expensive to calculate. The series are never quite the same, but they are similar; there are 4 examples below. Ideally, I would like to be able to guess the final answer (getting as close as possible), knowing only the first few (say 5?) steps.

Example series:

22.1365571473 39.1003909811 60.8702429029 87.3193552323 117.479117043 149.298938154 180.099415362 207.478769226 230.033683334 247.487707416 260.35893824 269.520601585 275.88012284 280.218467629 283.143170475 285.099206545 286.400448741 287.263033108 287.833493354

43.8168649647 119.274730769 228.310938956 332.800659827 406.364683614 449.036198231 471.258177801 482.206944282 487.456776422 489.94148426 491.110264146 491.658457589

13.7709904649 17.4517204683 20.862400148 23.9136500982 26.5768107479 28.8599125041 30.7910913202 32.4079080805 33.7507827028 34.8591665245 35.7694839095 36.5141882847 37.1214961348 37.6155120979 38.016560732 38.3416106934 38.6047214436 38.8174732756 38.9893605432 39.1281383997 39.2401237101 39.3304495994 39.4032795394

19.5526511118 31.7547501442 45.9545707135 61.7006795681 78.515831743 95.8079163675 112.898129782 129.114767641 143.90065881 156.888846484 167.923989061 177.034730079 184.379068592 190.185787294 194.706624478 198.184227677 200.8346208 202.840305035 204.349975449 205.481710536 206.327550943 206.958285211 207.427820219 207.776913165

Improve this question
$\endgroup$
5
  • $\begingroup$ As I understand, you have an equation in 4 variables ($x_1$, $x_2$, $x_3$ and $x_4$) that your are trying to solve. Could you write down this equation (not in Python code but in mathematical script)? $\endgroup$
    – GertVdE
    Commented Sep 25, 2013 at 12:01
  • $\begingroup$ @GertVdE, I started writing it out in mathematics, and then I realised that what I was doing was just plain wrong. Sorry. I've removed the code snippet from my question. $\endgroup$
    – user1412633
    Commented Sep 25, 2013 at 12:20
  • $\begingroup$ OK. Just come back when you're ready... $\endgroup$
    – GertVdE
    Commented Sep 25, 2013 at 13:16
  • 1
    $\begingroup$ 20 steps of what? $\endgroup$
    – Nico Schlömer
    Commented Sep 25, 2013 at 21:35
  • $\begingroup$ I wouldn't see this as the problem of predicting a limit of a sequence. This is a model identification problem. See @RodyOldenhuis answer. $\endgroup$
    – Jan
    Commented Sep 26, 2013 at 7:46

3 Answers 3

Reset to default
1
$\begingroup$

The Shanks Transform is a good way to improve the convergence of a series. There are some other series acceleration methods described on Wikipedia too.

Bender and Orzsag's book also has an entire chapter on summation of series (although I don't have it handy now).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, I've applied Aitken's delta-squared process (which I found in your link to the Shanks transform) and that gets sufficient accuracy in roughly 3 iterations of 3 steps, which pretty much halves the time. So far it seems to be robust too. $\endgroup$
    – user1412633
    Commented Sep 26, 2013 at 10:54
2
$\begingroup$

The series you show appear to have roughly the first three significant digits stable by the last term you show.

In most of those same series, the first 5 steps have not gotten you to a correct first significant digit. On a log scale, this is a huge distance. To ask for a prediction that far out from so few terms is, to put it charitably, insanely optimistic.

As well, be incredibly careful with multiple iterations of methods such as Shanks (as one response suggested.) That method tends to massively amplify floating point noise in your computations, so that after several iterations of that method, the noise has grown enough to overwhelm the signal. The point is, IF you do apply Shanks, only a few iterations will be of any value.

Is it impossible to predict a limit from such a sequence after only a few terms? I won't say that, but to do any kind of a decent job, YOU need to provide input. Extrapolation (which is what you are doing) is a NASTY process, fraught with problems. However, if you can supply useful information that restricts the family of curves one might expect to see in this process, then the problem becomes far more tractable. (This is not always easy to do.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I totally agree that it's optimistic to do it in 1 jump. I should have worded my question better to make it obvious that I'm happy with an iterative process. The Aitken transformation seems to work best for my problem $\endgroup$
    – user1412633
    Commented Sep 26, 2013 at 10:58
1
$\begingroup$

Given by how you state the problem, I take it accuracy is not a really important issue here :)

For your data sets: the fist-order differences ($a_2-a_1, a_3-a_2, ...$) look like they could be part of a Gaussian distribution.

So you could detect whether a peak occurs in the first-order differences, and stop evaluating your generator function when it does. Fit a Gaussian to the data points you have thus far to obtain $\mu$ and $\sigma$, and extrapolate to infinity.

The result should be close to the value of the Gaussian CDF for those values of $\mu$ and $\sigma$.

It'll be a nice ballpark estimate, so if that suffices for the rest of your application, it should be OK. But please don't expect this to be anywhere near accurate -- fitting a Gaussian accurately through 5 data points is, well...you'll have to be extremely lucky :)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Cheers, I've tried this and like you implied it sometimes works well and other times doesn't give a particularly good guess. It seems to always gets a good enough approximation in 3 iterations, but it's more expensive than an Aitken transformation because that only needs 2 calculations per iteration, rather than 4. $\endgroup$
    – user1412633
    Commented Sep 26, 2013 at 11:03

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