Engineering College Chemical Engineering Dept.

Chapter -3-
Direct Methods for Solving Linear Systems
3.1 Introduction
Linear systems of equations are associated with many problems in engineering and science,
as well as with applications of mathematics to the social sciences and the quantitative study
of business and economic problems.
A linear system of n equations in n unknowns 𝑥1 , 𝑥2 , … , 𝑥𝑛 is a set of equations
𝐸1 , 𝐸2 , … , 𝐸𝑛 of the form
𝐸1 : 𝑎11 𝑥1 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1
𝐸2 : 𝑎21 𝑥1 + ⋯ + 𝑎2𝑛 𝑥𝑛 = 𝑏2
(1)
… … … … … … … … … … … … … … ..
𝐸𝑛 : 𝑎𝑛1 𝑥1 + ⋯ + 𝑎𝑛𝑛 𝑥𝑛 = 𝑏𝑛
where the coefficients 𝑎𝑗𝑘 , & 𝑏𝑗 re given numbers. The system is called homogeneous
if all the 𝑏𝑗 are zero; otherwise, it is called nonhomogeneous. Using matrix multiplication
the equation (1) will be written as a single vector equation
𝐴𝑥 = 𝑏 (2)
Where
𝑎11 𝑎12 … 𝑎1𝑛 𝑥1 𝑏1
𝑎21 𝑎22 … 𝑎2𝑛 𝑥2 𝑏
𝐴=[… … … … ], 𝑎𝑛𝑑 𝑥 = [ … ] , 𝑎𝑛𝑑 𝑏 = [ 2 ]
…
𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑛 𝑥𝑛 𝑏𝑛
he following matrix 𝐴̃ is called the augmented matrix of the system (1):
𝑎11 𝑎12 … 𝑎1𝑛 𝑏1
𝑎 𝑎22 … 𝑎2𝑛 𝑏2
𝐴̃ = [𝐴 𝑏] = [ 21 ]
… … … … …
𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑛 𝑏𝑛

19
Engineering College Chemical Engineering Dept.

3.2 Gauss Elimination

This standard method for solving linear systems (1) is a systematic process of elimination
that reduces (1) to triangular form because the system can then be easily solved by back
substitution.

𝑎11 𝑎12 … 𝑎1𝑛 𝑏1

𝑎 𝑎22 … 𝑎2𝑛 𝑏2
𝐴̃ = [𝐴 𝑏] = [ 21 ]
… … … … …
𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑛 𝑏𝑛
Will be
𝑎11 𝑎12 … 𝑎1𝑛 𝑏1
0 𝑎22 … 𝑎2𝑛 𝑏2
𝐴̃ = [ ]
⋮ ⋮ ⋮ ⋮ ⋮
0 0 … 𝑎𝑛𝑛 𝑏𝑛

backward substitution can be performed. Solving the nth equation for xn gives
𝑏𝑛
𝑥𝑛 =
𝑎𝑛𝑛
Solving the n-1th equation for xn-1 gives
𝑏𝑛 − 𝑎𝑛−1,𝑛 𝑥𝑛
𝑥𝑛−1 =
𝑎𝑛−1,𝑛−1

20
Engineering College Chemical Engineering Dept.

The general form for solution

𝑏𝑖 − ∑𝑛𝑗=𝑖+1 𝑎𝑖𝑗 𝑥𝑗
𝑥𝑖 =
𝑎𝑖,𝑖

Example 1: Solve the system

𝐸1 : 8 𝑥2 + 2 𝑥3 = −7
𝐸2 : 3𝑥1 + 5 𝑥2 + 2 𝑥3 = 8
𝐸3 : 6𝑥1 + 2 𝑥2 + 8 𝑥3 = 26
Solution.
𝐸1 : 6𝑥1 + 2 𝑥2 + 8 𝑥3 = 26
𝐸2 : 3𝑥1 + 5 𝑥2 + 2 𝑥3 = 8
𝐸3 : 8 𝑥2 + 2 𝑥3 = −7
Elimination of 𝑥1 from 𝐸2
6 2 8 26
1
𝐴(1) = [3 5 2| 8 ] now (𝐸2 − ∗ 𝐸1 ) → 𝐸2
2
0 8 2 −7
Elimination of 𝑥2 from 𝐸3

