NAG Toolbox: nag_linsys_real_gen_sparse_lsqsol (f04qa)

Purpose

Syntax

Description

References

Parameters

Compulsory Input Parameters

1:     $\mathrm{n}$ – int64int32nag_int scalar

$n$, the number of columns of the matrix $A$.

Constraint: $\mathbf{n}\ge 1$.

2:     $\mathrm{b}\left(\mathbf{m}\right)$ – double array

The right-hand side vector $b$.

3:     $\mathrm{aprod}$ – function handle or string containing name of m-file

aprod must perform the operations $y:=y+Ax$ and $x:=x+A^{\mathrm{T}}y$ for given vectors $x$ and $y$.

[mode, x, y, user] = aprod(mode, m, n, x, y, user, lruser, liuser)

Input Parameters

1:     $\mathrm{mode}$ – int64int32nag_int scalar

Specifies which operation is to be performed.

$\mathbf{mode}=1$

aprod must compute $y+Ax$.

$\mathbf{mode}=2$

aprod must compute $x+A^{\mathrm{T}}y$.

2:     $\mathrm{m}$ – int64int32nag_int scalar

$m$, the number of rows of $A$.

3:     $\mathrm{n}$ – int64int32nag_int scalar

$n$, the number of columns of $A$.

4:     $\mathrm{x}\left(\mathbf{n}\right)$ – double array

The vector $x$.

5:     $\mathrm{y}\left(\mathbf{m}\right)$ – double array

The vector $y$.

6:     $\mathrm{user}$ – Any MATLAB object

7:     $\mathrm{lruser}$ – int64int32nag_int scalar

8:     $\mathrm{liuser}$ – int64int32nag_int scalar

aprod is called from nag_linsys_real_gen_sparse_lsqsol (f04qa) with the object supplied to nag_linsys_real_gen_sparse_lsqsol (f04qa).

Output Parameters

1:     $\mathrm{mode}$ – int64int32nag_int scalar

May be used as a flag to indicate a failure in the computation of $y+Ax$ or $x+A^{\mathrm{T}}y$. If mode is negative on exit from aprod, nag_linsys_real_gen_sparse_lsqsol (f04qa) will exit immediately with ifail set to mode.

2:     $\mathrm{x}\left(\mathbf{n}\right)$ – double array

If $\mathbf{mode}=1$, x must be unchanged.

If $\mathbf{mode}=2$, x must contain $x+A^{\mathrm{T}}y$.

3:     $\mathrm{y}\left(\mathbf{m}\right)$ – double array

If $\mathbf{mode}=1$, y must contain $y+Ax$.

If $\mathbf{mode}=2$, y must be unchanged.

4:     $\mathrm{user}$ – Any MATLAB object

4:     $\mathrm{damp}$ – double scalar

The value $\lambda$. If either problem (1) or problem (2) is to be solved, then damp must be supplied as zero.

5:     $\mathrm{atol}$ – double scalar

The tolerance, ${\mathit{tol}}_1$, of the convergence criteria (6) and (7); it should be an estimate of the largest relative error in the elements of $A$. For example, if the elements of $A$ are correct to about $4$ significant figures, then atol should be set to about $5\times {10}^{-4}$. If atol is supplied as less than $\epsilon$, where $\epsilon$ is the machine precision, then the value $\epsilon$ is used instead of atol.

6:     $\mathrm{btol}$ – double scalar

The tolerance, ${\mathit{tol}}_2$, of the convergence criterion (6); it should be an estimate of the largest relative error in the elements of $B$. For example, if the elements of $B$ are correct to about $4$ significant figures, then btol should be set to about $5\times {10}^{-4}$. If btol is supplied as less than $\epsilon$, then the value $\epsilon$ is used instead of btol.

7:     $\mathrm{conlim}$ – double scalar

The value $c_{\lim }$ of equation (8); it should be an upper limit on the condition number of $\stackrel{-}{A}$. conlim should not normally be chosen much larger than $1.0/\mathbf{atol}$. If conlim is supplied as zero, then the value $1.0/\epsilon$ is used instead of conlim.

8:     $\mathrm{itnlim}$ – int64int32nag_int scalar

An upper limit on the number of iterations. If $\mathbf{itnlim}\le 0$, then the value n is used in place of itnlim, but for ill-conditioned problems a higher value of itnlim is likely to be necessary.

9:     $\mathrm{msglvl}$ – int64int32nag_int scalar

The level of printing from nag_linsys_real_gen_sparse_lsqsol (f04qa). If $\mathbf{msglvl}\le 0$, then no printing occurs, but otherwise messages will be output on the advisory message channel (see nag_file_set_unit_advisory (x04ab)). A description of the printed output is given in Printed output. The level of printing is determined as follows:

$\mathbf{msglvl}\le 0$

No printing.

$\mathbf{msglvl}=1$

A brief summary is printed just prior to return from nag_linsys_real_gen_sparse_lsqsol (f04qa).

$\mathbf{msglvl}\ge 2$

A summary line is printed periodically to monitor the progress of nag_linsys_real_gen_sparse_lsqsol (f04qa), together with a brief summary just prior to return from nag_linsys_real_gen_sparse_lsqsol (f04qa).

Optional Input Parameters

1:     $\mathrm{m}$ – int64int32nag_int scalar

Default: the dimension of the array b.

$m$, the number of rows of the matrix $A$.

Constraint: $\mathbf{m}\ge 1$.

2:     $\mathrm{user}$ – Any MATLAB object

user is not used by nag_linsys_real_gen_sparse_lsqsol (f04qa), but is passed to aprod. Note that for large objects it may be more efficient to use a global variable which is accessible from the m-files than to use user.

Output Parameters

1:     $\mathrm{b}\left(\mathbf{m}\right)$ – double array

2:     $\mathrm{x}\left(\mathbf{n}\right)$ – double array

The solution vector $x$.

3:     $\mathrm{se}\left(\mathbf{n}\right)$ – double array

The estimates of the standard errors of the components of $x$. Thus $\mathbf{se}\left(i\right)$ contains an estimate of $\sqrt{{\nu }_{ii}}$, where ${\nu }_{ii}$ is the $i$th diagonal element of the estimated variance-covariance matrix $V$. The estimates returned in se will be the lower bounds on the actual estimated standard errors, but will usually be correct to at least one significant figure.

4:     $\mathrm{itnlim}$ – int64int32nag_int scalar

Unchanged unless $\mathbf{itnlim}\le 0$ on entry, in which case it is set to n.

5:     $\mathrm{itn}$ – int64int32nag_int scalar

The number of iterations performed.

6:     $\mathrm{anorm}$ – double scalar

An estimate of $‖\stackrel{-}{A}‖$ for the matrix $\stackrel{-}{A}$ of (4).

7:     $\mathrm{acond}$ – double scalar

An estimate of $\mathrm{cond}\left(\stackrel{-}{A}\right)$ which is a lower bound.

8:     $\mathrm{rnorm}$ – double scalar

An estimate of $‖\stackrel{-}{r}‖$ for the residual, $\stackrel{-}{r}$, of (5) corresponding to the solution $x$ returned in x. Note that $‖\stackrel{-}{r}‖$ is the function being minimized.

9:     $\mathrm{arnorm}$ – double scalar

An estimate of the $‖{\stackrel{-}{A}}^{\mathrm{T}}\stackrel{-}{r}‖$ corresponding to the solution $x$ returned in x.

10:   $\mathrm{xnorm}$ – double scalar

An estimate of $‖x‖$ for the solution $x$ returned in x.

11:   $\mathrm{user}$ – Any MATLAB object

12:   $\mathrm{inform}$ – int64int32nag_int scalar

The reason for termination of nag_linsys_real_gen_sparse_lsqsol (f04qa).

$\mathbf{inform}=0$

The exact solution is $x=0$. No iterations are performed in this case.

$\mathbf{inform}=1$

The termination criterion of (6) has been satisfied with ${\mathit{tol}}_1$ and ${\mathit{tol}}_2$ as the values supplied in atol and btol respectively.

$\mathbf{inform}=2$

The termination criterion of (7) has been satisfied with ${\mathit{tol}}_1$ as the value supplied in atol.

$\mathbf{inform}=3$

The termination criterion of (6) has been satisfied with ${\mathit{tol}}_1$ and/or ${\mathit{tol}}_2$ as the value $\epsilon$, where $\epsilon$ is the machine precision. One or both of the values supplied in atol and btol must have been less than $\epsilon$ and was too small for this machine.

$\mathbf{inform}=4$

The termination criterion of (7) has been satisfied with ${\mathit{tol}}_1$ as the value $\epsilon$. The value supplied in atol must have been less than $\epsilon$ and was too small for this machine.

The values $\mathbf{inform}=5$, $6$ and $7$ correspond to failure with $\mathbf{ifail}=\mathbf{2}$, $\mathbf{3}$ and $\mathbf{4}$ respectively (see Error Indicators and Warnings) and when ifail is negative inform will be set to the same negative value.

13:   $\mathrm{ifail}$ – int64int32nag_int scalar

$\mathbf{ifail}=\mathbf{0}$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

W  $\mathbf{ifail}<0$

A negative value of ifail indicates an exit from nag_linsys_real_gen_sparse_lsqsol (f04qa) because you have set mode negative in aprod. The value of ifail will be the same as your setting of mode.

   $\mathbf{ifail}=1$

