Advanced Mathematics (CIVL7001)

Lecture 4. Linear Algebraic Equations and

Solutions II

1. Gaussian Elimination Method

2. Problems and Measures for Improving Solutions

3. Scaling for Determining Pivoting Element

4. Solutions of Nonlinear Algebraic Equations

1
1. Gaussian elimination method

The procedure for getting the row echelon form or re-

duced row echelon form of the augmented matrix through
row operations is just the procedure of Gaussian elimi-
nation.

• Gaussian elimination method is one of the popularly

used method for solving the system of linear equations.

• Computer program can be implemented for Gaus-

sian elimination method to solve large linear system.

• There are two steps with Gaussian elimination method

in solving linear equations.

Step 1: Elimination

In this step, the augmented matrix is changed to row

echelon form with the row operations.

Step 2: Back substitution

2
 In this step, the solution is obtained by back substi-
tution step-by-step.

• Gaussian elimination procedure for the system with

unique solution.

Suppose that there are n unknowns and n equations,

i.e.,
   


a11 a12 ... a1n b1   a11 a12 ... a1n a1,n+1 
a21 a22 ... a2n b2   a21 a22 ... a2n a2,n+1 
   


..  =  ..





.. .. ... .. .. ... .. .. 


   
an1 an2 ... ann bn an1 an2 ... ann an,n+1
   

Step 1: Elimination (calculate in sequence as follows:)

For k = 1, 2, . . . , n:

3
 (1)
 


1 a12 ... a1k a1,k+1 . . . akn b1 

0 1 ... a2k a2,k+1 . . . akn b2
 
 
 
 
......
 
 
 
 

0 0 ... akk ak,k+1 . . . akn bk

 
 
 
 


 0 0 ... ak+1,k ak+1,k+1 . . . ak+1,n bk+1 

.. .. . . . .. ..

 
 
 
 
 
0 0 . . . an,k an,k+1 . . . ann bn
 

If akk = 0, row k and the row p (apk ̸= 0, p =

k + 1, k + 2, · · ·, or n) are interchanged by







t = aks




aks = aps (s = k, k + 1, ..., n + 1)
 a
ps = t




akk is called pivoting element.

After this procedure, the pivoting element akk be-

comes nonzero.

(2) If akk ̸= 0,

4
 akj
akj = (j = k + 1, k + 2, · · · , n + 1)
akk
aij = −aik akj + aij
(i = k + 1, k + 2, · · · , n; j = k + 1, k + 2, · · · , n + 1)
akk = 1
aik = 0 (i = k + 1, k + 2, · · · , n)

After the above, the updated augmented matrix be-

comes
 
 1 a12 ... a1n b1 

 0 1 ... a2n b2 
 

 . .. .. .. 

 . ...

 
0 0 ... 1 bn
 

which is in row echelon form and the values of all the

entries are updated ones.

Step 2: Back substitution

x n = bn
n
x i = bi − aik xk (i = n − 1, n − 2, . . . , 1)
X

k=i+1
5
 Example 1. Solve the following equations with Gaus-
sian elimination method.
2x2 + 3x3 = 8
4x1 + 6x2 + 7x3 = −3
2x1 + x2 + 6x3 = 5

Solution: 1. The augmented matrix of this system is

 


0 2 3 8 
4 6 7 −3 
 



2 1 6 5
 

2. Elimination
 


0 2 3 8 
4 6 7 −3 
 



2 1 6 5
 

Because a11 = 0, exchanging row (1) and row (2) gives

6
  


4 6 7 −3 
0 2 3 8 
 



2 1 6 5
 

row (1)× 41 gives

3 7
− 43
 


1 2 4 

0 2 3 8
 
 
 
 
2 1 6 5
 

row (1)×(−2) + row (3) → updated row (3) gives

3 7
− 34
 


1 2 4 

0 2 3 8
 
 
 
 
0 −2 25 13
 
