** Next:** Error Bounds for
Generalized ** Up:** Error
Bounds for Linear ** Previous:** Error Bounds for Linear ** Contents** ** Index**

##

Further Details: Error Bounds for Linear Least Squares Problems

The conventional error analysis of linear least squares problems goes
as follows. As above, let
be the solution to minimizing
computed by LAPACK using one of the least squares drivers xGELS, xGELSX,
xGELSY, xGELSS or xGELSD (see subsection 2.3.2). We discuss the most common
case, where *A* is overdetermined (i.e.,
has more rows than columns) and has full rank [16,25,55,67]:

The computed solution
has a small normwise backward error. In other words
minimizes
, where *E* and *f* satisfy

and *p*(*n*) is a modestly growing function
of *n*. We take *p*(*n*)=1 in the code fragments
above. Let
(approximated by 1/`RCOND` in the above code fragments),
(= `RNORM` above), and
(`SINT = RNORM / BNORM` above). Here,
is the acute angle between the vectors
and *b*. Then when
is small, the error
is bounded by

where
= `COST` and
= `TANT` in the code fragments above.

We avoid overflow by making sure `RCOND` and `COST` are
both at least
`EPSMCH`, and by handling the case of a zero `B` matrix separately
(`BNORM = 0`).

may be computed directly from the singular values of *A* returned
by xGELSS or xGELSD (as in the code fragment) or by xGESVD or xGESDD. It
may also be approximated by using xTRCON following calls to xGELS, xGELSX
or xGELSY. xTRCON estimates
or
instead of
, but these can differ from
by at most a factor of *n*.

If *A* is rank-deficient, xGELSS, xGELSD, xGELSY and xGELSX
can be used to **regularize** the problem by treating all singular values less than a user-specified
threshold (
) as exactly zero. The number of singular values treated as nonzero is returned
in `RANK`. See [16,55,67] for
error bounds in this case, as well as [28] for the underdetermined case. The ability to deal with rank-deficient
matrices is the principal attraction of these four drivers, which are more
expensive than the simple driver xGELS.

The solution of the overdetermined, full-rank problem may also be characterized as the solution
of the linear system of equations

By solving this linear system using xyyRFS or xyySVX (see section 4.4) componentwise error bounds can also
be obtained [7].

** Next:** Error Bounds for
Generalized ** Up:** Error
Bounds for Linear ** Previous:** Error Bounds for Linear ** Contents** ** Index**
*Susan Blackford*

*1999-10-01*