Thread: Recurrence relations in Python

I am trying to make a program in Python to find the solutions for for in a recurrence relation.

The recurrence relation is:

with

Which means that:




Solving this gives the answer:





The program I wrote was:

from math import *

N = 801

x = range(0,N)

x[0] = 1.0
x[1] = (3-sqrt(5))/2

for n in range(2,N):
x[n] = 3* x[n-1] - x[n-2]
print n, ': ', x[n]


It starts off good; with the values:
2 : 0.14589803375
3 : 0.0557280900008
4 : 0.0212862362522

but then, at n = 19 to n = 20, I get:
19 : 9.31783539215e-09
20 : -1.18877885313e-09


Why is this?
I calculated that the computer would run the program as if:


- where 10^-17

But this expression for should not have large negative values when n becomes large


So, didn't I write the program correctly? Or is the last expression for incorrect?

Originally Posted by jenkki

I am trying to make a program in Python to find the solutions for for in a recurrence relation.

The recurrence relation is:

with

Which means that:




Solving this gives the answer:





The program I wrote was:

from math import *

N = 801

x = range(0,N)

x[0] = 1.0
x[1] = (3-sqrt(5))/2

for n in range(2,N):
x[n] = 3* x[n-1] - x[n-2]
print n, ': ', x[n]


It starts off good; with the values:
2 : 0.14589803375
3 : 0.0557280900008
4 : 0.0212862362522

but then, at n = 19 to n = 20, I get:
19 : 9.31783539215e-09
20 : -1.18877885313e-09


Why is this?
I calculated that the computer would run the program as if:


- where 10^-17

But this expression for should not have large negative values when n becomes large


So, didn't I write the program correctly? Or is the last expression for incorrect?

It is the result of rounding errors

CB

Originally Posted by CaptainBlack

It is the result of rounding errors

Yes it is. What I don't understand is why I get large negative values instead of large positive values for large values of n.


When I used the fact the the computer looks at the start-value like it says: , where is the small error, I got this expression for :






Which says that should take large positive values when n is a large number. But the Python-program I made says that the larger the n, the more negative becomes.



Therefore I suspect my program (see first post) is incorrect. I would really appriciate it if someone would help me what's wrong with it

Originally Posted by jenkki

Yes it is. What I don't understand is why I get large negative values instead of large positive values for large values of n.


When I used the fact the the computer looks at the start-value like it says: , where is the small error, I got this expression for :







Which says that should take large positive values when n is a large number. But the Python-program I made says that the larger the n, the more negative becomes.



Therefore I suspect my program (see first post) is incorrect. I would really appriciate it if someone would help me what's wrong with it

You have not got large values of any kind, negative powers of 10 are small numbers.

The sequence is decreasing so the small random errors in the initial stages can eventually dominate and the error will have an essentially random sign when it becomes dominant (it is actually deterministic but we don't know what it will be without an analysis of the floating point representation of the initial numbers and tracking the floating point errors as the accumulate through the iteration).

In fact since you know the analytic solution of the recurrence you can compare the results at each stage and see the error grow and eventually dominate.

If you continue the iteration beyond the point where the errors start to dominate you will get a sequence growing in absolute value. Since the iteration has a general solution with a growing term and a shrinking term and eventually the errors will drive the dominant growing term.

The initial conditions for the exact iteration force the selection of the decreasing term in the general solution of the recurrence, any error at any stage (and there are errors at all stages) will give free reign to the growing noise driven solution eventually.

(if you must focus only on the original error: your has a random sign)

CB