hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_linsys_real_gen_lsqsol (f04am)

Purpose

nag_linsys_real_gen_lsqsol (f04am) calculates the accurate least squares solution of a set of mm linear equations in nn unknowns, mnmn and rank = n=n, with multiple right-hand sides, AX = BAX=B, using a QRQR factorization and iterative refinement.

Syntax

[x, qr, alpha, ipiv, ifail] = f04am(a, b, eps, 'm', m, 'n', n, 'ir', ir)
[x, qr, alpha, ipiv, ifail] = nag_linsys_real_gen_lsqsol(a, b, eps, 'm', m, 'n', n, 'ir', ir)
Note: the interface to this routine has changed since earlier releases of the toolbox:
Mark 22: m has been made optional
.

Description

To compute the least squares solution to a set of mm linear equations in nn unknowns (mn)(mn) AX = BAX=B, nag_linsys_real_gen_lsqsol (f04am) first computes a QRQR factorization of AA with column pivoting, AP = QRAP=QR, where RR is upper triangular, QQ is an mm by mm orthogonal matrix, and PP is a permutation matrix. QTQT is applied to the mm by rr right-hand side matrix BB to give C = QTBC=QTB, and the nn by rr solution matrix XX is calculated, to a first approximation, by back-substitution in RX = CRX=C. The residual matrix S = BAXS=B-AX is calculated using additional precision, and a correction DD to XX is computed as the least squares solution to AD = SAD=S. XX is replaced by X + DX+D and this iterative refinement of the solution is repeated until full machine accuracy has been obtained.

References

Wilkinson J H and Reinsch C (1971) Handbook for Automatic Computation II, Linear Algebra Springer–Verlag

Parameters

Compulsory Input Parameters

1:     a(lda,n) – double array
lda, the first dimension of the array, must satisfy the constraint ldamldam.
The mm by nn matrix AA.
2:     b(ldb,ir) – double array
ldb, the first dimension of the array, must satisfy the constraint ldbmldbm.
The mm by rr right-hand side matrix BB.
3:     eps – double scalar
Must be set to the value of the machine precision.

Optional Input Parameters

1:     m – int64int32nag_int scalar
Default: The first dimension of the arrays a, b. (An error is raised if these dimensions are not equal.)
mm, the number of rows of the matrix AA, i.e., the number of equations.
Constraint: m1m1.
2:     n – int64int32nag_int scalar
Default: The second dimension of the array a.
nn, the number of columns of the matrix AA, i.e., the number of unknowns.
Constraint: 0nm0nm.
3:     ir – int64int32nag_int scalar
Default: The second dimension of the array b.
rr, the number of right-hand sides.

Input Parameters Omitted from the MATLAB Interface

lda ldx ldb ldqr e y z r

Output Parameters

1:     x(ldx,ir) – double array
ldxnldxn.
The nn by rr solution matrix XX.
2:     qr(ldqr,n) – double array
ldqrmldqrm.
Details of the QRQR factorization.
3:     alpha(n) – double array
The diagonal elements of the upper triangular matrix RR.
4:     ipiv(n) – int64int32nag_int array
Details of the column interchanges.
5:     ifail – int64int32nag_int scalar
ifail = 0ifail=0 unless the function detects an error (see [Error Indicators and Warnings]).

Error Indicators and Warnings

Errors or warnings detected by the function:
  ifail = 1ifail=1
The rank of AA is less than nn; the problem does not have a unique solution.
  ifail = 2ifail=2
The iterative refinement fails to converge, i.e., the matrix AA is too ill-conditioned.

Accuracy

Although the correction process is continued until the solution has converged to full machine accuracy, all the figures in the final solution may not be correct since the correction DD to XX is itself the solution to a linear least squares problem. For a detailed error analysis see page 116 of Wilkinson and Reinsch (1971).

Further Comments

The time taken by nag_linsys_real_gen_lsqsol (f04am) is approximately proportional to n2(3mn)n2(3m-n), provided rr is small compared with nn.

Example

function nag_linsys_real_gen_lsqsol_example
a = [1.1, 0.9;
     1.2, 1;
     1, 1];
b = [2.2;
     2.3;
     2.1];
epsilon = 1.111307226797642e-16;
[x, qr, alpha, ipiv, ifail] = nag_linsys_real_gen_lsqsol(a, b, epsilon)
 

x =

    1.3010
    0.7935


qr =

    3.0105   -1.6697
    1.2000   -0.1727
    1.0000    0.1464


alpha =

   -1.9105
    0.1484


ipiv =

                    1
                    2


ifail =

                    0


function f04am_example
a = [1.1, 0.9;
     1.2, 1;
     1, 1];
b = [2.2;
     2.3;
     2.1];
epsilon = 1.111307226797642e-16;
[x, qr, alpha, ipiv, ifail] = f04am(a, b, epsilon)
 

x =

    1.3010
    0.7935


qr =

    3.0105   -1.6697
    1.2000   -0.1727
    1.0000    0.1464


alpha =

   -1.9105
    0.1484


ipiv =

                    1
                    2


ifail =

                    0



PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013