Page 105 - Compact Numerical Methods For Computers

Chapter 8

THE SYMMETRIC POSITIVE DEFINITE
MATRIX AGAIN

8.1. THE GAUSS-JORDAN REDUCTTON
Another approach to the solution of linear equations (and in fact nonlinear ones)
is the method of substitution. Here, one of the unknowns x is chosen and one of
k
the equations in which it has a non-zero coefficient is used to generate an
expression for it in terms of the other x , j k, and b. For instance, given
j
Ax = b (2.2)
and A 11 0, we might use

(8.1)

The substitution of this into the other equations gives a new set of (n - 1)
equations in (n - 1) unknowns which we shall write
A'x' = b' (8.2)

in which the indices will run from 2 to n. In fact x' will consist of the last (n - 1)
elements of x. By means of (8.1) it is simple to show that

(8.3)
and
(8.4)
for k, j = 2, . . . , n. Notice that if b is included as the (n + 1)th column of A, (8.4) is
the only formula needed, though j must now run to (n + 1).
We now have a set of equations of order (n – l), and can continue the process
until only a set of equations of order 1 remains. Then, using the trivial solution of
this, a set of substitutions gives the desired solution to the original equations. This
is entirely equivalent to Gauss elimination (without pivoting) and back-substitution,
and all the arithmetic is the same.
Consider, however, that the second substitution is made not only of x into the
2
remaining (n – 2) equations, but also into the formula (8.1) for x . Then the final
1
order-1 equations yield all the x j at once. From the viewpoint of elimination it
corresponds to eliminating upper-triangular elements in the matrix R in the
system
Rx = f (6.4)
94