Introduction

• I n t h i s c h a p t e r, we w i l l d e a l w i t h t h e c a s e o f
determining the values of x 1 , x 2 ,..., x n that
simultaneously satisfy the set of equations:

f1  x1 , x2 ,..., xn   0
f 2 x1 , x2 ,..., xn   0
(3.1)
......
f n x1 , x2 ,..., xn   0
• In particular we will consider linear algebraic equations
which are of the form:
a11 x1  a12 x 2  ...  a1n x n  b1
a 21 x1  a 22 x 2  ...  a 2 n x n  b 2 (3.2)
....
a n1 x1  a n12 x 2  ...  a n1n x n  b n
• where the a's are constant coefficients, the b's are
constants, and n is the number of equations.

• The above system of linear equations may also be

written in matrix form as:

A X   B  (3.3)
• Where [A] is an n by n square matrix of coefficients (called the
coefficient matrix),

 a11 a12 ... a1n 

a a 22 ... a 2 n 
A   21
 ... ... ... ... 
 
 a1n a2n ... a nn 
{B} is an n by 1 column vector of constants,

B T
 b1 b2 ... bn 
and {X} is an n by 1 row vector of unknowns:

X   x1 x2 ... x n 
 Non - Computer methods
• There are some non-computer methods which are used to solve small
(n≤3 ) sets of simultaneous equations that do not require a computer.

1. The Graphical Method

• Plotting the graphs (straight lines) and finding the point of intersection
of the graphs.

E.g Use the graphical method to solve

3x1+2x2=18

-x1+2x2=2
2. Cramer's Rule
• Cramer's rule states that the solution of a set of linear
equations given in Eq. 3.3 can be give as:
Di
xi  (3.4)
D

• where D is the determinant of the coefficient matrix

[A] , and Di is the determinant of the matrix obtained
by replacing the coefficients of the unknown xi in the
coefficient matrix by the constants b1,b2 , ...,bn .
• For example, x1 can be obtained as:

b1 a 12 a 13
b2 a 22 a 23
b3 a 32 a 33
x1 
D
• For more than three equations, Cramer's rule
becomes impractical because, as the number of
equations increase, the determinants are time-
consuming to evaluate by hand.

•Consequently, more efficient alternatives are used.

Example 1 : Use Cramer’s Rule to solve the linear system. (manually)

Example 2: Use Cramer ’s Rule to solve the linear system. (using

programming )
−2 1 1 2 4 𝑥1 6
⎡ ⎤ ⎡ ⎤
5 −1 2 3 2 ⎛𝑥2⎞ 25
⎢ ⎥ ⎢ ⎥
1 2 −1 4 2 ⎜𝑥3⎟ = 7
⎢ ⎥ ⎢ ⎥
⎢ 3 −3 1 2 5⎥ 𝑥4 ⎢25⎥
⎣6 2 1 3 5⎦ ⎝𝑥5⎠ ⎣22⎦
3. Elimination of Unknowns
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.
1. Gauss Elimination

Description of the method

• The approach is designed to solve a general set of equations:

a11 x1  a12 x 2  ...  a1n x n  b1 (3.5a)

a 21 x1  a 22 x 2  ...  a 2 n x n  b2 (3.5b)

....
a 1 n x 1  a 1 n x 2  ...  a nn x n  b n (3.5c)
• The naive Gauss elimination method consists of two phases:

1. Forward Elimination : The first step is designed to reduce the set of

equations to an upper triangular system.

• The initial step will be to eliminate the first unknown x1, from the second
through the nth equations. To do this, multiply Eq. (3.5a) by a21/a11 to give:

a 21 a 21 a 21
a 21 x 1  a 12 x 2  ...  a1n x n  b1 (3.6)
a 11 a 11 a 11
• Now this equation can be subtracted from Eq. 3.5b to give:

 a21   a21  a21

 a22  a12  x2  ...   a2n  a1n xn  b2  b1
 Or a11   a11  a11

 x 2  .....  a 2 n x n  b 2
a 22
• the prime indicates that the elements have been changed from their
original values.

• The procedure is then repeated for the remaining equations.

• For instance, Eq. (3.5a) can be multiplied by a 31 /a 11 and the result
subtracted from the third equation.

• Repeating the procedure for the remaining equations results in the

following modified system:

a 11 x1  a 12 x 2  a 13 x 3  ...  a 1 n x n  b1 (3.7a)
 x 2  a 23
a 22  x 3  ...  a 2 n x n  b 2 (3.7b)

 x 2  a 33
a 32  x 3  ...  a 3 n x n  b 3 (3.7c)

.....
a n 2 x 2  a n 3 x 3  ...  a nn
 x n  b n (3.7d)
• For the foregoing steps, Eq.(3.5a) is called the pivot equation, and a11 is
the pivot coefficient or element.

qNow repeat the above to eliminate the second unknown from Eq. (3.7c)
through Eq. (3.7d).

a11 x1  a12 x 2  a13 x3  ...  a13 x n  b1

a 22 x 2  a 23 x3  ...  a 2 n x n  b2
 x 3  ...  a 3n x n  b3
a 33
.....

a n3 x 3  ...  a nn
 x n  bn
üthe double prime indicates that the elements have been modified twice.

• The procedure can be continued using the remaining pivot equations.

• The final manipulation in the sequence is to use the (n-1)th equation to

eliminate xn-1the term from the n th equation.

• At this point, the system will have been transformed to an upper

triangular system:
 a 11 x 1  a 12 x 2  a 13 x 3  ...  a 1 n x n  b1 n (3.8a)

(3.8b)
 x 2  a 23
a 22  x 3  ...  a 2 n x n  b 2

 x 3  ...  a 3n x n  b 3

a 33 (3.8c)

.
. .

n  1 
a nn x n  b n n  1  (3.8d)

2. Back Substitution : Eq. (3.8d) can now be solved for xn :

b n n  1 
xn  n  1 
an
• This result can be back substituted into the (n-1)th equation to solve for
xn-1 .

• The procedure, which is repeated to evaluate the remaining x's, can be

represented by the following formula:

n
b ii  1   
j i1
a iji  1  x j

xi  for i  n 1 , n  2, ...,1
a iii  1 
Example 1: Use Gauss Elimination to solve the linear system. (manually)

a)

b)

Example 2: Use Gauss Elimination to solve the linear system. (using

programming )
−2 1 1 2 4 𝑥1 −3
⎡ ⎤ ⎡ ⎤
5 −1 2 3 2 ⎛𝑥2⎞ 24
⎢ ⎥ ⎢ ⎥
1 2 −1 4 2 ⎜𝑥3⎟ = 4
⎢ ⎥ ⎢ ⎥
⎢3 −3 1 2 5⎥ 𝑥4 ⎢9⎥
⎣6 2 1 3 5⎦ ⎝𝑥5⎠ ⎣ 13 ⎦
 Pitfalls of Gauss Elimination
• There are some pitfalls that must be explored before writing general
computer program to implement the method.

i, Division by Zero

• During both elimination and back-substitution phases, it is possible that a

division by zero can occur.

• Problems also arise when the coefficient is very close to zero.

ØThe technique of pivoting (to be discussed later) has been developed to
partially avoid these problems.

ii, Round-off Errors

The problem of round-off errors can become particularly important

when large numbers of equations are to be solved.

In any event, one should always substitute the answers back into the
original equations to check whether a substantial error has occurred.
iii, conditioned Systems

• Ill-conditioned systems are those where a small change in coefficients

results in large changes in the solution.

• An alternative interpretation of ill-conditioning is that a wide range of

answers can approximately satisfy the equations.

• An ill-conditioned system is one with a determinant of the coefficient

matrix close to zero.
iv, Singular Systems

• The system is singular when at least two of the equations are identical.

• In such cases, we would lose one degree of freedom, and would be

dealing with impossible case of n-1 equations in n unknowns.

• Such cases might not be obvious particularly when dealing with large
equation sets.

• Consequently, it would be nice to have some way of automatically

detecting singularity.
• The answer to this problem is neatly offered by the fact that the
determinant of a singular system is zero.

• This idea can, in turn, be connected to Gauss elimination by recognizing

that after the elimination step, the determinant can be evaluated as the
product of the diagonal elements.

• Thus, a computer algorithm can test to detect whether a zero diagonal

element is created during the elimination stage.
Techniques for Improving Solutions

1. Use of more significant figures.

2. Pivoting: can be partial or complete.

3. Scaling: Scaling is the process by which the maximum element in a row

is made to be 1 by dividing the equation by the largest coefficient.