MODULE-II

SYSTEM OF LINEAR EQUATIONS

The system of linear equations

a1x  b1 y  c1z  d1
a2 x  b2 y  c2 z  d 2 (1)
a3 x  b3 y  c3 z  d3
is said to be diagonally dominant if
a1  b1  c1
b2  a2  c2
c3  a3  b3

The process of iteration in solving the system of equations (1) will converge
quickly if the system is diagonally dominated.

Gauss-Seidel iteration method:

Suppose the system of equations

a1x  b1 y  c1z  d1
a2 x  b2 y  c2 z  d 2 (1)
a3 x  b3 y  c3 z  d3
is diagonally dominant, then (1) can be written as

1
x  d  b y  c1z 
a1 1 1
----------------------------- (2)
1
y   d2  a2 x  c2 z  ----------------------------- (3)
b2
1
z   d3  a3 x  b3 y  ----------------------------- (4)
c3
First iteration:

Taking y  0 and z  0 in (2), we get

d
x1  1
a1
Taking x  x1 and z  0 in (3), we get

y 1 
b 
1
2
d 2  a2 x 
1

Taking x  x1 and y  y1 in (4), we get
 z 1 
1
c
 d  a x   b y 
3
3 3
1
3
1

Second iteration:

Taking y  y 1 and z  z 1 in (2), we get

x 2  
1
a1 
d1  b1 y    c1 z  
1 1

Taking x  x  and z  z 1 in (3), we get
2

y   1  d2  a2 x 2  c2 z 1 
2
b2  

Taking x  x  and y  y   in (4), we get

2 2

 2  1  d  a x  2  b y  2  
z  3 3 3 
c3  
Continue this process till to get two successive iterations are very close to each
other.

1. Solve the following system of equations using Gauss-Seidel iteration method

6 x 15 y  2 z  72 ;
x  y  54 z  110 ;
27 x  6 y  z  85 .

Solution: Clearly the given system is not diagonally dominant.

We can write the given system as

27 x  6 y  z  85
6 x 15 y  2 z  72 (1)
x  y  54 z  110
Now, system (1) is diagonally dominant. Therefore, from (1) we have
1
x
27
85  6 y  z  ----------------------------- (2)
1
y   72  6 x  2 z  ----------------------------- (3)
15
1
z  110  x  y  ----------------------------- (4)
54
First iteration:

Taking y  0 and z  0 in (2), we get

x1  3.1481
Taking x  x1  3.1481 and z  0 in (3), we get

y 1  3.5408
Taking x  x1  3.1481 and y  y1  3.5408 in (4), we get
 z 1  1.9132 .

Second iteration:

Taking y  y 1  3.5408 and z  z1  1.9132 in (2), we get

x   2.4322
2

Taking x  x   2.4322 and z  z1  1.9132 in (3), we get

2

y   3.572
2

Taking x  x   2.4322 and y  y    3.572 in (4), we get

2 2

z
2 1.9258
Third iteration:

Taking y  y  2  3.572 and z  z 2  1.9258 in (2), we get

x3  2.4257
Taking x  x   2.4257 and z  z 2  1.9258 in (3), we get
3

y   3.5729
3

Taking x  x   2.4257 and y  y    3.5729 in (4), we get

3 3

z
3 1.926
Fourth iteration:

Taking y  y 3  3.5729 and z  z3  1.926 in (2), we get

x4  2.4255
Taking x  x   2.4255 and z  z3  1.926 in (3), we get
4

y   3.573
4

Taking x  x   2.4255 and y  y    3.573 in (4), we get

4 4

z
4 1.926

The Values of x, y, z in the third and fourth iterations are very close to each other.

Therefore an approximate solution of the given system of equations is

x  2.4255, y  3.573, z 1.926 .

2. Solve the following system of equations using Gauss-Seidel iteration method

(i) 10 x  2 y  z  9 ; x  10 y  z  22 ; 2 x  3 y  10 z  22 .
(ii) 28x  4 y  z  32 ; x  3 y  10 z  24 ; 2 x  17 y  4 z  35 .
LU decomposition method (Crout’s method):

1. Solve the following system of equations using LU decomposition method.

x  y  z  9 ; 2 x  3 y  4 z  13 ; 3x  4 y  5z  40 .
Solution: The given system of equations can be written as

AX  B -------------------- (1)

1 1 1  x 9
   
where A   2 3 4  , X   y  , B  13 
 3 4 5   z   40 
Let A  LU ---------------------------------------------------------------------- (2)

 l11 0 0 1 u12 u13 

where L  l21 l22 0  and U  0 1 u23 
l31 l32 l33  0 0 1 
Then LU  A gives

 l11 l11u12 l11u13  1 1 1 