6 2 8 26
(2)
𝐴 = [0 4 −2|−5] (𝐸3 − 2 ∗ 𝐸2 ) → 𝐸3
0 8 2 −7
6 2 8 26
𝐴(3) = [0 4 −2|−5]
0 0 6 3
Back substitution. Determination of 𝑥1 , 𝑥2 , 𝑥3
3 1
𝑥3 = =
6 2

21
Engineering College Chemical Engineering Dept.

1 1
4𝑥2 − 2𝑥3 = −5 → 𝑥2 = ∗ (−5 + 2 ∗ ) = −1
4 2
1 1
6𝑥1 + 2𝑥2 + 8𝑥3 = 26 → 𝑥1 = (26 − (2 ∗ −1) − 8 ∗ ) = 4
6 2
Example 2: Solve the system
𝐸1 : 𝑥1 + 𝑥2 + 3 𝑥4 = 4 ,
𝐸2 : 2𝑥1 + 𝑥2 − 𝑥3 + 𝑥4 = 1,
𝐸3 : 3𝑥1 − 𝑥2 − 𝑥3 + 2𝑥4 = −3,
𝐸4 : − 𝑥1 + 2 𝑥2 + 3𝑥3 − 𝑥4 = 4
Sol.
1 1 0 3 4
2 1 −1 1 1
𝐴(1) =[ | ]
3 −1 −1 2 −3
−1 2 3 −1 4
Elimination of 𝑥1
(𝐸2 − 2 ∗ 𝐸1 ) → 𝐸2
(𝐸3 − 3 ∗ 𝐸1 ) → 𝐸3
(𝐸4 + 𝐸1 ) → 𝐸4
1 1 0 3 4
0 −1 −1 −5 −7
𝐴(2) =[ | ]
0 −4 −1 −7 −15
0 3 3 2 8
Elimination of 𝑥2
(𝐸3 − 4 ∗ 𝐸2 ) → 𝐸3
(𝐸4 + 3 ∗ 𝐸2 ) → 𝐸4
1 1 0 3 4
0 −1 −1 −5 −7
𝐴(3) =[ | ]
0 0 3 13 13
0 0 0 −13 −13
Back substitution. Determination of 𝑥1 , 𝑥2 , 𝑥3 & 𝑥4
22
Engineering College Chemical Engineering Dept.

−13 𝑥4 = −13 → 𝑥4 = 1
3𝑥3 + 13 𝑥4 = 13 → 𝑥3 = 0
−𝑥2 − 𝑥3 − 5 𝑥4 = −7 → 𝑥2 = 2
𝑥1 + 𝑥2 + 3 𝑥4 = 4 → 𝑥1 = −1

3.3 Pivoting Strategies

In deriving the Gaussian elimination method, we found that a row interchange is needed
when one of the pivot elements, 𝑎𝑖,𝑖 is zero. This row interchange has the form (Ei) ↔ (Ep),
where p is the smallest integer greater than i with 𝑎𝑝𝑖 ≠ 0. To reduce the round-off error
associated with finite-digit arithmetic, it is often necessary to perform row interchanges
even when the pivot elements are not zero.

𝑎𝑖𝑖 is small in magnitude compared to 𝑎𝑗𝑖 , the magnitude of the multiplier

𝑎𝑗𝑖
𝑚𝑗𝑖 =
𝑎𝑖𝑖
will be much larger than 1. A round-off error introduced in the computation of one of the
terms 𝑎𝑖𝑙 is multiplied by 𝑚𝑗𝑖 when computing 𝑎𝑗𝑖 , compounding the original error. Also,
when performing the backward substitution for
𝑏𝑖 − ∑𝑛𝑗=𝑖+1 𝑎𝑖𝑗 𝑥𝑗
𝑥𝑖 =
𝑎𝑖,𝑖
with a small value of 𝑎𝑖𝑖 , any round-off error in the numerator is dramatically increased
when dividing by 𝑎𝑖𝑖 .
Example 3: Solve the system
𝐸1 : 0.003𝑥1 + 59.14𝑥2 = 59.17 ,
𝐸2 : 5.921 𝑥1 − 6.31𝑥2 = 46.78,
Sol.
The exact solution for this system 𝑥1 = 10.00 , & 𝑥2 = 1.000

23
Engineering College Chemical Engineering Dept.

Suppose Gaussian elimination is performed on this system using four-digit arithmetic

