Re: Estimating accuracy in finite precision computations Message #17 Posted by Thomas Klemm on 21 Feb 2013, 5:54 p.m., in response to message #16 by hugh steers
A fixed point of x = 4*x*(1 - x) is 3/4, the other being 0, but that's not so interesting.
We obviously can represent 0.75 exactly in a calculator, even in binary. So if you iterate the logistic map you will stay at the same number.
If however you use a small interval around this fixed point the iteration of the logistic map will smear it all over the whole interval [0, 1].
This little program will illustrate this behavior:
#!/usr/bin/python
def f(x):
return 4*x*(1 - x)
eps = 1E-6
x = 3 / 4.0
u = x - eps
v = x + eps
for i in range(20):
print "%.6f %.6f %.6f" % (u, x, v)
[u, x, v] = map(f, [u, x, v])
This is the result:
0.749999 0.750000 0.750001
0.750002 0.750000 0.749998
0.749996 0.750000 0.750004
0.750008 0.750000 0.749992
0.749984 0.750000 0.750016
0.750032 0.750000 0.749968
0.749936 0.750000 0.750064
0.750128 0.750000 0.749872
0.749744 0.750000 0.750256
0.750512 0.750000 0.749488
0.748975 0.750000 0.751023
0.752045 0.750000 0.747949
0.745893 0.750000 0.754085
0.758147 0.750000 0.741764
0.733441 0.750000 0.766201
0.782021 0.750000 0.716548
0.681856 0.750000 0.812428
0.867713 0.750000 0.609554
0.459147 0.750000 0.951991
0.993324 0.750000 0.182815
While the interval might indicate a "total annihilation of all precision" the main value is still 100% correct.
It might seem obvious in the case above where the periodicity is 1 because you notice that 0.75 is a fixed point.
Quote:
For the r = 4 case (...) there exist cycles of length k for all integers k >= 1.
You might return after 17 iteration to your initial value (or to something very close) but think after 16 iterations that the result is utter garbage because the interval indicates so.
Kind regards
Thomas
Just to illustrate the last point we can calculate the fixed points of the n-th iteration using the formula:
You can use the following lines in the program above to calculate the fixed point for 5 iterations:
from math import *
y = 2**5 - 1
x = sin(2*pi/y)**2
This results in the following table:
0 0.040520 0.040521 0.040522
1 0.155513 0.155517 0.155520
2 0.525314 0.525325 0.525335
3 0.997437 0.997435 0.997433
4 0.010227 0.010235 0.010243
5 0.040489 0.040521 0.040553
6 0.155399 0.155517 0.155634
7 0.525000 0.525325 0.525649
8 0.997500 0.997435 0.997369
9 0.009975 0.010235 0.010498
10 0.039503 0.040521 0.041551
11 0.151771 0.155517 0.159299
12 0.514947 0.525325 0.535692
13 0.999106 0.997435 0.994904
14 0.003571 0.010235 0.020278
15 0.014234 0.040521 0.079468
16 0.056125 0.155517 0.292613
17 0.211900 0.525325 0.827962
18 0.667992 0.997435 0.569763
19 0.887114 0.010235 0.980532
20 0.400571 0.040521 0.076354
As can be seen we return to the initial value after the 5th, 10th, 15th, ... iteration, while the interval degrades.
Or if you prefer the example where n = 17:
from math import *
y = 0b11011100101110 / (2.**17 - 1)
x = sin(2*pi*y)**2
0 0.392606 0.392607 0.392608
1 0.953866 0.953867 0.953868
2 0.176022 0.176019 0.176016
3 0.580154 0.580145 0.580137
4 0.974302 0.974307 0.974312
5 0.100152 0.100132 0.100112
6 0.360486 0.360423 0.360360
7 0.922143 0.922073 0.922002
8 0.287182 0.287419 0.287656
9 0.818833 0.819237 0.819640
10 0.593381 0.592351 0.591320
11 0.965120 0.965885 0.966642
12 0.134655 0.131804 0.128980
13 0.466091 0.457728 0.449377
14 0.995401 0.992852 0.989749
15 0.018312 0.028387 0.040583
16 0.071908 0.110323 0.155746
17 0.266948 0.392607 0.525956
18 0.782748 0.953867 0.997305
19 0.680215 0.176019 0.010750
20 0.870091 0.580145 0.042540
Edited: 21 Feb 2013, 7:21 p.m.
|