NAG Library Routine Document

F04AMF

INTEGER	LDA, LDX, LDB, M, N, IR, LDQR, IPIV(N), IFAIL
REAL (KIND=nag_wp)	A(LDA,N), X(LDX,IR), B(LDB,IR), EPS, QR(LDQR,N), ALPHA(N), E(N), Y(N), Z(N), R(M)

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 Parameters

1: A(LDA,N) – REAL (KIND=nag_wp) arrayInput: On entry: the $m$ by $n$ matrix $A$ .
2: LDA – INTEGERInput: 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) arrayOutput: On exit: the $n$ by $r$ solution matrix $X$ .
4: LDX – INTEGERInput: 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) arrayInput: On entry: the $m$ by $r$ right-hand side matrix $B$ .
6: LDB – INTEGERInput: 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 – INTEGERInput: On entry: $m$ , the number of rows of the matrix $A$ , i.e., the number of equations.
Constraint: $M \geq 1$ .
8: N – INTEGERInput: 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 – INTEGERInput: 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) arrayOutput: On exit: details of the $Q R$ factorization.
12: LDQR – INTEGERInput: 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) arrayOutput: On exit: the diagonal elements of the upper triangular matrix $R$ .
14: E(N) – REAL (KIND=nag_wp) arrayWorkspace
15: Y(N) – REAL (KIND=nag_wp) arrayWorkspace
16: Z(N) – REAL (KIND=nag_wp) arrayWorkspace
17: R(M) – REAL (KIND=nag_wp) arrayWorkspace
18: IPIV(N) – INTEGER arrayOutput: On exit: details of the column interchanges.
19: IFAIL – INTEGERInput/Output: On entry: IFAIL must be set to $0$ , $- 1 or 1$ . If you are unfamiliar with this parameter you should refer to Section 3.3 in the Essential Introduction for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value $- 1 or 1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is $0$ . 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, i.e., the matrix $A$ is too ill-conditioned.

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 Further Comments

The time taken by F04AMF is approximately proportional to

n^{2} (3 m - n)

, provided

r

is small compared with

n

9 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}

NAG Library Routine DocumentF04AMF

+− Contents

1 Purpose

2 Specification