l l21u13  l22u23    2 3 4 
 21 l21u12  l22
l31 l31u12  l32 l31u13  l32u23  l33   3 4 5 

Equating the elements of the matrix, we have

12
l11  1, l21  2, l31  3, l22  5, l32  1, l33 
5
2
and u12  1, u13  1, u23  . .
5

 
1 0 0 1 1 1 
   2 
Therefore L   2 5 0  and U  0 1 .
  5 
12  0
 3 1   0 1 
 5
Now substituting A  LU in (1) we get LU X  B ----------------------- (3)

r 
Let U X  B1 where B1   s  say.
 t 

Therefore, from (3) we have L B1  B .

  
1 0 0 r   9 
   s   13 
i,e.,  2 5 0     
 12   t   40 
3 1 
 5

which gives r  9, s  1, t  5 .
1 1 1 
9     x  9 
2     
Therefore, B1  1  . Now, U X  B1   0 1 y  1
 5    
5  0 0  z  5 
 1     

2
which implies that x  y  z  9, y  z  1, z  5 .
5
Hence the required solution of the given system is x  1, y  3, z  5 .

2. Solve the following system of equations using LU decomposition method.

(i) 2 x  6 y  8z  24 ; 5x  4 y  3z  2 ; 3x  y  2 z  16 .
(ii) x  y  2 ; 2x  3 y  5 .
(iii) x  5 y  z  21 ; 2 x  y  3z  20 ; 3x  y  4 z  26 .

Tri-diagonal System of equations-Thomas Algorithm:

The system of equations of the form

a11x1  a12 x2  d1
a21x1  a22 x2  a23 x3  d2 ---------------------- (1)
a32 x2  a33 x3  a34 x4  d3
a43 x3  a44 x4  d4
is called a Tri-diagonal system in four variables.

System of equations (1) can be written as

 a11 a12 0 0   x1   d1 
   x  d 
 a21 a22 a23 0   2   2
 0 a32 a33 a34   x3   d3 
     
 0 0 a43 a44   x4   d 4 

It can also be written as

  b1 c1 0 0  x1   d1 
   x  d 
 a2 b2 c2 0  2    2  ----------------------- (2)
0 a3 b3 c3   x3   d3 
     
0 0 a4 b4   x4   d 4 

Here, b1  a11, b2  a22 , b3  a33 , b4  a44 c1  a12 , c2  a23 , c3  a34 , c4  0,

a1  0, a2  a21, a3  a32 , a4  a43 .

By Thomas Algorithm, we can reduce (2) as

 1 1 0 0  x1   1 
   x   
0 1 2 0  2    2  ---------------------- (3)
0 0 1 3   x3   3 
     
0 0 0 1  x4    4 
ci
where  1 
c1
and i  , i  2 , 3.
b1 bi  ai  i 1
d d a 
1  1 and  i  i i i 1 , i  2 , 3,4.
b1 bi  ai i 1

Solving (3), we get the solution of (1).

Note: The condition for this Algorithm is stable if bi  ai  ci for all i .

1. Solve the system of equations using Thomas Algorithm

x1  x2  3 ;
 x1  2 x2  x3  6 ;
3x2  2 x3  12
Solution: The given system of equations can be written as

 1 1 0   x1   3 
    
 1 2 1   x2    6  -------------------- (1)
 0 3 2   x  12 
  3   

Compare (1) with the following

 b1 c1 0   x1   d1 
    
 a2 b2 c2   x2    d 2  --------------------- (2)
0 b3   x3   d3 
 a3

here b1  1, b2  2, b3  2, c1  1, c2  1, c3  0, a1  0, a2  1, a3  3, d1  3, d2  6, d3  12 .

By the Thomas Algorithm, we have

  1  1 0   x1   1 
    
 0 1  2   x2     2  ------------------------ (3)
0 0 1  x    
  3   3 
c1 ci
where  1   1 and  i  , i  2.
b1 bi  ai i 1
1
so 2  .
3
d1 d a 
also, 1   3 and i  i i i 1 , i  2, 3 .
b1 bi  ai i 1
9 3
so  2   3 , 3   3 .
3 1
Therefore from (3), we have
1 1 0 
   x1   3 
0 1 1   x2    3  ------------------- (4)
 3     
 0 0 1   x3   3 
 
1
which gives x1  x2  3 , x2  x3  3 and x3  3 .
3
Solving the above equations, we get x1  1, x2  2, x3  3 is the solution of (1).

2. Solve the following system of equations using Thomas Algorithm

