Page 84 - Compact Numerical Methods For Computers

Linear equations—a direct approach 73
Furthermore, the sum of any two equations of (6.5) is also an equation of the set
(6.5). Multiplying the first equation (i.e. that for i = 1) by
m = A /A (6.6)
i1 i1 11
and subtracting it from the ith equation gives new equations

for i = 2, 3, . . ., n
(6.7)
where

= A – m A 1 k (6.8)
i 1
ik
and
(6.9)
But
(6.10)

so that we have eliminated all but the first element of column 1 of A. This process
can now be repeated with new equations 2, 3, . . . , n to eliminate all but the first
two elements of column 2. The element A is unchanged because equation 1 is
12
not a participant in this set of eliminations. By performing (n - 1) such sets of
eliminations we arrive at an upper-triangular matrix R. This procedure can be
thought of as an ordered sequence of multiplications by elementary matrices. The
elementary matrix which eliminates A will be denoted M ij and is defined by
ij
M = 1 – m ij i j (6.11)
n
ij
where
m ij = A /A jj (6.12)
ij
(the elements in A are all current, not original, values) and where ij is the matrix
having 1 in the position ij and zeros elsewhere, that is
(6.13)
which uses the Kronecker delta, d ir = 1 for i = r and d = 0 otherwise. The effect
ir
on M ij when pre-multiplying a matrix A is to replace the ith row with the
difference between the ith row and m ij times the jth row, that is, if

A' = M A (6.14)
i j
then
for r i (6.15)
(6.16)
with k = 1, 2, . . . , n. Since A = 0 for k < j, for computational purposes one need
jk
only use k = j, (j+ 1), . . . , n. Thus

(6.17)
- 1
= L A (6.18)