next up previous index
Next: E230 Constrained and Up: CERNLIB Previous: E211 Cubic Splines

E222 Solution of Overdetermined Linear System in the Chebychev Norm

Routine ID: E222
Author(s): Library: MATHLIB
Submitter: Submitted: 01.12.1994
Language: FortranRevised:

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 = max1≤i≤mci = max1≤i≤m| bi- ∑j=1naijxj|.

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 (≤m) of unknowns.
A
(type according to t) Two-dimensional array of dimension (MDIM,d), where d≥n+3 . On entry, A(I,J) must contain the coefficients aij (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≥m+1 .
B
(type according to t) One-dimensional array of length ≥m+1 . On entry, the first m elements of B must contain the vector b. On exit, these elements contain the residuals ci .
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 ≥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 r'<r , and the computed solution x' in X and the maximum residual c' in RESMAX are such that (c'-c)/c < r' , 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 RESMAX < TOL .

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



next up previous index
Next: E230 Constrained and Up: CERNLIB Previous: E211 Cubic Splines


Janne Saarela
Mon Apr 3 15:06:23 METDST 1995