Integer, Intent (In)	::	lda, ldx, ldb, m, n, ir, ldqr
Integer, Intent (Inout)	::	ifail
Integer, Intent (Out)	::	ipiv(n)
Real (Kind=nag_wp), Intent (In)	::	a(lda,n), b(ldb,ir), eps
Real (Kind=nag_wp), Intent (Inout)	::	x(ldx,ir), qr(ldqr,n)
Real (Kind=nag_wp), Intent (Out)	::	alpha(n), e(n), y(n), z(n), r(m)

C Header Interface

#include <nag.h>

void

f04amf_ (const double a[], const Integer *lda, double x[], const Integer *ldx, const double b[], const Integer *ldb, const Integer *m, const Integer *n, const Integer *ir, const double *eps, double qr[], const Integer *ldqr, double alpha[], double e[], double y[], double z[], double r[], Integer ipiv[], Integer *ifail)

The routine may be called by the names f04amf or nagf_linsys_real_gen_lsqsol.

3 Description

To compute the least squares solution to a set of

m

linear equations in

n

unknowns

(m \geq n)

A X = B

, f04amf first computes a

Q R

factorization of

A

with column pivoting,

A P = Q R

, where

R

is upper triangular,

Q

is an

m

m

orthogonal matrix, and

P

is a permutation matrix.

Q^{T}

is applied to the

m

r

right-hand side matrix

B

to give

C = Q^{T} B

, and the

n

r

solution matrix

X

is calculated, to a first approximation, by back-substitution in

R X = C

. The residual matrix

S = B - A X

is calculated using additional precision, and a correction

D

X

is computed as the least squares solution to

A D = S

X

is replaced by

X + D

and this iterative refinement of the solution is repeated until full machine accuracy has been obtained.

4 References

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

5 Arguments

1: $a (lda, n)$ – Real (Kind=nag_wp) array Input: On entry: the $m$ by $n$ matrix $A$ .
2: $lda$ – Integer Input: On entry: the first dimension of the array a as declared in the (sub)program from which f04amf is called.

Constraint: $lda \geq m$ .
3: $x (ldx, ir)$ – Real (Kind=nag_wp) array Output: On exit: the $n$ by $r$ solution matrix $X$ .
4: $ldx$ – Integer Input: On entry: the first dimension of the array x as declared in the (sub)program from which f04amf is called.

Constraint: $ldx \geq n$ .
5: $b (ldb, ir)$ – Real (Kind=nag_wp) array Input: On entry: the $m$ by $r$ right-hand side matrix $B$ .
6: $ldb$ – Integer Input: On entry: the first dimension of the array b as declared in the (sub)program from which f04amf is called.

Constraint: $ldb \geq m$ .
7: $m$ – Integer Input: On entry: $m$ , the number of rows of the matrix $A$ , i.e., the number of equations.

Constraint: $m \geq 1$ .
8: $n$ – Integer Input: On entry: $n$ , the number of columns of the matrix $A$ , i.e., the number of unknowns.

Constraint: $0 \leq n \leq m$ .
9: $ir$ – Integer Input: On entry: $r$ , the number of right-hand sides.
10: $eps$ – Real (Kind=nag_wp) Input: On entry: must be set to the value of the machine precision.
11: $qr (ldqr, n)$ – Real (Kind=nag_wp) array Output: On exit: details of the $Q R$ factorization.
12: $ldqr$ – Integer Input: On entry: the first dimension of the array qr as declared in the (sub)program from which f04amf is called.

Constraint: $ldqr \geq m$ .
13: $alpha (n)$ – Real (Kind=nag_wp) array Output: On exit: the diagonal elements of the upper triangular matrix $R$ .
14: $e (n)$ – Real (Kind=nag_wp) array Workspace
15: $y (n)$ – Real (Kind=nag_wp) array Workspace
16: $z (n)$ – Real (Kind=nag_wp) array Workspace
17: $r (m)$ – Real (Kind=nag_wp) array Workspace
18: $ipiv (n)$ – Integer array Output: On exit: details of the column interchanges.
19: $ifail$ – Integer Input/Output: On entry: ifail must be set to $0$ , $- 1$ or $1$ to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of $0$ causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of $- 1$ means that an error message is printed while a value of $1$ means that it is not.

If halting is not appropriate, the value $- 1$ or $1$ is recommended. If message printing is undesirable, then the value $1$ is recommended. Otherwise, the value $0$ is recommended. When the value $- 1$ or $1$ is used it is essential to test the value of ifail on exit.

On exit: $ifail = 0$ unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry

ifail = 0

- 1

, explanatory error messages are output on the current error message unit (as defined by x04aaf).

Errors or warnings detected by the routine:

$ifail = 1$: The rank of a is less than n. The problem does not have a unique solution.

$ifail = 2$: The iterative refinement fails to converge. The matrix $A$ is too ill-conditioned.

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.
See Section 7 in the Introduction to the NAG Library FL Interface for further information.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.

$ifail = - 999$: Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 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

D

X

is itself the solution to a linear least squares problem. For a detailed error analysis see page 116 of Wilkinson and Reinsch (1971).

8 Parallelism and Performance

f04amf makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.

Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

The time taken by f04amf is approximately proportional to

n^{2} (3 m - n)

, provided

r

is small compared with

n

10 Example

This example calculates the accurate least squares solution of the equations

\begin{array}{l} 1.1 x_{1} + 0.9 x_{2} = 2.2 \\ 1.2 x_{1} + 1.0 x_{2} = 2.3 \\ 1.0 x_{1} + 1.0 x_{2} = 2.1 \end{array}

f04am: FL CL CPP AD

NAG FL Interfacef04amf (real_​gen_​lsqsol)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG FL Interface
f04amf (real_gen_lsqsol)