A heavy cargo crane travels on track above a buried beacon, and measures its signed distance to the beacon 100 times a second (by signed distance, we mean that the distance is positive if the crane has not yet reached the beacon and negative if the crane has traveled past it). A human operator usually drives the crane and parks it just above the beacon. The crane then keeps itself in place automatically by always accelerating towards the beacon at a rate proportional to its distance from the beacon. On one unfortunate day, the operator noticed that the crane seemed to be "rocking" back and forth over the beacon, and tried to fix the problem by flipping the sign of the distance sensor. The crane almost immediately sped off down the track, halted only by the quick-thinking operator, who shut down the crane. Why did this happen?
In the previous prelab, we assumed that we could control the crane by sending it velocity commands, which led to a first-order difference equation model. A more realistic model would be to assume that we can send the Crane acceleration commands, and that will lead to a more complicated higher-order difference equation model. We will start in the same way, and will represent the crane's measured distance to the beacon as a sequence, d, where d[n] is the n^{th} measured distance. Then d[n] can be related to d[n-1] by
To begin, consider that an LDE holds for all n, so we can shift the index by one and write equivalent LDEs for d and v,
Subtracting the shifted from the unshifted LDE for d yields a second-order LDE for d and v,
The shifted LDE for v can be used to eliminate velocity, and after that elimination,
So now we need to learn about solving higher order difference equations, and we will start with a classic example, the Fibonacci series.
Consider the Fibonacci sequence, in which the next element in the sequence is the sum of the previous two. The sequence has a second-order LDE description,
Since the LDE for the Fibonacci sequence uses the previous two values, we refer to its associated LDE as second-order. If we specify y[0] and y[1], which we often refer to as initial conditions, then we can use the above difference equation to iteratively compute y[n] for all n \ge 2.
For example, to generate the classic Fibonacci numbers, set y[0] = 0 and y[1] = 1, and repeatedly apply the above formula with n =2 , then n=3, n=4, and so on, to determine y[2]=1, y[3]=2, y[4]=3, y[5]=5, ... etc. In general, given an LDE and enough initial conditions, it is easy to explicitly enumerate the rest of the sequence values.
These questions refer to the Fibonacci difference equation
Suppose the initial conditions for the difference equation are given by two constants, A and B , where y[0] = A and y[1] = B . What will be true about the generated sequence y[2], y[3], y[4], y[5], ... ? Please check all that apply.
Sequences described by second-order homogenous LDEs, like the Fibonacci sequence, have the property that y[n] is given by a weighted combination of y[n-1] and y[n-2]. Their general form is
To uniquely specify the sequence associated with the second-order difference equation, it is necessary to specify two initial conditions, y[0] and y[1]. First-order difference equations only require one initial condition, but a more problematic difference is that an explicit solution is not as readily apparent for the second-order homogenous LDE as it was in the first-order case. We will need a strategy for finding it.
To begin, we know that the general solution to the first-order homogenous LDE,
Suppose we assume that a second-order homogenous LDE has a solution of the form
and we then plug this assumed form back into the homogenous LDE to determine values for \lambda and c. Substituting y[n] = c \lambda ^ n into the general form for a second-order homogenous LDE yields
Simplifying by dividing through by c \cdot \lambda ^{n-2} results in a quadratic equation for \lambda,
which nearly always has two distinct solutions, the roots of the quadratic equation on the right side of the above. And the roots of the quadratic equation are explicit functions of a_1 and a_2 , given by the well-known quadratic formula:
Assumption: In the following approach for solving second-order homogenous LDEs, we implicitly assume that the quadratic equation for \lambda has two distinct roots, which we will later refer to as two distinct natural frequencies. It can happen that \lambda _1 = \lambda _2, and in this generally-rare repeated-root case, the approach below must be replaced with a distractingly complicated alternative. In our case, we are the ones creating the models and designing the controllers, so it is particularly easy for us to avoid the rare repeated-root case.
By solving the quadratic equation, we found a pair \lambda_1 and \lambda_2 such that \lambda_i^2 = a_1 \lambda_i + a_2, for i = {1,2} . As a result, we know that the second-order homogenous LDE will be satisfied by y[n] = c_1 \lambda_1^n or by y[n] = c_2 \lambda _2^n, and for any values of c_1 and c_2 we care to choose. For this reason, we refer to \lambda _1 and \lambda _2 as the two natural frequencies for the second-order homogenous LDE, they characterize how the difference equation behaves when there is no external input.
Like the first-order case, natural frequencies give us whole families of sequences that satisfy the homogenous LDE. But unlike the first-order case, we have two families that can be used in any combination. That is, y[n] = c_1 \lambda _1^ n + c_2 \lambda _2^ n satisfies the second-order homogenous LDE, for any c_1 and c_2. That there is such a rich collection of solutions to the LDE is easily shown by plugging in and verifying. That is, we need to verify that
implies that
Using the assumed form for y[n],
and
which implies
By combining terms with a common \lambda_i, we can determine an equivalent verification. That is, we need only verify that
is equal to zero for any c_1 and c_2. But we know that each of the above parenthesized terms is zero, and therefore their weighted sum is zero, because setting those parenthesized terms to zero is how we determined \lambda_1 and \lambda_2 in the first place.
Suppose the solution to a second order difference equation is
If y[n] goes to zero as n \rightarrow \infty , what is c_1 ?
If y[n] \ge 0 for all n \ge 0 and c_2 = 3 , then what is the smallest possible value for c_1 (give answer as a decimal number)?
For what values of a_1 and a_2 will y[n] = a_1 y[n-1] + a_2 y[n-2]?
What is the value of a_1:
...and a_2:?
For the following problems, consider the second-order linear difference equation
with the solution
Determine a_1, a_2, y[0], and y[1].
a_1=
a_2=
y[0]=
y[1]=
Now that we have the two natural frequencies, there is the matter of initial conditions. How to incorporate the initial conditions is best seen by example, so we will examine solving the second-order homogenous LDE for the Fibonacci sequence. Since the next value in the Fibonacci sequence is the sum of the previous two,
or a_1 = a_2 = 1 in our general second-order homogenous LDE.
Using the quadratic formula above, we find that the Fibonacci LDE has two distinct natural frequencies,
therefore any sequence of the form
will satisfy the Fibonacci LDE.
In order to produce the classical Fibonacci sequence, we need to find values for c_1 and c_2 so that y[0] = 0 and y[1]= 1. To start, consider how y[0] = 0 constrains c_1 and c_2,
Including the constraint from y[1] = 1,
So, the final equation for the Fibonacci sequence is
Evaluating the numeric constants (approximately)
Are there values of y[0] and y[1] for which the sequence given by
decays to 0 as n approaches \infty?
Select the most accurate response below:
Consider a system modeled by the difference equation
with initial conditions y[0]=1 and y[1]=-1.
Which of the following most accurately characterizes the eventually (large n) behavior of the sequence y?
The approach for solving second-order homogenous LDEs can be easily generalized to arbitrary order. The general form for a homogenous LDEs of order k is
To find solutions to the k^{th}-order homogenous LDE, one again assumes solutions of the form y[n] = c \lambda ^ n, and substitutes that form into the LDE to generate its characteristic equation,
The roots of the characteristic equation, \lambda _1, \ldots , \lambda _ k, are the k natural frequencies of the LDE.
Given k initial conditions, and assuming k distinct natural frequencies, one can solve k linear equations in k unknowns,
There are some complications in the higher-order case. The roots of higher-order polynomials are almost always computed numerically. And with more natural frequencies, there are more ways for repeated natural frequencies to make life complicated. For the case of control system design, difference equations of order higher than three are rarely used. Instead, one switches to state-space methods, a topic you will certainly learn if you continue studying control theory.
