EE550: Linear Systems Final Exam SIST, ShanghaiTech

Final Exam — Solutions

Course: Linear Systems
Teacher: Prof. Boris Houska
Duration: 85min

YOUR NAME: (type in English letters)

I Introduction
This exam consist of three sections, named, Modeling Linear Control Systems, Kalman Filter, and
Linear Quadratic Regulator. Keep in mind that all questions admit short and elegant solutions.

This is an “open-book” exam.

Overview: (max 60 points in total)

• Section II: max 20 points

• Section III: max 20 points

• Section IV: max 20 points

1
EE550: Linear Systems Final Exam SIST, ShanghaiTech

II Modeling Linear Control Systems

• Consider the mass-spring-damper system in Figure 1.

Figure 1: A mass-spring-damper system.

1. Let x(t) be the position of the trolley with mass m and v(t) its velocity at time t. The
force of the spring is given by Fs = −Dx(t). The force of the damper is Fd = −cv(t).
Now, assume that our control input is the force F (t) with which we can pull (or push)
the mass point m in x-direction. Show that the dynamics of this mass-spring-damper
system can be modelled by a linear control system of the form

ẏ(t) = Ay(t) + Bu(t) .

What are the matrices A and B in this example? How do you define the states y(t)
and control input function u(t)? (5 points)

Solution: Newton’s law of motion can be written in the form

ẋ(t) = v(t)

mv̇(t) = −cv(t) − Dx(t) + F (t) .

Thus, if we introduce the state vector y(t) = [x(t), v(t)]T and control input u(t) = F (t),
the linear control system can be written in the form
   
0 1 0
ẏ(t) = Ay(t) + Bu(t) with A = D c and B = 1 .
−m −m m

2
EE550: Linear Systems Final Exam SIST, ShanghaiTech

2. Work out an explicit expression for the solution G(t, τ ) of the differential equation

∂
G(t, τ ) = AG(t, τ ) with G(τ, τ ) = I
∂t
for all t, τ ∈ R. You may assume D > 0 as well as m > 0 and c ≥ 0. (5 points)

Solution: The solution for the differential equation can be written in the form

G(t, τ ) = eA(t−τ ) .

In order to work out the exponential function explicitly, we work out the eigenvalues
r
c c2 D
λ1,2 = ± 2
−
2m 4m m
of the matrix A. Since we have D > 0 and m > 0, we must have λ1 6= λ2 , which
implies that the (normed) eigenvectors
   
1 1 1 1
v1 = and v2 =
1 + λ21 λ1 1 + λ22 λ2

are linearly independent, i.e., the matrix T = [v1 , v2 ] is invertible. In summary, we

have  λ (t−τ ) 
e 1 0
G(t, τ ) = T T −1 .
0 eλ2 (t−τ )

3
EE550: Linear Systems Final Exam SIST, ShanghaiTech

3. Assume that we have D > 0, m > 0, and c > 0. The set

Z t Z t 
2

S(t) = G(t, τ )Bu(τ ) dτ  ku(τ )k2 dτ ≤ 1
0 0

is called the controllability ellipsoid of the linear control system. It can be interpreted
as the set of reachable points in the states space, which can be obtained with control
inputs whose L2 -norm is bounded by 1. Find an explicit expression for the limit set

S ∗ = lim S(t) .
t→∞

Make a 2-dimensional sketch of the set S ∗ and discuss how the geometry of the set
S ∗ depends on the parameters m, D, and c and give physical interpretations of your
results. What happens for very small damping parameters c → 0 ? (10 points)

Solution: The controllability ellipsoid can be written in the form

n o
S(t) = P (t)v | v T v ≤ 1 ,

where P (t) denotes the solution of the Lyapunov differential equation

Ṗ (t) = AP (t) + P (t)AT + BB T .

As the system is open-loop stable (since c > 0), the state of the Lyapunov differential equation
must converge to a limit state P̄ , which satisfies the steady-state condition
D
     
