E222 Solution of Overdetermined Linear System in the Chebychev Norm

Subroutine subprograms RCHEBN and DCHEBN find the Chebyshev or minimax solution to a set of overdetermined linear equations $Ax=b$ , i.e. the vector x which minimizes

$c\; =\; max$_1≤i≤mc_i = max_1≤i≤m| b_i- ∑_j=1ⁿa_ijx_j|.

On computers other than CDC or Cray, only the double-precision version DCHEBN is available. On CDC and Cray computers, only the single-precision version RCHEBN is available.

Structure:

SUBROUTINE subprograms
User Entry Names: RCHEBN, DCHEBN
External References:

RVSCA,	RVSCL,	RVSCS,	RVSET,	RVXCH,
DVSCA,	DVSCL,	DVSCS,	DVSET,	DVXCH	(F002)

Usage:

For $t=R$ (type REAL), $t=D$ (type DOUBLE PRECISION),

    CALL tCHEBN(M,N,A,MDIM,B,TOL,RELERR,X,RESMAX,IRANK,ITER,ICODE)

M

( INTEGER) Number m of equations.

N

( INTEGER) Number $n\hspace{0.17em}(\le m)$ of unknowns.

A

(type according to t) Two-dimensional array of dimension (MDIM,d), where $d\ge n+3$ . On entry, A(I,J) must contain the coefficients $a$_ij (i=1,...,m; j=1,...,n) of matrix A. The contents of A is destroyed during execution.

MDIM

( INTEGER) Declared first dimension of array A, where $MDIM\ge m+1$ .

B

(type according to t) One-dimensional array of length $\ge m+1$ . On entry, the first m elements of B must contain the vector b. On exit, these elements contain the residuals $c$_i .

TOL

Tolerance parameter which should be set to a value somewhat greater than the machine precision.

RELERR

(type according to t) On entry, RELERR should be set to zero if the true minimax solution is required. (For RELERR non-zero see Notes).

X

(type according to t) One-dimensional array of length $\ge n+3$ . On exit, the first n elements of X contain the solution vector x.

RESMAX

(type according to t) On exit, RESMAX contains the value c of the maximum residual.

IRANK

( INTEGER) On exit, IRANK contains an estimate of the rank of the matrix A. (This estimate may depend on TOL).

ITER

( INTEGER) On exit, ITER contains the number of simplex iterations performed.

ICODE

( INTEGER) On exit, ICODE contains one of the following:
$=\; 0:$ Solution x is not unique,
$=\; 1:$ Solution x is unique,
$=\; 2:$ Calculation terminated prematurely because of rounding error.

Method:

Modified simplex method of linear programming applied to the dual of the stated minimax problem.

Notes:

1. If RELERR on entry contains a non-zero positive value r, RELERR on exit contains a value , and the computed solution x$\text{'}$ in X and the maximum residual $c\text{'}$ in RESMAX are such that , where c is the maximum residual corresponding to the true minimax solution x. By setting RELERR non-zero (e.g. RELERR = 0.1), the number of simplex iterations is usually reduced.
2. If RESMAX is within one or two orders of magnitude of TOL, the computed residuals in B on exit may contain few significant digits, and may have been set to zero if .

The subprograms are based on a Fortran algorithm given in Ref. 1.

References:

1. I. Barrodale and C. Phillips, Algorithm 495: Solution of an overdetermined system of linear equations in the Chebyshev norm, ACM Trans. Math. Software 1 (1975) 264--270.

E230