[Authors]
 V. A. Daugavet and N. A. Tanygina

[Title]
 The estimate of the best approximation in the uniform
 $\Sigma\Pi$-approximation problem

[AMS Subj-class]
 90C30 Nonlinear programming
 49M25 Discrete approximations
 90C47 Minimax problems

[Abstract]
 The uniform approximation problem of the rectangular matrix $F$
 by matrices $Z$ of fixed rank $r$ less than rank $F$ is considered.
 There is a simple method of a relaxation type for finding the solution
 of this nonlinear problem, which, however, doesn't result in solution.
 To determine closeness of matrix $Z_0$ with rank $r$, obtained by this
 process, to the solution $Z_*$, it is desirable to have a rather high
 estimate from below for the best approximation $\|F-Z\|_\infty$.
 Such estimate may be obtained by solving the problem similar to the
 original one not for the entire matrix $F$, but only for its $(r+1)$
 rows or columns (strip problem). It is shown that strip problem solving
 is reduced to that of the finite number of linear programming problems.
 Solving the problem on some strip, we obtain the two-sided estimate
 for the best approximation 
 $$
  \nu_L\le\|F-Z_*\|_\infty\le\|F-Z_0\|_\infty,
 $$
 where $\nu_L$ is the best strip approximation. If the upper and lower
 estimates in this double inequality are close, then the matrix $Z_0$ may
 be accepted as a goot approximation to the solution $Z_*$. In an opposite
 case relaxation process may be repeated with another starting matrix.
 The numerical calculations indicated to the efficiency of using such
 estimates are adduced. 

[Comments]
 Russian, 9 pp.

[Contact e-mail]
 Daugavet@VD3999.spb.edu
 natusya_t@yahoo.com