Numerical Methods

Lecture 05
5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 1
 Direct Solution of Linear Equations
❑ Necessity
Analysis of linear equations is significant for a number of reasons:
– Mathematical models of many of the real world problems are either linear or
can be approximated reasonably well using linear relationships.
– The analysis of linear relationship of variables is generally easier than that of
nonlinear relationships.

❑ Linear Equation
– A linear equation involving two variables x and y has the standard form:
ax + by = c
Where a, b and c are real numbers and a and b cannot both equal zero.
– Some examples of linear equations:
4x + 7y = 15
- x - 2/3y = 0

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 2

 Direct Solution of Linear Equations
❑ Non-Linear Equation
– Some examples of nonlinear equations:
2x – xy + y = 2
x2 + y2 = 25

– In practice, linear equations occur in more than two variables. A linear equation
with n variables has the form:
a1x1 + a2x2 + a3x3 + . . . . . . . . . . + anxn = b
Where ai are real numbers and at least one of them is not zero.
– The main concern is to solve for xi, given the values of ai and b.
– An infinite set of xi values will satisfy the above equation. There is no unique
solution.

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 3

 Direct Solution of Linear Equations
❑ Direct Solution of Linear Equations
– The techniques and methods for solving systems of linear algebraic equations
belong to two fundamentally different approaches:
• Elimination Approach
• Iterative Approach

❑ Elimination Approach
– Elimination approach, also known as direct method, reduces the given system
of equations to a form which the solution can be obtained by simple
substitution.
Some elimination methods are given:
• Basic Gauss elimination method
• Gauss elimination with pivoting
• Gauss-Jordan method
• LU decomposition methods
• Matrix inverse method

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 4

 Direct Solution of Linear Equations
❑ Iterative Approach
– Iterative approach involves assumptions of some initial values which are then
refined repeatedly till they reach some accepted level of accuracy.

❑ Existence of Solution
– Given an arbitrary system of equations, it is difficult to say whether the system
has a solution or not. Sometimes there may be a solution but it may not be
unique. There are four possibilities:
• System has a unique solution
• System has no solution
• System has a solution but not a unique one (i.e. it has infinite solutions)
• System is ill-conditioned

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 5

 Direct Solution of Linear Equations
❑ Unique Solution
Consider the system
x + 2y = 9
2x – 3y = 4
The system has a solution: x = 5 and y = 2.
Since no other pair of values of x and y would satisfy the equations, the solution is
said to be unique. The system is shown in the fig.

3x – 1.5y = 4

4.5 x + 2y = 9 y
2x - 3y = 4 2x - y = 5
y
(x = 5, y = 2)

0 x 9 0 x
2

System with unique solution System with no solution

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 6

 Direct Solution of Linear Equations
❑ No Solution
Consider the system
2x – y = 5
3x – 3/2y = 4
The system has no solution. These two lines are parallel as shown in the fig.
Therefore, they never meet. Such equations are called inconsistent equations.

❑ Infinite Solution (No Unique Solution)

Consider the system
-2x + 3y = 6
4x – 6y = -12
The system has many different solutions. We can see that these are two different
forms of the same equation and therefore, they represent the same line. Such
equations are called dependent equations.

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 7

 Direct Solution of Linear Equations
❑ Ill-Conditioned System
Consider the system
x – 2y = -2
0.45x – 0.91y = -1
The system has a solution but it is very difficult to identify the exact point at which
the lines intersect. Such system are said to be ill-conditioned.

y y x - 2y = -2
-2x + 3y = 6
0.45x – 0.91y = -1

4x - 6y = -12

0 x 0 x

System with infinite solutions Ill-Conditioned System

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 8

 Direct Solution of Linear Equations
❑ Basic Gauss Elimination Method
– Gauss elimination method proposes a systematic strategy for reducing the
system of equations to the upper triangular form using the forward elimination
approach and then for obtaining values of unknowns using the back
substitution process.

