MAT2003 - Applied Numerical Methods

[Link] Jaison

School of Advanced Sciences and Languages,

VIT Bhopal,
Kotri Kalan, Ashta,
Bhopal, Madhya Pradesh - 466114

November 11, 2025

Gaussian elimination with pivoting

Example 2.0.1
Solve the system of equations

x1 − x2 + x3 = 2
−6x1 + x2 − x3 = 3
3x1 + x2 + x3 = 4

using Gaussian elimination method (GEM) with partial pivoting and backward
substitution.
Solution: Consider the augmented matrix of the given system of equations
 
1 −1 1 2
 −6 1 −1 3 
3 1 1 4

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 26 / 68

Step: 1 Find the largest absolute value in the first column and shift the row into
first row. Among {|1|, | − 6|, |3|}, R2 has the largest absolute value | − 6| = 6.
So, bring R2 into first row.
 
−6 1 −1 3
R2 ←→ R1 ⇒  1 −1 1 2 
3 1 1 4

Step: 2 To obtain echelon form, let us make first element of R2 into 0 using R1 .
 
  −6 1 −1 3
1
R2 + R1 −→ R2 ⇒  0 −5 6
5
6
5 
2
6
3 1 1 4

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 27 / 68

Step: 3 To obtain echelon form, let us make first element of R3 into 0 using R1 .
 
  −6 1 −1 3
1
R3 + R1 −→ R3 ⇒  0 −5 6
5
6
5 
2
2 3 1 11
0 2 2 2

Step: 4 Now, compare the absolute value of second element of R2 and R3 . (i.e.)
−5 3 rd
6 , 2 . Since absolute value of second element of 3 row is maximum.
Swap R3 and R2 . Then, we have,
 
  −6 1 −1 3
1 3 1 11 
R3 + R1 −→ R3 ⇒  0 2 2 2
2
0 −56
5
6
5
2

Step: 5 To obtain echelon form, let us make second element of R3 into 0 using
R2 (Since first element of R2 is zero).
 
  −6 1 −1 3
5
R3 + R2 −→ R3 ⇒  0 32 1
2
11 
2
9
0 0 10 9
50
9

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 28 / 68

Step: 6 Now, let us convert the augmented matrix into equations.

−6x1 + 1x2 − 1x3 =3 (4)

3 1 11
x2 + x3 = (5)
2 2 2
10 50
x3 = (6)
9 9
Step: 7 Using backward substitution to solve the equations.
From Eq.(6), we have,

10 50
x3 =
9 9
50 9
x3 = ×
9 10
x3 =5

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 29 / 68

