Page 65 - Compact Numerical Methods For Computers

54 Compact numerical methods for computers
4.3. EXTENSION TO A SINGULAR-VALUE DECOMPOSITION

In order to determine if linear dependencies are present, it is possible to extend
the Givens’ reduction and compute a singular-value decomposition by ortho-
gonalising the rows of R by plane rotations which act from the left. It is not
necessary to accumulate the transformations in a matrix U; instead they can be
T
applied directly to Q b, in fact, to the first n elements of this vector which form
d . The rotations can be thought of as acting all at once as the orthogonal matrix
1
T
P . Applying this to equation (4.14) gives
T T
P Rx = P d 1 = f. (4.15)
T
However, the rows of P R are orthogonal, that is
T
P R = SV T (4.16)
with
T 2
SV VS = S . (3.17)
Combining the Givens’ reduction and orthogonalisation steps gives

T
T
P Q A = P T (4.18)
or
(4.19)

which is a singular-value decomposition.
As in the case of the columnwise orthogonalisation, small singular values (i.e.
T
rows of P R having small norm) will cause V to possess some unnormalised rows
having essentially zero elements. In this case (4.17) will not be correct. since

(4.20)

where k is the number of singular values larger than some pre-assigned tolerance
for zero. Since in the solution of least-squares problems these rows always act
+
only in products with S or S , this presents no great difficulty to programming an
algorithm using the above Givens’ reduction/row orthogonalisation method.

4.4. SOME LABOUR-SAVING DEVICES

The above method is not nearly so complicated to implement as it may appear.
Firstly, all the plane rotations are row-wise for both the Givens’ reduction and the
orthogonalisation. Moreover, one or more (say g) vectors b can be concatenated
with the matrix A so that rotations do not have to be applied separately to these,
but appear to act on a single matrix.
The second observation which reduces the programming effort is that the rows
of this matrix (A, b) are needed only one at a time. Consider a working array