C H A P T E R 9

Gauss E l i m i n a t i o n
This chapter deals with simultaneous linear algebraic equations that can be represented generally
as

mm + max* H — + atum—m
mtixi+a&m + =

where the a's are constant coefficients and the 6's are constants.
The technique described in this chapter is called Gauss elimination because it involves
combining equations to eliminate unknowns.
9.1 SOLVING SMALL NUMBERS OF EQUATIONS
Before proceeding to the computer methods, we will describe several methods that are
appropriate for solving small (n < 3) sets of simultaneous equations and that do not require a
computer. These are the graphical method, Cramer's rule, and the elimination of unknowns.
9.1.1 The Graphical Method
A graphical solution is obtainable for two equations by plotting them on Cartesian coordinates
with one axis corresponding to x\d the other to X2.
Because we are dealing with linear systems, each equation is a straight line. This can be easily
illustrated for the general equations

Both equations can be solved for X2'.

Thus, the equations are now in the form of straight lines; that is, X2 = (slope) x\ intercept.
These lines can be graphed on Cartesian coordinates with x as the ordinate and x\s the
2

abscissa.
The values of x\d X2 at the intersection of the lines represent the solution.

E X A M P L E 9.1 The Graphical Method for Two Equations

Problem Statement. Use the graphical method to solve
3x, + 2 x = 1 8
2 (E9.1.1)
-X! + 2x = 2
2 (E9.1.2)
Solution.
Let xi be the abscissa. Solve Eq. (E9.1.1) for x : 2

x = (-3/2) x, + 9
2

which, when plotted on Fig. 9.1, is a straight line with an intercept of 9 and a slope of-3/2.

FWSURE 9.1

8 -
\

S -
- V So uric: r,
i -

2 -

0 - 1 1 1 1 1
0 4 6
Equation (E9.1.2) can also be solved for x : 2

I
jt z = -jr T + 1
2

which is also plotted on Fig. 9.1.

The solution is the intersection of the two lines at x\4 and x = 3. This result can be checked by
2

substituting these values into the original equations to yield

3(4)+ 2(3)= 18
- ( 4 ) + 2(3) = 2
Thus, the results are equivalent to the right-hand sides of the original equations.
For three simultaneous equations, each equation would be represented by a plane in a three-
dimensional coordinate system. The point where the three planes intersect would represent the
solution. Beyond three equations, graphical methods break down and, consequently, have little
practical value for solving simultaneous equations.
However, they sometimes prove useful in visualizing properties of the solutions. For example,
Fig. 9.2 depicts three cases that can pose problems when solving sets of linear equations.
Figure 9.2a shows the case where the two equations represent parallel lines. For such situations,
there is no solution because the lines never cross.
Figure 9.2b depicts the case where the two lines are coincident. For such situations there is an
infinite number of solutions. Both types of systems are said to be singular.
In addition, systems that are very close to being singular (Fig. 9.2c) can also cause problems.
These systems are said to be ill-conditioned. Graphically, this corresponds to the fact that it is
difficult to identify the exact point at which the lines intersect. Ill-conditioned systems will also
pose problems when they are encountered during the numerical solution of linear equations. This
is because they will be extremely sensitive to round-off error.

FIGURE 9,2
Gtephltd depidkxi of singular and ilkanc&fofisd systems: faj no xkBan. [fef wims solutions,
and fe} llkjorsAaned systen ssne-e lie slsoes are so dose tfici the point ofrtersecitnIs
dfSciitadetect <Awdkf.

X-, Xr, X;

. Ufa _^#»
><^\
<— \fs

x%

9.1.2 Determinants and Cramer's Rule

Cramer's rule is another solution technique that is best suited to small numbers of equations.
Before describing this method, we will briefly introduce the concept of the determinant, which is
used to implement Cramer's rule.

3
Determinants. The determinant can be illustrated for a set of three equations:

where [A] is the coefficient matrix:

3n a ii an
M = an 3 22 %3
%i am ®m
The determinant D of this system is formed from the coefficients of the equation, as in

mi mi
D= am as

