MIZAN TEPI UNIVERSITY

COLLEGE OF ENGINEERING AND TECHNOLOGY

DEPARTMENT OF MECHANICAL ENGINEERING

Numerical Methods (Menge 2063)

CHAPTER THREE

LINEAR ALGEBRAIC EQUATIONS

By: TESFAHUN MESHESHA

Feb, 2021
Tepi, Ethiopia
 CHAPTER THREE
3. LINEAR ALGEBRAIC EQUATIONS

3.1. Introduction
Consider a system of n linear algebraic equations in n unknowns,

𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1

𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 = 𝑏2
… … … … …
𝑎𝑛1 𝑥1 + 𝑎𝑛2 𝑥2 + ⋯ + 𝑎𝑛𝑛 𝑥𝑛 = 𝑏𝑛

where 𝑎𝑖𝑗 , 𝑖 = 1, 2, . . . , 𝑛, 𝑗 = 1, 2, … , 𝑛, are the known coefficients 𝑏𝑖 , 𝑖 = 1, 2, … , 𝑛, are the known

right hand side values and 𝑥𝑖 , 𝑖 = 1, 2, … , 𝑛 are the unknowns to be determined.
In matrix notation we write the system as;
𝑨𝒙 = 𝒃 (𝟑. 𝟏. 𝟏)
Where:
𝑎11 𝑎12 … 𝑎1𝑛 𝑥1 𝑏1
𝑎21 𝑎22 … 𝑎2𝑛 𝑥2 𝑏
𝐀 = [ ... … … … ], 𝒙 = [ … ] and 𝒃 = [ 2 ]
…
𝑎1𝑛 𝑎2𝑛 … 𝑎𝑛𝑛 𝑥𝑛 𝑏𝑛
The matrix [A | b], obtained by appending the column b to the matrix A is called the augmented matrix.
That is
𝑎11 𝑎12 … 𝑎1𝑛 𝑏1
𝑎21 𝑎22 … 𝑎2𝑛 𝑏2
[𝐀|𝐛] = [ . . . … … … |…]
𝑎1𝑛 𝑎2𝑛 … 𝑎𝑛𝑛 𝑏𝑛
We define the following.
(i) The system of equations (3.1.1) is consistent (has at least one solution), if rank (A) = rank [A | b] = r.
If r = n, then the system has unique solution.
If r < n, then the system has (n – r) parameter family of infinite number of solutions.

(ii) The system of equations (3.1.1) is inconsistent (has no solution) If rank (A) ≠ rank [A | b].

We assume that the given system is consistent.

The methods of solution of the linear algebraic system of equations (3.1.1) may be classified as direct and
iterative methods.

MTU, Numerical Methods (Menge 2063) Page 1 of 20

(a) Direct methods produce the exact solution after a finite number of steps (disregarding the round-off
errors). In these methods, we can determine the total number of operations (additions, subtractions,
divisions and multiplications). This number is called the operational count of the method.
(b) Iterative methods are based on the idea of successive approximations. We start with an initial
approximation to the solution vector 𝒙 = 𝒙𝟎 , and obtain a sequence of approximate
vectors 𝒙𝟎 , 𝒙𝟏 , . . . , 𝒙𝒌 , which in the limit as 𝑘 → ∞, converge to the exact solution vector 𝒙.
3.2. Non computer methods of solution of linear algebraic equation
These are methods which are used to solve small (n≤3) sets of simultaneous equations that do not require
a computer. These includes graphical method, Cramer’s rule, and elimination method.

3.2.1. Graphical Method

Linear simultaneous equations in two unknowns may be solved graphically by:
(i) Plotting the two straight lines on the same axes, and
(ii) Noting their point of intersection.
The co-ordinates of the point of intersection give the required solution.
Example [Link]:
Solve the simultaneous equations below graphically:
2𝑥 − 𝑦 = 4
𝑥+𝑦=5

Solution:
Rearranging each equation into 𝑦 = 𝑚𝑥 + 𝑐 form
𝑦 = 2𝑥 − 4 (1)
FIGURE 3-1: GRAPH OF EXAMPLE [Link]
𝑦 =5−𝑥 (2)
Only three co-ordinates need be calculated for each graph since both are straight lines.

𝑥 0 1 2 𝑥 0 1 2
𝑦 = 2𝑥 − 4 -4 -2 0 𝑦 = −𝑥 + 5 5 4 3

Each of the graphs is plotted as shown in Fig. 3.1. The point of intersection is at (3, 2) and since this is the only
point which lies simultaneously on both lines. Therefore 𝑥 = 3, 𝑎𝑛𝑑 𝑦 = 2 is the solution.

3.2.2. Cramer’s rule

Cramer’s rule is determinant formula for solving a system of equations 𝑨𝑿 = 𝑩, when 𝑨 is 𝒏 × 𝒏 and
nonsingular. In this case, the system has the unique solution 𝑿 = 𝑨−𝟏 𝑩. We can therefore find 𝑿 by
replacing 𝑨−𝟏 and then 𝑨−𝟏 𝑩.
Let 𝑨 be 𝒏 × 𝒏 matrix of numbers. Then the unique solution of 𝑨𝑿 = 𝑩 is;

MTU, Numerical Methods (Menge 2063) Page 2 of 20

 𝒙𝟏
