Linear Algebra › Section D · Vector spaces › Topic D.8
Difference equations
Many quantities change in steps: a savings balance month by month, a population year by year, a sampled sound signal sample by sample. Linear difference equations describe such step-by-step change, and the ideas of subspace, basis and dimension tell you exactly what their solutions look like.
Signals and step-by-step change
"Vector spaces and subspaces" introduced \(\mathbb{S}\), the space of signals: doubly infinite sequences \(\{y_k\}\), added and scaled term by term. Think of \(y_k\) as a measurement taken at time step \(k\). Many rules that generate signals say how each term depends on the terms just before it, such as \(y_{k+2} = y_{k+1} + 6y_k\). Such a rule is a difference equation, the discrete cousin of a differential equation. Because \(\mathbb{S}\) is a vector space, its solutions can be studied with everything you know about subspaces, independence and dimension.
Linear difference equations
Given scalars \(a_1, \ldots, a_n\) with \(a_n \ne 0\) and a signal \(\{z_k\}\), the equation
is a linear difference equation of order n. It is homogeneous when every \(z_k\) is 0, and nonhomogeneous otherwise. The left side is a linear transformation of the signal \(\{y_k\}\): sums go to sums and multiples to multiples. So the solutions of the homogeneous equation form the kernel of that transformation, which makes them a subspace of \(\mathbb{S}\). A simpler example of such a map is \(\{y_k\} \mapsto \{y_{k+1} - y_k\}\), whose kernel is the constant signals.
Trying powers: the auxiliary equation
For a homogeneous equation, try a solution of the form \(y_k = r^k\) with \(r \ne 0\). Substituting into \(y_{k+2} + a_1 y_{k+1} + a_2 y_k = 0\) gives \(r^k(r^2 + a_1 r + a_2) = 0\), so \(r^k\) is a solution exactly when
This is the auxiliary equation, and the same idea works for any order. Each real root \(r\) gives a solution \(r^k\). If \(r \ne 0\) is a repeated root, \(kr^k\) is a second solution. Because the solutions form a subspace, any linear combination of these solutions is again a solution.
Dimension of the solution space
Two facts make the picture complete. 1. Existence and uniqueness: once the n starting values \(y_0, \ldots, y_{n-1}\) are chosen, the equation determines every other term, forwards by solving for \(y_{k+n}\), and backwards by solving for \(y_k\), which is possible because \(a_n \ne 0\). 2. So the map sending a solution to its starting values \((y_0, \ldots, y_{n-1})\) is a one-to-one linear map onto \(\mathbb{R}^n\). Hence the solution set of a homogeneous linear difference equation of order n is an n-dimensional subspace of \(\mathbb{S}\). By the basis theorem from "The dimension of a vector space", any n independent solutions form a basis.
Testing independence: the Casorati matrix
How do you check that two signals \(\{u_k\}\) and \(\{v_k\}\) are independent? Suppose \(c_1u_k + c_2v_k = 0\) for every \(k\). Then it holds at \(k\) and \(k + 1\):
The matrix is the Casorati matrix of the two signals. If it is invertible for at least one value of \(k\), then \(c_1 = c_2 = 0\) and the signals are independent. For n signals, use n consecutive rows, from \(k\) to \(k + n - 1\).
Worked example: a second-order equation
Solve \(y_{k+2} - y_{k+1} - 6y_k = 0\) with \(y_0 = 2\) and \(y_1 = 1\). 1. The auxiliary equation is \(r^2 - r - 6 = 0\), which factors as \((r - 3)(r + 2) = 0\), so \(r = 3\) or \(r = -2\). 2. The signals \(3^k\) and \((-2)^k\) are solutions. At \(k = 0\) their Casorati matrix has rows (1, 1) and (3, -2), with determinant \(-5 \ne 0\), so they are independent. Since the solution space has dimension 2, they form a basis. 3. The general solution is \(y_k = c_1 3^k + c_2(-2)^k\). 4. Fit the start: \(c_1 + c_2 = 2\) and \(3c_1 - 2c_2 = 1\) give \(c_1 = c_2 = 1\). 5. So \(y_k = 3^k + (-2)^k\). Check: \(y_2 = 9 + 4 = 13\), and the equation gives \(y_2 = y_1 + 6y_0 = 13\).
Nonhomogeneous equations
The solution set of a nonhomogeneous equation is not a subspace, since the zero signal fails. It has the same shape as the solution set of \(A\mathbf{x} = \mathbf{b}\) in "Solution sets of linear systems": every solution is one particular solution plus a solution of the homogeneous equation. For a constant right side, try a constant particular solution. For example, \(y_{k+2} - y_{k+1} - 6y_k = -12\) has the constant solution \(y_k = C\) when \(C - C - 6C = -12\), so \(C = 2\). Its general solution is therefore \(y_k = 2 + c_1 3^k + c_2(-2)^k\).
Worked example: a growing savings account
A saver opens an account with $0, the bank pays 0.5% interest per month, and $100 is deposited at the end of each month. Assume the rate never changes. 1. The balance obeys \(y_{k+1} = 1.005y_k + 100\), a first-order equation \(y_{k+1} - 1.005y_k = 100\). 2. Homogeneous part: the auxiliary equation \(r - 1.005 = 0\) gives the solutions \(c(1.005)^k\). 3. Particular part: a constant \(C\) needs \(C = 1.005C + 100\), so \(C = -20{,}000\). 4. General solution: \(y_k = -20{,}000 + c(1.005)^k\). The start \(y_0 = 0\) gives \(c = 20{,}000\). 5. After 12 months, \(y_{12} = 20{,}000(1.005^{12} - 1)\), about $1,233.56, of which $1,200 is deposits and about $33.56 is interest.
Rewriting as a first-order system
An equation of order n can be rewritten as a first-order matrix equation by stacking consecutive terms into a state vector. For \(y_{k+2} = y_{k+1} + 6y_k\), let \(\mathbf{x}_k = (y_k, y_{k+1})\). Then
The first row just copies \(y_{k+1}\); the second row is the equation itself. The whole history is then \(\mathbf{x}_k = A^k\mathbf{x}_0\). This form is the starting point for "Discrete dynamical systems", and the Markov chains of the next topic have the same shape.
Common mistakes to avoid
Using too few starting values is common: an order-n equation needs n of them, so a second-order one needs both \(y_0\) and \(y_1\). A second slip is fitting the starting values before adding the particular solution; in a nonhomogeneous problem, fit the constants to the full general solution. A third is forgetting that a nonhomogeneous solution set is not a subspace, so two of its solutions do not add to give a third. Finally, a Casorati matrix that is singular at one value of \(k\) does not by itself prove that general signals are dependent.
Key takeaways
A linear difference equation of order n, \(y_{k+n} + a_1y_{k+n-1} + \cdots + a_ny_k = z_k\) with \(a_n \ne 0\), is determined by n starting values. The homogeneous solutions form an n-dimensional subspace of \(\mathbb{S}\). Roots of the auxiliary equation give solutions \(r^k\), and a Casorati matrix invertible at some \(k\) proves independence. Nonhomogeneous solutions are one particular solution plus the homogeneous ones. Stacking terms into \(\mathbf{x}_k\) turns any such equation into \(\mathbf{x}_{k+1} = A\mathbf{x}_k\).
Flashcards
Flashcard
The space of signals {yโ}
Test your understanding
Question 1 of 5
What is the general solution of y(k+2) - 5y(k+1) + 6y(k) = 0?
Question 2 of 5
What is the dimension of the solution space of a homogeneous linear difference equation of order 3 with aโ โ 0?
Question 3 of 5
The Casorati matrix of the signals uโ and vโ at k = 0 has rows (1, 1) and (2, 4). What can you conclude?
Question 4 of 5
Which signal is a particular solution of y(k+1) - 3y(k) = 8?
Question 5 of 5
Writing y(k+2) = 2y(k+1) + 3y(k) as x(k+1) = A x(k), with x(k) = (y(k), y(k+1)), what is A?
