0
$\begingroup$

Having a finite sequence of double precision floating point numbers (obtained using the fixed point iteration of a function), is there any algorithm which can be used to determine that this sequence is eventually convergent?

I tried to use the relative error between two consecutive elements, but this is not always working nice. For example, considering the fixed point iteration of $2*x/3$, with initial value $x_0 = 1/2$ the below sequence is produced, in which the relative error between two consecutive values is always $0.33$, although the absolute error is decreasing towards zero (but I think that the absolute error can't be used reliably with floating point numbers).

 0: 0.333333
 1: 0.222222
 2: 0.148148
 3: 0.098765
 4: 0.065843
 5: 0.043895
 6: 0.029263
 7: 0.019509
 8: 0.013006
 9: 0.008670
10: 0.005780
11: 0.003853
12: 0.002569
13: 0.001712
14: 0.001141
15: 0.000761
16: 0.000507
17: 0.000338
18: 0.000225
19: 0.000150
20: 0.000100
$\endgroup$
  • $\begingroup$ Using the relative error doesn't make sense if the limit is zero - the relative error of any non-exact approximation of zero is $\infty$. $\endgroup$ – fgp Apr 12 '14 at 17:55
  • $\begingroup$ I use the relative error between elements of the fixed point iteration (so the actual limit is not involved in the computations, since this is not know in advance). For relative error I am using this function stackoverflow.com/a/4915891/468820, which is actually computing an absolute error when very small values (floating point subnormals) are involved. $\endgroup$ – Andrei Bozantan Apr 12 '14 at 18:44
  • $\begingroup$ That's still bogus, and still for the reason I outline. It doesn't matter whether you use the actual limit zero in the computation or not. The point is, the values get smaller and smaller, and so the relative error can even get bigger, yet the sequence can still converge. Try any sequence that converges slower than a geometric sequence (which is what your fixed point iteration yields) $\endgroup$ – fgp Apr 12 '14 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.