(i) 2 x1  2 x2  1; x1  2 x2  3x3  2; 2 x2  2 x3  4 x4  1; x3  x4  3 .
(ii) x1  x2  3; x1  2 x2  x3  7; 3x2  2 x3  12 .
Eigen Values and Eigen Vectors of Square Matrix
Let A be square matrix of order n and  a scalar (real or complex). If there is a non-zero
vector X of order n1 such that AX   X then X is called an eigen vector of A corresponding
to an eigen value  of A .

Iterative method to determining the largest eigen value (Power method):

Let X 1 be an initial eigen vector which is normalized by choosing its first or last coefficient as 1 .
Now, we form the product AX 1 and express it in the form AX1  1 X 2 where X 2 is also
normalized in the same manner. We now form the product AX 2 and express it in the form
AX 2  2 X 3 where X 3 is also normalized in the same manner.
Thus we have the sequence of equations
AX1  1 X 2 , AX 2  2 X 3 , AX 3  3 X 4 ,…..
Continue this iterative process until X n1 is very close to X n .
Therefore, we have AX n  n X n . Here n is an approximation for the largest eigen value of A
corresponding to the eigen vector X n of A .

Note: To find the numerically smallest eigen value of A , first obtain the largest eigen value  of
A . Let B  A   I and 1 be the numerically largest eigen value of B . Then the numerically
smallest value of A is   1 .
1. Determine the largest eigen value and the corresponding eigen vector of the matrix

1 2 3
 
A   0 4 2  and hence find the remaining eigenvalues of A .
0 0 7
 
0
 
Solution: Let X 0   0  be the initial eigen vector of A .
1
 

 1 2 3  0   3   0.43 
      
Then AX 0   0 4 2  0    2   7  0.29  .
 0 0 7  1   7   1 
      

 0.43   1 2 3  0.43   4.01   0.57 

        
Let X 1   0.29  . Then AX 1   0 4 2  0.29    0.84   7  0.12  .
 1   0 0 7  1   7   1 
        

 0.57   1 2 3  0.57   3.81  0.54 

        
Let X 2   0.12  . Then AX 2   0 4 2  0.12   1.52   7  0.22  .
 1   0 0 7  1   7   1 
        

 0.54   1 2 3  0.54   3.98   0.57 

        
Let X 3   0.22  . Then AX 3   0 4 2  0.22    1.12   7  0.16  .
 1   0 0 7  1   7   1 
        

 0.57   1 2 3  0.57   3.89   0.56 

        
Let X 4   0.16  . Then AX 4   0 4 2  0.16    1.36   7  0.19  .
 1   0 0 7  1   7   1 
        

 0.56   1 2 3  0.56   3.94   0.56 

        
Let X 5   0.19  . Then AX 5   0 4 2  0.19    1.24   7  0.18  .
 1   0 0 7  1   7   1 
        

 0.56 
 
Let X 6   0.18  . Since X 6 is very close to X 5 , the largest eigen value is   7 and the
 1 
 
 0.56 
 
corresponding eigen vector is  0.18  .
 1 
 
 1 2 3 7 0 0   6 2 3 
     
Now, let B  A   I   0 4 2    0 7 0    0 11 2  .
0 0 7 0 0 7   0 0 0 
  
1
Let Y0   0  be the initial eigenvector of B.
0
 
 6 2 3   1   6  1 1
Then BY0   0 11 2   0    0   6  0  . Let Y1   0  . Since Y1  Y0 , numerically largest
       
 0 0 0   0   0   0 0
    
eigenvalue of B is 1  6 .
Therefor numerically smallest eigen value of A is   1  7  6  1 .
Let 2 be the other eigenvalue of A .
We know that the sum of the eigenvalues of A is equal to trace of A and hence
7  1  2  trace of A which implies that 2  4 .
Therefore the eigenvalues of A are 4, 1, 7.

2. Determine the largest eigen value and the corresponding eigen vector of the matrix

 1 3 1
 
A 3 2 4 
 1 4 10 
 

0
 
Solution: Let X 0   0  be the initial eigen vector of A .
1
 
 1 3 1 0   1  0.1
      
Then AX 0   3 2 4  0    4   10  0.4  .
 1 4 10  1   10   1 
      

 0.1  1 3 1 0.1  0.1   0.009 

        
Let X 1   0.4  . Then AX 1   3 2 4  0.4    4.5   11.7  0.385  .
 1   1 4 10  1  11.7   1 
        

 0.009   1 3 1 0.009   0.164   0.014 

        
Let X 2   0.385  . Then AX 2   3 2 4  0.385    4.797   11.531 0.416  .
 1   1 4 10  1  11.531  1 
        

 0.014   1 3 1 0.014   0.262   0.022 

        
Let X 3   0.416  . Then AX 3   3 2 4  0.416    4.874   11.65  0.418  .
 1   1 4 10  1   11.65   1 
        
  0.022   1 3 1 0.022   0.276   0.024 
        
