Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
604 B Solving Difference Equations
We define the one-sided z-transform of s
i
as
S(z) =
∞
i=0
s
i
z
−i
(B.21)
Now take the z-transform of both sides of (B.20) to obtain
S(z) −s
0
=
N
k=0
a
k
z
−k
×
∞
i=0
s
i−k
z
−(i−k)
(B.22)
We assume that a
k
= 0 when k > N and we also assume that s
i
= 0 when i < 0.
Based on these two assumptions, we can change the upper limit for the summation
over k and we can change the variable of summation of the term in square brackets
as follows.
S(z) −s
0
=
∞
k=0
a
k
z
−k
×
∞
m=0
s
m
z
−m
(B.23)
where we introduced the new variable m = i − k. Define the z-transform of the
coefficients a
k
as
A(z) =
∞
k=0
a
k
z
−k
(B.24)
Thus, we get
S(z) −s
0
= A(z) ×
∞
m=0
s
m
z
−m
= A(z) × S(z) (B.25)
Notice that the two summations on the right-hand side are now independent.
Thus, we finally get
S(z) =
s
0
1 − A(z)
(B.26)
We can write the above equation in the form
S(z) =
s
0
D(z)
(B.27)
References 605
where the denominator polynomial is
D(z) = 1 − A(z) (B.28)
MATLAB allows us to find the inverse z-transform of S(z) using the command
RESIDUE (a, b)
where a and b are the coefficients of the nominator and denominator polynomials
A(z) and B(z), respectively, in descending powers of z
−1
.
The function RESIDUE returns the column vectors r, p, and c which give the
residues, poles, and direct terms, respectively.
The solution for s
i
is given by the expression
s
i
= c
i
+
m
j=1
r
j
(p
j
)
(i−1)
i > 0 (B.29)
where m is the number of elements in r or p vectors.
References
1. J.R. Norris, Markov Chains, Cambridge University Press, New York, 1997.
2. V.K. Ingle and J.G. Proakis, Digital Signal Processing Using MATLAB, Brooks/Cole, Pacific
Grove, 2000.
3. A. Antoniou, Digital Filters: Analysis, Design, and Applications, McGraw-Hill, New York,
1993.
Appendix C
Finding s(n) Using the z-Transform
When the transition matrix P of a Markov chain is not diagonalizable, we could
use the z-transform technique to find the value of the distribution vector at any time
instance s(n). An alternative, and more appealing technique, is to use the Jordan
canonic form—however, we will explain the z-transform here. The z-transform of
the distribution vector s is given by
S(z) =
∞
n=0
s(n) z
−n
(C.1)
We express s(n) in the above equation in terms of the transition matrix P using
the relation
s(n) = P
n
s(0) (C.2)
Alternatively, s(n) can be written as
s(n) = Ps(n − 1) (C.3)
From (C.1), the z-transform of s(n) can be written as
S(z) = s(0) +
∞
n=1
Ps(n − 1)z
−n
(C.4)
Thus we have
S(z) −s(0) = z
−1
P
∞
n=1
s(n − 1) z
−(n−1)
(C.5)
Changing the index of summation, we get
S(z) −s(0) = z
−1
PS(z)(C.6)
607
608 C Finding s(n) Using the z-Transform
We can thus obtain an expression for the z-transform of the distribution vector as
S(z) =
I − z
−1
P
−1
s(0) (C.7)
Denoting the transform pair
S(z) ⇔ s(n)(C.8)
then we can write (C.7), using (C.2), in the form
I − z
−1
P
−1
s
(
0
)
⇔ P
n
s
(
0
)
(C.9)
Since s
(
0
)
is arbitrary, we have the z-transform pair
P
n
⇔
I−z
−1
P
−1
(C.10)
WWW: We have defined the MATLAB function invz(B,a) which accepts the
matrix B whose elements are the nominator polynomials of
I − z
−1
P
−1
and the
polynomial a which is the denominator polynomial of
I − z
−1
P
−1
. The function
returns the residue matrices r that correspond to each pole of the denominator.
The following two examples illustrate the use of this function.
Example C.1 Consider the Markov chain matrix
P =
⎡
⎣
0.50.80.4
0.50 0.3
00.20.3
⎤
⎦
Use the z-transform technique to find a general expression for the distribution
vector at step n and find its value when n = 3 and 100 assuming an initial distribu-
tion vector s(0) =
100
t
First, we must form
I − z
−1
P =
⎡
⎣
1 −0.5z
−1
−0.8z
−1
−0.4z
−1
−0.5z
−1
1 −0.3z
−1
0 −0.2z
−1
1 −0.3z
−1
⎤
⎦
We have to determine the inverse of this matrix using determinants or any other
technique to obtain
(
I −z
−1
P
−1
=
1
D
×
⎡
⎣
1 −0.3z
−1
−0.06z
−2
0.8z
−1
−0.16z
−2
0.4z
−1
+0.24z
−2
0.5z
−1
−0.15z
−2
1 −0.8z
−1
+0.15z
−2
0.3z
−1
+0.05z
−2
0.10z
−2
0.2z
−1
−0.10z
−2
1 −0.5z
−1
−0.40z
−2
⎤
⎦
C Finding s(n) Using the z-Transform 609
where
D =
1 − z
−1
1 +0.45z
−1
1 −0.25z
−1
We notice that the poles of this matrix are the eigenvalues of P.Wenowhaveto
find the inverse z-transform of
I − z
−1
P
−1
which can be done on a term-by-term
basis [1] or by using the MATLAB function invz(B,a) [1]:
P
n
=
⎡
⎣
0.59 0.59 0.59
0.32 0.32 0.32
0.09 0.09 0.09
⎤
⎦
+
(−0.45)
n
⎡
⎣
0.27 −0.51 0.06
−0.37 0.70 −0.08
0.10 −0.19 0.02
⎤
⎦
+
(0.25)
n
⎡
⎣
0.14 −0.08 −0.64
0.05 −0.02 −0.24
−0.19 0.10 0.88
⎤
⎦
n = 0, 1,...
We notice that the matrix corresponding to the pole z
−1
= 1 is column stochastic
and all its columns are equal. For the two matrices corresponding to the poles z
−1
=
−0.45 and 0.25, the sum of each column is exactly zero.
s(3) is given from the above equation by substituting n = 3 in the expression
for P
n
:
s(3) = P
3
s(0) = s(3) =
⎡
⎣
0.57
0.36
0.08
⎤
⎦
t
s(100) is given by
s(100) = P
100
s(0) =
⎡
⎣
0.59
0.32
0.09
⎤
⎦
t
Example C.2 Consider the Markov chain matrix
P =
⎡
⎣
0.20.40.4
0.80.10.4
00.50.2
⎤
⎦
Use the z-transform technique to find a general expression for the distribution
vector at step n and find its value when n = 7 for an initial distribution vector
s(0) =
100
t
610 C Finding s(n) Using the z-Transform
First, we must form
I − z
−1
P =
⎡
⎣
1 −0.2z
−1
−0.4z
−1
−0.4z
−1
−0.8z
−1
1 −0.1z
−1
−0.4z
−1
0 −0.5z
−1
1 −0.2z
−1
⎤
⎦
We have to determine the inverse of this matrix using determinants or any other
techniques to obtain
(
I −z
−1
P
−1
=
1
D
×
⎡
⎣
1 −0.3z
−1
−0.18z
−2
0.4z
−1
+0.12z
−2
0.4z
−1
+0.12z
−2
0.8z
−1
−0.16z
−2
1 −0.4z
−1
+0.40z
−2
0.4z
−1
+0.24z
−2
0.40z
−2
0.5z
−1
−0.10z
−2
1 −0.3z
−1
−0.30z
−2
⎤
⎦
where
D =
1 − z
−1
1 +0.3z
−1
1 +0.2z
−1
We notice that the poles of this matrix are the eigenvalues of P.Wenowhaveto
find the inverse z-transform of
I − z
−1
P
−1
which can be done on a term-by-term
basis [1] or by using the function invz(B,a):
P
n
=
⎡
⎣
0.33 0.33 0.33
0.41 0.41 0.41
0.26 0.26 0.26
⎤
⎦
+
(−0.3)
n
⎡
⎣
0.00.00.0
−3.08 1.92 0.92
3.08 −1.92 −0.92
⎤
⎦
+
(−0.2)
n
⎡
⎣
0.67 0.67 0.67
2.67 2.67 2.67
−3.33 −3.33 −3.33
⎤
⎦
n = 0, 1,...
We notice that the matrix corresponding to the pole z
−1
= 1 is column stochastic
and all its columns are equal. For the two matrices corresponding to the poles z
−1
=
−0.3 and 0.2, the sum of each column is exactly zero.
s(7) is given from the above equation as
s(7) = P
7
s(0)
Reference 611
or
s(7) =
⎡
⎣
0.33
0.41
0.26
⎤
⎦
Problems
C.1 Use the z-transform to find the distribution vector at any time instant n for the
transition matrix
⎡
⎣
0.20.40.4
0.80.10.4
00.50.2
⎤
⎦
C.2 Use the z-transform to find the distribution vector at any time instant n for the
transition matrix
0.50.3
0.50.7
C.3 Use the z-transform to find the distribution vector at any time instant n for the
transition matrix
⎡
⎢
⎢
⎣
0.20.30.50.6
0.30.10.20.1
0.50.10.10.2
00.50.20.1
⎤
⎥
⎥
⎦
C.4 Use the z-transform to find the distribution vector at any time instant n for the
transition matrix
⎡
⎣
0.10.40.1
0.700.3
0.20.60.6
⎤
⎦
Reference
1. V.K. Ingle and J.G. Proakis, Digital Signal Processing Using MATLAB, Brooks/Cole, Pacific
Grove, CA, 2000.
Appendix D
Vectors and Matrices
D.1 Introduction
The objective of this appendix is to briefly review the main topics related to ma-
trices since we encounter them in most of our work on queuing theory. There are
excellent books dealing with this subject and we refer the reader to them for a more
comprehensive treatment. Perhaps one of the best books on matrices is [1]. This
book is not only easy to read, but the author’s writing style and insights make the
topic actually enjoyable. The reader that wants to read a comprehensive book, albeit
somewhat dry, could consult [2].
D.2 Scalars
A scalar is a real or complex number. We denote scalars in this book by lower-case
letters or Greek letters. Sometimes, but not too often, we use upper-case letters to
denote scalars.
D.3 Vectors
A vector is an ordered collection of scalars v
1
, v
2
, ···, which are its components.We
use bold lower-case letters to indicate vectors. A subscript on a vector will denote a
particular component of the vector. Thus the scalar v
2
denotes the second component
of the vector v. Usually, we say v is a 3-vector to signify that v has three components.
A vector v could have its component values change with the time index n.At
time n, that vector will be denoted by v(n).
As an example, a vector that has only three components is written as
v =
⎡
⎣
v
1
v
2
v
3
⎤
⎦
(D.1)
613
614 D Vectors and Matrices
To conserve space, we usually write a column vector in the following form
v =
v
1
v
2
v
3
t
(D.2)
where the superscript t indicates that the vector is to be transposed by arranging the
components horizontally instead of vertically.
A vector is, by default, a column vector. A row vector r could be obtained by
transposing v
r = v
t
=
v
1
v
2
v
3
(D.3)
D.4 Arithmetic Operations with Vectors
Two vectors can be added if they have the same number of components
v +w =
⎡
⎣
v
1
+w
1
v
2
+w
2
v
3
+w
3
⎤
⎦
=
(
v
1
+w
1
)(
v
2
+w
2
)(
v
3
+w
3
)
t
(D.4)
A vector can be multiplied by a scalar if all the vector components are multiplied
by the same scalar as shown by
a v =
av
1
av
2
av
3
t
(D.5)
A row vector can multiply a column vector as long as the two vectors have the
same number of components:
rc=
r
1
r
2
r
3
⎡
⎣
c
1
c
2
c
3
⎤
⎦
(D.6)
= r
1
c
1
+r
2
c
2
+r
3
c
3
(D.7)
The dot product of a vector is just a scalar that is defined as
v ·w = v
1
w
1
+v
2
w
2
+v
3
w
3
(D.8)
where corresponding components are multiplied together.
Two vectors x and y are said to be orthogonal if their dot product vanishes:
x ·y = 0
D.6 Matrices 615
D.5 Linear Independence of Vectors
The two vectors x
1
and x
2
are said to be linearly independent or simply independent
when
a
1
x
1
+a
2
x
2
= 0 (D.9)
is true if and only if
a
1
= 0
a
2
= 0
D.6 Matrices
Assume we are given this set of linear equations
a
11
x
1
+a
12
x
2
+a
13
x
3
= b
1
a
21
x
1
+a
22
x
2
+a
23
x
3
= b
2
(D.10)
a
31
x
1
+a
32
x
2
+a
33
x
3
= b
3
We can write the equations in the form
⎡
⎣
a
11
a
12
a
13
a
21
a
22
a
23
a
31
a
32
a
33
⎤
⎦
⎡
⎣
x
1
x
2
x
3
⎤
⎦
=
⎡
⎣
b
1
b
2
b
3
⎤
⎦
(D.11)
where the first equation is obtained by multiplying the first row and the vector x and
the second equation is obtained by multiplying the second row and the vector x, and
so on. A concise form for writing the system of linear equations in (D.10) is to use
vectors and matrices:
Ax = b (D.12)
The coefficient matrix of this system of equations is given by the array of numbers
A =
⎡
⎣
a
11
a
12
a
13
a
21
a
22
a
23
a
31
a
32
a
33
⎤
⎦
(D.13)
A matrix with m rows and n columns is called a matrix of order m ×n or simply
an m × n matrix. When m = n, we have a square matrix of order n. The elements
a
ii
constitute the main diagonal of A.