# Finding the closed form of a recursive LTI system

Tags:
1. Jan 14, 2017

### kostoglotov

1. The problem statement, all variables and given/known data

Find the closed form of the impulse response of the system $y[n] = 7y[n-1]-12y[n-2]+x[n]$ using the peel away and guess method. Ie, by using Python code to find the geometric ratios and amplitudes of the outputs as n grows large, then calculate residuals, and find the geometric ratios and amplitudes of the residuals, and so on.

2. Relevant equations

3. The attempt at a solution

This is the code:

Code (Text):
memo = {}
def f(n):
if n <= 0: return 1.0
if n == 1: return 7.0
if n in memo: return memo[n]
memo[n] = 7*f(n-1) - 12*f(n-2)
return memo[n]
# residual
def g(n):
return f(n) - 4*4**n

for i in range(1,500):
print i, ": ", f(i)
# this closed form found from transfer function
print i, ": ", 4*4**i - 3*3**i
I was able to find an exact matching closed form for the system from performing partial fraction decomposition on the transfer function H(z) and then doing inverse Z-Transform on that...but I did this as a last resort.

My problem was that when I check the ratio of the residuals, when n gets above 127, the ratios of the residuals don't stabilize, they oscillate.

This code:

Code (Text):
for i in range(1,500):
print i, ": ", g(i)/g(i-1)
produces this output at large n:

I spent a long time trying to reconcile this in a closed form. As you can see, this pattern goes $4*1.05^{-1}, 4*1.05^0, 4*1.05^1, 4*1.05^0,...$. This seemed very messy.

Of course, the real closed form is simple enough when figured out from the transfer function, it's $y[n]= 4*4^n - 3*3^n$.

And below n = 127, the ratio of the residuals seems to want to settle around 3, so guessing 3 at that point would be fine.

Why are the residuals oscillating like that? Why doesn't it affect or appear in the actual closed form? How would one go about making a judgement on which value for the geometric ratio of the residuals to guess? If I had kept going with the later oscillating ratios of the residuals, wouldn't I have to introduce imaginary numbers?

2. Jan 18, 2017

### Stephen Tashi

I'm unfamiliar with the "signals and systems" approach to difference equations. From glancing at the notes

you are working exercise 23 of chapter 4.

If I assume $x[n] = 0$ and consider the problem as a homogeneous linear recurrence relation with constant coefficients (https://en.wikipedia.org/wiki/Recur...currence_relations_with_constant_coefficients )

Then we have the difference equation $a[n] = 7 a[n-1] - 12 a[n-2]$
This has characteristic polynomial $p(t) = t^2 - 7t + 12 = (t-4)(t-3)$
Which gives the general solution $a[n] = k_14^n + k_23^n$

So I don't understand how the $4^i - 3^i$ in your code reconciles with the your initial condition $f[1] = 7$, which, in my notation would be $a[1] = 7$. To get $a[1] = 7$, I would use $k_1 = k_2 = 1$ instead of $k_1 = 1, k_2 = -1$.

3. Jan 18, 2017

### Staff: Mentor

Above, your equation is $y[n] = 7y[n-1]-12y[n-2]+x[n]$, but your code below uses $y[n] = 7y[n-1]-12y[n-2]$; i.e., no x[n] term. Why do you have this descrepancy?
I believe the numbers you are seeing result from doing arithmetic on very large numbers, too large for the computer to represent exactly.
For example, when i = 46, f(i) is approx. 1.98 X 10^28, and 4 * 4 ^ 46 is a 29-digit number. For larger i, the values get even larger. From about i = 121, the ratio of the residuals are probably at the limit of the computer's ability to do precise division, which, I believe, leads to the oscillation that you're seeing.

4. Jan 18, 2017

### Ibix

If Mark44 is correct, you might try setting your initial conditions to 1 and 7 rather than 1.0 and 7.0. Python has a built in big integer class that I think it will use if you do that.

5. Jan 18, 2017

### kostoglotov

The x[n] is there as an impulse at time 0 and 1, at t = 0 the impulse is 1 and t = 1 the impulse is 7.

Code (Text):
if n <= 0: return 1.0
if n == 1: return 7.0