am (9.2)
Although the determinant D and the coefficient matrix [A] are composed of the same elements,
they are completely different mathematical concepts. That is why they are distinguished visually
by using brackets to enclose the matrix and straight lines to enclose the determinant.
In contrast to a matrix, the determinant is a single number. For example, the value of the second-
order determinant

3m I
D= 1 311

1%1 3 22 I
is calculated by

(9.3)
For the third-order case [Eq. (9.2)], a single numerical value for the determinant can be
computed as
• '
22 | 3>2i J
D'— ifj 111: 322
a
1 *~ I »-|
12 a :
| 4 i %3 1 1 «3L "32 1
(9.4)
where the 2 by 2 determinants are called minors
Cramer's Rule. This rule states that each unknown in a system of linear algebraic equations
may be expressed as a fraction of two determinants with denominator D and with the numerator

4
obtained from D by replacing the column of coefficients of the unknown in question by the
constants b\, b ,..., b„.
2

For example, x\d be computed as

b& Ms am

^1 =
D (9.5)

E X A M P L E 9.2 Determinants
Problem Statement. Compute values for the determinants of the systems represented in Figs.
9.1 and 9.2.
Solution.
For Fig. 9.1:

2 . 3 , 2 - a.(-0= §
Z

For Rg, 9,2 b'

-1-^1 +Xj =\ 0 U-0 = o

E X A M P L E 9.3 Cramer's Rule

Problem Statement. Use Cramer's rule to solve

0.3.n ^ 0 . 5 2 x 2 + - n = -0.01
[Link] - x j + 1.9x3 = 0.G7
0Jx T + 0 . 3 x + CISx^ =
2 -0.44

Solution. The determinant D can be written as [Eq. (9.2)]

 0.3 0,52. J
D =
0.5" 1
OH 0.3 0.5"

M lm o r s

1 \,1
- 1 (o.5j_ . 0,0?
03 0.5

| 0-5 19 \
A**
1 o.1 0.5"

A s = I 0,5 A
0.5" / o . 3 ) _ 1 (o-0 = [Link]
I 0.-1 03

0 o tM) AAii -
= a adu u A * + e , ^ A 3 = 0 ^ ( - 0 , 0 f j _ _ G . 5 2 f 0 . 0 b ) + U o . 0 5 ^ -0.
0,0022

0,51 I
[Link] i
\M 0.3 0.5"
g 0.03 2 ? g _ - -ik>?
*1 =
-0. OO 22 "O. 0 0 2 2

0.3 1

0.5" 19
0,5"
- [Link]-9 = -29.S"
-O, 0022
- 0.0022

0.3> 0,52 ^0.04

0,5 1 0,6?
OH 0. 3 -o,44

-0,0022
0.00 2 2

For mofe. \ W i n ^ ecjuaVlons / C r a m e r s rJle. [Link] JmprodUcnl W c a u s e

c^s r W number- ^ ex^uoA-iorxs Increases / -JW <4^WW*IY=*AX Qr & ^Ime

or" Otj oomput

•A
9.1.3 The Elimination of Unknowns
The elimination of unknowns by combining equations is an algebraic approach that can
beillustrated for a set of two equations:

(9.6)

I"* ' )
The basic strategy is to multiply the equations by constants so that one of the unknowns will be
eliminated when the two equations are combined.
The result is a single equation that can be solved for the remaining unknown. This value can then
be substituted into either of the original equations to compute the other variable.
For example, Eq. (9.6) might be multiplied by a \d Eq. (9.7) by a to give
2 n

eInil2\Xl — SjZ^ijMz = fife 421 ~ ^

(9.9)
Subtracting Eq. (9.8) from Eq. (9.9) will, therefore, eliminate the xi term from the equations to
yield

% 2 ^ ] L*2 — ^WfaJft = ^ 31 —
a h^Zl

which can be solved for

u as - (9.10)

Equation (9.10) can then be substituted into Eq. (9.6), which can be solved for

(9.11)
Notice that Eqs. (9.10) and (9.11) follow directly from Cramer's rule, which states