T T 0 1 0 −m 0 0
0 = AP̄ + P̄ A + BB = P̄ + P̄ + .
−mD
−m c
1 −m c
0 m12

This is a linear equation system for P̄ , which can be solved explicitly:

 1 
1 D 0
P̄ = .
2cm 0 1

Thus, the limit set S ∗ = P̄ v | v T v ≤ 1 is an ellipsoid whose axis are aligned with the position

1 1
and velocity coordinate and have the lengths √2cm and √2cmD , respectively. For c → 0 the
controllability ellipsoid becomes arbitrarily large,

lim S ∗ = R2 .
c→0

4
EE550: Linear Systems Final Exam SIST, ShanghaiTech

III Kalman Filter

• Consider the linear control system from the previous section for u = 0 and c = 0, i.e., under
the assumption that we neither apply an external force nor have damping such that
 
0 1
ẏ(t) = Ay(t) with A = D . (1)
−m 0

We use a camera in order to measure the position x(t) = Cy(t) of the mass point at time t.
Notice that the matrix C = ( 1, 0 ) returns the first component of the state vector y. The
error of the position measurement is assumed to be a Gaussian white-noise signal satisfying
n o
E {η(t) − Cy(t)} = 0 and E (η(t) − Cy(t)) (η(t) − Cy(t))T = V

for given the variance matrix V = 1. Here, η(t) denotes the position measurement from
the camera. We assume that the model is exact and that there is no process noise.

1. A continuous-time Kalman filter is based on the solving the Riccati differential equa-
tion
Ṗ (t) = AP (t) + P (t)AT − P (t)C T V −1 CP (t) with P (0) = P0 .
Here, P0 = E{x(0)x(0)T } = I denotes the variance matrix of the initial state x(0),
which is assumed to be given and equal to the unit matrix. The inverse matrix
F (t) = P (t)−1 is called the information matrix that is associated with the Kalman
filter. Prove that F satisfies a Lyapunov differential equation. Solve this Lyapunov
differential equation as explicitly as possible and use this result to find a solution of
the above Riccati differential equation for P . Interpret your result. (10 points)

Solution: The function F satisfies the Lyapunov differential equation

∂
Ḟ (t) = P (t)−1 = −F (t)Ṗ (t)F (t) = −F (t)A − AT F (t) + C T V −1 C (2)
∂t
with F (0) = I. The solution for the matrix F has the form
Z t
T
F (t) = Φ(t, 0)Φ(t, 0) + Φ(t, τ )C T V −1 CΦ(t, τ )T dτ
0

T
with Φ(t, τ ) = e−A (t−τ ) = G(τ, t)T . Recall that an explicit expression for fundamental
solution G has already been worked out in the previous section. The solution of the
Riccati differential equation can then be recovered as P (t) = F (t)−1 . (We gave full
points for this or similar solutions, even if the above integral for F was not worked
out explicitly.)

5
EE550: Linear Systems Final Exam SIST, ShanghaiTech

2. Assume that we want to run the above Kalman on an embedded hardware system with
limited memory capacities. Also assume that there is additional (Gaussian) process
noise present and that variance matrix of the initial value is a steady-state of the
Riccati differential equation for the Kalman filter. Explain how you would implement
the filter in this case. Which variables do we need to store on the hardware in order
to run the filter? Which variables can be computed offline (beforehand), e.g., on a
desktop computer? Which operations do we have to perform online (and in real-time)
on the embedded hardware system whenever new measurements arrive? You may
assume that the measurements come in at a high sampling rate (much faster than the
time-scale of the system dynamics). The computation time of basic operations on a
modern processor (for static memory) is given below (1ns = 10−9 seconds).

Operation CPU Time

z[i] = x[i] 1.03ns
z[i] += x[i] 1.30ns
z[i] = x[i] + y[i] 1.38ns
z[i] += x[i] + y[i] 1.49ns
z[i] = x[i] * y[i] 1.50ns
z[i] += x[i] * y[i] 1.86ns

Estimate of the performance of your Kalman filter implementation in terms of how