with rounding.
0.003 59.14 59.17
𝐴(1) = [ | ]
5.291 −6.13 46.78
𝑎21 5.291
𝑚21 = = = 1763.66
𝑎11 0.003
And for Performing (𝐸2 − 𝑚21 ∗ 𝐸1 ) → 𝐸2 and the appropriate rounding gives
0.003 59.14 59.17
𝐴(2) = [ | ]
0 −104300 −104400
instead of the precise values
0.003 59.14 59.17
𝐴(2) = [ | ]
0 −104309.376 −104309.376
The introduced round-off error, but the error has not yet been propagated. Backward
substitution yields
𝑥2 ≈ 1.001
which is a close approximation to the actual value, 𝑥2 = 1. However, because
of the small pivot 𝑎11 = 0.003
59.18 − 59.14 ∗ 1.001
𝑥𝑖 = = −10.00
0.003
This ruins the approximation to the actual value 𝑥1 = 10.00 (see fig below)

24
Engineering College Chemical Engineering Dept.

This is clearly a contrived example and the graph demonstrate why the error can so easily
occur, but for only slightly larger systems it is much more difficult to predict in advance
when devastating round-off error can occur.
The simplest strategy is to select, at the ith step, the element in the same column that is
below the diagonal and has the largest absolute value; that is, to determine the smallest
p≥ i such that
|𝑎𝑝𝑖 | = max |𝑎𝑘𝑖 |
𝑖≤𝑘≤𝑛

and perform (Ei) ↔(Ep). In this case no interchange of columns is used.

Example 3: Solve the system
𝐸1 : 0.003𝑥1 + 59.41𝑥2 = 59.17 ,
𝐸2 : 5.921 𝑥1 − 6.31𝑥2 = 46.78,
𝑠𝑜𝑙
max{|𝑎11 |, |𝑎21 |} = max{|0.003|, |5.291|} = |5.291|
The operation (E2) ↔(E1) is then performed to give the system
𝐸1 : 5.921 𝑥1 − 6.31𝑥2 = 46.78,
𝐸2 : 0.003𝑥1 + 59.41𝑥2 = 59.17 ,
𝑎21 0.003
𝑚21 = = = 0.000567
𝑎11 5.291
(𝐸2 − 𝑚21 ∗ 𝐸1 ) → 𝐸2
5.291 −6.13 46.78
𝐴(2) = [ | ]
0 59.14 59.14
Back substitution. Determination of 𝑥1 , 𝑥2
59.14
𝑥2 = =1
59.14
46.78 + 6.13 52.91
𝑥1 = = = 10
5.291 5.921

25
Engineering College Chemical Engineering Dept.

Note:
1- The technique just described is called partial pivoting, or maximal column Pivoting.
2- Although partial pivoting is sufficient for many linear systems, situations do arise when
it is inadequate.
3.3.1 scaled partial pivoting
The first step in this procedure is to define a scale factor sP for each row:
𝑆𝑘 = max |𝑎𝑘𝑗 |
𝑖≤𝑘≤𝑛

The appropriate row interchange to place zeros in the first column is determined by
choosing the first integer p with
𝑎𝑝1 |𝑎𝑘1 |
= max
𝑆𝑝 𝑖≤𝑘≤𝑛 𝑆𝑘

and performing (E1)↔(Ep). The effect of scaling is to ensure that the largest element in
each row has a relative magnitude of 1 before the comparison for row interchange is
performed.
In a similar manner, before eliminating variable xi using the operations
Ek −mkiEi → Ek for k = i +1,...,n
we select the smallest integer p ≥ i with
𝑎𝑝𝑖 |𝑎𝑘𝑖 |
= max
𝑆𝑝 𝑖≤𝑘≤𝑛 𝑆𝑘

and perform the row interchange Ei ↔ Ep if i = p.

Example 4: Solve the system
𝐸1 : 30𝑥1 + 594100𝑥2 = 591700 ,
𝐸2 : 5.921 𝑥1 − 6.31𝑥2 = 46.78,
𝑠𝑜𝑙
𝑆1 = {|30|, |594100|} = 591400 & 𝑆2 = {|5.291|, |6.31|} = 6.31
𝑎11 30 𝑎21 5.291
Consequently, = = 0.5073 ∗ 10−4 𝑎𝑛𝑑 = = 0.8631
𝑆1 591400 𝑆2 6.13

and the interchange (E1) ↔ (E2) is made.

