Page 85 - Compact Numerical Methods For Computers

74 Compact numerical methods for computers
gives the triangular matrix in question. The choice of symbol

(6.19)

is deliberate, since the matrix product is lower-triangular by virtue of the
lower-triangular nature of each M ij and the lemmas below which will be stated
without proof (see, for instance, Mostow and Sampson 1969, p 226).
Lemma 1. The product of two lower-/upper-triangular matrices is also lower-
/upper-triangular.
Lemma 2. The inverse of a lower-/upper-triangular matrix is also lower-/upper-
triangular.
-l
By virtue of lemma 2, the matrix L (the inverse of L ) is lower-triangular. The
elements of L are given by
0 for j > i
L = 1 for j = i (6.20)
ij
m ij for j < i
This is proved simply by forming
- 1
L L = 1 (6.21)
using (6.19) and (6.20). Note that (6.18) implies that

A = LR (6.22)
which is a triangular decomposition of the matrix A. It permits us to rewrite the
original equations
A x = LRx = b (6.23)
as
- l - l
Rx = L Ax = L b = f. (6.24)
Because we can retain the triangular structure by writing the unit matrix
- 1
1 = DD (6.25)
where D is a non-singular diagonal matrix so that
- 1
A = LR = LDD R = L'R' (6.26)
the Gauss elimination is not the only means to obtain a triangular decomposition
of A.
In fact, the Gauss elimination procedure as it has been explained so far is
unsatisfactory for computation in finite arithmetic because the m are computed
ij
from current elements of the matrix, that is, those elements which have been
computed as a result of eliminating earlier elements in the scheme. Recall that
(6.12)
using the prime to denote current values of the matrix elements, that is, those
values which have resulted from eliminating elements in columns 1, 2, . . . , (j – 1).