2

row (2)× 21 gives

3 7
− 43
 


1 2 4 


1 32
 
0 4
 
 
 
 

−2 25 13
 
0
 
2

row (2)×2 + row (3) → updated row (3) gives

7
 3 7
− 43
 


1 2 4 

3
 
0 1 4
 
 

 2 

11 29
 
0 0
 
2 2
2
row (3)× 11 gives
3 7
− 43
 


1 2 4 


1 32
 
0 4
 
 
 
 
29
 
0 0 1
 
11

3. Back substitution

29
x3 = 11

x2 = 4 − 32 x1 = 4 − 32 × 29
11 =
1
22

x1 = − 34 − 23 x2 − 74 x3 = − 34 − 23 × 22
1
− 74 × 29 239
11 = − 11

The solution is (x1, x2, x3) = (− 239 1 29

44 22 , 11 ).
,

8
 2. Problems and Measures for Improving
Solutions

The above solution procedure can’t give accurate so-

lution in some cases.

2.1 Small pivoting element

Problem: Since a pivoting element is a denominator

in the Gaussian elimination procedure, the small value
of pivoting element can lead to large round-off errors.

Measure to handle the problem: The technique of

pivoting is needed when the denominator is equal or
close to zero.

• Column pivoting: The maximum element in a col-

umn behind and including the pivoting element is se-
lected as the pivoting element through row exchange.

• Row pivoting: The maximum entry in a row behind

and including the pivoting element is selected as the
pivoting element through column exchange.
9
 • Complete pivoting: The maximum entry in rows
and columns behind and including the pivoting element
is selected as the pivoting element through row and col-
umn exchange.

Example 2. Use Gaussian elimination to solve

0.0003x1 + 3x2 = 2.0001
x1 + x2 = 1
Solution: (1) The exact solution of the system is (x1, x2) =
( 31 , 23 ).

(2) By naive Gaussian elimination, the solution is

(x1, x2) = ( 2.0001−3x 2 , 2 ) = ( 2.0001−3(2/3) , 2 ).
0.0003 3 0.0003 3

SF x1 x2 Error of x1 (%)
3 -3.00 0.667 1099
4 0.0000 0.6667 100
5 0.30000 0.66667 10
6 0.330000 0.666667 1
7 0.3330000 0.6666667 0.1

10
 (3) By column pivoting Gaussian elimination, the sys-
tem becomes
x1 + x2 = 1
0.0003x1 + 3x2 = 2.0001

Then, the solution is got to be (x1, x2) = ( 1−x

1
2 , 2) =
3
1−2/3 2
( 1 , 3 ).

SF x1 x2 Error of x1 (%)
3 0.333 0.667 0.1
4 0.3333 0.6667 0.01
5 0.33333 0.66667 0.001
6 0.333333 0.666667 0.0001
7 0.3333333 0.6666667 0.00001

The results after column pivoting are much improved.

11
 2.2 Ill-conditioned systems

• Ill-conditioned systems are those in which small

changes in coefficients result in large changes in the so-
lution or a wide range of answers can approximately
satisfy the equations.

Example 3. Solve the first system:

x1 + 2x2 = 10
1.1x1 + 2x2 = 10.4

Then, solve it again, but the coefficient of x1 in the

second equation is modified slightly to 1.05, or solve
the second system:
x1 + 2x2 = 10
1.05x1 + 2x2 = 10.4

Solution: The solution of the first system is

2 × 10 − 2 × 10.4
x1 = =4
1 × 2 − 2 × 1.1
12
 1 × 10.4 − 1.1 × 10
x2 = =3
1 × 2 − 2 × 1.1

The solution of the second system is

2 × 10 − 2 × 10.4
x1 = =8
1 × 2 − 2 × 1.05
1 × 10.4 − 1.05 × 10
x2 = =1
1 × 2 − 2 × 1.05
It shows that slight change in the system parameter can
lead to large change in solution. This is one of the be-
haviors of the ill-conditioned system.

