Gebali F. Analysis Of Computer And Communication Networks

Подождите немного. Документ загружается.

626 D Vectors and Matrices

The reduced echelon form is given by

R = rref(A, b)

⎡

⎣

100 2

010 4

001−3

⎤

⎦

Thus the solution to our system of equations is

x =



14−3



Let us now see the reduced echelon form when the system has no solution:

+2x

= 1

= 0

+2x

+4x

= 6

The augmented matrix is given by





⎡

⎣

3213

2110

6246

⎤

⎦

The reduced echelon form is given by

R = rref(A, b)

⎡

⎣

10 10

01−10

00 01

⎤

⎦

The last equation implies that

+0x

= 1

There are no values of x

, x

, and x

that satisfy this equation and hence the

system has no solution.

The following system has an infinite number of solutions.

+2x

= 3

= 0

+3x

+2x

= 3

D.16 Direct Techniques for Solving Systems of Linear Equations 627

The augmented matrix is given by





⎡

⎣

3213

2110

5323

⎤

⎦

The reduced echelon form is given by

R = rref(A, b)

⎡

⎣

10 1−3

01−16

0000

⎤

⎦

Thus we have two equations for three unknowns and we could have infinity so-

lutions.

D.16 Direct Techniques for Solving Systems of Linear Equations

Direct techniques for solving systems of linear equations are usually the first one

attempted to obtain the solution. These techniques are appropriate for small matrices

where computational errors will be small. In the next section, we discuss iterative

techniques which are useful for large matrices.

D.16.1 Givens Rotations

Givens rotations operation performs a number of orthogonal similarity transforma-

tions on a matrix to make it an upper triangular matrix. Another equivalent technique

is the Householder transformation; but we will illustrate the Givens technique here.

The technique is very stable and does not suffer from the pivot problems of Gauss

elimination. We start with the equilibrium steady-state Markov chain equation

Ps= s (D.43)

and write it in the form

(

P −I

)

s = 0 (D.44)

As= 0 (D.45)

where 0 is a zero column vector. Thus, finding s amounts to solving a homogeneous

system of n linear equations in n unknowns. The system has a nontrivial solution

if the determinant of A is zero. This is assured here since the determinant of the

628 D Vectors and Matrices

matrix is equal to the product of its eigenvalues. Here, A has a zero eigenvalue,

which results in a zero determinant and this guarantees finding a nontrivial solution.

Applying a series of Givens rotations [6] will transform A into an upper triangu-

lar matrix T such that

Ts= 0 (D.46)

We are now able to do back-substitution to find all the elements of s.Thelast

row of T could be made identically zero since the rank of T is n − 1. We start our

back-substitution by ignoring the last row of T and assuming an arbitrary value for

= 1, then proceed to evaluate s

n−1

, and so on. There still remains one equation

that must be satisfied:



i=1

= 1 (D.47)

Let us assume that the sum of the components that we obtained for the vector s

gives



i=1

= b (D.48)

then we must divide each value of s by b to get the true normalized vector that we

desire.

Example D.2 Use Givens method to find the equilibrium state vector state s for the

Markov chain with transition matrix given by

P =

⎡

⎣

0.40.20

0.10.50.6

0.50.30.4

⎤

⎦

Step 1 Obtain the matrix A = P −I

A =

⎡

⎣

−0.60.20.0

0.1 −0.50.6

0.50.3 −0.6

⎤

⎦

Step 2 Create a zero in the (2, 1) position using the Givens rotation matrix G

⎡

⎣

cs0

−sc0

001

⎤

⎦

with θ = tan

−1

0.1

−0.6

D.17 Iterative Techniques 629

which gives

= G

A =

⎡

⎣

0.6083 −0.2795 0.0986

00.4603 −0.5918

0.50.3 −0.6

⎤

⎦

Step 3 Create a zero in the (3, 1) position using the Givens rotation matrix G

⎡

⎣

c 0 s

010

−s 0 c

⎤

⎦

with θ = tan

−1

0.5

0.6083

which gives

= G

⎡

⎣

0.7874 −0.0254 −0.3048

00.4603 −0.5918

00.4092 −0.5261

