Saddle points and overdetermined complex equations. (English) Zbl 0559.41020

Streit, Roy L.

Linear Algebra Appl. 64, 57-76 (1985).

It is known that the best uniform norm solution of overdetermined complex valued systems of equations satisfying the Haar condition for matrices is also a best weighted \(\ell_ p\) norm solution for each \(p\geq 1\), for some weight vector depending on p. This paper presents an alternative proof of this result which is valid for arbitrary matrices A. The proof relies on the fundamental theorem of game theory. It is shown that a saddle point \((z^*,\lambda^*)\) of a certain function gives a uniform norm solution, \(z^*\), of \(Az=b\) and a weight vector \(\lambda^*\) of the equivalent weighted \(\ell_ p\) norm problem. With appropriate qualifications concerning the weights, it follows that the worst (i.e., largest) possible weighted least \(\ell_ p\) norm error is also the best (i.e., least) possible Chebyshev error. For \(p=2\), it is shown that the weight vector \(\lambda^*\) solves a nonlinear optimization problem which can be posed without reference to solution vectors of \(Az=b\). In other words, the problem of finding the best uniform norm solution of \(Az=b\), when stated as a convex optimization problem, has a convex dual which for \(p=2\) can be posed independently of the primal variables z. The dual variables are the weights \(\lambda\).

MSC:

41A45	Approximation by arbitrary linear expressions
41A50	Best approximation, Chebyshev systems
30E10	Approximation in the complex plane
30E15	Asymptotic representations in the complex plane

Keywords:

best uniform norm solution of overdetermined complex valued systems of equations; weights; Chebyshev error; convex optimization problem

References:

[1]	Motzkin, T. S.; Walsh, J. L., Polynomials of best approximation on an interval, (Proc. Nat. Acad. Sci. U.S.A., 45 (1959)), 1523-1528 · Zbl 0097.04901
[2]	Motzkin, T. S.; Walsh, J. L., Polynomials of best approximation on a real finite point set I, Trans. Amer. Math. Soc., 91, 231-245 (1959) · Zbl 0089.04801
[3]	Lawson, C. L., Contributions to the theory of linear least maximum approximations, (Ph.D. Thesis (1961), UCLA)
[4]	Rice, J. R., (The Approximation of Functions, Vol. 2 (1969), Addison-Wesley) · Zbl 0185.30601
[5]	Rice, J. R.; Usow, K. H., The Lawson algorithm and extensions, Math. Comp., 22, 118-127 (1968) · Zbl 0155.21902
[6]	de la Vallée Poussin, C. J., Sur la méthode de l’approximation minimum, Ann. Soc. Sci. Bruxelles, Seconde Partie, Memoires, 35, 1-16 (1911) · JFM 42.0255.02
[7]	Rivlin, T. J.; Shapiro, H. S., A unified approach to certain problems of approximation and minimization, J. Soc. Indust. Appl. Math., 9, 670-699 (1961) · Zbl 0111.06103
[8]	Cline, A. K., Rate of convergence of Lawson’s algorithm, Math. Comp., 26, 167-176 (1972) · Zbl 0284.41004
[9]	Davis, P. J., Interpolation and Approximation (1975), Dover · Zbl 0111.06003
[10]	Kneser, H., Sur un théorème fondamental de la theorie des jeux, C. R. Acad. Sci. Paris, 234, 2418-2420 (1952) · Zbl 0046.12201
[11]	Gol’stein, E. G., Theory of Convex Programming, (Translations of Mathematical Monographs, Vol. 36 (1972), Amer. Math. Soc: Amer. Math. Soc Providence, R.I) · Zbl 0271.90035
[12]	Elzinga, D. J.; Hearn, D. W., The minimal covering sphere problem, Management Sci., 19, 96-104 (1972) · Zbl 0242.90061
[13]	Gantmacher, F. R., (The Theory of Matrices, Vol. I (1960)), Chelsea · Zbl 0085.01001
[14]	Avriel, M., Nonlinear Programming (1976), Prentice-Hall · Zbl 0361.90035