Solves a linear least-squares problem with iterative refinement.
Required Arguments
A — Real NRA by NCA matrix containing the coefficient matrix of the least-squares system to be solved. (Input)
B — Real vector of length NRA containing the right-hand side of the least-squares system. (Input)
X — Real vector of length NCA containing the solution vector with components corresponding to the columns not used set to zero. (Output)
Optional Arguments
NRA — Number of rows of A.
(Input)
Default: NRA = size (A,1).
NCA — Number of columns of A.
(Input)
Default: NCA = size (A,2).
LDA — Leading dimension of A exactly as specified
in the dimension statement of the calling program.
(Input)
Default: LDA = size (A,1).
TOL — Real scalar containing the nonnegative
tolerance used to determine the subset of columns of A to be included in
the solution. (Input)
If TOL is zero, a full
complement of min(NRA, NCA) columns is used.
See Comments.
Default: TOL = 0.0
RES — Real vector of length NRA containing the residual vector B − AX. (Output)
KBASIS — Integer scalar containing the number of columns used in the solution. (Output)
FORTRAN 90 Interface
Generic: CALL LSBRR (A, B, X [,…])
Specific: The specific interface names are S_LSBRR and D_LSBRR.
FORTRAN 77 Interface
Single: CALL LSBRR (NRA, NCA, A, LDA, B, TOL, X, RES, KBASIS)
Double: The double precision name is DLSBRR.
Description
Routine LSBRR solves the linear least-squares problem using iterative refinement. The iterative refinement algorithm is due to Björck (1967, 1968). It is also described by Golub and Van Loan (1983, pages 182−183).
Comments
1. Workspace may be explicitly provided, if desired, by use of L2BRR/DL2BRR. The reference is:
CALL L2BRR (NRA, NCA, A, LDA, B, TOL, X, RES, KBASIS, QR, BRRUX,
IPVT, WK)
The additional arguments are as follows:
QR — Work vector of length NRA * NCA representing an NRA by NCA matrix that contains information from the QR factorization of A. See LQRRR for details.
BRRUX — Work vector of length NCA containing information about the orthogonal factor of the QR factorization of A. See LQRRR for details.
IPVT — Integer work vector of length NCA containing the pivoting information for the QR factorization of A. See LQRRR for details.
WK — Work vector of length NRA + 2 * NCA − 1.
2. Informational error
Type Code
4 1 The data matrix is too ill-conditioned for iterative refinement to be effective.
3. Routine
LSBRR calculates
the QR decomposition with pivoting of a matrix A and tests the
diagonal elements against a user-supplied tolerance TOL. The first integer
KBASIS =
k is determined for which
In effect, this condition implies that a set of columns with a condition number approximately bounded by 1.0/TOL is used. Then, LQRSL performs a truncated fit of the first KBASIS columns of the permuted A to an input vector B. The coefficient of this fit is unscrambled to correspond to the original columns of A, and the coefficients corresponding to unused columns are set to zero. It may be helpful to scale the rows and columns of A so that the error estimates in the elements of the scaled matrix are roughly equal to TOL. The iterative refinement method of Björck is then applied to this factorization.
4. Integer Options with Chapter 11 Options Manager
16 This
option uses four values to solve memory bank conflict (access inefficiency)
problems. In routine L2BRR the leading
dimension of QR
is increased by IVAL(3) when N is a multiple of
IVAL(4). The
values IVAL(3)
and IVAL(4) are
temporarily replaced by IVAL(1) and IVAL(2), respectively, in
LSBRR.
Additional memory allocation for QR and option value
restoration are done automatically in LSBRR. Users directly
calling L2BRR
can allocate additional space for QR and set IVAL(3) and IVAL(4) so that memory
bank conflicts no longer cause inefficiencies. There is no requirement that
users change existing applications that use LSBRR or L2BRR. Default values
for the option are
IVAL(*) = 1, 16, 0, 1.
17 This option has two valuess that determine if the L1 condition number is to be computed. Routine LSBRR temporarily replaces IVAL(2) by IVAL(1). The routine L2CRG computes the condition number if IVAL(2) = 2. Otherwise L2CRG skips this computation. LSBRR restores the option. Default values for the option are IVAL(*) = 1, 2.
Example
This example solves the linear least-squares problem with A, an 8 × 4 matrix. Note that the second and fourth columns of A are identical. Routine LSBRR determines that there are three columns in the basis.
USE
LSBRR_INT
USE
UMACH_INT
USE WRRRN_INT
! Declare variables
PARAMETER (NRA=8, NCA=4, LDA=NRA)
REAL A(LDA,NCA), B(NRA), X(NCA), RES(NRA), TOL
!
! Set values for A
!
! A = ( 1 5 15 5 )
! ( 1 4 17 4 )
! ( 1 7 14 7 )
! ( 1 3 18 3 )
! ( 1 1 15 1 )
! ( 1 8 11 8 )
! ( 1 3 9 3 )
! ( 1 4 10 4 )
!
DATA A/8*1, 5., 4., 7., 3., 1., 8., 3., 4., 15., 17., 14., &
18., 15., 11., 9., 10., 5., 4., 7., 3., 1., 8., 3., 4. /
!
! Set values for B
!
DATA B/ 30., 31., 35., 29., 18., 35., 20., 22. /
!
! Solve the least squares problem
TOL = 1.0E-4
CALL LSBRR (A, B, X, tol=tol, RES=RES, KBASIS=KBASIS)
! Print results
CALL UMACH (2, NOUT)
WRITE (NOUT,*) 'KBASIS = ', KBASIS
CALL WRRRN ('X', X, 1, NCA, 1)
CALL WRRRN ('RES', RES, 1, NRA, 1)
!
END
Output
KBASIS = 3
X
1 2 3 4
0.636 2.845 1.058 0.000
RES
1 2 3 4 5 6 7 8
-0.733 0.996 -0.365 0.783 -1.353 -0.036 1.306 -0.597
|
Visual Numerics, Inc. PHONE: 713.784.3131 FAX:713.781.9260 |