Finding the closed form of a recursive LTI system

[kostoglotov]

Homework Statement

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.

Homework Equations

The Attempt at a Solution

[/B]
This is the code:

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:

for i in range(1,500):
    print i, ": ", g(i)/g(i-1)

produces this output at large n:

imgur link: https://i.imgur.com/CTukJxO.png

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?

 

[Stephen Tashi]

Homework Statement

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.

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

https://ocw.mit.edu/courses/electri...tems-fall-2011/readings/MIT6_003F11_chap2.pdf

https://ocw.mit.edu/courses/electri...tems-fall-2011/readings/MIT6_003F11_chap4.pdf

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$.

 

[Mark44]

Homework Statement

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.

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?

Homework Equations

The Attempt at a Solution

[/B]
This is the code:

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:

for i in range(1,500):
    print i, ": ", g(i)/g(i-1)

produces this output at large n:

imgur link: https://i.imgur.com/CTukJxO.png

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?

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.

 

[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.

 

[kostoglotov]

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?

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.

if n <= 0: return 1.0
if n == 1: return 7.0