Substitute x3 = 5 in Eq.(5), we have,
3 1 11
x2 + x3 =
2 2 2
3 1 11
x2 + (5) =
2 2 2
3 11 5
x2 = − = 3
2 2 2
2
x2 =3
3
x2 =2
Substitute x2 = 2 and x3 = 5 in Eq.(4), we have,
−6x1 + x2 − x3 =3
−6x1 + (2) − (5) =3
−6x1 =3 + 3 = 6
x1 = − 1
So, the roots are x1 = −1, x2 = 2 and x3 = 5.
[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 30 / 68
Example 2.0.2
Let us use the GEM with partial pivoting to solve the following system:

2x1 + x2 + x3 = 5
4x1 − 6x2 = −2
−2x1 + 7x2 + 2x3 = 9.

 
2 1 1 5
 4 −6 0 −2 
−2 7 2 9
 
4 −6 0 −2
R1 ←→ R2  2 1 1 5 
−2 7 2 9

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 31 / 68

  
4 −6 0 −2
R2 → R2 − (1/2)R1 , R3 → R3 + (1/2)R1  0 4 1 6 
0 4 2 8

 
4 −6 0 −2
R3 ⇒ R3 − R2  0 4 1 6 
0 0 1 2
Thus x3 = 2.
Then 4x2 + x3 = 6 gives x2 = 1, and 4x1 − 6x2 = −2 gives x1 = 1.
Hence x1 = 1, x2 = 1, x3 = 2 is the (unique) solution of the given linear
system.

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 32 / 68

Practice problem

Example 2.0.3
Solve the system equations

x1 + x2 + x3 =3
4x1 + 3x2 + 4x3 =8
9x1 + 3x2 + 4x3 =7

using Gauss elimination method with partial pivoting and backward substitu-
tion method.

Solution
R1 ←→ R1
R2 → R2 − 4R3 , R3 → R1 − 9R3
R3 → −6R2 + R3
x1 = − 15 , x2 = 4 and x3 = − 54
[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 33 / 68
Gauss-Seidel method

Definition 2.1.1 (Diagonally Dominant Matrix)

A square matrix is called diagonally dominant if
n
X
|Ai,i | ≥ |Aij |
j=1, j6=i

A is called strictly diagonally dominant if

n
X
|Ai,i | > |Aij |
j=1, j6=i

for all i.

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 34 / 68

Example 2.1.2
Find the solution to the following system of equations using the Gauss-Seidel
method.

5x1 − x2 + 2x3 = 12 (7)

3x1 + 8x2 − 2x3 = −25 (8)
x1 + x2 + 4x3 = 6 (9)

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 35 / 68

The coefficient matrix
   
5 −1 2 a11 a12 a13
[A] = 3 8 −2 = a21 a22 a23 
1 1 4 a31 a32 a33

is diagonally dominant as

|a11 | = 5 5 ≥ |a12 | + |a13 | = | − 1| + |2| = 3

|a22 | = 8 8 ≥ |a21 | + |a23 | = |3| + | − 2| = 5
|a33 | = 4 4 ≥ |a31 | + |a32 | = |1| + |1| = 2

and the inequality is strictly greater than for at least one row. Hence, the solu-
tion should converge using the Gauss-Seidel method.

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 36 / 68

Since, no initial values are given, let us assume x1 = 0, x2 = 0 and x = 0 arbi-
trarily. Find the x1 , x2 and x3 values form Eqs (7), (8) and (9) correspondingly.

12 + x2 − 2x3
x1 = (10)
5
−25 − 3x1 + 2x3
x2 = (11)
8
6 − x1 − x2
x3 = (12)
4

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 37 / 68

I st Iteration:
Let us assume x1 = 0, x2 = 0 and x3 = 0 in Eq (10), (11) and (12), Then form
Eq.(10) we have

12 + x2 − 2x3 12 + (0) − 2(0) 12

x1 = = = = 2.4
5 5 5
Now the recent x1 = 2.4. So, substitute x1 = 2.4, x2 = 0 and x3 = 0 in
Eq.(11), then we have,

−25 − 3x1 + 2x3 −25 − 3(2.4) + 2(0)

x2 = = = −4.025
8 8
Now substitute the recent value of x1 = 2.4, x2 = −4.025 and x3 = 0 in
Eq.(12) we have

6 − x1 − x2 6 − (2.4) − (−4.025)
x3 = = = 1.90625
4 4

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 38 / 68

2nd Iteration:
Now the recent value of x1 = 2.4, x2 = −4.025 and x3 = 1.90625. Substitute
these values in Eq.(10), we get

12 + x2 − 2x3 12 + (−4.025) − 2(1.90625)

x1 = = = 0.8325.
5 5
Substitute the recent value of x1 = 0.8325, x2 = −4.025 and x3 = 1.90625 in
Eq.(11), we get

−25 − 3x1 + 2x3 −25 − 3(0.8325) + 2(1.90625)

x2 = = = −2.960625.
8 8
Substitute the recent values of x1 = 0.8325, x2 = −2.960625 and x3 =
1.90625 in Eq.(12), we get

6 − x1 − x2 6 − (0.835) − (−2.960625)
x3 = = = 2.03203125
4 4

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 39 / 68

3nd Iteration:
Now the recent value of x1 = 0.8325, x2 = −2.960625 and x3 = 2.03203125.
Substitute these values in Eq.(10), we get

12 + x2 − 2x3 12 + (−2.960625) − 2(2.03203125)

x1 = = = 0.9950625.
5 5
Substitute the recent value of x1 = 0.9950625, x2 = −2.960625 and x3 =
2.03203125 in Eq.(11), we get

−25 − 3x1 + 2x3 −25 − 3(0.9950625) + 2(2.03203125)

x2 = = = −2.990140
8 8
Substitute the recent values of x1 = 0.9950625, we get x2 = −2.990140625
and x3 = 2.03203125 in Eq.(12)

6 − x1 − x2 6 − (0.9950625) − (−2.990140625)
x3 = = = 1.99876953125
4 4

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 40 / 68

Three iteration values are tabulated below.
x1 x2 x3
I st iteration 2.4 -4.025 1.90625
II nd iteration 0.8325 -2.960625 2.03203125
III rd iteration 0.9950625 -2.9901406525 1.9987953125

From the table one can conclude the value of x1 = 1, x2 = −3 and x3 = 2.

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 41 / 68

Example 2.1.3
Find the solution to the following system of equations using the Gauss-Seidel
method.

12x1 + 3x2 − 5x3 = 1

x1 + 5x2 + 3x3 = 28
3x1 + 7x2 + 13x3 = 76.
   
x1 1
Use x2 = 0 as the initial guess and conduct three iterations.
  
x3 1

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 42 / 68

The coefficient matrix
   
12 3 −5 a11 a12 a13
[A] =  1 5 3  = a21 a22 a23 
3 7 13 a31 a32 a33

is diagonally dominant as

|a11 | = 12 12 ≥ |a12 | + |a13 | = |3| + | − 5| = 8

|a22 | = 5 5 ≥ |a21 | + |a23 | = |1| + |3| = 4
|a33 | = 13 13 ≥ |a31 | + |a32 | = |3| + |7| = 10

and the inequality is strictly greater than for at least one row. Hence, the solu-
tion should converge using the Gauss-Seidel method.

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 43 / 68

Rewriting the equations, we get
1 − 3x2 + 5x3
x1 =
12
28 − x1 − 3x3
x2 =
5
76 − 3x1 − 7x2
x3 = .
13
   
x1 1
Assuming an initial guess of x2  = 0 .
x3 1

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 44 / 68

Iteration I

1 − 3x2 + 5x3 1 − 3(0) + 5(1)

x1 = = = 0.50000
12 12
28 − x1 − 3x3 28 − (0.50000) − 3(1)
x2 = = = 4.9000
5 5
76 − 3x1 − 7x2 76 − 3(0.50000) − 7(4.9000)
x3 = = = 3.0923
13 13

Iteration II

1 − 3x2 + 5x3 1 − 3(4.9000) + 5(3.0923)

x1 = = = 0.14679
12 12
28 − x1 − 3x3 28 − (0.14679) − 3(3.0923)
x2 = = = 3.7153
5 5
76 − 3x1 − 7x2 76 − 3(0.14679) − 7(3.7153)
x3 = = = 3.8118
13 13

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 45 / 68

Iteration III

1 − 3x2 + 5x3 1 − 3(3.7153) + 5(3.8118)

x1 = = = 0.742758
12 12
28 − x1 − 3x3 28 − (0.742758) − 3(3.8118)
x2 = = = 3.164368
5 5
76 − 3x1 − 7x2 76 − 3(0.742758) − 7(3.164368)
x3 = = = 3.9708
13 13

Iteration x1 x2 x3
1 0.50000 4.9000 3.0923
2 0.14679 3.7153 3.8118
3 0.74275 3.1644 3.9708
4 0.94675 3.0281 3.9971

From the table we can approximate the solution x1 = 1, x2 = 3 and x3 = 4.

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 46 / 68

Example 2.1.4
Given the system of equations

3x1 + 7x2 + 13x3 = 76

x1 + 5x2 + 3x3 = 28
12x1 + 3x2 − 5x3 = 1
   
x1 1
find the solution using the Gauss-Seidel method. Use x2 = 0 as the
  
x3 1
initial guess.

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 47 / 68

Rewriting the equations, we get
76 − 7x2 − 13x3
x1 =
3
28 − x1 − 3x3
x2 =
5
1 − 12x1 − 3x2
x3 =
−5
   
x1 1
Assuming an initial guess of x2  = 0 the next six iterative values are
x3 1
given in the table below.

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 48 / 68

 Iteration x1 x2 x3
1 21.000 0.80000 50.680
2 –196.15 14.421 –462.30
3 1995.0 –116.02 4718.1
4 –20149 1204.6 –47636

You can see that this solution is not converging and the coefficient matrix is
not diagonally dominant. The coefficient matrix
 
3 7 13
[A] =  1 5 3 
12 3 −5

is not diagonally dominant as

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 49 / 68

 |a11 | = |3| = 3  |a12 | + |a13 | = |7| + |13| = 20
Hence, the Gauss-Seidel method may or may not converge. However, it is the
same set of equations as the previous example and that converged. The only
difference is that we exchanged first and the third equation with each other and
that made the coefficient matrix not diagonally dominant.
Therefore, it is possible that a system of equations can be made diagonally
dominant if one exchanges the equations with each other. However, it is not
possible for all cases. For example, the following set of equations

x1 + x2 + x3 = 3
2x2 + 3x2 + 4x3 = 9
x1 + 7x2 + x3 = 9

cannot be rewritten to make the coefficient matrix diagonally dominant.

[Link] Jaison MAT2003 - Applied Numerical Methods November 11, 2025 50 / 68