𝒙𝟐 𝟏
( ⋮ ) , 𝑤ℎ𝑒𝑟𝑒 𝒙𝒌 = |𝑨| |𝑨(𝒌; 𝑩)|
𝒙𝒏
and 𝑨(𝒌; 𝑩) is a matrix obtained from 𝑨 by replacing column 𝒌 𝑜𝑓 𝑨 𝑏𝑦 𝑩;
𝒃𝟏
𝒃
𝑩 = ( 𝟐)
⋮
𝒃𝒏
Multiply column 𝑘 of 𝐴 by 𝑥𝑘 . The determinant of the resulting matrix is 𝒙𝒌 |𝑨|, so
𝒂𝟏𝟏 𝒂𝟏𝟐 … 𝒂𝟏𝒌 𝒙𝒌 ⋯ 𝒂𝟏𝒏
𝒂𝟐𝟏 𝒂𝟐𝟐 … 𝒂𝟐𝒌 𝒙𝒌 ⋯ 𝒂𝟐𝒏
𝒙𝒌 |𝑨| = | ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ |
𝒂𝒏𝟏 𝒂𝒏𝟐 ⋯ 𝒂𝒏𝒌 𝒙𝒌 ⋯ 𝒂𝒏𝒏
For each 𝒋 ≠ 𝒌, add 𝒙𝒋 times column 𝒋 to column 𝒌. This operation does not change the value of the
determinant.
𝒂𝟏𝟏 𝒂𝟏𝟐 … 𝒂𝟏𝟏 𝒙𝟏 + 𝒂𝟏𝟐 𝒙𝟐 … + 𝒂𝟏𝒏 𝒙𝟏 ⋯ 𝒂𝟏𝒏
𝒂 𝒂𝟐𝟐 … 𝒂𝟐𝟏 𝒙𝟏 + 𝒂𝟐𝟐 𝒙𝟐 … + 𝒂𝟐𝒏 𝒙𝟏 ⋯ 𝒂𝟐𝒏
𝒙𝒌 |𝑨| = | ⋮𝟐𝟏 ⋮ ⋮ ⋮ ⋮ ⋮ |
𝒂𝒏𝟏 𝒂𝒏𝟐 ⋯ 𝒂𝒏𝟏 𝒙𝟏 + 𝒂𝒏𝟐 𝒙𝟐 … + 𝒂𝒏𝒏 𝒙𝟏 ⋯ 𝒂𝒏𝒏
𝒂𝟏𝟏 𝒂𝟏𝟐 … 𝒃𝟏 ⋯ 𝒂𝟏𝒏
𝒂 𝒂𝟐𝟐 … 𝒃𝟐 ⋯ 𝒂𝟐𝒏
= | 𝟐𝟏 | = |𝑨(𝒌; 𝑩)|
⋮ ⋮ ⋮ ⋮ ⋮ ⋮
𝒂𝒏𝟏 𝒂𝒏𝟐 ⋯ 𝒃𝒏 ⋯ 𝒂𝒏𝒏
Solving for 𝑥𝑘 yields the conclusion of Cramer’s rule.
Example [Link]:
Solve the system of equation
𝑥1 − 3𝑥2 − 4𝑥3 = 1
−𝑥1 + 𝑥2 − 3𝑥3 = 14
𝑥2 − 3𝑥3 = 5
Solution:
The matrix of the coefficient is
1 −3 −4
𝐴 = [−1 1 −3]
0 1 −3
We find that |𝐴| = 13. By Cramer’s rule,

MTU, Numerical Methods (Menge 2063) Page 3 of 20

 1 −3 −4
1 −117
𝑥1 = 13 | 14 1 −3| = 13 = −9
5 1 −3
1 1 −4
1 −10
𝑥2 = 13 |−1 14 −3| = 13
0 5 −3
1 −3 1
1 −25
𝑥3 = 13 |−1 1 14| = 13
0 1 5
Exercise [Link]:
Using Cramer’s rule solve the system of equation:
5𝑥1 − 6𝑥2 + 𝑥3 = 4
−𝑥1 + 3𝑥2 − 4𝑥3 = 5
2𝑥1 + 3𝑥2 + 3𝑥3 = −8

3.2.3. Elimination method

The basic strategy is to multiply the equations by constants so that one of the unknowns will be eliminated
when the equations are combined.

The result is a single equation that can be solved for the remaining unknown. This can then be substituted
into either of the original equations to compute the other variable.

The elimination of unknowns can be extended to systems with more than two or three equations. However,
the numerous calculations that are required for larger systems make the method extremely tedious to
implement by hand. However, the technique can be formalized and readily programmed for the computer.

Example [Link]:
Solve the problem given in exercise [Link] by using elimination method.
Solution:
𝑥1 − 3𝑥2 − 4𝑥3 = 1 (1)
−𝑥1 + 𝑥2 − 3𝑥3 = 14 (2)
𝑥2 − 3𝑥3 = 5 (3)
Apparently the value of 𝑥1 is zero in equation (3), which makes the solution process easier. With this
advantage we can eliminate both 𝑥1 𝑎𝑛𝑑 𝑥2 . To do so let’s multiply equation (3) by 2, which results in;
𝑥1 − 3𝑥2 − 4𝑥3 = 1 (1)
−𝑥1 + 𝑥2 − 3𝑥3 = 14 (2)
2𝑥2 − 6𝑥3 = 10 (4)
Addition of the same terms vertically downward,

−13𝑥3 = 25 (5)

MTU, Numerical Methods (Menge 2063) Page 4 of 20

From equation (5), we have
−25
𝑥3 = 13

Substituting the value of 𝑥3 in to equation (4), we have

−10
𝑥2 = 13

Finally substituting the value of 𝑥3 𝑎𝑛𝑑 𝑥2 into equation (1), we come up with
−117
𝑥1 = 13

3.3. Gauss Elimination

The method is based on the idea of reducing the given system of equations 𝑨𝒙 = 𝒃, to an upper triangular
system of equations 𝑼𝒙 = 𝒛, using elementary row operations. We know that these two systems are
equivalent. That is, the solutions of both the systems are identical. This reduced system 𝑼𝒙 = 𝒛, is then
solved by the back substitution method to obtain the solution vector x.

We illustrate the method using the 3 × 3 system

𝑎11 𝑥1 + 𝑎12 𝑥2 + 𝑎13 𝑥3 = 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + 𝑎23 𝑥3 = 𝑏2 (3.3.1)
𝑎31 𝑥1 + 𝑎32 𝑥2 + 𝑎33 𝑥3 = 𝑏3
We write the augmented matrix [𝑨 | 𝒃] and reduce it to the following form

𝐺𝑎𝑢𝑠𝑠 𝑒𝑙𝑖𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛
[𝑨|𝒃] → [𝑼|𝒛]
The augmented matrix of the system (3.3.1) is

𝑎11 𝑎12 𝑎13 𝑏1

[ 21 𝑎22 𝑎23|𝑏2 ]
𝑎 (3.3.2)
𝑎31 𝑎32 𝑎33 𝑏3

First stage of elimination

We assume 𝒂𝟏𝟏 ≠ 𝟎. This element 𝒂𝟏𝟏 in the 1 × 1 position is called the first pivot. We use this pivot to
reduce all the elements below this pivot in the first column as zeroes. Multiply the first row in (3.3.2) by
𝒂𝟐𝟏 /𝒂𝟏𝟏 and 𝒂𝟑𝟏 /𝒂𝟏𝟏 respectively and subtract from the second and third rows. That is, we are performing
elementary row operations 𝑹𝟐 – (𝒂𝟐𝟏 /𝒂𝟏𝟏 )𝑹𝟏 and 𝑹𝟑 – (𝒂𝟑𝟏 /𝒂𝟏𝟏 )𝑹𝟏 respectively. We obtain the new
augmented matrix as;
𝑎11 𝑎12 𝑎13 𝑏1
[ 0 𝑎22 (1) 𝑎23 (1) |𝑏2 (1) ] (3.3.3)
0 𝑎32 (1) 𝑎33 (1) 𝑏3 (1)

MTU, Numerical Methods (Menge 2063) Page 5 of 20

 where:
𝑎 (1) 𝑎 𝑎
𝑎22 (1) = 𝑎22 − 𝑎21 (𝑎12 ), 𝑎23 (1) = 𝑎23 − 𝑎21 (𝑎13 ), 𝑏2 = 𝑏2 − 𝑎21 (𝑏1 )
11 11 11
[ (1) 𝑎31 (1) 𝑎31 (1) 𝑎31 ]
𝑎32 = 𝑎32 − 𝑎 (𝑎12 ), 𝑎33 = 𝑎33 − 𝑎 (𝑎 ),
13 𝑏3 = 𝑏3 − 𝑎 (𝑏1 )
11 11 11

Second stage of elimination

We assume 𝒂𝟐𝟐 (𝟏) ≠ 𝟎 . This element 𝒂𝟐𝟐 (𝟏) ≠ 𝟎 in the 𝟐 × 𝟐 position is called the second pivot. We
use this pivot to reduce the element below this pivot in the second column as zero. Multiply the second
row in (3.3.3) by 𝒂𝟑𝟐 (𝟏) / 𝒂𝟐𝟐 (𝟏) and subtract from the third row. That is, we are performing the
elementary row operation 𝑹𝟑 – (𝒂𝟑𝟐 (𝟏) / 𝒂𝟐𝟐 (𝟏) )𝑹𝟐 . We obtain the new augmented matrix as
𝑎11 𝑎12 𝑎13 𝑏1
[ 0 𝑎22 (1) 𝑎23 (1) |𝑏2 (1) ] (3.3.4)
0 0 𝑎33 (2) 𝑏3 (2)
where:
(1) (1)
𝑎 (2) (1) 𝑎 (1)
[ 𝑎33 (2) = 𝑎33 (1) − ( 𝑎32 1 ) (𝑎23 (1) ), 𝑏3 = 𝑏3 − ( 𝑎32 1 ) (𝑏2 )]
22 22

In equation (3.3.4), the element 𝑎33 (2) ≠ 0 is called the third pivot. This system is in the required upper
triangular form [𝑼|𝒛]. The solution vector 𝒙 is now obtained by back substitution.

(𝟐)
From the third row, we get 𝒙𝟑 = 𝒃𝟑 ⁄𝒂𝟑𝟑 (𝟐) .
(𝟏)
(𝒃𝟐 − (𝒂𝟐𝟑 (𝟏) )𝒙𝟑 )
From the second row, we get 𝒙𝟐 = .
𝒂𝟐𝟐 (𝟏)
(𝒃𝟏 – 𝒂𝟏𝟐 𝒙𝟐 – 𝒂𝟏𝟑 𝒙𝟑 )
From the first row, we get 𝒙𝟏 = .
𝒂𝟏𝟏

Remarks 3.3.1:
 When does Gauss elimination method as described above fail? It fails when any one of the pivots is zero
or it is a very small number, as the elimination progresses. If a pivot is zero, then division by it gives over
flow error, since division by zero is not defined. Similarly if a pivot is a very small number, then division
by it introduces large round-off errors and the solution may contain large errors.

For example, we may have the system

2𝑥2 + 5𝑥3 = 7
7𝑥1 + 𝑥2 − 2𝑥3 = 6
2𝑥1 + 3𝑥2 + 82𝑥3 = 13

in which the first pivot is zero.

MTU, Numerical Methods (Menge 2063) Page 6 of 20

In general, using a pivot, all the elements below that pivot in that column are made zeros. Alternately, at
each stage of elimination, we may also make the pivot as 1, by dividing that particular row by the pivot.

Pivoting Procedures
How do we avoid computational errors in Gauss elimination? To avoid computational errors, we follow
the procedure of partial pivoting. In the first stage of elimination, the first column of the augmented matrix
is searched for the largest element in magnitude and brought as the first pivot by interchanging the first
row of the augmented matrix (first equation) with the row (equation) having the largest element in
magnitude. In the second stage of elimination, the second column is searched for the largest element in
magnitude among the n – 1 elements leaving the first element, and this element is brought as the second
pivot by interchanging the second row of the augmented matrix with the later row having the largest
element in magnitude. This procedure is continued until the upper triangular system is obtained. Therefore,
partial pivoting is done after every stage of elimination. There is another procedure called complete
pivoting. In this procedure, we search the entire matrix A in the augmented matrix for the largest element
in magnitude and bring it as the first pivot. This requires not only an interchange of the rows, but also an
interchange of the positions of the variables. It is possible that the position of a variable is changed a

Remark 3.3.2
Gauss elimination method is a direct method. Therefore, it is possible to count the total number of operations, that is, additions,
subtractions, divisions and multiplications. Without going into details, we mention that the total number of divisions and multiplications
(division and multiplication take the same amount of computer time) is 𝑛(𝑛2 + 3𝑛 – 1)/3. The total number of additions and
subtractions (addition and subtraction take the same amount of computer time) is 𝑛(𝑛 – 1)(2𝑛 + 5)/6.
Remark 3.3.3
When the system of algebraic equations is large, how do we conclude that it is consistent or not, using the Gauss elimination method? A
way of determining the consistency is from the form of the reduced system (3.3.4). We know that if the system is inconsistent then rank
(A) ≠ rank [A|b]. By checking the elements of the last rows, conclusion can be drawn about the consistency or inconsistency.
Suppose that in (3.3.4), 𝑎33 (2) ≠ 0 and 𝑏 ≠ 0. Then, rank (A) = rank [A|b] = 3. The system is consistent and has a unique solution.
Suppose that we obtain the reduced system as
𝑎11 𝑎12 𝑎13 𝑏1
(1)
[ 0 𝑎22 (1) 𝑎23 (1) |𝑏2 ]
0 0 0 𝑏3 (2)
Then, rank (A) = 2, rank [A|b] = 3 and rank (A) ≠ rank [A|b]. Therefore, the system is inconsistent and has no solution.
Suppose that we obtain the reduced system as
𝑎11 𝑎12 𝑎13 𝑏1
[ 0 𝑎22 (1) 𝑎23 (1) |𝑏2 (1) ]
0 0 0 0
Then, rank (A) = rank [A|b] = 2 < 3. Therefore, the system has 3 – 2 = 1 parameter family of infinite number of solutions.

MTU, Numerical Methods (Menge 2063) Page 7 of 20

number of times during this pivoting. We need to keep track of the positions of all the variables. Hence,
the procedure is computationally expensive and is not used in any software.

Example 3.3.1:
Solve the system of equations given in example [Link] using the Gauss elimination.
Solution:
The augmented matrix is given by;
1 −3 −4 1
[−1 1 −3|14]
0 1 −3 5
Phase 1: Forward elimination
First stage of elimination:
𝑎 −1
𝑎21 (1) = 𝑎21 – (𝑎21 ) 𝑎11 = −1 − ( 1 ) (1) = 0
11
(1) 𝑎21 −1
𝑎22 = 𝑎22 – (𝑎 ) 𝑎12 = 1 − ( 1 ) (−3) = −2 𝒂
𝑎21
11
−1
≫≫ 𝑹𝟐 (𝟏) = 𝑹𝟐 – (𝒂𝟐𝟏 ) 𝑹𝟏
(1)
𝑎23 = 𝑎23 – (𝑎 ) 𝑎13 = −3 − ( 1 ) (−4) = −7 𝟏𝟏
11
(1) 𝑎 −1
𝑏2 = 𝑏2 – (𝑎21 ) 𝑏1 = 14 − ( 1 ) (1) = 15 }
11

