Numerical Methods: Module-II

January 27, 2026

1 Linear System of Equations

Consider the system of m equations in n unknowns:

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

a21 x1 + a22 x2 + · · · + a2n xn = b2
..
.
T

am1 x1 + am2 x2 + · · · + amn xn = bm

AF
DR

Its matrix form is Ax = b, where A and b are

   
a11 a12 · · · a1n b1
   
 a21 a22 · · · a2n 
 , b =  b2 
 
A=  ... .. . . . ..   ... 
 . .   
am1 am2 · · · amn bm

The augmented matrix is

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

1
1.1 Consistent

The system Ax = b is said to be consistent if

ρ(A) = ρ(A|b)

where ρ(A) denotes the rank of matrix A.

1. Unique solution if det(A) 6= 0.

2. Infinitely many solutions if det(A) = 0.

1.2 Inconsistent:

if ρ(A) 6= ρ(A|b) (no solution).

2 Solution of Linear Systems

T
AF

2.1 Direct Methods

DR

• Matrix Inversion

• Gauss Elimination

• Gauss Jordan

• LU Decomposition

2.2 Iterative Methods

• Gauss Jacobi

• Gauss Seidel

2
3 Matrix Inversion Method

The system in the matrix form can be written as

Ax = b

where
     
a11 a12 · · · a1n x1 b1
     
 a21 a22 · · · a2n   x2   b2 
A=
 ... .. . . . ..  ,
 x=
 ...  ,
 b=
 ... 

 . .     
an1 an2 · · · ann xn bn

6 0, so that A−1 exists.

Let A be a nonsingular matrix, i.e., |A| =

A−1 Ax = A−1 b ⇒ x = A−1 b

As A−1 A = I = AA−1 , we have Ix = x.

T
AF
DR

3.1 Solve by the matrix inversion method

3x + y + 2z = 3
2x − 3y − z = −3
x + 2y + z = 4
Solution:  
3 1 2
 
A=
2 −3 −1

1 2 1

|A| = 8 6= 0 ⇒ A is invertible.

 
−1 3 5
1
A−1

=  −3 1 7 
8  
7 −5 −11

3
     
−1 3 5 8 1
1
x = A−1 b = 
     
−3 1 7  −3 =  2 
8    
7 −5 −11 4 −1
Thus, x = 1, y = 2, z = −1.
Drawback: Unsuitable for solving large systems of equations. (Hard to
compute A−1 for large systems.)

4 Gauss Elimination Method

The system Ax = b is reduced to U x = b0 and x is computed using

backward substitution. That is,
row operations
(A|b) −−−−−−−−→ (U |c)
T
AF

4.1 Solve by Gauss elimination method

DR

2x + y + z = 10
3x + 2y + 3z = 18
x + 4y + 9z = 16
Solution: The augmented matrix is
 
2 1 1 10
 
A=  3 2 3 18 

1 4 9 16

Applying row operations: R2 → 2R2 − 23 R1 , R3 → 2R3 − R1 , we

get
 
2 1 1 10
 
0 1 3 6 
 
0 7 17 22

4
Applying row operation: R3 → R3 − 7R2 , we have
 
2 1 1 10
 
0 1 3 6 
 
0 0 −4 −20
i.e.
2x + y + z = 10, y + 3z = 6, −4z = −20

By back substitution method, we have z = 5; y + 3(5) = 6 ⇒ y = −9

and finally, 2x − 9 + 5 = 10 ⇒ 2x = 14 ⇒ x = 7.
Hence, the solution is: x = 7, y = −9, z=5

4.2 Solve by Gauss elimination method

0.0002x + 0.3003y = 0.1002

T

2.0000x + 3.0000y = 2.0000

AF

Without pivoting:
DR

!
0.0002 0.3003 0.1002
2.0000 3.0000 2.0000

2
Applying row operation, R2 → R2 − 0.0002 R1 we have
!
0.0002 0.3003 0.1002
0 −3000 −1000
From the equations:
1
0.0002x+0.3003y = 0.1002, −3000y = −1000 ⇒ 3y = 1 ⇒ y=
3
Substitute into the first equation: 0.0002x+0.3003· 13 = 0.1002 ⇒ 0.0002x =
0.1002 − 0.1001 = 0.0001.
1
x=
2