Let X 4   0.418  . Then AX 4   3 2 4  0.418    4.902   11.65  0.421  .
 1   1 4 10  1   11.65   1 
        

 0.024   1 3 1 0.024   0.287   0.025 

        
Let X 5   0.421  . Then AX 5   3 2 4  0.421    4.914   11.66  0.421  .
 1   1 4 10  1   11.66   1 
        

 0.025 
 
Let X 6   0.421  . Since X 6 is very close to X 5 , the largest eigenvalue is 11.66 and the
 1 
 
 0.025 
 
corresponding eigen vector is  0.421  .
 1 
 

1. Find the largest eigenvalues and corresponding eigen vectors of the following matrices
using Power method.

1 6 1  1 3 2 
1 2
(i) A  (ii) A   1 2 0  (iii) A   4 4 1 .
 
3 4 0 0 3 6 3 5 
   

Finding eigenvalues and eigenvectors using Jacobi’s Method

Let the eigenvalues of a real symmetric matrix A can be obtained by finding a real
orthogonal matrix P such that P-1AP=D , where D is a diagonal matrix.

 a ii a ij 
Let us consider A=  
 a ji a jj 
 
 cos -sin 
We proceed to find an orthogonal matrix of the form S=   such that
 sin cos 
S-1AS is a diagonal matrix.

 cos  sin    aii aij   cos   sin  

S-1AS=      
  sin  cos    a ji a jj   sin  cos  

 1 
 a ii cos   a jj sin   aij sin 2 a ij cos 2  (a jj  aii )sin 2 
2 2

= 2 

a ii sin   a jj cos   aij sin 2 
1
 a ji cos 2  2 (a jj  aii )sin 2
2 2

 
This matrix reduces to diagonal form if

aij cos 2  1 (a jj  aii )sin 2  0

2
2aij
i.e., tan 2 
aii  a jj
1  2a 
or,   tan 1  ij
 ------------------------ (1)
2  aii  a jj 

 if aij  0

If a ii  a jj , then  =  4
  if a  0

 4
ij

- 
Note: We normally choose  satisfying (1) in the range   .
4 4

 1 2 2
 
1. Find all eigenvalues and eigenvectors of the matrix A=  2 3 2  using Jacobi’s
 
 2 2 1 

method.

Solution: The largest off diagonal element is a13  2  a31 and also a11  1  a33 . Therefore  =
4
 cos  0  sin   1/ 2 0 1/ 2 
   
and hence the rotational matrix is S1   0 1 0  0 1 0 .
 sin  0 cos   1/ 2 
 0 1/ 2 
 1/ 2 0 1/ 2   1 2 2  1/ 2 0 1/ 2 
   
Therefore A1  S11 AS1   0 1 0  2 3 2  0 1 0 
   
 1/ 2 0 1/ 2   2 2 1  1/ 2 0 1/ 2 

3 2 0 
 
 2 3 0 
 0 0 1 
 

Now the largest off diagonal element is a12  2  a21 and also a11  3  a22 . Therefore  =
4
 cos   sin  0  1/ 2 1/ 2 0 
   
and hence the rotational matrix is S2   sin  cos  0   1/ 2 1/ 2 0  .
 0  
 0 1   0 0 1
 
 1/ 2 1/ 2 0   3 2 0  1/ 2 1/ 2 0 
   
Therefore A 2 =S2 1 A1S2   1/ 2 1/ 2 0   2 3 0  1/ 2 1/ 2 0 
   
 0 0 1   0 0 1  0 0 1
   
 5 0 0 
 
  0 1 0   D, a diagonal matrix.
 0 0 1
 

Hence the eigenvalues of the given matrix are 5, 1, -1 and the corresponding eigenvectors are
respectively the columns of the matrix
1/ 2 0 1/ 2  1/ 2 1/ 2 0  1/ 2 1/ 2 1/ 2 
    
S=S1S2   0 1 0  1/ 2 1/ 2 0   1/ 2 1/ 2 0 .
    
1/ 2 0 1/ 2   0 0 1  1/ 2 1/ 2 1/ 2 
  

2 0 1
 
2. Find all eigenvalues and eigenvectors of the matrix A=  0 2 0  using Jacobi’s
1 0 2
 
method.
 2 3 1
 
3. Find all eigenvalues and eigenvectors of the matrix A=  3 2 2  using Jacobi’s
 1 2 1
 
method.
2 1
4. Find all eigenvalues and eigenvectors of the matrix A=   using Jacobi’s method.
1 2
 1 2 2 
 
5. Find all eigenvalues and eigenvectors of the matrix A=  2 3 2  using Jacobi’s
 
 2 2 1 
 
method.