Difference Equations / Recurrence Relations

This is a discussion on Difference Equations / Recurrence Relations within the A Brief History of Cprogramming.com forums, part of the Community Boards category; I know the large majority of people on here might not know what difference equations are (or maybe you know ...

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738

    Difference Equations / Recurrence Relations

    I know the large majority of people on here might not know what difference equations are (or maybe you know them as recurrence relations, because that's what Wikipedia lists them as), but I got a question that maybe someone can help me out with.

    I have a difference equation of the form:

    y(k+2) + y(k+1) + y(k) = b * r^k

    My particular equation is this:

    y(k+2) + y(k+1) - 2y(k) = 2 * 1^k

    Now, this is a non-homogeneous difference equation, so the first thing I did is create an associated homogeneous difference equation:

    z(k+2) + z(k+1) - 2z(k) = 0

    Now, if we assume that z(k) = Lambda^k, we get:

    (I am going to use the letter L for lambda)

    L^(k+2) + L^(k+1) - 2 * L^k = 0

    Simplify:

    L^2 + L - 2 = 0

    We can then solve for lambda, and we get

    L1 = 1
    L2 = -2

    Great. We have our lambda values. Now we need to find the general solution. We know that

    y(k) = y*(k) + z(k)

    where y*(k) is a particular solution to y(k) and z(k) is a general solution to our homogenous equation. Now, in a normal situation, I would do the following:

    y*(k) = d * r^k

    And then I would solve for "d".

    My problem is that "r" is equal to one of our roots (lambda). In other words, r = Lambda_1 (because r is 1 in our very first equation up above).

    So if I do y*(k) = dr^k, we end up solving it, and it turns out that 0 = 2, which we know is wrong.

    How can I solve for y*(k)?

    I was reading some notes, and I read that "when r is equal to a root, treat it as a repeated root of the extended polynomial." The notes gave some information on how to handle that in z(k)...but not in y*(k). Basically, right now I know that:

    y(k) = y*(k) + c1 * L1^k + c2 * k * L2^2

    But I need to find y*(k) and I cannot figure out how to do that. Anyone know how to do that?
    My Website

    "Circular logic is good because it is."

  2. #2
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    [addition to first post]

    After doing a bit more looking around my notes, I discovered that I was slightly wrong near the end of my explanation.

    Instead of:

    y(k) = y*(k) + c1 * L1^k + c2 * k * L2^2

    It is actually:

    y(k) = y*(k) + c1 * L1^k + c2 * L2^2

    and

    y*(k) = d1 * r^k + d2 * k * r^k

    So that solves the problem of what y*(k) actually is, but I still don't understand how to solve for y*(k), because it turns out to be like this:

    y*(k) = d1 * 1^k + d2 * k * 1^(k)
    y*(k) = d1 + d2 * k

    Now we plug that into y(k) to get:

    (d1 + d2 * (k+2)) + (d1 + d2 * (k+1)) - (d1 + d2 * k)) = 2

    When we simplify it comes out to:

    d1 + d2 * k + 3 * d2 = 2

    At this point I am not sure what to do. What do we plug in for k? our initial conditions? I remember something about separating the d1 and d2 terms into 2 separate equations...but I am not sure about the details of doing that.

    [/addition to first post]
    My Website

    "Circular logic is good because it is."

  3. #3
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    This is like programming but boring.

  4. #4
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    hahaha

    yeah i agree but it's still something that must be done
    My Website

    "Circular logic is good because it is."

  5. #5
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Your homogenous solution would be:

    z(k) = C1 * (-2)^k + C2

    The RHS of your equation is equal to 2? You wrote 2*1^k.

    To find the particular solotion, assume a solution of the form y*(k) = A * k. This will give you A=2/3. A particular solution is y*(k) = 2*k/3.

    Thus the final solution is:

    y(k) = C1 * (-2)^k + C2 + 2*k/3.

    The constants C1 and C2 are determined by the initial conditions.
    Last edited by Sang-drax; 10-05-2007 at 03:49 PM. Reason: Forgot the division by 3 in the final solution.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Review required for program of date difference
    By chottachatri in forum C Programming
    Replies: 6
    Last Post: 10-31-2008, 11:46 AM
  2. What's the difference between var++ and ++var
    By ulillillia in forum C Programming
    Replies: 6
    Last Post: 05-31-2007, 02:27 AM
  3. Replies: 10
    Last Post: 11-06-2005, 08:29 PM
  4. LUP Decomposition (simultaneous equations)
    By Markallen85 in forum C Programming
    Replies: 6
    Last Post: 08-24-2003, 02:08 AM
  5. equations for a program
    By anthonye in forum C Programming
    Replies: 4
    Last Post: 06-19-2002, 04:38 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21