How do you solve difference equations?

The forced response of a DLIT system can be done by iteratively solving a difference equation of order n, or by the discrete convolution of the input with the impulse response of the system.

How do you solve the difference equations?

The calculation of the forced response of a DLIT system (see previous article) in response to u(k) input can be done by iteratively solving the difference equation of order n, or by resorting to the discrete convolution of the input with the impulse response of the system.

If the latter is not available, it can be derived by iteratively solving the difference equation with an input u(k)=δ(k) and null inputs and outputs for k<0.

In the case where the initial conditions are not null, it is possible to obtain y(k), given the sequence u(k) and the N values of the output prior to the instant k = 0, with a procedure very similar to that used for the solution of linear differential equations with constant coefficients for continuous systems over time.

Forced response and free-evolution of system

For the linearity of the system, you can consider the output y(k), for k≥0, as the sum of the forced response to the input signal starting from -M, and the free-evolution of the system, that is, u(k)=0 for every k and y(-1), y(-2), … y(-N) equal to the given initial values, namely:

y(k)=\sum_{i=-M}^{k}u(i)h(k-i)+y_{L}(k)

The free evolution response y_{L}(k) can be calculated with:

y_{L}(k)-a_{1}y_{L}(k-1)-a_{2}y_{L}(k-2)-\cdots -a_{N}y_{L}(k-N)=0

This is called the associated homogeneous equation.

Characteristic equation

The general solution of the associated homogeneous equation is constructed from the roots of the characteristic equation:

C(\lambda )=\lambda ^{N}-\lambda ^{N-1}-a_{2}\lambda ^{N-2}-\cdots -a_{N}=0

If p is a simple root of the characteristic equation, it is easy to verify that the sequence p^{k} satisfies the associated homogeneous equation.

Case of distinct roots

If C(λ)=0 has N distinct roots, the general solution of the homogeneous equation is given by the linear combination of linearly independent sequences p_{i}^{k}, that is:

y_{L}(k)=\sum_{i=1}^{N}c_{i}(p_{i})^{k}

The constants c_{i} shall be calculated so that y(k) assumes the values given in k=-1….-N.

Case of root with multiplicity r and complex roots

In the case that the root p has multiplicity r, it contributes to the general solution y_{L}(k) with the linear combination of r linearly independent sequences:

k^{j}p^{k} where j=0,1,2…r-1

For r=3, we get the sequences p^{k}, kp^{k}, k^{2}p^{k}.

In the case of simple but complex roots, they will be in complex conjugate pairs, since the coefficients of C(λ) are real, and in the same way the coefficients c must also be complex conjugates.

Solving difference equation: a basic example

y(k)=ay(k-1)+bu(k)

It is a linear equation to the differences of order 1, in fact N = 1, M = 0.

The homogeneous equation results:

y(k)-ay(k-1)=0

and the characteristic equation:

C(\lambda )=\lambda -a=0

which has a single simple root a. The general solution then becomes:

y_{L}(k)=ca^{k}

If one wishes to evaluate the free evolution from the initial condition y(-1)=0.7, the coefficient c must be calculated so that:

y_{L}(-1)=0.7=ca^{-1}

which results:

c=0.7a

We can also proceed through the calculation of the impulse response of the system. We can derive h(k) from the difference equation and it is:

h(k)=ba^{k}\delta _{-1}(k)

where the factor \delta _{-1}(k) is to make h(k) causal.

The total response y(k), starting from a given value of y(-1) and with generic input u(k), is given by:

y(k)=y(-1)a^{k+1}+b\sum_{i=0}^{k}a^{i}u(k-i)

where the second term represents the forced response y_{F}(k) of the system.

Consider now the latter with step input, i.e. u(k)=\delta _{-1}(k):

y_{F}(k)=b\sum_{i=0}^{k}a^{i}=b\frac{1-a^{k+1}}{1-a}

When \left| a\right|\geqslant 1, y_{F}(k) diverges, and when \left| a\right|< 1 it converges to the value \frac{b}{1-a}.

For 0< a< 1 the response is monotonous increasing, while for -1< a< 0 the response is oscillatory, as shown in the following figures in which (b=1-a) has been placed.

How do you solve the difference equations?

Solving difference equation: another example

\\y(k)-y(k-1)+y(k-2)=u(k)\\y(-1)=y(-2)=0\\u(k)=1\;k=0,1\\u(k)=0\; k\neq 0,1

Solution through impulse response

We determine the h(k) samples needed to calculate y(k) for k=0,1,2,3,4,5. That is, let’s determine the impulse response:

[1] y(k)=\sum_{i=0}^{k}h(i)u(k-i)

To evaluate the samples h(k) we place in input a pulse: u(0)=δ(0)=1 and solve iteratively:

\\y(k)=y(k-1)-y(k-2)+u(k)\\h(0)=h(-1)-h(-2)+u(0)=1\\h(1)=h(0)-h(-1)+u(1)=1\\h(2)=h(1)-h(0)+u(2)=0\\h(3)=h(2)-h(1)+u(3)=-1\\h(4)=h(3)-h(2)+u(4)=-1\\h(5)=h(4)-h(3)+u(5)=0

Iterative solution and comparison with the previous solution

Starting from:

\\y(k)=y(k-1)-y(k-2)+u(k)

we iteratively perform the calculation of the response and compare it with the previous solution, remembering [1].

\\y(0)=h(0)u(0)=1\\y(0)=y(-1)-y(-2)+u(0)=1\\\\y(1)=h(0)u(1)+h(1)u(0)=1+1=2\\y(1)=y(0)-y(-1)+u(1)=1-0+1=2\\\\y(2)=h(0)u(2)+h(1)u(1)+h(2)u(0)=+1+0=1\\y(2)=y(1)-y(0)+u(2)=2-1+0=1\\\\y(3)=h(0)u(3)+h(1)u(2)+h(2)u(1)+h(3)u(0)=0+0+0-1=-1\\y(3)=y(2)-y(1)+u(3)=1-2+0=-1\\\\y(4)=h(0)u(4)+h(1)u(3)+h(2)u(2)+h(3)u(1)+h(4)u(0)=0+0+0-1-1=-2\\y(4)=y(3)-y(2)+u(4)=-1-1+0=-2\\\\y(5)=h(0)u(5)+h(1)u(4)+h(2)u(3)+h(3)u(2)+h(4)u(1)+h(5)u(0)=0+0+0+0-1+0=-1\\y(5)=y(4)-y(3)+u(5)=-2+1+0=-1

As we can see, the results of the two methods coincide.

Avatar photo
About Carlo Bazzo 17 Articles
Sysadmin & network eng. @Epysoft, editor @TheTechGoggler, CTO @HDEMO. Former developer @MSFT @GOOG. Former MOps consultant @XRX @HPQ. LinkedIn: it.linkedin.com/in/carlobazzo