– The strategy consists of two phases:

Forward elimination phase: This phase is concerned with the manipulation of
equations in order to eliminate some unknowns from the equations and produce
an upper triangular system.
Back substitution phase: This phase is concerned with the actual solution of
the equations and uses the back substation process on the reduced upper
triangular system.

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 9

 Direct Solution of Linear Equations
❑ Algorithm for Basic Gauss Elimination Method
–
❑ Example: Solve the following system using the basic Gauss elimination method.
3x1 + 6x2 + x3 = 16
2x1 + 4x2 + 3x3 = 13
x1 + 3x2 + 2x3 = 9
Solution:
3x1 + 6x2 + x3 = 16
0 + 0 + x3 = 1 ( R2 = R2 - (2/3)R1 )
0 + 3x2 + 5x3 = 11 ( R3 = R3 - (1/3)R1 )
Now reorder the equations:
3x1 + 6x2 + x3 = 16
0 + 3x2 + 5x3 = 11
0 + 0 + x3 = 1
Solution is
x3 = 1, x2 = 2 and x1 = 1

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 10

 Direct Solution of Linear Equations
❑ Gauss Elimination with Pivoting
– In the basic Gauss elimination method, the element when i = j is known as a
pivot element. Each row is normalized by dividing the coefficients of that row
by its pivot element. That is,

= j=1, ……, n

If = 0, k-th row cannot be normalized. Therefore, the procedure fails. One way
to overcome this problem is to interchange this row with another row below it
which does not have a zero element in that position. It can be proved that round-off
errors would be reduced if the absolute value of the pivot element is large.
Therefore, it is suggested that the row with zero pivot element should be
interchanged with the row having the largest (absolute value) coefficient in that
position.

In general, the reordering of equations is done to improve accuracy, even if the

pivot element is not zero.
5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 11
 Direct Solution of Linear Equations
❑ Gauss Elimination with Pivoting

The procedure of reordering involves the following steps:

– Search and locate the largest absolute value among the coefficients in the first column.
– Exchange the first row with the row containing that element.
– Then eliminate the first variable in the second equation.
– When the second row becomes the pivot row, search for the coefficients in the second
column from the second row to the nth row and locate the largest coefficient. Exchange
the second row with the row containing the large coefficient.
– Continue this procedure till (n – 1) unknowns are eliminated.
– This process is referred to as partial pivoting.

– In complete pivoting, at each stage, the largest element in any of the remaining rows is
used as the pivot. Complete pivoting requires a lot of overhead and therefore, it is not
generally used.

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 12

 Direct Solution of Linear Equations
❑ Example: Solve the following system of equations using partial pivoting technique:
2x1 + 2x2 + x3 = 6
4x1 + 2x2 + 3x3 = 4
x1 - x2 + x3 = 0
Solution:
Original system
2 2 1 6 (R1 and R2 are interchanged)
4 2 3 4
1 -1 1 0

Interchange row-1 and row-2:

4 2 3 4 (pivot row)
2 2 1 6
1 -1 1 0

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 13

 Direct Solution of Linear Equations
❑ Example: Solve the following system of equations using partial pivoting technique:
2x1 + 2x2 + x3 = 6
4x1 + 2x2 + 3x3 = 4
x1 - x2 + x3 = 0
Solution:
Now perform (R2 = R2 - (1/2)R1 ) and ( R3 = R3 - (1/4)R1 )
4 2 3 4
0 1 -0.5 4 (R2 and R3 are interchanged)
0 -1.5 0.25 -1

Interchange row-2 and row-3:

4 2 3 4
0 -1.5 0.25 -1 (pivot row)
0 1 -0.5 4

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 14

 Direct Solution of Linear Equations
❑ Example: Solve the following system of equations using partial pivoting technique:
2x1 + 2x2 + x3 = 6
4x1 + 2x2 + 3x3 = 4
x1 - x2 + x3 = 0
Solution:
Now perform, R3 = R3 + (1/1.5)R2
4 2 3 4
0 -1.5 0.25 -1
0 0 -1/3 10/3