26
Engineering College Chemical Engineering Dept.

𝐸1 : 5.921 𝑥1 − 6.31𝑥2 = 46.78,

𝐸2 : 30𝑥1 + 594100𝑥2 = 591700 ,
5.291 −6.31 46.78
𝐴(1) = [ | ]
30 591400 597100
𝑎21 30
𝑚21 = = = 5.67
𝑎11 5.291
(𝐸2 − 𝑚21 ∗ 𝐸1 ) → 𝐸2
5.291 −6.13 46.78
𝐴(2) = [ | ]
0 591435.7 596834.7
Back substitution. Determination of 𝑥1 , 𝑥2
596834.7
𝑥2 = ≈1
591435.7
46.78 + 6.13 52.91
𝑥1 = = = 10
5.291 5.921
Example 5: Solve the system
𝐸1 : 2.11𝑥1 − 4.21𝑥2 + 0.921 𝑥3 = 2.01 ,
𝐸2 : 4.01 𝑥1 + 10.2 𝑥2 −1.12 𝑥3 = −3.09,
𝐸2 : 1.09 𝑥1 + 0.987 𝑥2 + 0.832 𝑥3 = 4.21,
𝑠𝑜𝑙
2.11 −4.21 0.921 2.01
𝐴(1) = [4.01 10.2 −1.12|−3.09]
1.09 0.987 0.832 4.21

𝑆1 = 4.21, 𝑆2 = 10.2, & 𝑆3 = 1.09

𝑎11 2.11 𝑎21 4.01 𝑎31 1.09

Consequently, = = 0.501 𝑎𝑛𝑑 = = 0.393 𝑎𝑛𝑑 = =1
𝑆1 4.21 𝑆2 10.2 𝑆3 1.09
𝑎31
Since the largest one, and the interchange (E1) ↔ (E3) is made.
𝑆3

27
Engineering College Chemical Engineering Dept.

1.09 0.987 0.832 4.21

(1)
𝐴 = [4.01 10.2 −1.12|−3.09]
2.11 −4.21 0.921 2.01
𝑎21 4.01 𝑎31 2.11
𝑚21 = = , & 𝑚31 = =
𝑎11 1.09 𝑎11 1.09
(𝐸2 − 𝑚21 ∗ 𝐸1 ) → 𝐸2 & (𝐸3 − 𝑚31 ∗ 𝐸1 ) → 𝐸3
1.09 0.987 0.832 4.21
(2)
𝐴 = [ 0 6.57 −4.18 |−18.6]
0 −6.12 −0.689 −6.16

𝑎21 6.57 𝑎31 6.12

= = 0.644 < = = 1.45
𝑆2 10.2 𝑆3 4.21
the interchange (E2) ↔ (E3) is made
1.09 0.987 0.832 4.21
(2)
𝐴 = [ 0 −6.12 −0.689|−6.16]
0 6.57 −4.18 −18.6
𝑎32 6.57
𝑚32 = =
𝑎22 −6.12
(𝐸3 − 𝑚32 ∗ 𝐸2 ) → 𝐸3
1.09 0.987 0.832 4.21
(3)
𝐴 = [ 0 −6.12 −0.689|−6.16]
0 0 −4.92 −25.2

Back substitution. Determination of 𝑥1 , 𝑥2 &𝑥3

𝑥1 = −0.431, 𝑥2 = 0.43 &𝑥3 = 5.12

28
Engineering College Chemical Engineering Dept.

3.4 Gauss-Jordan Elimination Method

In this method instead of transforming the coefficient matrix into upper or lower triangular
system, we transform the coefficient matrix into diagonal (in particular identity) matrix
using elementary row operations.
𝐸1 : 𝑎11 𝑥1 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1
𝐸2 : 𝑎21 𝑥1 + ⋯ + 𝑎2𝑛 𝑥𝑛 = 𝑏2
… … … … … … … … … … … … … … ..
𝐸𝑛 : 𝑎𝑛1 𝑥1 + ⋯ + 𝑎𝑛𝑛 𝑥𝑛 = 𝑏𝑛
𝑎11 𝑎12 … 𝑎1𝑛 𝑏1
𝑎 𝑎22 … 𝑎2𝑛 𝑏2
𝐴̃ = [𝐴 𝑏] = [ 21 ]
… … … … …
𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑛 𝑏𝑛
Will be
1 0 … 0 𝑏𝑖
0 1 … 0 𝑏𝑖+1
𝐴̃ = [ ]
⋮ ⋮ ⋮ ⋮ ⋮
0 0 … 1 𝑏𝑛+1
Example6. Solve the following linear system using Gauss-Jordan elimination method
3 𝑥1 + 4𝑥2 + 3 𝑥3 = 10
𝑥1 + 5𝑥2 − 𝑥3 = 7
6𝑥1 + 3𝑥2 + 7𝑥3 = 15
Sol.
3 4 3 10
(1)
𝐴 = [1 5 −1| 7 ]
6 3 7 15
1
∗ 𝐸 → 𝐸1
3 1
4 10
1 1
3
𝐴(2) = [ |3 ]
1 5 −1 7
6 3 7 15
29
Engineering College Chemical Engineering Dept.