On entry,	$\mathbf{m}<1$,
or	$\mathbf{n}<1$,
or	$\mathit{lruser}<1$,
or	$\mathit{liuser}<1$.

   $\mathbf{ifail}=2$

The condition of (8) has been satisfied for the value of $c_{\lim }$ supplied in conlim. If this failure is unexpected you should check that aprod is working correctly. Although conditions (6) or (7) have not been satisfied, the values returned in rnorm, arnorm and xnorm may nevertheless indicate that an acceptable solution has been reached.

   $\mathbf{ifail}=3$

The condition of (8) has been satisfied for the value $c_{\lim }=1.0/\epsilon$, where $\epsilon$ is the machine precision. The matrix $\stackrel{-}{A}$ is nearly singular or rank deficient and the problem is too ill-conditioned for this machine. If this failure is unexpected, you should check that aprod is working correctly.

   $\mathbf{ifail}=4$

The limit on the number of iterations has been reached. The number of iterations required by nag_linsys_real_gen_sparse_lsqsol (f04qa) and the condition of the matrix $\stackrel{-}{A}$ can depend strongly on the scaling of the problem. Poor scaling of the rows and columns of $A$ should be avoided whenever possible.

   $\mathbf{ifail}=-99$

An unexpected error has been triggered by this routine. Please contact NAG.

   $\mathbf{ifail}=-399$

Your licence key may have expired or may not have been installed correctly.

   $\mathbf{ifail}=-999$

Dynamic memory allocation failed.

Accuracy

Further Comments

Description of the Printed Output

Example

Open in the MATLAB editor: f04qa_example

function f04qa_example


fprintf('f04qa example results\n\n');

m = int64(13);
n = int64(12);
a = [  1,  0,  0, -1,  0,  0,  0,  0,  0,  0,  0,  0;
       0,  1,  0,  0, -1,  0,  0,  0,  0,  0,  0,  0;
       0,  0,  1, -1,  0,  0,  0,  0,  0,  0,  0,  0;
      -1,  0, -1,  4, -1,  0,  0, -1,  0,  0,  0,  0;
       0, -1,  0, -1,  4, -1,  0,  0, -1,  0,  0,  0;
       0,  0,  0,  0, -1,  1,  0,  0,  0,  0,  0,  0;
       0,  0,  0,  0,  0,  0,  1, -1,  0,  0,  0,  0;
       0,  0,  0, -1,  0,  0, -1,  4, -1,  0, -1,  0;
       0,  0,  0,  0, -1,  0,  0, -1,  4, -1,  0, -1;
       0,  0,  0,  0,  0,  0,  0,  0, -1,  1,  0,  0;
       0,  0,  0,  0,  0,  0,  0, -1,  0,  0,  1,  0;
       0,  0,  0,  0,  0,  0,  0,  0, -1,  0,  0,  1;
       1,  1,  1,  0,  0,  1,  1,  0,  0,  1,  1,  1];
b = zeros(m,1);
b(4:5) = -0.01;
b(8:9) = -0.01;
b(m)   = 10;

damp   = 0;
atol   = 1e-05;
btol   = 1e-04;
conlim = 10^6 - 10^-11;
itnlim = int64(100);
msglvl = int64(1);

[b, x, se, itnlim, itn, anorm, acond, rnorm, arnorm, xnorm, ...
 ruser, inform, ifail] = ...
f04qa( ...
       n, b, @aprod, damp, atol, btol, conlim, itnlim, msglvl, 'user', a);
fprintf('\n\nSolution is x:\n');
fprintf('%9.3f%9.3f%9.3f%9.3f%9.3f%9.3f\n',x);
fprintf('\n\nNorm of the residual = %12.2e\n', rnorm);



function [mode, x, y, user] = aprod(mode, m, n, x, y, user)

  % a is passed as user

  if (mode == 1)
    y = y + user*x;
  else
    x = x + transpose(user)*y;
  end

f04qa example results

 Output from sparse linear least squares solver.

 Least squares solution of  A*x = b

 The matrix A has     13 rows and     12 cols
 The damping parameter is  damp =      0.00E+00

 atol =     1.00E-05     conlim =      1.00E+06
 btol =     1.00E-04     itnlim =    100

 No. of iterations  =      2
 stopping condition =      2
 ( The least squares solution is good enough, given atol )


 Actual        norm(rbar), norm(x)            1.15E-02    4.33E+00
    Norm(transpose(Abar)*rbar)                6.98E-15
 Estimates of  norm(Abar), cond(Abar)         4.12E+00    2.45E+00


Solution is x:
    1.250    1.250    1.250    1.247    1.247    1.250
    1.250    1.247    1.247    1.250    1.250    1.250


Norm of the residual =     1.15e-02