Results 1 to 4 of 4

Math Help - Recurrence relations in Python

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    33

    Recurrence relations in Python

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

    The recurrence relation is:

    x_{n+2} - 3x_{n+1} + x_{n} = 0 with x_{0} = 1, x_{1} = \frac{3-sqrt(5)}{2}

    Which means that:

    x_{n+2} = 3x_{n+1} - x_{n} = 0


    Solving this gives the answer:

    x_{n} = (\frac{3-sqrt(5)}{2})^n



    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:

    x_{n} = (\frac{\epsilon}{sqrt(5)})(\frac{3+sqrt(5)}{2})^n + (1 -(\frac{\epsilon}{sqrt(5)})(\frac{3-sqrt(5)}{2})^n
    - where \epsilon \approx 10^-17

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


    So, didn't I write the program correctly? Or is the last expression for x_n incorrect?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jenkki View Post
    I am trying to make a program in Python to find the solutions for for x_n in a recurrence relation.

    The recurrence relation is:

    x_{n+2} - 3x_{n+1} + x_{n} = 0 with x_{0} = 1, x_{1} = \frac{3-sqrt(5)}{2}

    Which means that:

    x_{n+2} = 3x_{n+1} - x_{n} = 0


    Solving this gives the answer:

    x_{n} = (\frac{3-sqrt(5)}{2})^n



    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:

    x_{n} = (\frac{\epsilon}{sqrt(5)})(\frac{3+sqrt(5)}{2})^n + (1 -(\frac{\epsilon}{sqrt(5)})(\frac{3-sqrt(5)}{2})^n
    - where \epsilon \approx 10^-17

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


    So, didn't I write the program correctly? Or is the last expression for x_n incorrect?
    It is the result of rounding errors

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2010
    Posts
    33
    Quote Originally Posted by CaptainBlack View Post
    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 x_1 like it says: x_1 = \frac{3-sqrt(5)}{2} + \epsilon, where \epsilon is the small error, I got this expression for x_n:

    x_{n} = (\frac{\epsilon}{sqrt(5)})(\frac{3+sqrt(5)}{2})^n + (1 -(\frac{\epsilon}{sqrt(5)}))(\frac{3-sqrt(5)}{2})^n




    Which says that x_n 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 x_n 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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jenkki View Post
    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 x_1 like it says: x_1 = \frac{3-sqrt(5)}{2} + \epsilon, where \epsilon is the small error, I got this expression for x_n:

    x_{n} = (\frac{\epsilon}{sqrt(5)})(\frac{3+sqrt(5)}{2})^n + (1 -(\frac{\epsilon}{sqrt(5)}))(\frac{3-sqrt(5)}{2})^n





    Which says that x_n 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 x_n 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 \epsilon has a random sign)

    CB
    Last edited by CaptainBlack; September 26th 2010 at 08:23 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 28th 2011, 03:50 PM
  2. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 26th 2009, 02:07 PM
  3. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 08:56 PM
  4. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 14th 2008, 07:45 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 11th 2008, 12:57 AM

Search Tags


/mathhelpforum @mathhelpforum