𝐸2 − 𝐸1 → 𝐸2 & 𝐸3 − 6 ∗ 𝐸1 → 𝐸3
4 10
1 1
3 3
𝐴(3) = 11 | 11
0 −2
3 3
[0 −5 1 −5]
3
∗ 𝐸 → 𝐸2
11 2
4
1 1 10
3 3
𝐴(4) = 6| 1
0 1 −
11
[0 −5 1 −5]

4
𝐸1 − 𝐸2 → 𝐸1 & 𝐸3 + 5 ∗ 𝐸2 → 𝐸3
3
19
1 0
11 2
|
𝐴(5) = 0 1 − 6 1
11|
19 0
[ 0 0 −
11 ]
6
𝐸1 + 𝐸3 → 𝐸1 & 𝐸2 − 𝐸3 → 𝐸2
19
1 0 0 2
𝐴(6) = [0 1 0 |1]
19
0 0 −
11 0
−11
∗ 𝐸3 → 𝐸3
19
1 0 02
(7)
𝐴 = [0 1 0|1]
0 0 10
𝑥1 = 2, 𝑥2 = 1&𝑥3 = 0

30
Engineering College Chemical Engineering Dept.

Example7. Solve the following linear system & find the inverse matrix using Gauss-Jordan
elimination method
2𝑥1 − 7𝑥2 + 4 𝑥3 = 9
𝑥1 + 9𝑥2 − 6𝑥3 = 1
−3𝑥1 + 8𝑥2 + 5𝑥3 = 6
Sol.
2 −7 4 9 1 0 0
(1)
𝐴 =[ 1 9 −6| 1 |0 1 0]
−3 8 5 6 0 0 1
1
∗ 𝐸 → 𝐸1
2 1
1 −7/2 2 9/2 1/2 0 0
[1 9 −6| 1 | 0 1 0]
−3 8 5 6 0 0 1
𝐸2 − 𝐸1 & 𝐸3 + 3 ∗ 𝐸1
1 −7/2 2 9/2 1/2 0 0
[0 25/2 −8| −7/2 |−1/2 1 0]
0 −5/2 11 39/2 3/2 0 1
2
∗ 𝐸 → 𝐸2
25 2
1 −7/2 2 9/2 1/2 0 0
[0 1 −16/25| −7/25 |−1/25 2/25 0]
0 −5/2 11 39/2 3/2 0 1
7 5
𝐸1 + 𝐸2 & 𝐸3 + ∗ 𝐸2
2 2
1 0 −6/25 88/25 9/25 7/25 0
[0 1 −16/25| −7/25 |−1/25 2/25 0]
0 0 47/5 94/2 7/5 1/5 1
5
∗ 𝐸 → 𝐸3
47 3

31
Engineering College Chemical Engineering Dept.

1 0 −6/25 88/25 9/25 7/25 0

[0 1 −16/25| −7/25 |−1/25 2/25 0 ]
0 0 1 2 7/47 1/47 5/47
6 16
𝐸1 + 𝐸3 & 𝐸2 + ∗𝐸
25 25 3
1 0 0 4 93/235 67/235 6/235
[0 1 0| 1 |13/235 235/235 16/235]
0 0 1 2 7/47 1/47 5/47
𝑥1 = 4, 𝑥2 = 1&𝑥3 = 2
93/235 67/235 6/235
𝐴−1 = [13/235 235/235 16/235|
7/47 1/47 5/47
1 2 5 −1
Det. A = [ ∗ ∗ ] = 235
2 25 47

32