5
 Thus, without pivoting:

x = 12 , y= 1
3

With Pivoting:
Interchange R1 ↔ R2 :
!
2.0000 3.0000 2.0000
0.0002 0.3003 0.1002

Perform elimination:
0.0002
R2 → R2 − R1
2.0000

!
2.0000 3.0000 2.0000
0 0.3 0.1
T
AF

From the second equation:

DR

1
0.3y = 0.1 ⇒ y= 3

Substitute into the first equation:

1 1
2x + 3 · 3 =2 ⇒ 2x + 1 = 2 ⇒ x= 2

Thus, with pivoting:

x = 12 , y= 1
3

4.3 Solve by Gauss-elimination method

    
1 3 3 4 x1 4
    
2 6 5 −4 x2   3 
3 7 2 2  x  = 12
    
   3  
2 3 5 6 x4 5

6
 The augmented matrix is
 
1 3 3 4 4
 
2 6 5 −4 3 
(A|b) = 
3 7 2 2 12

 
2 3 5 6 5

Applying row operations: R2 → R2 − 2R1 , R3 → R3 − 3R1 , R4 →

R4 − 2R1
 
1 3 3 4 4
 
0 0 −1 −12 −5
⇒
0 −2 −7 −10 0 

 
0 −3 −1 −2 −3
Since pivot a22 = 0, interchange with R3 or R4 (because |a42 | > |a32 |).
So, R2 ↔ R4 :
T
AF

 
1 3 3 4 4
DR

 
0 −3 −1 −2 −3
 
0 −2 −7 −10 0 
 
0 0 −1 −12 −5
Now eliminate below pivot:
2
R3 → R3 − R2
3

 
1 3 3 4 4
 
0 −3 −1 −2 −3 
 
0 0 − 19 − 26 2 
 3 3 
0 0 0 − 202
19 − 101
19

Using Back Substitution:

202 101 1
− x4 = − ⇒ x4 = 2
19 19

7
 x3 = −1, x2 = 1, x1 = 2

5 Gauss-Jordan Method
Elementary row operations
(A|b) −−−−−−−−−−−−−−−→ (I|c)

Here, I is the identity matrix.

• This reduction is equivalent to finding the solution as x = A−1 b.

• The first step is the same as in the Gauss elimination method.

• From the second step onward, make elements above and below the
pivot as zeros.

• Divide each row by its pivot to obtain the form (I|c).

Remark: If at any stage the pivot element becomes zero, then we

T

interchange rows as in the Gauss elimination method.

AF
DR

5.1 Using Gauss-Jordan method, find the inverse of the matrix

 
1 −1 1
 
A=  2 1 −3 .

1 1 1
Hence, solve the system Ax = b, where
 
0
 
b= 4 .

1

Solution: We begin with the augmented matrix (A|I):

 
1 −1 1 1 0 0
 
(A|I) = 
 2 1 −3 0 1 0 .

1 1 1 0 0 1

8
By operating the row operations: R2 → R2 − 2R1 , R3 → R3 − R1
 
1 −1 1 1 0 0
 
 0 3 −5 −2 1 0  .
 
0 2 0 −1 0 1

By operating the row operation: R2 → 31 R2

 
1 −1 1 1 0 0
 
 0 1 −5 −2 1 0  .
 3 3 3 
0 2 0 −1 0 1
By operating the row operation: R1 → R1 + R2 , R3 → R3 − 2R2
 
1 0 − 23 1
3
1
3 0
 
0 1
 − 53 − 23 1
3 0.
10 1
0 0 3 3 − 23 1
T
AF

3
By operating the row operation: R3 → 10 R3
DR

 
1 0 − 23 1
3
1
3 0
 
0 1
 − 35 − 32 1
3 .
0 
1
0 0 1 10 − 15 3
10

Starting with the augmented matrix (A|I), after successive row opera-
tions, we obtain:  
2 1 1
1 0 0 5 5 5
 
 0 1 0 −1 0 1 .
 2 2 
1 2 3
0 0 1 10 − 10 10

Thus,  
2 1 1
5 5 5
A−1 = 

1 1 .
− 2 0 2
1 2 3
10 − 10 10

