BOUNDS FOR THE SOLUTION OF DISCRETE COUPLED
LYAPUNOV EQUATION
Adam Czornik
Silesian Technical University, Department of Automatic Control and Robotics
Akademicka Street 16, 44-100 Gliwice, Poland
Aleksander Nawrat
Silesian Technical University, Department of Automatic Control and Robotics
Akademicka Street 16, 44-100 Gliwice, Poland
Keywords:
Coupled Lyapunov equation, jump linear systems, eigenvalues bounds.
Abstract:
Upper and lower matrix bounds for the solution of the discrete time coupled algebraic Lyapunov equation for
linear discrete-time system with Markovian jumps in parameters are developed. The bounds of the maximal,
minmal eigenvalues, the summation of eigenvalues, trace and determinant are also given.
1 INTRODUCTION
It is well known that algebraic Lyapunov and Riccati
equations are widely applied to various engineering
areas including different problems in signal process-
ing and, especially, control theory. In the area of
control system analysis and design, these equations
play crucial role in system stability and boundedness
analysis, optimal and robust controllers and filters de-
sign, the transient behavior estimates, etc. During the
past two decades many bounds for the solution of var-
ious types of algebraic Lyapunov and Riccati equation
have been reported. The surveys of such results can be
found in (Mori and Derese, 1984), (Komaroff, 1996),
(Kwon et al., 1996), (Czornik and Nawrat, 2000). The
reasons that the problem to estimate upper and lower
bounds of these equations has become an attractive
topic are that the bounds are also applied to solve
many control problems such as stability analysis (Lee
et al., 1995), (Patel and Toda, 1980), time-delay sys-
tem controller design (Mori et al., 1983), estimation
of the minimal cost and the suboptimal controller de-
sign (Langholz, 1979), convergence of numerical al-
gorithms (Allwright,1980), robust stabilization prob-
lem (Boukas et al., 1997). Eigenvalue bounds can be
also used to determine whether or not the system un-
der consideration possesses the singularly perturbed
structure (Gajic and Qureshi, 1995). An excellent mo-
tivation to study the bounds for Lyapunov equation is
given in (Gajic and Qureshi, 1995) (Section 2.2). The
authors advocated the results in this area by saying
that sometimes we are just interested in the general
behavior of the underlying system and then the behav-
ior can be determined by examining certain bounds on
the parameters of the solution instead of the full solu-
tion.
Considering the linear dynamical systems with
Markovian jumps in parameter values, which have re-
cently attracted a great deal of interest, instead of one
equation a set of coupled algebraic equations arises.
They are called coupled algebraic Riccati and cou-
pled Lyapunov equation. All the reasons mentioned
above could be repeated to show how the bounds for
coupled algebraic Lyapunov equations can be used.
Bounds for the coupled Riccati equation have been al-
ready obtained in (Czornik and Swierniak,2001a) and
(Czornik and Swierniak, 2001b). To our knowledge
this paper is the first where the bounds for coupled
algebraic Lyapunov equations are established.
The eigenvalues λ
i
(X), where i = 1, ..., n, of
a symmetric matrix X ∈ R
n×n
are assumed to be
arranged such that
λ
1
(X) ≥ λ
2
(X) ≥ ... ≥ λ
n
(X) .
When we consider the discrete time jump linear sys-
tem the following discrete coupled algebraic Lya-
punov equation (DCALE) arises (Chizeck et al.,
1986):
P
i
= Q
i
+ A
′
i
F
i
A
i
(1)
where
F
i
=
X
j∈S
p
ij
P
j
(2)
and A
i
, Q
i
, P
i
∈ R
n×n
, p
ij
∈ [0, 1] ,
P
j∈S
p
ij
=
1, i ∈ S , S is a finite set. The numbers p
ij
are the
transitions probabilities of a Markov chain.
We need the following lemma.
11
Czornik A. and Nawrat A. (2006).
BOUNDS FOR THE SOLUTION OF DISCRETE COUPLED LYAPUNOV EQUATION.
In Proceedings of the Third International Conference on Informatics in Control, Automation and Robotics, pages 11-15
DOI: 10.5220/0001201900110015
Copyright
c
SciTePress
Lemma 1 (Marshall and Olkin, 1979)Let X, Y ∈
R
n×n
with X = X
′
, Y = Y
′
, X, Y ≥ 0. Then the
following inequalities hold
λ
i+j−1
(XY ) ≤ λ
i
(X)λ
j
(Y ) , if i+j ≤ n +1 (3)
λ
i+j−n
(XY ) ≥ λ
i
(X)λ
j
(Y ) , if i+j ≥ n+1 (4)
l
X
k=1
λ
k
(X + Y ) ≤
l
X
k=1
λ
k
(X) +
l
X
k=1
λ
k
(Y ) (5)
l
X
k=1
λ
n−k+1
(X + Y ) ≥
l
X
k=1
λ
n−k+1
(X) +
l
X
k=1
λ
n−k+1
(Y ) . (6)
2 MAIN RESULTS
The next theorem contains the main result of the pa-
per.
Theorem 2 For the eigenvalues λ
k
(P
i
) , k =
1, ..., n, i ∈ S of positive definite solution P
i
, i ∈ S of
DCALE (1), the following inequalities hold
l
X
k=1
λ
k
(P
i
) ≤
l
X
k=1
λ
k
(Q
i
) +
max
j∈S
p
ij
λ
1
(A
i
A
′
i
) ·
·
P
i∈S
P
l
k=1
λ
k
(Q
i
)
1− max
j∈S
λ
1
A
j
A
′
j
max
j∈S
P
i∈S
p
ij
=
= α (l, i) , (7)
for l = 1, ..., n, if max
j∈S
λ
1
A
j
A
′
j
max
j∈S
P
i∈S
p
ij
<
1, and
l
X
k=1
λ
n−k+1
(P
i
) ≥
l
X
k=1
λ
n−k+1
(Q
i
) +
min
j∈S
p
ij
min
j∈S
λ
n
A
j
A
′
j
P
i∈S
P
l
k=1
λ
n−k+1
(Q
i
)
1− min
j∈S
λ
n
A
j
A
′
j
min
j∈S
P
i∈S
p
ij
=
= β (l, i) , (8)
for l = 1, ..., n, if min
j∈S
λ
n
A
j
A
′
j
min
j∈S
P
i∈S
p
ij
<
1.
Proof. From (1) it follows, by using (5) and (3), that
l
X
k=1
λ
k
(P
i
) ≤
l
X
k=1
λ
k
(Q
i
) +
l
X
k=1
λ
k
(A
′
i
F
i
A
i
) =
=
l
X
k=1
λ
k
(Q
i
) +
l
X
k=1
λ
k
(F
i
A
i
A
′
i
)
≤
l
X
k=1
λ
k
(Q
i
) + λ
1
(A
i
A
′
i
)
l
X
k=1
λ
k
(F ) . (9)
Applying (5) to (2) leads to
l
X
k=1
λ
k
(F ) ≤
X
j∈S
p
ij
l
X
k=1
λ
k
(P
j
)
!
. (10)
Combining (9) with (10) yields to
l
X
k=1
λ
k
(P
i
) ≤
l
X
k=1
λ
k
(Q
i
) +
+ max
j∈S
λ
1
A
j
A
′
j
X
j∈S
p
ij
l
X
k=1
λ
k
(P
j
)
!
. (11)
Summing the above inequality over i ∈ S we have
X
i∈S
l
X
k=1
λ
k
(P
i
) ≤
X
i∈S
l
X
k=1
λ
k
(Q
i
)
+ max
j∈S
λ
1
A
j
A
′
j
X
i,j∈S
p
ij
l
X
k=1
λ
k
(P
j
)
!
=
X
i∈S
l
X
k=1
λ
k
(Q
i
) + max
j∈S
λ
1
A
j
A
′
j
·
·
X
j∈S
X
i∈S
p
ij
!
l
X
k=1
λ
k
(P
j
)
!
≤
X
i∈S
l
X
k=1
λ
k
(Q
i
) + max
j∈S
λ
1
A
j
A
′
j
·
·
max
j∈S
X
i∈S
p
ij
!
X
i∈S
l
X
k=1
λ
k
(P
i
) .
Solving this inequality respect to
P
i∈S
P
l
k=1
λ
k
(P
i
) and taking into account
that
max
j∈S
λ
1
A
j
A
′
j
max
j∈S
X
i∈S
p
ij
< 1
we obtain
X
i∈S
l
X
k=1
λ
k
(P
i
) ≤
ICINCO 2006 - SIGNAL PROCESSING, SYSTEMS MODELING AND CONTROL
12
P
i∈S
P
l
k=1
λ
k
(Q
i
)
1− max
j∈S
λ
1
A
j
A
′
j
max
j∈S
P
i∈S
p
ij
. (12)
(9) implies also that
l
X
k=1
λ
k
(P
i
) ≤
l
X
k=1
λ
k
(Q
i
) +
λ
1
(A
i
A
′
i
)
X
j∈S
p
ij
l
X
k=1
λ
k
(P
j
)
!
≤
l
X
k=1
λ
k
(Q
i
) +
max
j∈S
p
ij
·
·λ
1
(A
i
A
′
i
)
X
j∈S
l
X
k=1
λ
k
(P
j
) . (13)
Applying (12) on the right hand side of (13) we have
(7).
To proof (8) let’s observe that the use of (6) and (4)
to (1) to gives
l
X
k=1
λ
n−k+1
(P
i
) ≥
l
X
k=1
λ
n−k+1
(Q
i
) +
l
X
k=1
λ
n−k+1
(A
′
i
F
i
A
i
) =
l
X
k=1
λ
n−k+1
(Q
i
) +
l
X
k=1
λ
n−k+1
(F
i
A
i
A
′
i
) ≥
l
X
k=1
λ
n−k+1
(Q
i
) + λ
n
(A
i
A
′
i
) ·
l
X
k=1
λ
n−k+1
(F
i
) ≥
l
X
k=1
λ
n−k+1
(Q
i
) +
min
j∈S
λ
n
A
j
A
′
j
l
X
k=1
λ
n−k+1
(F
i
) . (14)
Summing (14) over i ∈ S we have
X
i∈S
l
X
k=1
λ
n−k+1
(P
i
) ≥
X
i∈S
l
X
k=1
λ
n−k+1
(Q
i
) +
min
j∈S
λ
n
A
j
A
′
j
X
i∈S
l
X
k=1
λ
n−k+1
(F
i
) . (15)
Applying (6) to (2) leads to
l
X
k=1
λ
n−k+1
(F
i
) ≥
X
j∈S
p
ij
l
X
k=1
λ
n−k+1
(P
j
) . (16)
Combining (15) with (16) yields to
X
i∈S
l
X
k=1
λ
n−k+1
(P
i
) ≥
X
i∈S
l
X
k=1
λ
n−k+1
(Q
i
) +
min
j∈S
λ
n
A
j
A
′
j
·
·
X
i∈S
X
j∈S
p
ij
l
X
k=1
λ
n−k+1
(P
j
)
=
X
i∈S
l
X
k=1
λ
n−k+1
(Q
i
) + min
j∈S
λ
n
A
j
A
′
j
·
·
X
j∈S
X
i∈S
p
ij
!
l
X
k=1
λ
n−k+1
(P
j
)
!
≥
X
i∈S
l
X
k=1
λ
n−k+1
(Q
i
) + min
j∈S
λ
n
A
j
A
′
j
·
· min
j∈S
X
i∈S
p
ij
X
i∈S
l
X
k=1
λ
n−k+1
(P
i
) .
Solving this inequality with respect to
P
i∈S
P
l
k=1
λ
n−k+1
(P
i
) and taking into account
that
min
j∈S
λ
n
A
j
A
′
j
min
j∈S
X
i∈S
p
ij
< 1
we obtain
X
i∈S
l
X
k=1
λ
n−k+1
(P
i
) ≥
P
i∈S
P
l
k=1
λ
n−k+1
(Q
i
)
1− min
j∈S
λ
n
A
j
A
′
j
min
j∈S
P
i∈S
p
ij
. (17)
Combining (14) and (16) we conclude that
l
X
k=1
λ
n−k+1
(P
i
) ≥
l
X
k=1
λ
n−k+1
(Q
i
) +
min
j∈S
p
ij
·
· min
j∈S
λ
n
A
j
A
′
j
X
i∈S
l
X
k=1
λ
n−k+1
(P
i
) .
Applying (17) to the right hand side of the above in-
equality we obtain (8).
Using the Theorem 2 we can establish the follow-
ing general matrix bound for the solution of DCALE
(1).
Theorem 3 For the positive definite solution P
i
, i ∈
S of DCALE (1) we have
P
i
≤
X
j∈S
p
ij
α (1, j)
A
′
i
A
i
+ Q
i
, (18)
BOUNDS FOR THE SOLUTION OF DISCRETE COUPLED LYAPUNOV EQUATION
13
if max
j∈S
λ
1
A
j
A
′
j
max
j∈S
P
i∈S
p
ij
< 1 and
P
i
≥
X
j∈S
p
ij
β (1, j)
A
′
i
A
i
+ Q
i
(19)
if min
j∈S
λ
n
A
j
A
′
j
min
P
i∈S
p
ij
j∈S
< 1, where α (1, j)
and β (1, j) are given in Theorem 2.
Proof. In (Rugh, 1993) it has been shown that for any
symmetric matrix T ∈ R
n×n
and x ∈ R
n
λ
n
(T )x
′
x ≤ x
′
T x ≤ λ
1
(T )x
′
x.
Using this inequality to (1) we have
X
j∈S
p
ij
λ
n
(P
j
)
A
′
i
A
i
+ Q
i
≤ P
i
≤
≤
X
j∈S
p
ij
λ
1
(P
j
)
A
′
i
A
i
+ Q
i
.
Combining this inequality with (7) and (8) for l = 1
we get the conclusions of the theorem.
From Theorem 3 on the obvious way the bounds
for det (P
i
), t r (P
i
), λ
i
(P ) can be obtained and they
are collected in the next Remark.
Remark 1 For the positive definite solution P
i
, i ∈ S
of DCALE (1) we have
tr (P
i
) ≤
X
j∈S
p
ij
α (1, j)
tr (A
′
i
A
i
) + trQ
i
,
det (P
i
) ≤ det
X
j∈S
p
ij
α (1, j)
(A
′
i
A
i
) + Q
i
,
λ
k
(P
i
) ≤ λ
k
X
j∈S
p
ij
α (1, j)
(A
′
i
A
i
) + Q
i
,
if max
j∈S
λ
1
A
j
A
′
j
max
j∈S
P
i∈S
p
ij
< 1 and
tr (P
i
) ≥
X
j∈S
p
ij
β (1, j)
tr (A
′
i
A
i
) + tr (Q
i
)
det (P
i
) ≥ det
X
j∈S
p
ij
β (1, j)
(A
′
i
A
i
) + Q
i
λ
k
(P
i
) ≥ λ
k
X
j∈S
p
ij
β (1, j)
tr (A
′
i
A
i
) + Q
i
,
if min
j∈S
λ
n
A
j
A
′
j
min
P
i∈S
p
ij
j∈S
< 1. Where α (1, j)
and β (1, j) are given in Theorem 2.
Now we have bounds of λ
1
(P
i
) and tr (P
i
) in The-
orem 2 and in Corollary 1 similar for the lower bounds
of λ
n
(P
i
) and tr (P
i
) , but in general is difficult to say
which one are better, however the example presented
in the next section suggests that the bounds from The-
orem 3 can be better.
3 NUMERICAL EXAMPLE
Consider the following fourth-order jump linear sys-
tem with three switching modes (Gajic and Qureshi,
1995): S = {1, 2, 3}
[p
ij
]
i,j∈S
=
"
0.1 0.3 0.6
0.5 0.25 0.25
0 0.3 0.7
#
A
1
=
0.0667 0.0665 0.0844 −0.2257
0.1383 −0.1309 0.0797 0.1162
0.0658 0.0298 0.0645 −0.1018
−0.2283 0.2438 −0.1990 0.2997
A
2
=
0.1885 −0.3930 −0.0894 −0.1919
−0.4230 0.3598 −0.1224 −0.1548
0.0350 −0.1950 −0.1967 −0.1017
−0.2648 −0.2440 −0.0542 0.0484
A
3
=
0.2746 0.0634 0.3414 −0.0692
0.0796 0.4167 0.0283 −0.1207
−0.1607 0.0344 −0.2227 0.1617
0.1175 −0.2969 0.4149 0.3314
Q
1
= Q
2
= Q
3
= I
4
.
For the solution P
1
, P
2
, P
3
we have
λ
1
(P
1
) = 1.3533, λ
2
(P
1
) = 1.1182, λ
3
(P
1
) = 1.0124,
λ
4
(P
1
) = 1.0000,
λ
1
(P
2
) = 1.7003, λ
2
(P
2
) = 1.2309, λ
3
(P
2
) = 1.0979,
λ
4
(P
2
) = 1.0104,
λ
1
(P
3
) = 1.6385, λ
2
(P
3
) = 1.3763, λ
3
(P
3
) = 1.0665,
λ
4
(P
3
) = 1.0019,
(7) and (8) give the following bounds
λ
1
(P
1
) ≤ 3.5806, λ
4
(P
1
) ≥ 1
λ
1
(P
2
) ≤ 4.7421, λ
4
(P
2
) ≥ 1
λ
1
(P
3
) ≤ 6.2760, λ
4
(P
3
) ≥ 1
which are not satisfying. However (18) and gives
1.0000 ≤ λ
4
(P
1
) ≤ 1.0000, 1.0101 ≤ λ
3
(P
1
) ≤ 1.0562,
1.0809 ≤ λ
2
(P
1
) ≤ 1.4486, 1.2928 ≤ λ
1
(P
1
) ≤ 2.6237,
1.0098 ≤ λ
4
(P
2
) ≤ 1.0445, 1.0807 ≤ λ
3
(P
2
) ≤ 1.3667,
1.2054 ≤ λ
2
(P
2
) ≤ 1.9334, 1.5095 ≤ λ
1
(P
2
) ≤ 3.3156,
1.0014 ≤ λ
4
(P
3
) ≤ 1.0082, 1.0550 ≤ λ
3
(P
3
) ≤ 1.3196,
1.3130 ≤ λ
2
(P
3
) ≤ 2.8202, 1.5134 ≤ λ
1
(P
3
) ≤ 3.9861.
ICINCO 2006 - SIGNAL PROCESSING, SYSTEMS MODELING AND CONTROL
14
4 CONCLUSION
Upper and lower matrix bounds for the solution of
DCALE have been developed. By these bounds, the
corresponding eigenvalue bounds (i.e. for each eigen-
values including the extreme ones, the trace and the
determinant) have been defined in turn.
ACKNOWLEDGEMENTS
The work has been supported by KBN grant No 0
T00B 029 29 and 3 T11A 029 028.
REFERENCES
J. C. Allwright, A Lower Bound for the Solution of the
Algebraic Riccati Equation of Optimal Control and a
Geometric Convergence for the Kleinman Algorithm,
IEEE Transactions on Automatic Control, vol. 25,
826-829, 1980.
E. K. Boukas, A. Swierniak, K. Simek and H. Yang, Robust
Stabilization and Guaranteed Cost Control of Large
Scale Linear Systems With Jumps, Kybernetika, vol.
33, 121-131, 1997.
H. J. Chizeck, A.S. Willsky, D. Castanon, Discrete-Time
Markovian-Jump Linear Quadratic Optimal Control,
International Journal of Control, vol 43, no. 1, 213-
231, 1986.
A. Czornik, A. Nawrat, On the Bounds on the Solutions
of the Algebraic Lyapunov and Riccati Equation,
Archives of Control Science, vol. 10, no. 3-4, 197-
244, 2000.
A. Czornik, A. Swierniak, Lower Bounds on the Solution
of Coupled Algebraic Riccati Equation, Automatica,
vol. 37, no. 4, 619-624, 2001,
A. Czornik, A. Swierniak, Upper Bounds on the Solution
of Coupled Algebraic Riccati Equation, Journal of In-
equalities and Applications, vol. 6, no. 4, 373-385,
2001.
A. Gajic, M. Qureshi, Lyapunov Matrix Equation in System
Stability and Control, Mathematics in Science and En-
gineering, vol. 195, Academic Press, London, 1995.
N. Komaroff, On Bounds for the Solution of the Riccati
Equation for Discrete-Time Control System, Control
and Dynamics Systems, vol. 76, pp. 275, 311, 1996.
W. H. Kwon, Y. S. Moon and S. C. Ahn, Bounds in Al-
gebraic Riccati and Lyapunov Equations: Survey and
Some New Results, International Journal of Control,
vol 64, no. 3, 377-389, 1996.
G. Langholz, A New Lower Bound on the Cost of Optimal
Regulator, IEEE Transactions on Automatic Control,
vol. 24, 353-354, 1979.
C. H. Lee, T.-H.S. Li, and F. C. Kung, A New Approach for
the Robust Stability of Perturbed Systems with Class
of Non-Commensurate Time Delays, IEEE Transac-
tions on Circuits and Systems -I, vol. 40, 605-608,
1995.
A. W. Marshall and I. Olkin, Inequalities: Theory of Ma-
jorization and its Applications, Academic Press, New
York, 1979.
T. Mori, E. Noldus, M. Kuwahara, A Way to Stabilizable
Linear System With Delayed State, Automatica, vol.
19, 571-574, 1983.
T. Mori and I. A. Derese, A Brief Summary of the Bounds
on the Solution of the Algebraic Matrix Equations in
Control Theory, International Journal of Control, vol
39, no. 2, 247-256, 1984.
R. V. Patel and M. Toda, Quantitative Measures of Robust-
ness for Multivariable Systems, Proceedings of the
Joint Automatic Control Conference, San Francisco,
TP8-A, 1980.
W. J. Rugh, Linear System Theory, Englewood Cliffs, NJ:
Prentice-Hall, 1993.
BOUNDS FOR THE SOLUTION OF DISCRETE COUPLED LYAPUNOV EQUATION
15
