nag_lone_fit (e02gac) calculates an  solution to an over-determined system of linear equations.

Given a matrix  with  rows and  columns  and a vector  with  elements, the function calculates an  solution to the over-determined system of equations

That is to say, it calculates a vector , with  elements, which minimizes the  norm (the sum of the absolute values) of the residuals

where the residuals  are given by

Here  is the element in row  and column  of ,  is the th element of  and  the th element of . The matrix  need not be of full rank.

Typically in applications to data fitting, data consisting of  points with co-ordinates  are to be approximated in the  norm by a linear combination of known functions ,

This is equivalent to fitting an  solution to the over-determined system of equations

Thus if, for each value of  and , the element  of the matrix  in the previous paragraph is set equal to the value of  and  is set equal to , the solution vector  will contain the required values of the . Note that the independent variable  above can, instead, be a vector of several independent variables (this includes the case where each  is a function of a different variable, or set of variables).

The algorithm is a modification of the simplex method of linear programming applied to the primal formulation of the  problem (see Barrodale and Roberts (1973) and Barrodale and Roberts (1974)). The modification allows several neighbouring simplex vertices to be passed through in a single iteration, providing a substantial improvement in efficiency.

"NE_ALLOC_FAIL"

Dynamic memory allocation failed.

"NE_BAD_PARAM"

On entry, argument  had an illegal value.

"NE_INT"

 On entry, . Constraint: .

"NE_INT_2"

On entry, , . Constraint: .

 On entry, : , .

"NE_INTERNAL_ERROR"

An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please consult NAG for assistance.

"NE_NON_UNIQUE"

 An optimal solution has been obtained, but may not be unique.

"NE_TERMINATION_FAILURE"

 Premature termination due to rounding errors. Try using larger value of toler: .

Experience suggests that the computational accuracy of the solution  is comparable with the accuracy that could be obtained by applying Gaussian elimination with partial pivoting to the  equations satisfied by this algorithm (i.e., those equations with zero residuals). The accuracy therefore varies with the conditioning of the problem, but has been found generally very satisfactory in practice.

The effects of  and  on the time and on the number of iterations in the Simplex Method vary from problem to problem, but typically the number of iterations is a small multiple of  and the total time taken is approximately proportional to .

It is recommended that, before the function is entered, the columns of the matrix  are scaled so that the largest element in each column is of the order of unity. This should improve the conditioning of the matrix, and also enable the argument toler to perform its correct function. The solution  obtained will then, of course, relate to the scaled form of the matrix. Thus if the scaling is such that, for each , the elements of the th column are multiplied by the constant , the element  of the solution vector  must be multiplied by  if it is desired to recover the solution corresponding to the original matrix .