PDA

View Full Version : Difference Equations / Recurrence Relations

DavidP
10-04-2007, 07:31 PM
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?

DavidP
10-04-2007, 08:11 PM

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

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.

indigo0086
10-04-2007, 08:48 PM
This is like programming but boring.

DavidP
10-04-2007, 08:54 PM
hahaha

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

Sang-drax
10-05-2007, 10:26 AM