long it takes to update the state estimate whenever a new measurement arrives.
(10 points)

Solution: As the Kalman filter is assumed to be at steady-state, we can solve the

algebraic Riccati equation

0 = AP + P AT − P C T V −1 CP + W

for the variance-covariance matrix P offline. Here W denotes the variance of the
additional noise. The associated Kalman gain, given by

K = P CV −1

can be computed offline, too. The differential equation for the state estimate is then
∂
ŷ(t) = Aŷ(t) + K(η(t) − C ŷ(t)) .
∂t
For small time steps 0 < δ  1, this equation can also be approximated as
Z δ
(A−KC)δ
χk+1 = Aχk + Bηk with A = e , and B = e(A−KC)(δ−τ ) K dτ .
0

The matrices A and B can be computed offline, too. The pseudo code list below
suggests that the Kalman filter update takes for our example less than 15ns on modern
processors. Here A and B are assumed to be pre-computed. (We have of course also
accepted direct methods as a solution approach, which discretize first and work with
the discrete-time Kalman filter.)

6
EE550: Linear Systems Final Exam SIST, ShanghaiTech

Input: measurement eta, output: state estimate chi (static memory).

Operation CPU Time
s[0] = chi[0]; +1.03ns
s[1] = chi[1]; +1.03ns
chi[0] += A[0]*s[0]; +1.86ns
chi[0] += A[1] *s[1]; +1.86ns
chi[0] += B[0] *eta; +1.86ns
chi[1] += A[2] *s[0]; +1.86ns
chi[1] += A[3] *s[1]; +1.86ns
chi[1] += B[1] *eta; +1.86ns
TOTAL < 15ns

Pseudo code for the Kalman state update using C-syntax.

7
EE550: Linear Systems Final Exam SIST, ShanghaiTech

IV Linear Quadratic Regulator

We still consider the mass-spring damper system from the previous sections. The kinetic energy
of the trolley at the time T is given by
1
Ekin = m [v(T )]2 .
2
Moreover, the potential energy of the spring is given by
1
Epot = D [x(T )]2 .
2
Our goal is to minimize the sum of the kinetic and potential energy at the end time T and an
additional control penalty term of the form
Z T
 (u(t))2 dt .
0

Here,  ≥ 0 is a scalar weighting factor.

1. Formulate the above problem as a linear-quadratic optimal control problem (LQR problem)
in standard form assuming that the initial value y0 for the states of system at time 0 are
given. (10 points)

Solution: The sum of the kinetic and potential energy is a quadratic form,
 
1 D 0
Ekin + Epot = y(T )T Pend y(T ) with Pend = .
2 0 m

The control penalty term has the form

Z T Z T
2
 (u(t)) dt = u(t)T Ru(t) dt with R=.
0 0

We also set Q = 0 ∈ R2×2 as states only enter via the Mayer term. The standard LQR
problem is then given by
Z Tn (
T T
o
T ẏ(t) = Ay(t) + Bu(t)
min y(t) Qy(t) + u(t) Ru(t) dt + y(T ) Pend y(T ) s.t.
x,u 0 y(0) = y0 .

8
EE550: Linear Systems Final Exam SIST, ShanghaiTech

2. Discuss how the optimal solutions for the control input and the states of the above linear-
quadratic optimal problem depend on the control penalty weight  > 0. What happens for
 → 0+ ? What happens for  → ∞? You may assume that the parameters D > 0, m > 0,
as well as c > 0 are given and positive. (10 points)

Solution: We denote with (y∗ , u∗ ) the optimal solution of the LQR optimal control prob-
lem in dependence on .

(a) For  → 0+ the control penalty vanishes leading to extreme control reactions. As the
system is controllable, we have

lim y∗ (T ) = 0 .
→0

(b) For  → ∞ we find lim→0 u∗ (t) = 0 for (almost) all t ∈ [0, T ], as the control penalty
becomes infinitely large. Thus, the states correspond to the open-loop response and
we have Ekin + Epot > 0 at time T (assuming y0 6= 0).