Numerical Technique (MA-201)

Lecture Notes-14

by
Prof. Santwana Mukhopadhyay

Department of Mathematical Sciences

IIT(BHU), Varanasi

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 1 / 19
 Contents

1 Preliminaries

2 Direct Methods

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 2 / 19
 System of equations

Definition:
Consider a system of m linear equations in n (unknown) variables:

a11 x1 + a12 x2 + .... + a1n xn = b1

a21 x1 + a22 x2 + .... + a2n xn = b2
..................................................
..................................................
am1 x1 + am2 x2 + .... + amn xn = bm (1.1)

where aij and bj are real or complex numbers.

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 3 / 19
 System of equations contd...

Write
     
a11 a12 ..... a1n b1 x1
 a21 a22 ..... a2n   b2   x2 
A= , b =  , x = 
     
... ... ... ... ... ...

     
am1 am2 ... amn bm xn
Then, A is called the coefficient matrix of the system (1.1). We also
write A = (aij ).
In matrix form, the system (1.1) is written as
Ax = b (1.2)
If b = 0, then the system (1.2) would be called a homogeneous
system. So,
Ax = 0 (1.3)
is a homogeneous system of linear equation.
Then, x = 0 is a solution of the homogeneous system (1.3), to be
called the trivial solution.
Prof. S. Mukhopadhyay (Department of Mathematical
Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 4 / 19
 System of equations contd...

Corresponding to system (1.1), define the augmented matrix

 
a11 a12 ..... a1n b1
 a21 a22 ..... a2n b2 
[A|b] =  (1.4)
 
... ... ... ... ...

 
am1 am2 ... amn bm

In deed, the system (1.1) and the augmented matrix (1.4) has the
same information/data. The row operations performed on system
(1.1), can be performed on the augmented matrix (1.4), instead.

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 5 / 19
 Direct methods

Direct Methods based on elimentary row operations:

Gauss elimination method

Gauss-Jordan method
Gauss elimination method:
Let us introduce the Gaussian elimination method for n = 3. The method for a general
n × n system is similar.
a11 x1 + a12 x2 + a13 x3 = b1 (2.1)
a21 x1 + a22 x2 + a23 x3 = b2 (2.2)
a31 x1 + a32 x2 + a33 x3 = b3 (2.3)
The solution of the above system of equations can be obtained by Gauss elimination
methd in the following steps:

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 6 / 19
 Gauss elimination method contd...

Example:
Use Gaussian elimination with partial pivoting to solve the following system

0.143x1 + 0.357x2 + 2.01x3 = − 5.173

−1.31x1 + 0.911 + 1.99x3 = − 5.458
11.2x1 − 4.30x2 − 0.605x3 =4.415

After each intermediate calculation, round the result to three significant

digits.

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 7 / 19
 Gauss elimination method contd...
Solution:

The augmented matrix for the system Ax = b is

 
0.143 0.357 2.01 −5.17
 −1.31 0.911 1.99 −5.46 
[11.2] −4.30 −0.605 4.42
In the left column 11.2 is the pivot because it is the entry that has the largest
absolute value. Therefore we interchange the first and third rows and apply
elementary row operations as follows (interchange the first and third rows)
 
[11.2] −4.30 −0.605 4.42
 −1.31 0.911 1.99 −5.46 
0.143 0.357 2.01 5.17
Dividing the first row by 11.2 produces a new first row
 
1.00 −0.384 −0.054 0.395
 −1.31 0.911 1.99 −5.46 
0.143 0.357 2.01 −5.17
Prof. S. Mukhopadhyay (Department of Mathematical
Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 8 / 19
 Gauss elimination method contd...

Solution contd...

Adding 1.31 times the first row to the second row produces a new second row
1.00 −0.384 −0.0540 0.395
!
0.00 0.408 1.92 −4.94
0.143 0.357 2.01 −5.17
Adding – 0.143 times the first row to the third row produces a new third row
1.00 −0.384 −0.0540 0.395
!
0.00 0.408 1.99 −4.94
0.00 0.412 2.02 −5.23
This completes the first step. We consider the submatrix formed by deleting the first
row and first column. In this matrix the pivot is 0.412, which means that the second and
third rows should be interchanged (interchange the second and third rows)
1.00 −0.384 −0.054 0.395
!
0.00 [0.412] 2.02 −5.23
0.00 0.408 1.92 −4.94

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 9 / 19
 Gauss elimination method contd...

Solution contd...

Dividing the second row by 0.412 produces a new second row

1.00 −0.384 −0.054 0.395

!
0.00 1.00 4.90 −12.7
0.00 0.408 1.92 −4.94

Adding –0.408 times the second row to the third row produces a new third row

1.00 −0.384 −0.054 0.395

!
0.00 1.00 4.90 −12.7
0.00 0.00 −0.080 0.240

This completes the second step. By using back substitution, the solution can be
obtained as
x3 = −3.00, x2 = 2.00, x1 = 1.00
which agrees with the exact solution of x1 = 1, x2 = 2 and x3 = −3 when rounded to
three significant digits.

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 10 / 19
 Direct methods contd...

Gauss-Jordan elimination method:

Gauss-Jordan Elimination is an algorithm that can be used to solve
systems of linear equations and to find the inverse of any invertible matrix.

Steps for Gauss-Jordan elimination are in next slide.

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 11 / 19
 Gauss-Jordan elimination method contd...

Steps for Gauss-Jordan elimination:

1 Swap the rows so that all rows with all zero entries are on the bottom.
2 Swap the rows so that the row with the largest, leftmost nonzero
entry is on top.
3 Multiply the top row by a scalar so that top row’s leading entry
becomes 1.
4 Add/subtract multiples of the top row to the other rows so that all
other entries in the column containing the top row’s leading entry are
all zero.
5 Repeat steps 2-4 for the next leftmost nonzero entry until all the
leading entries are 1.
6 Swap the rows so that the leading entry of each nonzero row is to the
right of the leading entry of the row above it.
Prof. S. Mukhopadhyay (Department of Mathematical
Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 12 / 19
 Gauss-Jordan elimination method contd...

To obtain the inverse of a n × n matrix A:

Create the partitioned matrix (A|I) , where I is the identity matrix.

Perform Gauss-Jordan Elimination on the partitioned matrix with the
objective of converting the first part of the matrix to reduced-row
echelon form.
If
 done correctly, the resulting partitioned matrix will take the form
I|A−1 .

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 13 / 19
 Gauss-Jordan elimination method contd...

Example 1:
Find the inverse of the matrix
 
2 1 1
A= 3 2 1 
 
2 1 2

by Gauss-Jordan method.

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 14 / 19
 Gauss-Jordan elimination method contd...

Solution:

Applying Gauss-Jordan method, we get

2 1 1 1 0 0 1 1/2 1/2 1/2 0 0

! !
R1 → 21 R1
[A|I] = 3 2 1 0 1 0 −−−−−→ 3 2 1 0 1 0
2 1 2 0 0 1 2 1 2 0 0 1

1 1/2 1/2 1/2 0 0

R2 →R2 −3R1
!
R3 →R3 −2R1
−−−−−−−−→ 3 1/2 −1/2 −3/2 1 0
0 0 1 −1 0 1
1 1/2 1/2 1/2 0 0
!
R2 →2R2
−−−−−→ 0 1 −1 −3 2 0
0 0 1 −1 0 1
1 0 1 2 −1 0
!
R1 →R1 − 12 R2
−−−−−−−−− → 0 1 −1 −3 2 0
0 0 1 −1 0 1

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 15 / 19
 Gauss-Jordan elimination method contd...

Solution contd...

 
1
R1 →R1 −R3 0 0 3 −1 −1
R2 →R2 +R3
−−−−−−−→  0 1 0 −4 2 1 
0 0 1 −1 0 1
 
3 −1 −1
So, A−1 =  −4 2 1 .
−1 0 1

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 16 / 19
 Gauss-Jordan elimination method contd...

Example 2:
Find the inverse of the matrix
 
1 2 1
A =  2 3 −1 
 
2 −1 3

by Gauss-Jordan 
method. 
−8 7 5
Hint: A−1 = 161 
 8 −1 −3 .

8 −5 1

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 17 / 19
 Gauss-Jordan elimination method contd...

Example 3:
Solve the system by Gauss-elimination method and Gauss-Jordan method:

x1 + x2 + x3 = 1
4x1 + 3x2 − x3 = 4
3x1 + 5x2 + 3x3 = 6

Answer: Do by yourself

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 18 / 19
 Iteration Methods

Next class
****************

Prof. S. Mukhopadhyay (Department of Mathematical

Numerical
SciencesTechnique
IIT(BHU),(MA-201)
Varanasi) 19 / 19