Strict Chebyshev approximation for general systems of linear equations (Q1095588)

This paper is concerned with the solution of the following discrete Chebyshev approximation problem. Given a matrix \(A\in {\mathbb{R}}^{m\times n}\) of rank r and a vector \(b\in R^ m\), the authors search for a vector \(\hat x\in {\mathbb{R}}^ n\) which minimizes the Chebyshev norm of the residual vector \(r(x)=b-Ax\in {\mathbb{R}}^ m:\inf_{x\in {\mathbb{R}}^ n}\| r(x)\| =\| r(\hat x)\| =\alpha\) with \(\| r(x)\| =\max \{| r_ i(x)|: 1\leq i\leq m\}.\) The vector \(\hat x\) is said to be a Chebyshev solution to the system denoted by \(Ax\approx b\). In this article the authors present an ascent exchange algorithm for computing the strict Chebyshev solution to the presented general system of linear equations. It uses some generalized exchange rules to ensure convergence and splits up the entire system into subsystems by means of a canonical decomposition of a matrix obtained by the Gaussian elimination method. All updating procedures are developed. Several numerical examples are borrowed from the literature for testing the efficiency of the algorithm. The basic steps of the algorithm contain four substeps. It is too long to be cited here.