If we want to check if the much different solution of

system 2 is the solution of the system 1, the solution
of the second system is substituted into the right-hand
side of the first system. Then
8 + 2 × 1 = 10
1.1 × 8 + 2 × 1 = 10.8 ≈ 10.4

It shows that the system 1 is approximately satisfied

by the solution of system 2 though the two solutions
13
are much different. This is one of the behaviors of the
ill-conditioned system.

• Determinate of the ill-conditioned system

Consider the following system

a11x1 + a12x2 = b1
a21x1 + a22x2 = b2

Graphically the solution of the system is the intersection

of the two straight lines. For ill-conditioned system, the
slopes of the two straight lines are close.

The above equation can be written as

a11 b1
x2 = − x1 +
a12 a12
a21 b2
x2 = − x1 +
a22 a22

If the slopes of the two lines are nearly equal, then

14
 a11 a21
≈
a12 a22
or
a11 a21 a11a22 − a12a21
− = ≈0
a12 a22 a12a22

It is known that a11a22 − a12a21 is the determinate of

the system.

In general, the determinant of the ill-conditioned sys-

tem is close to zero.

If the determinant of the ill-conditioned system is close

to zero, then a slight change in the parameters of the
system coefficient matrix can make the determinant of
the matrix much different from zero and then much dif-
ferent solutions.

• Effect of scale on the determinant

Example 4. Evaluate the determinant of the following

systems. 
 3x1 + 2x2 = 18



(a)
 −x + 2x = 2


1 2


15
and 



 x1 + 2x2 = 10
(b)
 1.1x + 2x = 10.4


1 2


(c) Repeat (b) but with the equations multiplied by

10, or 
 10x1 + 20x2 = 100



(c)
 11x + 20x = 104


1 2


Solution: System (a) is a well-conditioned system and

its determinant is
D = 3 × 2 − 2 × (−1) = 8

System (b) is an ill-conditioned system and its determi-

nant is
1 × 2 − 2 × 1.1 = −0.2
which is close to zero.

System (c) should also be ill-conditioned, but the de-

terminant of system (c) is
10 × 20 − 20 × 11 = −20
16
which absolute value is greater than that of system (a).

Scaling is needed in order to calculate the determi-

nant and identify the condition of a system.

Scaling: multiplying or dividing a constant on each

equation to make the maximum absolute value of the
coefficients in each equation equal 1.

Example 5. Scaling the systems in Example 4. and

calculate the determinants of the systems.

Solution:




 3x1 + 2x2 = 18
(a)
 −x + 2x = 2


1 2


After scaling, the system becomes

x1 + 32 x2 = 6






 1
 − x + x = 1
2 1 2


and
2 2 −1
D =1× − × = 1.333
3 3 2

17
 



 x1 + 2x2 = 10
(b)
 1.1x + 2x = 10.4


1 2


After scaling, the system becomes





 0.5x1 + x2 = 5
 0.55x + x = 5.2


1 2


and
D = 0.5 × 1 − 1 × 0.55 = −0.05

(c) The scaled system (c) is the same as the scaled sys-
tem (b) and then their determinants are also the same.

18
 2.3 Singular system

If the determinant of the coefficients matrix equal

zero, the system is singular and is called singular system.

In the process of Gaussian elimination, if a pivoting

diagonal element is found to be zero, the system is sin-
gular.

2.4 Large system analysis

Problem: Even for weakly ill-conditioned or well-

conditioned system, round-off errors can become obvi-
ous if the system is large or great number of computa-
tion are needed to solve the equations.

The influence of the round-off errors can be identified

by substituting the solution to the equations to check if
the equations are satisfied.

Measure to handle the problem: Increase the signif-

icant figures in computation, but this can increases the
computational effort.
19
 3. Scaling for Determining Pivoting Ele-
ment