Therefore, solution is:

x3 = -10, x2 = -1 and x1 = 9

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 15

 Direct Solution of Linear Equations
❑ Gauss-Jordan Method
– In Gauss elimination method, a variable is eliminated from the rows below the
pivot equation. But in Gauss-Jordan method, it is eliminated from all other
rows (both below and above). This process thus eliminates all the off-diagonal
terms producing a diagonal matrix rather than a triangular matrix.

a11 a12 a13   x1  b1 

a a a 23   x2  = b2 
 21 22    
a31 a32 a33   x3  b3 

a11 a12 a13   x1  b1  1 0 0  x1  b / 1 

 / /   = b / 2   0 1 0  x  =  // 
 0 a 22 a 23 x
    b 2 
2
  2 
0 0 a 33   x3  b // 3 
//
0 0 1  x3  b /// 3 
  
Result of Gauss elimination Result of Gauss-Jordan elimination

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 16

 Direct Solution of Linear Equations
❑ Algorithm of Gauss-Jordan elimination Method

❑ Example: Solve the following system of equations using Gauss-Jordan method:

2x1 + 4x2 - 6x3 = -8
x1 + 3x2 + x3 = 10
2x1 - 4x2 - 2x3 = -12
Solution:
Normalize row-1 by dividing by 2 (pivot element).
x1 + 2x2 - 3x3 = -4
x1 + 3x2 + x3 = 10
2x1 - 4x2 - 2x3 = -12

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 17

 Direct Solution of Linear Equations
❑ Example: Solve the following system of equations using Gauss-Jordan method:
2x1 + 4x2 - 6x3 = -8
x1 + 3x2 + x3 = 10
2x1 - 4x2 - 2x3 = -12
Solution:
Perform R2 = R2 - R1 and R3 = R3 - 2R1
x1 + 2x2 - 3x3 = -4
0 + x2 + 4x3 = 14
0 - 8x2 + 4x3 = -4

Normalize row-2 (it is already in normalized form).

Perform R1 = R1 – 2R2 and R3 = R3 + 8R2
x1 + 0 - 11x3 = -32
0 + x2 + 4x3 = 14
0 - 0 + 36x3 = 108
5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 18
 Direct Solution of Linear Equations
❑ Example: Solve the following system of equations using Gauss-Jordan method:
2x1 + 4x2 - 6x3 = -8
x1 + 3x2 + x3 = 10
2x1 - 4x2 - 2x3 = -12
Solution:
Normalize row-3.
x1 + 0 - 11x3 = -32
0 + x2 + 4x3 = 14
0 - 0 + x3 = 3
Perform R1 = R1 + 11R3 and R2 = R2 - 4R3
x1 + 0 - 0 = 1
0 + x2 + 0 = 2
0 - 0 + x3 = 3

Therefore, solution is: x1 = 1, x2 = 2 and x3 = 3

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 19
 Direct Solution of Linear Equations
❑ Matrix Inversion Method
Consider the following system of equations:
a11x1 + a12x2 + a13x3 = b1
a21x1 + a22x2 + a23x3 = b2
a31x1 + a32x2 + a33x3 = b3

In matrix form:
Ax = b - - - - - - - - - - - - - - - - - - - - - - - - (1)
Where
a11 a12 a13   x1  b1 
A = a 21 a 22 a 23  x =  x2  and b = b2 
   
a31 a32 a33   x3  b3 
Multiply each side of equation (1) by the inverse of A. This yields
A-1Ax = A-1b
Therefore, x = A-1b
This gives the solution for x.
5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 20
 Direct Solution of Linear Equations
❑ Matrix Inversion Method
Computing Matrix Inverse
– Gauss-Jordan method is more complicated compared to Gauss elimination
method.
– Matrix inversion method provides a simple approach for obtaining the inverse
of a matrix.
– This is done as follows:
1. Argument the coefficient matrix A with an identity matrix as shown below:

a11 a12 a13  1 0 0

a a a  0 1 0
 21 22 23 
a31 a32 a33  0 0 1

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 21

 Direct Solution of Linear Equations
❑ Matrix Inversion Method
Computing Matrix Inverse
2. Apply the Gauss-Jordan method to the augmented matrix to reduce A to an
identity matrix. The result will be as shown below:
1 0 0  a11/ a12/ a13/ 
 / / / 
0 1 0  a 21 a 22 a 23 
0 /
0 1  a31 /
a32 a33 / 
 

– The right–hand side of the augmented matrix is the inverse of A. Now, we can
obtain the solution as follows:
x1 = a11/  b1 + a12/  b2 + a13/  b3
x2 = a 21
/
 b1 + a 22
/
 b2 + a 23
/
 b3
x3 = a31
/
 b1 + a32
/
 b2 + a33
/
 b3

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 22

 Direct Solution of Linear Equations
❑ Example: Solve the following system of equations using Matrix Inversion method:
2x1 + 4x2 - 6x3 = -8
x1 + 3x2 + x3 = 10
2x1 - 4x2 - 2x3 = -12
Solution:
In matrix form:
Ax = b - - - - - - - - - - - - (1)
Where x 
 2 4 − 6 1  −8 
A = 1 1 x =  x2  b =  10 

3
    
2 − 4 − 2   x3  − 12

Augmented matrix: 2 4 − 6  1 0 0
1 3 1  0 1 0
 
2 − 4 − 2  0 0 1

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 23

 Direct Solution of Linear Equations
❑ Example: Solve the following system of equations using Matrix Inversion method:
2x1 + 4x2 - 6x3 = -8
x1 + 3x2 + x3 = 10
2x1 - 4x2 - 2x3 = -12
Solution:
Perform R2 = R2 –(1/2) R1 and R3 = R3 - R1
2 4 − 6  1 0 0
0 1 4  − 0.5 1 0
 
0 − 8 4  −1 0 1

Perform R1 = R1 – 4R2 and R3 = R3 + 8R2

2 0 − 22  3 − 4 0
0 1 4  − 0.5 1 0
 
0 0 36  − 5 8 1 

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 24

 Direct Solution of Linear Equations
❑ Example: Solve the following system of equations using Matrix Inversion method:
2x1 + 4x2 - 6x3 = -8
x1 + 3x2 + x3 = 10
2x1 - 4x2 - 2x3 = -12
Solution:
Perform R1 = R1 + (11/18)R3 and R2 = R2 – (1/9)R3
2 0 0  − 1 / 18 8/9 11 / 18 
0 1 0  1 / 18 1/ 9 − 1 / 9
 
0 0 36  − 5 8 1 

Normalize row-1 and row-3:

1 0 0  − 1 / 36 4/9 11 / 36
0 1 0  1 / 18 1/ 9 −1/ 9 
 
0 0 1  − 5 / 36 2/9 1 / 36 

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 25

 Direct Solution of Linear Equations
❑ Example: Solve the following system of equations using Matrix Inversion method:
2x1 + 4x2 - 6x3 = -8
x1 + 3x2 + x3 = 10
2x1 - 4x2 - 2x3 = -12
Solution:
As we know, x = A-1b
Here,
 x1   − 1 / 36 4/9 11 / 36  −8 
x =  x2  A−1 =  1 / 18 1/ 9 −1/ 9  b =  10 
     
 x3   − 5 / 36 2/9 1 / 36  − 12

Therefore,
x1 = (-1/36)(-8) + (4/9)(10) + (11/36)(-12) = 1
x2 = (1/18)(-8) + (1/9)(10) + (-1/9)(-12) = 2
x3 = (-5/36)(-8) + (2/9)(10) + (1/36)(-12) = 3

5/27/2023 Md. Golam Moazzam, Dept. of CSE, JU 26