As we can see the value of 𝑎31 = 0, therefore no need to find for 𝑹𝟑 (𝟏)
1 −3 −4 1
[0 −2 −7|15]
0 1 −3 5
Second stage of elimination:
(1)
𝑎 1
𝑎32 (2) = 𝑎32 – (𝑎32 (1)) 𝑎22 = 1 − (−2) (−2) = 0
22
𝑎32 (1) 1 𝒂
𝑎33 (2) = 𝑎33 – (𝑎 (1) ) 𝑎23 = −3 − (−2) (−7) = −13/2 ≫≫ 𝑹𝟑 (𝟐) = 𝑹𝟑 – (𝒂𝟑𝟐 )𝑹𝟐
22 𝟐𝟐
(2) (1) 𝑎32 (1) (1) 1 25
𝑏3 = 𝑏3 – (𝑎 (1) ) 𝑏2 = 5 − (−2) (15) = }
22 2

1 −3 −4 1
[0 −2 −7 | 15 ]
0 0 −13/2 25/2
Phase 2: Back substitution
From the result obtained at second stage of elimination, we can find the value of 𝑥𝑖
13 25
− ( 2 ) 𝑥3 = 2

MTU, Numerical Methods (Menge 2063) Page 8 of 20

 25
𝑥3 = − 13
25
− 2𝑥2 + (−7) (− 13) = 15
10
𝑥2 = − 13

𝑥1 − 3 (−10⁄13) − 4(−25⁄13) = 1
−117
𝑥1 = 13