Example 6. Effect of scaling on pivoting and round-

off errors

(a) Solve the following set of equations using Gaussian

elimination and column pivoting strategy:

2x1 + 105x2 = 105







 x + x = 2


1 2


(b) Solve the same equations using Gaussian elimi-

nation and column pivoting strategy after scaling the
equations so that the maximum coefficient in each row
is 1.

(c) Use the scaled coefficients to determine whether

pivoting is necessary. However, solve the equations with
the original coefficient values.

For all cases, retain only 3 significant figures. Note

that the correct answers are x1 = 1.00002 ≈ 1.00 and

20
x2 = 0.99998 ≈ 1.00.

Solution: (a) Without scaling, forward elimination

gives

2.00x1 + 1.00 × 105x2 = 1.00 × 105







4
 −5.00 × 10 x = −5.00 × 10

 4
2


which can be solve by back substituting for x1 = 0.00

and x2 = 1.00.

(b) Scaling the original system gives

2.00 × 10−5x1 + 1.00x2 = 1.00







 x + x = 2


1 2


Therefore, the rows are exchanged for pivoting to put

the greatest value on the diagonal as follows.




 x1 + x2 = 2
 2.00 × 10
−5
x1 + 1.00x2 = 1.00




Forward elimination yields





 x1 + x2 = 2
 x = 1.00


2


21
which can be solved for x1 = x2 = 1.00.

The scaling leads to the need for pivoting and the piv-
oting leads to correct answer.

(c) The scaled coefficients indicate that exchanging

rows is needed. Exchanging the rows of the original
system gives




 x1 + x2 = 2
5
 2x + 10 x = 10

 5
1 2


Forward elimination yields





 x1 + x2 = 2
5
 1.00 × 10 x = 1.00 × 10

 5
2


which can be solved for x1 = x2 = 1.00.

The scaling is useful in determining whether pivoting

is necessary, but the equations themselves do not re-
quire scaling to arrive at a correct answer.

22
 4. Solutions of Nonlinear Algebraic Equa-
tions

For the nonlinear system








f1(x) = 0
f2(x) = 0









..



 f (x) = 0



n
or
f (x) = 0
where x = {x1, x2, ..., xn} and f (x) = {f1(x), f2(x), ..., fn(x)}t
Newton-Raphson method gives

(i+1) (i) ∂f (i) −1 (i)

x =x −[ ] f (x )
∂x
(i) (i) (i+1) (i+1)
where x(i) = {x1 , x2 , ..., x(i)
n }, x
(i+1)
= {x1 , x2 , ..., x(i+1
n
(i)
and xj is the value of xj at ith step.
∂f1 ∂f1 ∂f1
 

 ∂x1 ∂x2 ... ∂xn 

 

∂f2 ∂f2 ∂f2 
∂f (i) ...
 
 
 ∂x1 ∂x2 ∂xn 
= . 

.. .. ..


∂x .
 
 
 
 

∂fn ∂fn ∂fn 


∂x1 ∂x2 ... ∂x n


x=x(i)
23
which takes valve at x = x(i).

The Newton-Raphson equation can also be written as

∂f (i) (i+1) ∂f (i) (i)

[ ]x =[ ]x − f (x(i))
∂x ∂x
which can be solved by Gaussian elimination method
for x(i+1).

The initial value of x which is nearby the exact de-

sired solution is needed by Newton-Raphson method for
solution convergence. It can be guessed based on user’s
numerical experience and professional knowledge.

Assignment 4:

Get the solution of the following system by Gaussian

elimination method (1) without scaling and pivoting;
(2) with pivoting but not scaling; (3) with scaling but
not pivoting; (4) with both scaling and pivoting. (In
all cases, 3 significant figures and column pivoting are
used.)

24
−3x1 − 6x2 + 2x3 = −61.5
x1 + x2 + 5x3 = −21.5
10x1 + 2x2 − x3 = 27

25