9
 Equivalently, 
4 2 2
1 
A−1

= −5 0 5 .
10  
1 −2 3

Now, solving Ax = b:
x = A−1 b.


 
4 2 2 0
1   
x= −5 0 5 4 .
10   
1 −2 3 1
 
1
 
x= 1 
 2 .
− 12
T
AF

6 LU Decomposition Method
DR

The n × n matrix is decomposed as

A = LU,

where

L = Lower triangular matrix, U = Upper triangular matrix.

Structure of L and U
 
l11 0 0 ··· 0
 
 l21 l22 0
 ··· 0 
L =  l31 l32 l33 ··· 0
 
 . .. .. ... .. 
 .. . . . 
 
ln1 ln2 ln3 · · · lnn
n×n

10
  
u11 u12 u13 · · · u1n
 
 0 u22 u23
 · · · u2n 
U =  0 0 u33 · · · u3n 
 
 . .. .. . . . ... 
 .. . . 
 
0 0 0 · · · unn
n×n
To produce a unique solution, it is convenient to choose either

uii = 1 or lii = 1, i = 1, 2, . . . , n.


lii = 1 Doolittle’s method
u = 1 Crout’s method
ii

6.1 Solution of System

T

Consider the system:

AF

AX = b
DR

Since A = LU , we have
LU X = b

Let
UX = Z ⇒ LZ = b

LZ = b (Solve for Z)
UX = Z (Solve for X)
The unknowns z1 , z2 , . . . , zn are determined by forward substitution and
the unknowns x1 , x2 , . . . , xn are obtained by back substitution.

Z = L−1 b, X = U −1 b

A−1 = U −1 L−1

Note: The method fails if any of the diagonal elements uii or lii is zero.

11
The LU decomposition is guaranteed when the matrix A is positive definite.

a11 > 0, a22 > 0, a33 > 0

6.2 Solve by thre LU Decomposition Method

x1 + x2 + x3 = 1,
4x1 + 3x2 − x3 = 6,
3x1 + 5x2 + 3x3 = 4.
Solution: Choose uii = 1 and write (Crout’s Method):
    
1 1 1 l 0 0 1 u12 u13
   11  
4 3 −1 = l21 l22 0  0 1 u23 
    
3 5 3 l31 l32 l33 0 0 1
 
l l11 u12 l11 u13
 11
T


= l l u + l l u + l u
AF

21 21 12 22 21 13 22 23

 
l31 l31 u12 + l32 l31 u13 + l32 u23 + l33
DR

From which:
l11 = 1, l21 = 4, l31 = 3

u12 = 1, u13 = 1

l22 = −1, l32 = 2

u23 = 5, l33 = −10

Thus, we have:
   
1 0 0 1 1 1
   
L=
 4 −1 0 ,
 U =
0 1 5

3 2 −10 0 0 1

LU X = b, UX = Z

⇒ LZ = b

12
  
1
 
⇒Z=
−2

− 12
 
1
 
UX = Z ⇒ X= 1 
 2 
− 12
Example: Find the inverse of the matrix using LU decomposition method.
Take u11 = u22 = u33 = 1 (Crout’s Method).
 
3 2 1
 
A= 2 3 2

1 2 2
   
3 0 0 1 2 1
   3 3
L = 2 3 05 4
, U =0 1

T

5
AF

1 43 25 0 0 1
DR

   
1
0 0 1 − 23 1
 3 5
L−1 U −1
  
2 3
= −
 5 5 0 ,
 =0 1 − 45 

1
3 − 34 5
3 0 0 1
 
2 −2 1
1
A−1 = U −1 L−1

=  −2 5 −4
3 
1 −4 5
Example: Show that the LU Decomposition method fails to solve the
system of equations
    
1 1 −1 x1 2
    
2 2 5  x2  = −3
    
3 2 −3 x3 6

13
 Exact solution is:

x1 = 1, x2 = 0, x3 = −1

Take
l11 = l22 = l33 = 1, l21 = 2, u22 = 0

∴ LU Decomposition fails as the pivot u22 = 0

If
u11 = u22 = u33 = 1 ⇒ l22 = 0

∴ LU Decomposition method fails as the pivot l22 = 0