⎤

⎦

Step 4 Create a zero in the (3, 2) position using the Givens rotation matrix G

⎡

⎣

100

0 cs

0 −sc

⎤

⎦

with θ = tan

−1

0.4092

0.4603

which gives

= G

⎡

⎣

0.7874 −0.0254 −0.3048

00.6159 −0.7919

000

⎤

⎦

Step 5 Solve for the components of s assuming s

= 1

s =



0.3871 1.2857 1



After normalization, the true state vector becomes

s =



0.1448 0.4810 0.3741



D.17 Iterative Techniques

Iterative techniques continually refine the estimate of the solution while at the same

time suppressing computation noise. Thus, the answer could be accurate within the

machine precision. Iterative techniques are used when the system matrix is large and

sparse. This is a typical situation in Markov chains and queuing theory.

630 D Vectors and Matrices

D.17.1 Jacobi Iterations

We start with the steady-state Markov chain equation

Ps= s (D.49)

The matrix P is broken down as the sum of three components

P = L +D +U (D.50)

where L is the lower triangular part of P, D is the diagonal part of P, and U is the

upper triangular part of P. Thus, our steady-state equation can be written as

(

L +D +U

)

s = s (D.51)

We get Jacobi iterations if we write the above equation as

Ds=

(

I −L −U

)

s (D.52)

where I is the unit matrix and it is assumed that P has nonzero diagonal elements.

The technique starts with an assumed solution s

, then iterates to improve the guess

using the iterations

k+1

= D

−1

(

I −L −U

)

(D.53)

Each component of s is updated according to the equation

k+1

⎛

⎝

−

i−1



j=0

−

n−1



j=i+1

⎞

⎠

(D.54)

D.17.2 Gauss–Seidel Iterations

We get Gauss–Seidel iterations if we write (D.51) as

(

D +L

)

s =

(

I −U

)

s (D.55)

The technique starts with an assumed solution s

, then iterates to improve the

guess using the iterations

k+1

(

D +L

)

−1

(

I −U

)

(D.56)

D.18 Similarity Transformation 631

Each component of s is updated according to the equation

k+1

⎛

⎝

−

i−1



j=0

k+1

−

n−1



j=i+1

⎞

⎠

(D.57)

Notice that we make use of previously updated components of s to update the

next components as is evident by the iteration index associated with the first sum-

mation term (compare that with Jacobi iterations).

D.17.3 Successive Overrelaxation Iterations

We explain successive overrelaxation (SOR) technique by rewriting a slightly mod-

ified version of (D.57)

k+1

= s

⎛

⎝

−

i−1



j=0

k+1

−

n−1



j=i

⎞

⎠

(D.58)

We can think of the above equation as updating the value of s

by adding the

term in brackets. We multiply that term by a relaxation parameter ω to get the SOR

iterations:

k+1

= s

⎛

⎝

−

i−1



j=0

k+1

−

n−1



j=i

⎞

⎠

(D.59)

when ω = 1, we get Gauss–Seidel iterations again of course.

D.18 Similarity Transformation

Assume there exists a square matrix M whose inverse is M

−1

. Then the two square

matrices A and B = M

−1

AM aresaidtobesimilar.WesaythatB is obtained from

A by a similarity transformation. Similar matrices have the property that they both

have the same eigenvalues. To prove that, assume x is the eigenvector of A

Ax = λx (D.60)

We can write the above equation in the form

AMM

−1

x = λx (D.61)

632 D Vectors and Matrices

Premultiplying both sides of this equation by M

−1

, we obtain

−1

A MM

−1

x = λM

−1

x (D.62)

But B = M

−1

AM, by definition, and we have



−1



= λ



−1



(D.63)

Thus, we proved that the eigenvectors and eigenvalues of B are M

−1

x and λ,

respectively.

Thus, we can say that the two matrices A and B are similar when their eigenvalues

are the same and their eigenvectors are related through the matrix M.

D.19 Special Matrices

The following is an alphabetical collection of special matrices that were encountered

in this book.

D.19.1 Circulant Matrix

A square circulant matrix has the form

P =

⎡

⎢

⎣

000··· 001

