f04jgf finds the solution of a linear least squares problem, , where is a real matrix and is an element vector. If the matrix of observations is not of full rank, then the minimal least squares solution is returned.
The routine may be called by the names f04jgf or nagf_linsys_real_gen_solve.
The minimal least squares solution of the problem is the vector of minimum (Euclidean) length which minimizes the length of the residual vector .
The real matrix is factorized as
where is an orthogonal matrix and is an upper triangular matrix. If is of full rank, then the least squares solution is given by
If is not of full rank, then the singular value decomposition of is obtained so that is factorized as
where and are orthogonal matrices and is the diagonal matrix
with , these being the singular values of . If the singular values are negligible, but is not negligible, relative to the data errors in , then the rank of is taken to be and the minimal least squares solution is given by
The routine also returns the value of the standard error
being the residual sum of squares and the rank of .
Lawson C L and Hanson R J (1974) Solving Least Squares Problems Prentice–Hall
On exit: if svd is returned as .FALSE., a is overwritten by details of the factorization of .
If svd is returned as .TRUE., the first rows of a are overwritten by the right-hand singular vectors, stored by rows; and the remaining rows of the array are used as workspace.
4: – IntegerInput
On entry: the first dimension of the array a as declared in the (sub)program from which f04jgf is called.
5: – Real (Kind=nag_wp) arrayInput/Output
On entry: the right-hand side vector .
On exit: the first elements of b contain the minimal least squares solution vector . The remaining elements are used for workspace.
6: – Real (Kind=nag_wp)Input
On entry: a relative tolerance to be used to determine the rank of . tol should be chosen as approximately the largest relative error in the elements of . For example, if the elements of are correct to about significant figures then tol should be set to about . See Section 9 for a description of how tol is used to determine rank. If tol is outside the range , where is the machine precision, the value is used in place of tol. For most problems this is unreasonably small.
7: – LogicalOutput
On exit: is returned as .FALSE. if the least squares solution has been obtained from the factorization of . In this case is of full rank. svd is returned as .TRUE. if the least squares solution has been obtained from the singular value decomposition of .
8: – Real (Kind=nag_wp)Output
On exit: the standard error, i.e., the value when , and the value zero when . Here is the residual vector and is the rank of .
9: – IntegerOutput
On exit: , the rank of the matrix . It should be noted that it is possible for irank to be returned as and svd to be returned as .TRUE.. This means that the matrix only just failed the test for nonsingularity.
10: – Real (Kind=nag_wp) arrayOutput
On exit: if svd is returned as .FALSE., then the first elements of work contain information on the factorization of (see argument a above), and contains the condition number of the upper triangular matrix .
If svd is returned as .TRUE., then the first elements of work contain the singular values of arranged in descending order and contains the total number of iterations taken by the algorithm. The rest of work is used as workspace.
11: – IntegerInput
On entry: the dimension of the array work as declared in the (sub)program from which f04jgf is called.
12: – IntegerInput/Output
On entry: ifail must be set to , or to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of means that an error message is printed while a value of means that it is not.
If halting is not appropriate, the value or is recommended. If message printing is undesirable, then the value is recommended. Otherwise, the value is recommended. When the value or is used it is essential to test the value of ifail on exit.
On exit: unless the routine detects an error or a warning has been flagged (see Section 6).
6Error Indicators and Warnings
If on entry or , explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
On entry, and .
On entry, lwork is too small. Minimum size required: .
On entry, and .
On entry, .
The algorithm has failed to converge to the singular values in iterations. This failure can only happen when the singular value decomposition is employed, but even then it is not likely to occur.
An unexpected error has been triggered by this routine. Please
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
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.
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.
The computed factors , , , and satisfy the relations
being the machine precision, and and being modest functions of and . Note that .
For a fuller discussion, covering the accuracy of the solution see Lawson and Hanson (1974), especially pages 50 and 95.
8Parallelism and Performance
Background information to multithreading can be found in the Multithreading documentation.
f04jgf is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
f04jgf 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.
If the least squares solution is obtained from the factorization then the time taken by the routine is approximately proportional to . If the least squares solution is obtained from the singular value decomposition then the time taken is approximately proportional to . The approximate proportionality factor is the same in each case.
This routine is column biased and so is suitable for use in paged environments.
Following the factorization of the condition number
is determined and if is such that
then is regarded as singular and the singular values of are computed. If this test is not satisfied, is regarded as nonsingular and the rank of is set to . When the singular values are computed the rank of , say , is returned as the largest integer such that
unless in which case is returned as zero. That is, singular values which satisfy are regarded as negligible because relative perturbations of order tol can make such singular values zero.
This example obtains a least squares solution for , where