7-
 [h m

.If
311 &12

3*£1

an an
4*1 3z»

E X A M P L E 9.4 Elimination of Unknowns

Problem Statement. Use the elimination of unknowns to solve (recall Example 9.1)

3xi + 2x - 18
2

-x\ 2x2 = 2

Solution. Using Eqs. (9.11) and (9.10),

208)-2(2)
3{Z>—2C—I]
3(2i-(-1)38
3(2) — 2(—1)

which is consistent with our graphical solution (Fig. 9.1).

Xa^ 3 3
9.2 NAIVE GAUSS ELIMINATION
In the previous section, the elimination of unknowns was used to solve a pair of simultaneous
equations. The procedure consisted of two steps:
1. The equations were manipulated to eliminate one of the unknowns from the equations. The
result of this elimination step was that we had one equation with one unknown.
2. Consequently, this equation could be solved directly and the result back-substituted into one of
the original equations to solve for the remaining unknown.
This basic approach can be extended to large sets of equations by developing a systematic
scheme or algorithm to eliminate unknowns and to back-substitute.
Gauss elimination is the most basic of these schemes.
This section includes the systematic techniques for forward elimination and back substitution
that comprise Gauss elimination. Although these techniques are ideally suited for
implementation on computers, some modifications will be required to obtain a reliable algorithm.
In particular, the computer program must avoid division by zero. The following method is called
"naive " Gauss elimination because it does not avoid this problem.
The approach is designed to solve a general set of n equations:

4- m&Xi + - - - - + *mXa = fts ^ 1 2 a 9 1 2 b 9 1 2 < ^

As was the case with the solution of two equations, the technique for n equations consists of two
phases: elimination of unknowns and solution through back substitution.
Forward Elimination of Unknowns. The first phase is designed to reduce the set of equations
to an upper triangular system (Fig. 9.3).
The initial step will be to eliminate the first unknown, x i , from the second through the nth
equations. To do this, multiply
Eq. (9.12a) by a i/an to give
2

(9.13)

9
Now, this equation can be subtracted from Eq. (9.12b) to give

{' 321 321 \ .

mi j mi

Or

V I | u> , JF"^

where 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. (9.12a) can be
multiplied by a^/an and the result subtracted from the third equation. Repeating the procedure
for the remaining equations results in the following modified system:

(9.14a, 9.14b, 9.14c, 9.14d)

For the foregoing steps, Eq. (9.12a) is called the pivot equation and a u is called the pivot
coefficient or element.
Note that the process of multiplying the first row by a i/an is equivalent to dividing it by a l l
2

and multiplying it by a2i. Sometimes the division operation is referred to as normalization.

We make this distinction because a zero pivot element can interfere with normalization by
causing a division by zero.
We will return to this important issue after we complete our description of naive Gauss
elimination.
Now repeat the above to eliminate the second unknown from Eq. (9.14c) through (9.14J).
To do this multiply Eq. (9.146) by a'^/d'ii and subtract the result from Eq. (9.14c).
Perform a similar elimination for the remaining equations to yield

10
 - + Mb-Xm
^2,^2 + ^23 "> H
x

33yXy + '

where the double prime indicates that the elements have been modified twice.

3n a-i 3-1
3J| 2..
3;: J.:. CI23
4J-

fsewn mi
The two ptasaa d Gms ehil
arts" > - - ~ cr« cr»: 4
bac» . :• ?-« z- - C J ->/G "i
-arc-; - :> •. - r-r :—-23
-; ~. T I S

The procedure can be continued using the remaining pivot equations. The final manipulation in
the sequence is to use the (n - l)th equation to eliminate the x„-i term from the nth equation. At
this point, the system will have been transformed to an upper triangular system:

4 ^ 2 + * » * 3 + -•- + = ^
^g^i.( 1- a^jfc = i f

" B (9.15a, 9.15b, 9.15c, 9.15d)

Back Substitution. Equation (9A5d) can now be solved for xn:

11
 W' wsssswaw

(9.16)

This result can be back-substituted into the (n — l)th equation to solve for JC„_J. The procedure,
which is repeated to evaluate the remaining JC'S, can be represented by the following formula:

X,' = 3 ^ forf = / ? - 1./7- 2 \

4/ ( . )
9 1 7

Example. . T^Oowe. Gauss E!\'lrn»nccVior\

Pro(o\g>m S>fecWm^sxs-r U s e . Gauss Ei<Wna4ion 4 a so\\/s,

0.U1+ fxa-0.3xa- H9.3

0.3 x i - 0 . 2 x ^ 4 - 1 0 * = S

.Oft

b . i x , _ o. 0 3 3 3 3 3 0 . 0 3 3 3 3 3 x 3 = , 0.2^66?

- 0 . * * 1 4 0.033333*2.+ 0 . 0 3 3 3 3 3 x 3 ^ - G . l ^ U ?

f.0 3 3233*2. - 0.293333x3 ^ H 9 , 5 6 f ^ f ^ -19,561?

1Z
 0.3xi _ [Link]*j*__ O.0J2X3 = <0,?£S

0.3 x< _ 0 - 2 ^ -4 10x 3 = 71.4

- 0 . 3 Xt 4 [Link] * X + C,0J2X 3 = -[Link]

-0.190000x^4- 10* 0 ^ . 0 0 x 3 = 7G-b4SO

f.00333xjL - 0.295 g33x 2 ^ - ^ 9 , 5617"

-G,190OOOX^> 4- <0,0200x 5 = ^0,6160

To rem eve.

/_ o . n o o o o . ) ?,oo333x,_ LqAIoood) 0 i l , m 3 y

7.00333 7 I f, 0 0 3 3 3 / 9. 0 0 3 «

-O.i^OOOOxa 4- O.<0O?95?x 3 ^0.S3O7O?

- 0 . 4900 0 0 x . 4 10.0200x3 ~ TO.&Bo

[Link]^- O.QQ7952 K s _ -Q^sOWf

I* -0.<X:L_O.2X2>

7.00333x^, 0.29333^X3 = -HSlft

tG.0{20* a ^ 70.0^43

X ^ =• ^ O . Q g ^ j =r £OQG03

/O. O l i O

^ 0 0 3 3 3 X x - 0.293 2 3 3 ^ 0 0 0 0 3 ) ^ - 1 7 , 5 ^ ^
3,X,_X 0 j4. =( - .~22, .55 0
G0O0o -1 l J . - 0 . 2 . ^ 0 0 0 0 3 ^ 7>$5 [Link]
9.4 TECHNIQUES F O R IMPROVING SOLUTIONS
The following techniques can be incorporated into the naive Gauss elimination algorithm to
circumvent some of the pitfalls discussed in the previous section.

9.4.1 Use of More Significant Figures

The simplest remedy for ill-conditioning is to use more significant figures in the computation.
If your application can be extended to handle larger word size, such a feature will greatly reduce
the problem. However, a price must be paid in the form of the computational and memory
overhead connected with using extended precision.

9.4.2 Pivoting
Obvious problems occur when a pivot element is zero because the normalization step leads to
division by zero.
Problems may also arise when the pivot element is close to, rather than exactly equal to, zero
because i f the magnitude of the pivot element is small compared to the other elements, then
round-off errors can be introduced.
Therefore, before each row is normalized, it is advantageous to determine the largest available
coefficient in the column below the pivot element.
The rows can then be switched so that the largest element is the pivot element. This is called
partial pivoting.
The following example illustrates the advantages of partial pivoting.
Aside from avoiding division by zero, pivoting also minimizes round-off error. As such, it also
serves as a partial remedy for ill-conditioning.

E X A M P L E 9.9 Partial Pivoting

Problem Statement. Use Gauss elimination to solve

0.0003xi + 3.0000x2 = 2.0001

1.0000xi + 1.0000X2= 1.0000

Note that in this form the first pivot element, al 1 = 0.0003, is very close to zero. Then repeat the
computation, but partial pivot by reversing the order of the equations. The exact solution is xi =
1/3 and x = 2/3.
2
([Link]) (o OQ )
t 02 ^0,0003)

*| H O O O O ><___, 6 6 6 ^

1,OOOOxi 4- OCOOXi - 1-O0O0

- *4 _ HOOOOx^ - - 6 6 & f

2,0001 - 3,0000
X< -=

0.0003

4W n u m U s u ^ \ W ^ ^ures earned .ft ^e- compuVaVU:

3 [Link] -
4 0.666? 0.0GG0

^ Q,6666 f 0.30000 "

* 0.66666? 0.330OO0

^ o.66666_:f O.33300O0

"Wis is WcexuLse. U3<& cxre. s\AV*a.c.V\f\ 4UJO al^sV_<=3^ial numbers.

1>
\
4k 44v£±. | a r g f e r p^csV <a-W(v^r\-\ normalized.

0 , O O 0 3 x t 4- [Link] Xj. - 2, G Q O i

0.0OO3. \t 4- / 0 . O O O 3 \l _ / 0 , 0 0 0 3 \
j i^oooo; " ( - t ^ O " ; 1

O.Q003x, v 0 . 0 0 0 3 x 2 . - O.OOG3

[Link]-r- 3, 0 0 o o x i * a . o o o 1
-0t0003x(— 0.0003x^^-0.0003

2,9997xx - 1.999?
- [Link] % -r 0 , 6 6 6 6 _ Q , 2.22.2 _ 2.
2,9997- 0.99SS 0.3333 3

1,0000x14- f . O O Q O / 2. \O

X{ - { . O O O O 2__
3

3 0.667 0.333
4 0-666 7 0.3333
5" 0.6666 7 0.33 333
£ 0.6666 6 7 0.333323
? 0.666666 7 O.3333 333

16
9.4.3 Scaling
In Sec. 9.3.3, we proposed that scaling had value in standardizing the size of the determinant.
Beyond this application, it has utility in minimizing round-off errors for those cases where some
of the equations in a system have much larger coefficients than others.
Such situations are frequently encountered in engineering practice when widely different units
are used in the development of simultaneous equations.
For instance, in electric circuit problems, the unknown voltages can be expressed in units ranging
from microvolts to kilovolts.
Similar examples can arise in all fields of engineering. As long as each equation is consistent, the
system will be technically correct and solvable.
However, the use of widely differing units can lead to coefficients of widely differing
magnitudes.
This, in turn, can have an impact on round-off error as it affects pivoting, as illustrated by the
following example.

E X A M P L E 9.10 Effect of Scaling on Pivoting and Round-Off

Problem Statement.

(a) Solve the following set of equations using Gauss elimination and a pivoting strategy:
2xi + 100,000x2= 100,000
Xi + X2 = 2

(b) Repeat the solution after scaling the equations so that the maximum coefficient in each row is
1.

(c) Finally, use the scaled coefficients to determine whether pivoting is necessary.
However, actually solve the equations with the original coefficient values.
For all cases, retain only three significant figures.
Note that the correct answers are xi = 1.00002 and X2 = 0.99998 or, for three significant figures,
xi = x = 1.00.
2
2M + 400 Q00>o_ - 100 0 0 0
- S O OOOKZ^ "SO 000

• - ? ??9 >c_ « - h 9 ?9B

*_ = l O 0 5. correct

x"i.=-[Link] ^ /£)Q 0/0 e r r o r beicrx^e^ o^- oo^nei <O^T_L

0.0GGG2 ^ j

0 . 0 0 0 0 2 x 1 + x_ _ >f

O.0OG02M ^ O . 0 0 O 0 2 x__^ O . O 0 O 0 4-

O . 0 0 O 0 2 X i + K-2- - \
[Link]- 0 . 0 O O 0 2 K „ - "0,00004

0.999 9 ffxA - 0 ^ 9 9 9 ^
_ A-P-"V<—r corujord elimi n a b c m
X z - 1.0O —7* — r

X1 - r ^ O O - 2-
TW"- s c a U c o ^ c ! ^ U > c _ a U +W" ? ^ n g ^ necessary.

X, + X ^ =r 2-
Z *1 -H00 000 *__HOO ooo

2%\ 2-x x - if.

2*1^ {QOOQGxV- 100 0 0 0

- Zx^ - - ^

9 9 9 9 8 ' x ^ - 99996'
/jx - 4 , 0 0 ' > A-f-W-ruJcurc!> e\ m iY>cv4} p ft

I hus ( S C Q \ \ < ^ V-OCX-S: useful ir> cW4—trrntavVcj vjoV><s4k<i_r p\\jcsV\r\

UJCVS r«»cssssQ.r^ t>o4 « c ^ a V \ o n s
t 4k<ems_i\\)e£: 4 i a r>c4 repair©

19
9.7 GAUSS-JORDAN

The Gauss-Jordan method is a variation of Gauss elimination.

The major difference is that when an unknown is eliminated in the Gauss-Jordan method, it is
eliminated from all other equations rather than just the subsequent ones.
In addition, all rows are normalized by dividing them by their pivot elements.
Thus, the elimination step results in an identity matrix rather than a triangular matrix (Fig. 9.9).
Consequently, it is not necessary to employ back substitution to obtain the solution.
The method is best illustrated by an example.

EXAMPLE 9.12 Gauss-Jordan Method

Problem Statement. Use the Gauss-Jordan technique to solve the same system as in Example
9.5:
3 x i - 0 . 1 x - 0 . 2 x = 7.85
2 3

0.1 xj + 7 x - 0.3x = -19.3

2 3

0 . 3 x i - 0 . 2 x + 1 0 x = 71.4
2 3

Solution.
First, express the coefficients and the right-hand side as an augmented matrix:

2.0
 e. is <s_x
as an amqiYxe-r^b ^ [Link]\ y.
3r 2

3 -CM -0,2. 7.^5 7

OH 7 -0,3
0 ^ -0,2

K)orrY\cvll2B. 4W ^rsA" V^xo (?vj (5W<Auvcj rb b ^ bW- piM-ob <e\«£m^r\V 3. ;

i -0,c933S333 -G.066667 2.61667

0.1 7 -0,3> -<?,3
0,2, _0,2 10

Tb^- W(v> con b^ J t U m a i W A ^rem -rW sec» cS h r ui

D by

subVrdC-VUg 0,1 b'Ues W jpr^V r o ^ from +be- s ^ e o r x c i r o u .

P -0,033^333
^,0033333
-0,06666 9
- 0 , 2 ^ 3 333
2 64 667
t
7

0 '19.56-/ 66?
-0,19000OG •fO, O 2 0 O O O TO, 6 ( ^ 9 9 9
0

K) ormolbe- r o u ! ^UlcbVg W 7.0033333

1 -0,0233333 - 0 , 0 6 6 667 J2. 6 H 6 7

0 4
-^.79 320
iO , 0 2 0 0 0 0 70, 6/(9^9
0 -0,190000.0

5u^~b^c_"brvcj ro w

-0,0333333 ,

24
 \ „,9.06^063 2.52 3563
o 4 -<D.c04W4? - 2 . 7 9 320
0 -0.1900000 -to<020000 7 0 , 6*4 <?r»

SabWcbVq 2 ^ n no to ^rorw +be. 3*~ rou by mulWp\v)\rig i\f- b

3 v

0,4900000^

4 o -O 0^063c 2 52-35 6.3 7

o 4 -2.79^20 I
o o 10,0(20^2- m o ^ M

i rou «s nOmalUd by c\UdWcj H b^ 40,0 4204-2

r I o ^0,06^063 ^,'523S63
O I '2,79320
-o,o4W4£
C C 7.000G3 J

Subbrcxc^r\ 3 rouo fro

3
-O,06f0o3 •

o o 3,OOOCM
0 4 -O 04mW c -2,79320
0
0 i 7.00003 - 1

•H,

O 3, 0€>O0 f
G •~[Link] 4
4
7, OOOO3

3, oooo4
Xi ^
-2.5O0O 1
7. o o o o 3