Example 3.3.2:
Solve the following system of equations using the Gauss elimination without partial pivoting;
𝑥1 + 10𝑥2 − 𝑥3 = 3
2𝑥1 + 3𝑥2 + 20 𝑥3 = 7
10𝑥1 − 𝑥2 + 2 𝑥3 = 4
Solution:
The augmented matrix is given by;
1 10 −1 3
[2 3 20 |7]
10 −1 2 4
Phase 1: Forward elimination
First stage of elimination:
𝑎 2
𝑎21 (1) = 𝑎21 − 𝑎21 (𝑎11 ) = 2 − (1) (1) = 0
11
(1) 𝑎21 2
(1) 𝑎21 𝑎22 = 𝑎22 − 𝑎 (𝑎12 ) = 3 − (1) (10) = −17
𝑅2 = 𝑅2 − 𝑎 (𝑅1 ) ≫≫ 11
11 (1) 𝑎21 2
𝑎23 = 𝑎23 − 𝑎 (𝑎13 ) = 20 − (1) (−1) = 22
11
(1) 𝑎21 2
{ 𝑏2 = 𝑏2 − 𝑎 (𝑏1 ) = 7 − (1) (3) = 1
11

𝑎 10
𝑎31 (1) = 𝑎31 − 𝑎31 (𝑎11 ) = 10 − ( 1 ) (1) = 0
11
𝑎 10
(1) 𝑎31 𝑎32 (1) = 𝑎32 − 𝑎31 (𝑎12 ) = −1 − ( 1 ) (10) = −101
𝑅3 = 𝑅3 − 𝑎 (𝑅1 ) ≫≫ 11
11 (1) 𝑎 10
𝑎33 = 𝑎33 − 𝑎31 (𝑎13 ) = 2 − ( 1 ) (−1) = 12
11
(1) 𝑎31 10
{ 𝑏3 = 𝑏3 − 𝑎 (𝑏1 ) = 4 − ( 1 ) (3) = −26
11

1 10 −1 3
[0 −17 22 | 1 ]
0 −101 12 −26

MTU, Numerical Methods (Menge 2063) Page 9 of 20

Second stage of elimination:
(1)
𝑎 −101
𝑎31 (2) = 𝑎31 (1) − 𝑎32 (1) (𝑎21 (1) ) = 0 − ( −17 ) (0) = 0
22
(1)
𝑎 −101
(2) (1) 𝑎32(1) 𝑎32 (2) = 𝑎32 (1) − 𝑎32 (1) (𝑎22 (1) ) = −101 − ( −17 ) (−17) = 0
𝑅3 = 𝑅3 − 𝑎22 (1)
(𝑅2 (1) ) ≫ 22

(2) (1) 𝑎32 (1) −101

𝑎33 = 𝑎33 − 𝑎22 (1)
(𝑎23 (1) ) = 12 − ( −17 ) (22) = −118.7058
(1)
𝑎 −101
{ 𝑏3 (2) = 𝑏3 (1) − 𝑎32 (1) (𝑏2 (1) ) = −26 − ( −17 ) (1) = −31.941
22

1 10 −1 3
[0 −17 22 | 1 ]
0 0 −118.7058 −31.94
Phase 2: Back substitution
From the result obtained at second stage of elimination, we can find the value of 𝑥𝑖
−118.705𝑥3 = −31.94;
𝑥3 = 0.26908
− 17𝑥2 + 22 (0.26908) = 1
𝑥2 = 0.28939
𝑥1 + 10(0.28939) − (0.26908) = 3
𝑥1 = 0.3751
3.4. Gauss Jordan Elimination
The method is based on the idea of reducing the given system of equations Ax = b, to a diagonal system
of equations Ix = d, where I is the identity matrix, using elementary row operations. We know that the
solutions of both the systems are identical. This reduced system gives the solution vector x. This reduction
is equivalent to finding the solution as x = A–1b.

Gauss−Jordan method
[𝐀|𝐛] → [𝐈 | 𝐗]
In this case, after the eliminations are completed, we obtain the augmented matrix for a 3 × 3 system as
1 0 0 𝑑1
[0 1 0|𝑑2 ] (3.4.1)
0 0 1 𝑑3
and the solution is 𝑥𝑖 = 𝑑𝑖 , 𝑖 = 1, 2, 3.

Elimination procedure:
The first step is same as in Gauss elimination method, that is, we make the elements below the first pivot
as zeros, using the elementary row transformations.

MTU, Numerical Methods (Menge 2063) Page 10 of 20

From the second step onwards, we make the elements below and above the pivots as zeros using the
elementary row transformations. Lastly, we divide each row by its pivot so that the final augmented matrix
is of the form (3.4.1). Partial pivoting can also be used in the solution. We may also make the pivots as 1
before performing the elimination.

Example 3.4.1:
Solve the following system of equations using the Gauss-Jordan method (i) without partial pivoting, (ii)
with partial pivoting.
𝑥1 + 𝑥2 + 𝑥3 = 1
4𝑥1 + 3𝑥2 − 𝑥3 = 6
3𝑥1 + 5𝑥2 + 3𝑥3 = 4
Solution:
(i) Elementary row transformation and eliminations are performed as follow

We have the augmented matrix as

1 1 1 1
[4 3 −1|6]
3 5 3 4
Phase 1: Forward elimination
First stage of elimination:
𝑎 4
𝑎21 (1) = 𝑎21 − 𝑎21 (𝑎11 ) = 4 − (1) (1) = 0
11
(1) 𝑎21 4
(1) 𝑎21 𝑎22 = 𝑎22 − 𝑎 (𝑎12 ) = 3 − (1) (1) = −1
𝑅2 = 𝑅2 − 𝑎 (𝑅1 ) ≫≫ 11 𝑎𝑛𝑑
11 (1) 𝑎21 4
𝑎23 = 𝑎23 − 𝑎 (𝑎13 ) = −1 − ( ) (1) = −5
11 1
(1) 𝑎21 4
{ 𝑏2 = 𝑏2 − 𝑎 (𝑏1 ) = 6 − (1) (1) = 2
11

𝑎 3
𝑎31 (1) = 𝑎31 − 𝑎31 (𝑎11 ) = 3 − (1) (1) = 0
11
(1) 𝑎31 3
(1) 𝑎31 𝑎32 = 𝑎32 − 𝑎 (𝑎12 ) = 5 − (1) (1) = 2
𝑅3 = 𝑅3 − 𝑎 (𝑅1 ) ≫≫ 11
11 (1) 𝑎31 3
𝑎33 = 𝑎33 − 𝑎 (𝑎13 ) = 3 − (1) (1) = 0
11
(1) 𝑎31 3
{ 𝑏3 = 𝑏3 − 𝑎 (𝑏1 ) = 4 − (1) (1) = 1
11

1 1 1 1
[0 −1 −5|2]
0 2 0 1

Second stage of elimination:

MTU, Numerical Methods (Menge 2063) Page 11 of 20

 (1)
𝑎 2
𝑎31 (2) = 𝑎31 (1) − 𝑎32 (1) (𝑎21 (1) ) = 0 − (−1) (0) = 0
22
𝑎32 (1) 2
(2) (1) 𝑎32 (1) (1)
𝑎32 (2) = 𝑎32 (1) − 𝑎 (1) (𝑎22 (1) ) = 2 − (−1) (−1) = 0
𝑅3 = 𝑅3 −𝑎 (1) (𝑅2 ) ≫≫ 22
22 (2) (1) 𝑎32 (1) 2
𝑎33 = 𝑎33 −𝑎 (1) (𝑎23 (1) ) = 0 − (−1) (−5) = −10
22
(2) (1) 𝑎32 (1) (1) 2
{ 𝑏3 = 𝑏3 −𝑎 (1) (𝑏2 ) = 1 − (−1) (2) = 5
22

1 1 1 1
[0 −1 −5 |2]
0 0 −10 5
Phase 2: Backward elimination
Third stage of elimination:
(2)
𝑎 1
𝑎11 (3) = 𝑎11 (2) − 𝑎12 (2) (𝑎21 (2) ) = 1 − (−1) (0) = 1
22
𝑎12 (2) 1
(3) (2) 𝑎12 (2) (2)
𝑎12 (3) = 𝑎12 (2) − 𝑎 (2) (𝑎22 (2) ) = 1 − (−1) (−1) = 0
𝑅1 = 𝑅1 −𝑎 (2) (𝑅2 ) ≫≫ 22
22 (3) (2) 𝑎12 (2) 1
𝑎13 = 𝑎13 −𝑎 (2) (𝑎23 (2) ) = 1 − (−1) (−5) = −4
22
(3) (2) 𝑎12 (2) (2) 1
{ 𝑏1 = 𝑏1 −𝑎 (2) (𝑏2 ) = 1 − (−1) (2) = 3
22

1 0 −4 3
[0 −1 −5 |2]
0 0 −10 5

Fourth stage of elimination:

(3)
𝑎 −4
𝑎11 (4) = 𝑎11 (3) − 𝑎13 (3) (𝑎31 (3) ) = 1 − (−10) (0) = 1
33
(3)
𝑎 −4
(4) (3) 𝑎13(3) 𝑎12 (4) = 𝑎12 (3) − 𝑎13 (3) (𝑎32 (3) ) = 0 − (−10) (0) = 0
𝑅1 = 𝑅1 − 𝑎33 (3)
(𝑅3 (3) ) ≫≫ 33
𝑎13 (3) −4
𝑎13 (4) = 𝑎13 (3) − 𝑎33 (3)
(𝑎33 (3) ) = −4 − (−10) (−10) = 0
(4) (3) 𝑎13 (3) (3) −4
{ 𝑏1 = 𝑏1 − 𝑎33 (3)
(𝑏3 ) = 3 − (−10) (5) = 1

𝑎23 (3) −5
𝑎21 (4) = 𝑎21 (3) − (𝑎31 (3) ) =0−( ) (0) =0
𝑎33 (3) −10
(3)
𝑎 −5
(4) (3) 𝑎23 (3) 𝑎22 (4) = 𝑎22 (3) − 𝑎23 (3) (𝑎32 (3) ) = −1 − (−10) (0) = −1
𝑅2 = 𝑅2 − 𝑎33 (3)
(𝑅3 (3) ) ≫≫ 33
(3)
𝑎 −5
𝑎23 (4) = 𝑎23 (3) − 𝑎23 (3) (𝑎33 (3) ) = −5 − (−10) (−10) = 0
33
(3)
(4) (3) 23 (3) 𝑎 −5
{𝑏2 = 𝑏2 − 𝑎33 (3) (𝑏3 ) = 2 − (−10) (5) = −1/2

MTU, Numerical Methods (Menge 2063) Page 12 of 20

 1 0 0 1
[0 −1 0 |−1/2]
0 0 −10 5
Phase 3: Division of rows by respective Pivots and finalizing the solution
𝑅1 ⁄(1) , 𝑅2 ⁄(−1) , 𝑅3 ⁄(−10)
1 0 0 1
[0 1 0| 1/2 ]
0 0 1 −(1⁄2)
The solution vectors are:

𝒙𝟏 = 𝟏, 𝒙𝟐 = 𝟎. 𝟓, 𝒂𝒏𝒅 𝒙𝟑 = −𝟎. 𝟓

(ii) Elementary row transformation and eliminations are performed as follow

We have the augmented matrix as

1 1 1 1 4 3 −1 6
[4 3 −1|6] , 𝑅1 ↔ 𝑅2 [1 1 1 |1]
3 5 3 4 3 5 3 4
Phase 1: Forward elimination

First stage of elimination:

𝑎21 1
𝑎21 (1) = 𝑎21 − (𝑎11 ) = 1 − ( ) (4) = 0
𝑎11 4
(1) 𝑎21 1 1
𝑎 𝑎22 = 𝑎22 − 𝑎 (𝑎12 ) = 1 − (4) (3) = 4
𝑅2 (1) = 𝑅2 − 𝑎21 (𝑅1 ) ≫≫ 11 𝑎𝑛𝑑
11 (1) 𝑎21 1 5
𝑎23 = 𝑎23 − 𝑎 (𝑎13 ) = 1 − (4) (−1) = 4
11
(1) 𝑎21 1 1
{ 𝑏2 = 𝑏2 − 𝑎11 (𝑏1 ) = 1 − (4) (6) = − 2
𝑎 3
𝑎31 (1) = 𝑎31 − 𝑎31 (𝑎11 ) = 3 − (4) (4) = 0
11
𝑎 3 11
(1) 𝑎31 𝑎32 (1) = 𝑎32 − 𝑎31 (𝑎12 ) = 5 − (4) (3) =
4
𝑅3 = 𝑅3 − (𝑅1 ) ≫≫ 11
𝑎11 (1) 𝑎31 3 15
𝑎33 = 𝑎33 − 𝑎 (𝑎13 ) = 3 − (4) (−1) = 4
11
(1) 𝑎31 3 1
{𝑏3 = 𝑏3 − 𝑎11 (𝑏1 ) = 4 − (4) (6) = − 2
4 3 −1 6
[ 0 1/4 5/4 |−1/2]
0 11/4 15/4 −1/2
Second stage of elimination:
4 3 −1 6
𝑅2 ↔ 𝑅3 [0 11/4 15/4|−1/2]
0 1/4 5/4 −1/2

MTU, Numerical Methods (Menge 2063) Page 13 of 20

 (1) 1
𝑎
𝑎31 (2) = 𝑎31 (1) − 𝑎32 (1) (𝑎21 (1) ) = 0 − ( 11
4
) (0) = 0
22
4
(1) 1
𝑎 1 11
(1)
𝑎32 (2) = 𝑎32 (1) − 𝑎32 (1) (𝑎22 (1) ) = 4 − ( ) ( 4 ) = 0 4
11
𝑎 22
𝑅3 (2) = 𝑅3 (1) − 𝑎32 (1) (𝑅2 (1) ) ≫≫ 4
1
22 (1)
𝑎 15 10
𝑎33 (2) = 𝑎33 (1) − 𝑎32 (1) (𝑎23 (1) ) = 5/4 − ( 11
4
) ( 4 ) = 11
22
4
(1) 1
(2) (1) 𝑎 (1) 1 1 5
𝑏3 = 𝑏3 − 𝑎32 (1) (𝑏2 4
) = − 2 − ( ) (− 2) = − 11
11
{ 22
4

4 3 −1 6
[0 11/4 15/4 | −1/2 ]
0 0 10/11 −5/11
Phase 2: Backward elimination
Third stage of elimination:

𝑎 (2) 3
𝑎11 (3) = 𝑎11 (2) − 𝑎12 (2) (𝑎21 (2) ) = 4 − ( 11 ) (0) = 4
22
4
(2)
𝑎 3 11
(2)
𝑎12 (3) = 𝑎12 (2) − 𝑎12 (2) (𝑎22 (2) ) = 3 − ( 11 ) ( 4 ) = 0
𝑎 22
𝑅1 (3) = 𝑅1 (2) − 𝑎12 (2) (𝑅2 (2) ) ≫≫ 4
22 (2)
𝑎 3 15 56
𝑎13 (3) = 𝑎13 (2) − 𝑎12 (2) (𝑎23 (2) ) = −1 − ( 11 ) ( 4 ) = − 11
22
4
(2)
(3) (2) 𝑎 (2) 3 1 72
𝑏1 = 𝑏1 − 𝑎12 (2) (𝑏2 ) = 6 − ( 11 ) (− 2) = 11
{ 22
4

4 0 −56/11 72/11
[0 11/4 15/4 | −1/2 ]
0 0 10/11 −5/11
Fourth stage of elimination:
(3)
𝑎 −56/11
𝑎11 (4) = 𝑎11 (3) − 𝑎13 (3) (𝑎31 (3) ) = 4 − ( 10/11 ) (0) = 4
33
(3)
𝑎 −56/11
𝑎12 (4) = 𝑎12 (3) − 𝑎13 (3) (𝑎32 (3) ) = 0 − ( 10/11 ) (0) = 0
(3) 33
𝑎
𝑅1 (4) = 𝑅1 (3) − 𝑎13 (3) (𝑅3 (3) ) ≫≫ 𝑎 (3) 56 −
56
33
𝑎13 (4) = 𝑎13 (3) − 𝑎13 (3) (𝑎33 (3) ) = − 11 − ( 11
10 ) (10/11) = 0
33
11
56
(4) (3) 𝑎13 (3) (3) 72 −
11 5
𝑏1 = 𝑏1 − 𝑎33 (3)
(𝑏3 ) = 11
− ( 10 ) (− 11) = 4
{ 11

MTU, Numerical Methods (Menge 2063) Page 14 of 20

 15
𝑎23 (3)
(4)
𝑎21 = 𝑎21 −(3)
(𝑎31 ) = 0 − ( 4 ) (0) = 0
(3)
𝑎33 (3) 10
11
15
𝑎23 (3) 11
(4)
𝑎22 = 𝑎22 − (3)
(𝑎32 ) = 11/4 − ( 4 ) (0) =
(3)
𝑎33 (3) 10 4
𝑎23 (3) 11
𝑅2 (4) = 𝑅2 (3) − (𝑅3
(3)
) ≫≫
𝑎33 (3) 15
𝑎23 (3) 15 10
(4)
𝑎23 = 𝑎23 − (3) (3)
(𝑎33 ) = − ( 4 )( ) = 0
𝑎33 (3) 4 10 11
11
15
𝑎23 (3) 5 11
𝑏2 (4) = 𝑏2 (3) − (𝑏3 ) = −1/2 − ( 4 ) (− ) =
(3)
𝑎33 (3) 10 11 8
{ 11
4 0 0 4
[0 11/4 0 | 11/8 ]
0 0 10/11 −5/11
Phase 3: Division of rows by respective Pivots and finalizing the solution
𝑅1 ⁄(4) , 𝑅2 ⁄(11/4) , 𝑅3 ⁄(10/11)
1 0 0 1
[0 1 0| 1/2 ]
0 0 1 −(1⁄2)
Therefore the solution vectors are:

𝒙𝟏 = 𝟏, 𝒙𝟐 = 𝟎. 𝟓, 𝒂𝒏𝒅 𝒙𝟑 = −𝟎. 𝟓

3.5. LU Decomposition
In many applications where linear systems appear, one needs to solve Ax = b for many different vectors
b. For instance, a structure must be tested under several different loads, not just one.

Gaussian elimination with pivoting is the most efficient and accurate way to solve a linear system. Most
of the work in this method is spent on the matrix [𝐴] itself. If we need to solve several different systems
with the same [𝐴], and [𝐴] is big, then we would like to avoid repeating the steps of Gaussian elimination
on [𝐴] for every different {𝑏}. This can be accomplished by the LU decomposition, which in effect records
the steps of Gaussian elimination.

What we will do is show that we can decompose the matrix 𝑨 into the product of a lower triangular and
an upper triangular matrix:
𝐴 = 𝐿𝑈 (3.5.1)
This allows us to solve linear systems by, instead, solving two triangular systems:

MTU, Numerical Methods (Menge 2063) Page 15 of 20

 𝐴𝑥 = 𝑏 => 𝑈𝑥 = 𝑦, 𝑤ℎ𝑒𝑟𝑒 𝐿𝑦 = 𝑏 (3.5.2)
Thus, we first solve Ly = b and then Ux = y to get the solution
This shows that we can solve linear systems by (a) computing the LU factorization of A; then solving
appropriate lower and upper triangular systems. An example might be useful at this point. The main idea
of the LU decomposition is to record the steps used in Gaussian elimination on A in the places where the
zero is produced. Consider the matrix:

1 −2 3
𝐴 = (2 −5 12 )
0 2 −10
The first step of Gaussian elimination is to subtract 2 times the first row from the second row. In order to
record what we have done, we will put the multiplier, 2, into the place it was used to make a zero, i.e. the
second row, first column. In order to make it clear that it is a record of the step and not an element of A,
we will put it in parentheses. This leads to:

1 −2 3
((2) −1 6 )
0 2 −10
There is already a zero in the lower left corner, so we don’t need to eliminate anything there. We record
this fact with a (0). To eliminate the third row, second column, we need to subtract −2 times the second
row from the third row. Recording the −2 in the spot we have:
1 −2 3
((2) −1 6)
(0) (−2) 2
Let 𝑈 be the upper triangular matrix produced, and let 𝐿 be the lower triangular matrix with the records
and ones on the diagonal, i.e.:
1 0 0 1 −2 3
𝐿 = (2 1 0) 𝑎𝑛𝑑 𝑈 = (0 −1 6)
0 −2 1 0 0 2
Then we have the following mysterious coincidence:
1 0 0 1 −2 3 1 −2 3
𝐿𝑈 = (2 1 0) (0 −1 6) = (2 −5 12 ) = 𝐴
0 −2 1 0 0 2 0 2 −10
Thus we see that 𝐴 is actually the product of 𝐿 and 𝑈. Here 𝐿 is lower triangular and 𝑈 is upper triangular.
When a matrix can be written as a product of simpler matrices, we call that a decomposition of 𝐴 and this
one we call the 𝐿𝑈 decomposition.

Example 3.5.1:

MTU, Numerical Methods (Menge 2063) Page 16 of 20

Solve the system of equation shown in Example 3.4.1, using LU decomposition;
𝑥1 + 𝑥2 + 𝑥3 = 1
4𝑥1 + 3𝑥2 − 𝑥3 = 6
3𝑥1 + 5𝑥2 + 3𝑥3 = 4
Solution:
1 1 1
𝐴 = (4 3 −1) 𝑎𝑛𝑑 𝑏 𝑇 = (1 6 4)
3 5 3
𝑅2 (1) = 𝑅2 − (4⁄1)𝑅1 . Therefor multiplier (4), will be saved but only for row two column one;

𝑅3 (1) = 𝑅3 − (3⁄1)𝑅1 . Here also multiplier (3), will be saved but only for row three column one;
𝑎21 4
𝑎21 (1) = 𝑎21 − (𝑎11 ) = 4 − ( ) (1) = (4)
𝑎11 1
(1) 𝑎21 (1) 𝑎21 4
𝑅2 = 𝑅2 − 𝑎 (𝑅1 ) ≫≫ 𝑎22 = 𝑎22 − 𝑎 (𝑎12 ) = 3 − (1) (1) = −1 𝑎𝑛𝑑
11 11
𝑎 4
𝑎23 (1) = 𝑎23 − 𝑎21 (𝑎13 ) = −1 − (1) (1) = −5
{ 11

𝑎 3
𝑎31 (1) = 𝑎31 − 𝑎31 (𝑎11 ) = 3 − (1) (1) = (3)
11
(1) 𝑎31 (1) 𝑎31 3
𝑅3 = 𝑅3 − 𝑎 (𝑅1 ) ≫≫ 𝑎32 = 𝑎32 − 𝑎 (𝑎12 ) = 5 − (1) (1) = 2
11 11
𝑎 3
𝑎33 (1) = 𝑎33 − 𝑎31 (𝑎13 ) = 3 − (1) (1) = 0
{ 11

1 1 1
((4) −1 −5)
(3) 2 0

2
𝑅3 (2) = 𝑅3 (1) − (−1) 𝑅1 (1) . Here the multiplier (-2), will be saved but only for row three column two;
(1)
𝑎 2
𝑎31 (2) = 𝑎31 (1) − 𝑎32 (1) (𝑎21 (1) ) = 0 − (−1) (0) = (3)
22
(1) (1)
𝑎 𝑎 2
𝑅3 (2) = 𝑅3 (1) − 𝑎32 (1) (𝑅2 (1) ) ≫ 𝑎32 (2) = 𝑎32 (1) − 𝑎32 (1) (𝑎22 (1) ) = 2 − (−1) (−1) = (−2)
22 22

(2) 𝑎32 (1) 2

{ 𝑎33 = 𝑎33 (1) − 𝑎 (1) (𝑎23 (1) ) = 0 − (−1) (−5) = −10
22
1 1 1
((4) −1 −5 )
(3) (−2) −10

From the above result, the matrix 𝐴 is decomposed to lower and upper triangular as follow;
Let 𝑈 be the upper triangular matrix produced, and let 𝐿 be the lower triangular matrix with the records
and ones on the diagonal

MTU, Numerical Methods (Menge 2063) Page 17 of 20

 1 0 0 1 1 1
𝐿 = (4 1 0) 𝑎𝑛𝑑 𝑈 = (0 −1 −5 )
3 −2 1 0 0 −10
From equation (3.5.2), we have
1 1 0 0 𝑦1 1
𝐿𝑦 = 𝑏, Recall: 𝑏 = (6) ≫≫ (4 1 0) (𝑦2 ) = (6)
4 3 −2 1 𝑦3 4

𝑦1 = 1, 𝑦2 = 2, 𝑎𝑛𝑑 𝑦3 = 5

Similarly from equation (3.5.2), we have;

1 1 1 𝑥1 1
𝑈𝑥 = 𝑦 ≫≫ (0 −1 −5 ) (𝑥2 ) = (2)
0 0 −10 𝑥3 5

𝑥1 = 1, 𝑥2 = 0.5, 𝑎𝑛𝑑 𝑥3 = −0.5

3.6. Gauss-Seidel Method
All of the methods discussed above to solve system of equations are direct method, and Gauss Seidel
method is an iterative approach to solve systems of linear equation.
Gauss-Seidel Iteration Method use the updated values of 𝑥1 , 𝑥2 . . . , 𝑥𝑖−1 in computing the value of the
variable xi. We assume that the pivots 𝑎𝑖𝑖 ≠ 0, for all i. We write the equations as;

𝑎11 𝑥1 = 𝑏1 – (𝑎12 𝑥2 + 𝑎13 𝑥3 )

𝑎22 𝑥2 = 𝑏2 – (𝑎21 𝑥1 + 𝑎23 𝑥3 )
𝑎33 𝑥3 = 𝑏3 – (𝑎31 𝑥1 + 𝑎32 𝑥2 )

The Gauss-Seidel iteration method is defined as;

1
𝑥1 (𝑘+1) = [𝑏1 – (𝑎12 𝑥2 (𝑘) + 𝑎13 𝑥3 (𝑘) )]
𝑎11
1
𝑥2 (𝑘+1) = [𝑏2 – (𝑎21 𝑥1 (𝑘+1) + 𝑎23 𝑥3 (𝑘) )]
𝑎22 (3.6.1)
(𝑘+1) 1 (𝑘+1) (𝑘+1)
𝑥3 = [𝑏3 – (𝑎31 𝑥1 + 𝑎32 𝑥2 )]
𝑎33
𝑤ℎ𝑒𝑟𝑒 𝑘 = 0,1,2, . . . ⇝ 𝑁𝑜 𝑜𝑓 𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛

MTU, Numerical Methods (Menge 2063) Page 18 of 20

 Remark:
A sufficient condition for convergence of the Gauss-Seidel method is that the system of equations is diagonally dominant,
that is, the coefficient matrix A is diagonally dominant. This implies that convergence may be obtained even if the system
is not diagonally dominant. If the system is not diagonally dominant, we may exchange the equations, if possible, such that
the new system is diagonally dominant and convergence is guaranteed. The necessary and sufficient condition for
convergence is that the spectral radius of the iteration matrix 𝑯 is less than one unit, that is, 𝜌(𝑯) < 1, where 𝜌(𝑯) is
the largest Eigen value in magnitude of 𝑯. Testing of this condition is beyond the scope of the syllabus.

Example 3.6.1: Find the solution of the system of equations correct to three decimal places, using the
Gauss-Seidel iteration method.

45𝑥1 + 2𝑥2 + 3𝑥3 = 58

– 3𝑥1 + 22𝑥2 + 2𝑥3 = 47
5𝑥1 + 𝑥2 + 20𝑥3 = 67

Solution:

The given system of equations is strongly diagonally dominant. Hence, we can expect fast convergence.
Gauss-Seidel method gives the iteration
1
𝑥1 (𝑘+1) = [58 – 2𝑥2 (𝑘) − 3𝑥3 (𝑘) ]
45
1
𝑥2 (𝑘+1) = [47 + 3𝑥1 (𝑘+1) − 2𝑥3 (𝑘) ]
22 (3.6.1)
(𝑘+1) 1 (𝑘+1) (𝑘+1)
𝑥3 = [67 – 5𝑥1 − 𝑥2 ]
20
𝑤ℎ𝑒𝑟𝑒 𝑘 = 0,1,2, . . . ⇝ 𝑁𝑜 𝑜𝑓 𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛

Starting with 𝑥1 (0) = 0, 𝑥2 (0) = 0, 𝑎𝑛𝑑 𝑥3 (0) = 0, we get the following results;
First iteration: k =0
1 1
𝑥1 (1) = [58 – 2(𝑥2 (0) ) − 3𝑥3 (0) ] = 45 (58) = 1.28889
45
1 1
𝑥2 (1) = [47 + 3(𝑥1 (1) ) − 2𝑥3 (0) ] = 22 (47 + 3(1.28889) − 0) = 2.31212
22
1 1
𝑥3 (1) = [67 − 5(𝑥1 (1) ) − 𝑥2 (1) ] = 20 (67 − 5(1.28889) − (2.31212)) = 2.91217
20

Second iteration: k =1
1 1
𝑥1 (2) = [58 – 2(𝑥2 (1) ) − 3𝑥3 (1) ] = 45 [58 – 2(2.31212) − 3(2.91217)] = 0.99198
45
1 1
𝑥2 (2) = [47 + 3(𝑥1 (2) ) − 2𝑥3 (1) ] = 22 [47 + 3(0.99198) − 2(2.91217)] = 2.00689
22
1 1
𝑥3 (2) = [67 – 5(𝑥1 (2) ) − 𝑥2 (2) ] = 20 [67 – 5(0.99198) − (2.00689)] = 3.00166
20

MTU, Numerical Methods (Menge 2063) Page 19 of 20

Third iteration: k =2
1 1
𝑥1 (3) = [58 – 2(𝑥2 (2) ) − 3𝑥3 (2) ] = 45 [58 – 2(2.000689) − 3(3.00166)] = 0.99958
45
1 1
𝑥2 (3) = [47 + 3(𝑥1 (3) ) − 2𝑥3 (2) ] = 22 [47 + 3(0.99958) − 2(3.00166)] = 1.99979
22
1 1
𝑥3 (3) = [67 – 5(𝑥1 (3) ) − 𝑥2 (3) ] = 20 [67 – 5(0.99958) − (1.99979)] = 3.0001155
20

Fourth iteration: k =3

1 1
𝑥1 (4) = [58 – 2(𝑥2 (3) ) − 3𝑥3 (3) ] = 45 [58 – 2(1.99979) − 3(3.000155)] = 0.999999
45
1 1
𝑥2 (4) = [47 + 3(𝑥1 (4) ) − 2𝑥3 (3) ] = 22 [47 + 3(0.999999) − 2(3.00155)] = 1.99998
22

1 1
𝑥3 (4) = [67 – 5(𝑥1 (4) ) − 𝑥2 (4) ] = 20 [67 – 5(0.99999) − (1.99998)] = 3.00000125
20

We find;
|𝑥1 (4) − 𝑥1 (3) | = |0.99999 − 0.99958| = 0.00041
|𝑥2 (4) − 𝑥2 (3) | = |1.99998 − 1.99979| = 0.00019
|𝑥3 (4) − 𝑥3 (3) | = |3.00000125 − 3.0001155| = 0.000114
Since, all the errors in magnitude are less than 0.0005, the required solution is
𝑥1 = 1.0 𝑥2 = 1.99999, and 𝑥3 = 3.0.
Rounding to three decimal places, we get 𝑥1 = 1.0 𝑥2 = 2.0, and 𝑥3 = 3.0

Exercise 3.6.1
Compute problem given in Example 3.5.1, using Gauss-Seidel method

MTU, Numerical Methods (Menge 2063) Page 20 of 20