Page 109 - Compact Numerical Methods For Computers

98 Compact numerical methods for computers
substitution formulae for step k of the algorithm (i, j k)
(8.10)

(8.11)
(8.12)
(8.13)
For k = 1, therefore, the condition Y = – X T is given as

(8.14)
from equations (8.11) and (8.12).
Now assume

(8.15)
1 < h < k–1, k < j < n, for any of k = 2, . . . , n. We will show that the hypothesis is
then true for k. By equation (8.13) we have

(8.16)
where we use the identity
(8.17)

since these elements belong to a submatrix Z which is symmetric in accord with
the earlier discussion.
It remains to establish that
for j = (k+1), . . . , n (8.18)

but this follows immediately from equations (8.11) and (8.12) and the symmetry of
the submatrix Z. This completes the induction.
There is one more trick needed to make the Bauer-Reinsch algorithm ex-
tremely compact. This is a sequential cyclic re-ordering of the rows and columns
of A so that the arithmetic is always performed with k = 1. This re-numeration
relabels (j + 1) as j for j = 1, 2, . . . , (n - 1) and relabels 1 as n. Letting
(8.19)
this gives a new Gauss-Jordan step

(8.20)
(8.21)
(8.22)
(8.23)
for i, j = 2, . . . , n.