Thus, A is not positive definite, and hence its LU decomposition is not

guaranteed.
T
AF

7 Iterative Methods
DR

1. Gauss-Jacobi Method

2. Gauss-Seidel Method

Let the system be

a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn = b1 ,

a21 x1 + a22 x2 + a23 x3 + · · · + a2n xn = b2 ,
a31 x1 + a32 x2 + a33 x3 + · · · + a3n xn = b3 ,
..
.
an1 x1 + an2 x2 + an3 x3 + · · · + ann xn = bn ,

in which diagonal elements aii do not vanish. If this is not the case,
then the equations should be rearranged so that this condition is satisfied.

14
 1  
x1 = b1 − a12 x2 − a13 x3 − · · · − a1n xn ,
a11
1  
x2 = b2 − a21 x1 − a23 x3 − · · · − a2n xn ,
a22 (1)
..
.
1  
xn = bn − an1 x1 − an2 x2 − · · · − an,n−1 xn−1 .
ann
(0) (0) (0)
Suppose x1 , x2 , . . . , xn are any initial approximations to the un-
knowns x1 , x2 , . . . , xn . Substituting these in the above equations, we find:

(1) 1  (0) (0) (0)


x1 = b1 − a12 x2 − a13 x3 − · · · − a1n xn ,
a11
(1) 1  (0) (0) (0)

x2 = b2 − a21 x1 − a23 x3 − · · · − a2n xn ,
a22 (2)
..
.
1  (0) (0) (0)

x(1)
n = bn − an1 x1 − an2 x2 − · · · − an,n−1 xn−1
T

ann
AF

(n−1) (n−1) (n−1)

Similarly, if x1 , x2 , . . . , xn are a system of (n − 1)th approxi-
DR

mations, then the next approximation is given by the formula:

(n) 1  (n−1) (n−1) (n−1)


x1 = b1 − a12 x2 − a13 x3 − · · · − a1n xn ,
a11
(n) 1  (n−1) (n−1) (n−1)

x2 = b2 − a21 x1 − a23 x3 − · · · − a2n xn ,
a22 (2)
..
.
1  (n−1) (n−1) (n−1)

xn(n) = bn − an1 x1 − an2 x2 − · · · − an,n−1 xn−1 .
ann

If we rewrite equation (1) as

X = BX + c,

then the iteration formula (2) may be written as

X (n+1) = BX (n) + c

15
 This method is due to Jacobi and is called the method of simultaneous
displacements.
The sufficient condition for the convergence of this method is that

kBk < 1

8 Gauss-Seidel Method

If we substitute the initial approximation

(0) (0)
(x1 , x2 , . . . , x(0)
n )

(1)
into the right-hand side of equation (1) and denote the result as x1 , then
in the second equation we substitute

(1) (0) (0)

(x1 , x2 , x3 , . . . , x(0)
n )
T

(1)
AF

and denote the result as x2 .

DR

In the third equation, we substitute

(1) (1) (0)

(x1 , x2 , x3 , . . . , x(0)
n )

(1)
and denote the result as x3 .
In this manner, the first stage of iteration is completed. This process
is repeated until the values of x1 , x2 , . . . , xn are obtained to the desired
accuracy.
It is clear that this method uses an improved component as soon as it
is available, and it is called the method of successive displacements
or the Gauss-Seidel Method.

Convergence Condition:
Both Gauss-Jacobi and Gauss-Seidel methods converge for any choice

16
of the initial approximation if every equation of the system satisfies
n
X aij
≤1
j=1
a ii
j6=i

where the “<” sign should be valid in the case of at least one equation.

Remark: The Gauss-Seidel method converges about twice as fast as

the Jacobi method.

9 Example: Gauss-Jacobi Iteration

Consider the system of equations:

10x1 − 2x2 − x3 − x4 = 3
−2x1 + 10x2 − x3 − x4 = 15
T

−x1 − x2 + 10x3 − 2x4 = 27

AF

−x1 − x2 − 2x3 + 10x4 = −9

DR

Rewriting these equations in iteration form:

x1 = 0.3 + 0.2x2 + 0.1x3 + 0.1x4

