Page 18 - Matrix Analysis & Applied Linear Algebra

10 Chapter 1 Linear Equations

Algorithm for Back Substitution

Determine the x i ’s from (1.2.10) by first setting x n = c n /t nn and then
recursively computing

1
x i = (c i − t i,i+1 x i+1 − t i,i+2 x i+2 −· · · − t in x n )
t ii
for i = n − 1,n − 2,..., 2, 1.

One way to gauge the efficiency of an algorithm is to count the number of
3
arithmetical operations required. For a variety of reasons, no distinction is made
between additions and subtractions, and no distinction is made between multipli-
cations and divisions. Furthermore, multiplications/divisions are usually counted
separately from additions/subtractions. Even if you do not work through the de-
tails, it is important that you be aware of the operational counts for Gaussian
elimination with back substitution so that you will have a basis for comparison
when other algorithms are encountered.

Gaussian Elimination Operation Counts

Gaussian elimination with back substitution applied to an n × n system
requires
n 3 2 n
+ n − multiplications/divisions
3 3
and
n 3 n 2 5n
+ − additions/subtractions.
3 2 6
3
As n grows, the n /3 term dominates each of these expressions. There-
fore, the important thing to remember is that Gaussian elimination with
3
back substitution on an n × n system requires about n /3 multiplica-
tions/divisions and about the same number of additions/subtractions.

3
Operation counts alone may no longer be as important as they once were in gauging the ef-
ficiency of an algorithm. Older computers executed instructions sequentially,whereas some
contemporary machines are capable of executing instructions in parallel so that different nu-
merical tasks can be performed simultaneously. An algorithm that lends itself to parallelism
may have a higher operational count but might nevertheless run faster on a parallel machine
than an algorithm with a lesser operational count that cannot take advantage of parallelism.