SOLUTION OF SYSTEM OF LINEAR EQUATIONS
Direct methods
1. Gauss elimination method
2. Gauss Jordan method
3. Factorization Method
4. Matrix inversion method
Etc.
Indirect method or Iterative methods
1. Gauss Jacobi iterative method
2. Gauss Siedel iterative method
Gauss elimination method
Let us consider the systems
a1x +b1y+c1z = d1
a2x+b2y +c2z = d2
a3x +b3y +c3z = d3
The above system of equations can be written as
AX = B
a 1 b1 c 1 x d1
Where A = a 2 b2 c 2 , X = y , B = d2
a 3 b3 c 3 z d3
The augmented or partitioned matrix
a 1 b1 c 1 d 1
(A, B) a 2 b2 c 2 d 2
a 3 b3 c 3 d 3
a 1 b1 c1 d 1
If (A,B) 0 b2 ' c2 ' d 2 '
0 0 c3 ' d 3 '
Then we can write
a1x +b1y+c1z = d1
b2’y + c2’z = d2’
c3’z = d3’
For example
Solve the system of equations:
x +2y +3z =14, 2x + 5y +2z = 18, 3x +y +5z = 20 by Gauss elimination method
Solution:
The given system of equations can be written as
AX = B
1 2 3 x 14
Where, A = 2 5 2 , X = y , B = 18
3 1 5 z 20
The augmented or partitioned matrix
1 2 3 14
(A, B) 2 5 2 18
3 1 5 20
By R2→R2 – 2R1 and R3 →R3 – 3R1
1 2 3 14
(A, B) 0 1 −4 −10
0 −5 −4 −22
By R3 →R3 + 5R2
1 2 3 14
(A, B) 0 1 −4 −10
0 0 −24 −72
x +2y + 3z = 14, x = 14-2X2 -3 X 3 = 1
y -4z = -10, y=2
-24z = -72, z =3
Gauss Jordan method
Let us consider the systems
a1x +b1y+c1z =d1
a2x+b2y +c2z = d2
a3x +b3y +c3z = d3
The above system of equations can be written as
AX = B
a 1 b1 c 1 x d1
Where A = a 2 b2 c 2 , X = y , B = d2
a 3 b3 c 3 z d3
The augmented matrix
a 1 b1 c 1 d 1
(A, B) a 2 b2 c 2 d 2
a 3 b3 c 3 d 3
1 0 0 d1 '
If (A,B) 0 1 0 d2 '
0 0 1 d3 '
Then we can write
x = d1’, y = d2’, z = d3’
For example
Solve the system of equations:
x +2y +3z =14, 2x + 5y +2z = 18, 3x +y +5z = 20 by Gauss jordan method
Solution:
The given system of equations can be written as
AX = B
1 2 3 x 14
Where, A = 2 5 2 , X = y , B = 18
3 1 5 z 20
The augmented or partitioned matrix
1 2 3 14
(A, B) 2 5 2 18
3 1 5 20
By R2→R2 – 2R1 and R3 →R3 – 3R1
1 2 3 14
(A, B) 0 1 −4 −10
0 −5 −4 −22
By R3 →R3 + 5R2
1 2 3 14
(A, B) 0 1 −4 −10
0 0 −24 −72
By R1→R1 – 2R2
1 0 11 34
(A, B) 0 1 −4 −10
0 0 −24 −72
By R3 →(-1/24)R3
1 0 11 34
(A, B) 0 1 −4 −10
0 0 1 3
By R1→R1 – 11R3 and R2 →R2 + 4R3
1 0 0 1
(A, B) 0 1 0 2
0 0 1 3
Therefore x =1, y =2, z =3
Factorization Method or decomposition method
Dolittle’s factorization method
Let us consider the systems
a1x +b1y+c1z =d1
a2x+b2y +c2z = d2
a3x +b3y +c3z = d3
The above system of equations can be written as
AX = B
a 1 b1 c 1 x d1
Where A = a 2 b2 c 2 , X = y , B = d2
a 3 b3 c 3 z d3
In this method, the coefficient matrix A is factorized into unit lower triangular and upper triangular
matrix.
i.e. A = LU
a 1 b1 c 1 1 0 0 u11 u12 u13
a 2 b2 c 2 = 21 1 0 0 u22 u23
l
a 3 b3 c 3 l 31 l 32 1 0 0 u33
Multiplying matrix L and U and equating with matrix A, we get matrix L and U
We have
AX = B
LUX = B
Let UX = Y ………(i)
Then LY = B…….(ii)
Solving equation (ii) for Y
Y = ..
Now solving equation (i) for X
X = ...
For example
Solve the system of equations:
x +2y +3z =14, 2x + 5y +2z = 18, 3x +y +5z = 20 by Factorization method
Solution:
The given system of equations can be written as
AX = B
1 2 3 x 14
Where, A = 2 5 2 , X = y , B = 18
3 1 5 z 20
Now factorizing the coefficient matrix A is into unit lower triangular and upper triangular matrix.
i.e. A = LU
1 2 3 1 0 0 u11 u12 u13
2 5 2 =l 21 1 0 0 u22 u23
3 1 5 l 31 l 32 1 0 0 u33
1 2 3 u11 u12 u13
2 5 2 = l 31 u13 +l 32 u23 +u33 ¿
l 21 u11 l 21 u12+¿ u ¿ l 21 u 13+¿u ¿ l 31 u11 ¿
3 1 5 22 23
u11 =1, u12=2 , u13 = 3, l 21 u11 = 2, l 21 =2/1 =2, l 21 u12+¿ u ¿ = 5, u22 = 5-2X2 =1, l 21 u13+ ¿u ¿ = 2, u23 = 2-
22 23
2X3 = - 4, l 31 u11 = 3, l 31= 3/1 =3, l 31 u12 +l 32 u22 =1, l 32 = (1-3X2)/1 = -5, l 31 u13 +l 32 u23 +u33 =5, u33 = 5 – 3X3
– (-5)X (-4) = -24
Now
AX = B
LUX= B
Let UX =Y …….(i)
Then LY= B ……(ii)
Solving equation (ii) for Y
1 0 0 y 1 14
l 21 1 0 y 2 = 18
l 31 l 32 1 y 3 20
1 0 0 y 1 14
2 1 0 y 2 = 18
3 −5 1 y 3 20
y1 =14
2y1 + y2 = 18, y2 = 18 -2 X 14 = -10
3y1 – 5y2+ y3 = 20 , y3 = 20 -3X14 + 5X -10 = -72
Now solving equation (i) for X
1 2 3 x 14
0 1 −4 y = −10
0 0 −24 z −72
x +2y +3z = 14, x =1
y -4z = -10, y=2
-24z = -72, z=3
Note:
(i) If the coefficient matrix A is factorized into unit lower triangular matrix and upper triangular matrix
then it is called Dollitle’s factorization.
(ii) If the coefficient matrix A is factorized into lower triangular matrix and unit upper triangular matrix
then it is called Crout’s factorization.
Crout’s factorization method
Let us consider the systems
a1x +b1y+c1z =d1
a2x+b2y +c2z = d2
a3x +b3y +c3z = d3
The above system of equations can be written as
AX = B
a 1 b1 c 1 x d1
Where A = a 2 b2 c 2 , X = y , B = d2
a 3 b3 c 3 z d3
In this method, the coefficient matrix A is factorized into lower triangular and unit upper triangular
matrix.
A = LU
a 1 b1 c 1 l 11 0 0 1 u12 u13
a 2 b2 c 2 =l 21 l 22 0 0 1 u23
a 3 b3 c 3 l 31 l 32 l 33 0 0 1
For example
Solve the system of equations:
x +2y +3z =14, 2x + 5y +2z = 18, 3x +y +5z = 20 by Crout’s factorization method
Matrix inversion method
Let us consider the systems
a1x +b1y+c1z =d1
a2x+b2y +c2z = d2
a3x +b3y +c3z = d3
The above system of equations can be written as
AX = B
a 1 b1 c 1 x d1
Where A = a 2 b2 c 2 , X = y , B = d2
a 3 b3 c 3 z d3
We know that
adj. A
X = A-1B, where, A-1 = , | A| ≠ 0, adj.(A) = transpose of matrix of cofactors of A
|A|
For example
Solve the system of equations:
x +2y +3z =14, 2x + 5y +2z = 18, 3x +y +5z = 20 by matrix inversion method
Solution
The given system of equations can be written as
AX = B
1 2 3 x 14
Where, A = 2 5 2 , X = y , B = 18
3 1 5 z 20
| A| = 1(25-2) – 2(10 – 6) + 3(2 – 15) = 23 – 8 – 39 = -24
C 11 C12 C 13 M 11 −M 12 M 13 23 −4 −13
Matrix of cofactors = C 21 C22 C 23 = −M 21 M 22 −M 23 = −7 −4 5
C 31 C32 C 33 M 31 −M 32 M 33 11 4 1
23 −7 11
Adj.A =transpose of matrix of cofactors of A = −4 −4 4
−13 5 1
23 −7 11
adj. A 1
A-1 = = −4 −4 4
|A| −24 −13 5 1
−23 7 −11
24 24 24
1 1 −1
=
6 6 6
13 −5 −1
24 24 24
−23 7 −11
24 24 24
14
1 1 −1
X = A-1B = 18 =
6 6 6
20
13 −5 −1
24 24 24
Indirect method or Iterative methods
1. Gauss Jacobi iterative method
2. Gauss Siedel iterative method
Gauss Jacobi iterative method
Let us consider the system
a1x +b1y+c1z =d1 ……….(i)
a2x+b2y +c2z = d2 ……..(ii)
a3x +b3y +c3z = d3 …….(iii)
Iterative method is more suitable when the main diagonal elements are dominant.
|a 1| ≥|b1| + |c 1|
|b 2| ≥|a2| + |c 2|
|c 3| ≥|a3| + |b 3|
From equation (i)
x = (d1 - b1y- c1z)/ a1 ……(iv)
From equation (ii)
y = (d2 – a2x- c2z)/ b2 ……(v)
From equation (iii)
z = (d3 – a3x- b3y)/ c3 …..(vi)
First iteration [ let x=y=z=0]
x = d1 / a1 =a
y = d2 / b2 =b rough values
z = d3 / c3 =c
Second iteration
x = (d1 - b1b- c1c)/ a1 = d ≠a
y = (d2 – a2a- c2c)/ b2 = e ≠ b
z = (d3 – a3a- b3b)/ c3 = f ≠ c
Third iteration
x = (d1 - b1e- c1f)/ a1 = g ≠ d
y = (d2 – a2d- c2f)/ b2 = h ≠ e
z = (d3 – a3d- b3e)/ c3 = i ≠ f
The process will be continued until getting the same result in last two iterations
Gauss Sidel iterative method
Let us consider the system
a1x +b1y+c1z =d1 ……….(i)
a2x+b2y +c2z = d2 ……..(ii)
a3x +b3y +c3z = d3 …….(iii)
From equation (i)
x = (d1 - b1y- c1z)/ a1 ……(iv)
From equation (ii)
y = (d2 – a2x- c2z)/ b2 ……(v)
From equation (iii)
z = (d3 – a3x- b3y)/ c3 …..(vi)
First iteration [ y=z=0]
x = d1 / a1 =a
y = (d2 – a2a)/ b2 =b rough values
z =(d3 – a3a - b3b)/ c3 =c
Second iteration
x = (d1 - b1b- c1c)/ a1 = d ≠ a
y = (d2 – a2d- c2c)/ b2 = e ≠ b
z = (d3 – a3d- b3e)/ c3 = f ≠ c
Third iteration
x = (d1 - b1e- c1f)/ a1 = g ≠ d
y = (d2 – a2g - c2f)/ b2 = h ≠ e
z = (d3 – a3g- b3h)/ c3 = i ≠ f
The process will be continued until getting the same result in last two iterations
For example
Solve the following equations by (a) Gauss Jacobi and (ii) Gauss Siedel iterative method:
2x-7y-10z = -17
5x + y + 3z = 14
x + 10y + 9z = 7
Assume the suitable initial values.
Solution
Rewriting the given equations
5x + y + 3z = 14 …..(i)
x + 10y + 9z = 7……(ii)
2x-7y-10z = -17….(iii)
From equation (i)
x = ( 14-y - 3z)/5…….(iv)
From equation (ii)
y = ( 7-x - 9z)/10 ………(v)
From equation (iii)
z = ( -17- 2x + 7y)/-10
z = ( 17+ 2x - 7y)/10 …..(vi)
(a) Gauss Jacobi iterative method
First iteration, let [ x = y =z = 0]
x = 2.8
y =0.7
z = 1.7
Second iteration
x = 1.64
y = -1.11
z = 1.77
Third iteration
x = 1.96
y =-1.057
z = 2.805
Fourth iteration
x=
y=
z=
Fifth iteration
x=
y=
z=
Sixth iteration
x=
y=
z=
Seventh iteration
x=
y=
z=
(b) Gauss Sidel iterative method
First iteration, let [y =z = 0]
x = 2.8
y =0.42
z = 1.966
Second iteration
x = 0.7682
y =-1.146
z = 2.655
Third iteration
x=
y=
z=
Fourth iteration
x=
y=
z=
Fifth iteration
x=
y=
z=
Sixth iteration
x=
y=
z=
Seventh iteration
x=
y=
z=
Exercises
1. Solve the following system of equations by Gauss elimination method, Gauss Jordan and
factorization method.
4x + y + 2z = 4
3x + 5y + z = 7
x + y + 3z= 3
2. Solve the following system of equations by Gauss Jacobi and Gauss Sidel iterative method.
10x1 -x2 +2x3 = 4
x1 +10x2- x3 = 3
2x1 +3x2+20x3 =7
Ans[ 0.375, 0.289,0.269]