x2 = 1.5 + 0.2x1 + 0.1x3 + 0.1x4
x3 = 2.7 + 0.1x1 + 0.1x2 + 0.2x4
x4 = −0.9 + 0.1x1 + 0.1x2 + 0.2x3

Initial Approximation
(0) (0) (0) (0)
x1 = 0.3, x2 = 1.5, x3 = 2.7, x4 = −0.9

17
Iterations (Gauss-Jacobi Method)
(n) (n) (n) (n)
n x1 x2 x3 x4
0 0.3 1.5 2.7 −0.9
1 0.78 1.74 2.7 −0.018
2 0.9 1.908 2.916 −0.108
3 0.9624 1.9685 2.9592 −0.036
4 0.9845 1.9848 2.9851 −0.0158
5 0.9939 1.9938 2.9938 −0.006
6 0.9975 1.9975 2.9976 −0.0025
7 0.9990 1.9990 2.9990 −0.0010
8 0.9996 1.9996 2.9996 −0.0004
9 0.9998 1.9998 2.9998 −0.0002
10 0.9999 1.9999 2.9999 −0.0001
11 0.9999 1.9999 2.9999 0.0
12 1.0 2.0 3.0 0.0
T
AF

The solution converges to:

DR

x1 = 1, x2 = 2, x3 = 3, x4 = 0

9.1 Example: Gauss-Jacobi Iteration (3 Iterations)

Solve the system:

4x1 + x2 + x3 = 2
x1 + 5x2 + 2x3 = −6
x1 + 2x2 + 3x3 = −4
Rewriting in iteration form:

x1 = 0.5 − 0.25x2 − 0.25x3

x2 = −1.2 − 0.2x1 − 0.4x3
x3 = −1.3333 − 0.3333x1 − 0.6666x2

18
Initial Approximation
 
0.5
x(0)
 
=
−0.5 

−0.5

Iteration 1
(1)
x1 = 0.5 − 0.25(−0.5) − 0.25(−0.5) = 0.75
(1)
x2 = −1.2 − 0.2(0.5) − 0.4(−0.5) = −1.1
(1)
x3 = −1.3333 − 0.3333(0.5) − 0.6666(−0.5) = −1.1667

Iteration 2
(2)
x1 = 0.5 − 0.25(−1.1) − 0.25(−1.1667) = 1.0667
(2)
x2 = −1.2 − 0.2(0.75) − 0.4(−1.1667) = −0.8833
(2)
x3 = −1.3333 − 0.3333(0.75) − 0.6666(−1.1) = −0.85
T
AF

Iteration 3
DR

(3)
x1 = 0.5 − 0.25(−0.8833) − 0.25(−0.85) = 0.9333
(3)
x2 = −1.2 − 0.2(1.0667) − 0.4(−0.85) = −1.0733
(3)
x3 = −1.3333 − 0.3333(1.0667) − 0.6666(−0.8833) = −1.1000

Result After 3 Iterations

 
0.9333
x(3)
 
=
−1.0733

−1.1000

10 Example: Gauss-Seidel Iteration

Solve the system:

2x1 + x2 = 7
−x1 + 2x2 − x3 = 1
−x2 + 2x3 = 1

19
 Rewriting in iteration form:

x1 = 21 (7 + x2 )
x2 = 12 (1 + x1 + x3 )
x3 = 12 (1 + x2 )

Initial Approximation

x(0) = (0, 0, 0)

Iteration 1 (k = 1)
(1)
x1 = 21 (7 + 0) = 3.5
(1)
x2 = 12 (1 + 3.5 + 0) = 2.25
(1)
x3 = 12 (1 + 2.25) = 1.625

Iteration 2 (k = 2)
T
AF

(2)
x1 = 12 (7 + 2.25) = 4.625
DR

(2)
x2 = 12 (1 + 4.625 + 1.625) = 3.625
(2)
x3 = 12 (1 + 3.625) = 2.3125

Iteration 3 (k = 3)
(3)
x1 = 12 (7 + 3.625) = 5.3125
(3)
x2 = 12 (1 + 5.3125 + 2.3125) = 4.3125
(3)
x3 = 12 (1 + 4.3125) = 2.6563

Result After 3 Iterations

 
5.3125
x(3)
 
=
4.3125

2.6563

20