Page 67 - Compact Numerical Methods For Computers

56 Compact numerical methods for computers
by application of equation (4.16) and the condition that S , S k+2 , . . . , S , are all
n
k+l
‘zero’. Thus, using
(4.28)
and (4.22) with (4.27) and (4.23), the residual sum of squares in the rank-deficient
case is
(4.29)
From a practical point of view (4.29) is very convenient, since the computation of
the residual sum of squares is now clearly linked to those singular values which
are chosen to be effectively zero by the user of the method. The calculation is
once again as a sum of squared terms, so there are no difficulties of digit
cancellation.
The vector
(4.30)

in the context of statistical calculations is referred to as a set of uncorrelated
residuals (Golub and Styan 1973).
Nash and Lefkovitch (1976) report other experience with algorithm 4. In
particular, the largest problem I have solved using it involved 25 independent
variables (including a constant) and two dependent variables, for which there were
196 observations. This problem was initially run on a Hewlett-Packard 9830
calculator, where approximately four hours elapsed in the computation. Later the
same data were presented to a FORTRAN version of the algorithm on both Univac
1108 and IBM 370/168 equipment, which each required about 12 seconds of
processor time. Despite the order-of-magnitude differences in the timings bet-
ween the computers and the calculator, they are in fact roughly proportional to
the cycle times of the machines. Moreover, as the problem has a singularity of
order 2, conventional least-squares regression programs were unable to solve it,
and when it was first brought to me the program on the HP 9830 was the only one
on hand which could handle it.
Algorithm 4. Givens’ reductions, singular-value decomposition and least-squares
solution
procedure GivSVD( n : integer; {order of problem}
nRHS: integer; {number of right hand sides}
var B: x-matrix; {matrix of solution vectors}
var rss: r-vector; {residual sums of squares}
var svs: x-vector; {singular values}
var W: rmatrix; {returns V-transpose}
var nobs : integer); {number of observations}
{alg04.pas ==
Givens’ reduction, singular value decomposition and least squares
solution.
In this program, which is designed to use a very small working array yet
solve least squares problems with large numbers of observations, we do not
explicitly calculate the U matrix of the singular value decomposition.