100··· 000

010··· 000

000··· 000

000··· 100

000··· 010

⎤

⎥

⎦

(D.64)

Premultiplying a matrix by a circulant matrix results in circularly shifting all the

rows down by one row and the last row will become the first row.

An m × m circulant matrix C has the following two interesting properties:

Repeated multiplication m-times produces the identity matrix

= I (D.65)

where k is an integer multiple of m.

D.19 Special Matrices 633

Eigenvalues of the matrix all lie on the unit circle

= exp



j2π ×



= 1, 2, ···, m (D.66)

where j =

√

−1 and

= 1 (D.67)

D.19.2 Diagonal Matrix

A diagonal matrix has a

= 0 whenever i = j and a

= d

.A3× 3 diagonal

matrix D is given by

D =

⎡

⎣

0 d

00d

⎤

⎦

(D.68)

An alternative way of defining D is

D = diag





(D.69)

D = diag

(

)

(D.70)

where d is the vector of diagonal entries of D.

D.19.3 Echelon Matrix

An m × n matrix A can be transformed using elementary row operations into an

upper triangular matrix U, where elementary row operations include

1. Exchanging two rows.

2. Multiplication of a row by a nonzero constant.

3. Addition of a constant multiple of a row to another row.

Such operations are used in Givens rotations and Gauss elimination to solve the

system of linear equations

Ax = b (D.71)

by transforming it into

Ux = c (D.72)

634 D Vectors and Matrices

then doing back-substitution to find the unknown vector x. The matrix U that results

is in echelon form. An example of a 4 ×6 echelon matrix is

U =

⎡

⎢

⎣

xxxxxx

0 xxxxx

0000xx

00000x

⎤

⎥

⎦

(D.73)

Notice that the number of leading zeros in each row must increase. The number

of pivots

equals the rank r of the matrix.

D.19.4 Identity Matrix

An identity matrix has a

= 0 whenever i = j and a

= 1. A 3 ×3 identity matrix

I is given by

I =

⎡

⎣

100

010

001

⎤

⎦

(D.74)

D.19.5 Nonnegative Matrix

An m × n matrix A is nonnegative when

≥ 0 (D.75)

for all 1 ≤ i ≤ m and 1 ≤ j ≤ n

D.19.6 Orthogonal Matrix

An orthogonal matrix has the property

= I (D.76)

The inverse of A is trivially computed as A

−1

= A

. The inverse of an orthogonal

matrix equals its transpose. Thus, if G is an orthogonal matrix, then we have by

definition

G = G

−1

G = I (D.77)

A pivot is the leading nonzero element in each row.

D.19 Special Matrices 635

It is easy to prove that the Givens matrix is orthogonal. A matrix A is invertible

if there is a matrix A

−1

such that

−1

= A

−1

A = I (D.78)

D.19.7 Plane Rotation (Givens) Matrix

A5× 5 plane rotation (or Givens) matrix is one that looks like the identity matrix

except for elements that lie in the locations pp, pq, qp, and qq. Such a matrix is

labeled G

. For example, the matrix G

takes the form

⎡

⎢

⎣

1 0 000

0 c 0 s 0

0 0 100

0 −s 0 c 0

0 0 001

⎤

⎥

⎦

(D.79)

where c = cos θ and s = sin θ. This matrix is orthogonal. Premultiplying a matrix A

by G

modifies only rows p and q. All other rows are left unchanged. The elements

in rows p and q become

= ca

+sa

(D.80)

=−sa

+ca

(D.81)

D.19.8 Stochastic (Markov) Matrix

A column stochastic matrix P has the following properties:

1. a

≥ 0 for all values of i and j.

2. The sum of each column is exactly 1 (i.e.,



j=1

= 1).

Such a matrix is termed column stochastic matrix or Markov matrix. This matrix

has two important properties. First, all eigenvalues are in the range −1 ≤ λ ≤ 1.

Second, at least one eigenvalue is λ = 1.

D.19.9 Substochastic Matrix

A column substochastic matrix V has the following properties:

1. a

≥ 0 for all values of i and j.

2. The sum of each column is less than 1 (i.e.,



j=1

< 1).