A new algorithm for the Chebyshev solution of overdetermined linear systems

Boggs, Paul T.

doi:10.1090/S0025-5718-1974-0334482-3

A new algorithm for the Chebyshev solution of overdetermined linear systems
HTML articles powered by AMS MathViewer

by Paul T. Boggs PDF

Math. Comp. 28 (1974), 203-217 Request permission

Abstract:

Let $x(p)$ be the point which minimizes the residual of a linear system in the ${l_p}$ norm. It is known that under certain conditions $x(p) \to {x^\ast }$, the Chebyshev or ${l_\infty }$ solution, as $p \to \infty$. A differential equation describing $x(p)$ is derived from which an iterative scheme is devised. A convergence analysis is given and numerical results are presented.

References

Ian Barrodale and Andrew Young, Algorithms for best $L_{1}$ and $L_{\infty }$ linear approximations on a discrete set, Numer. Math. 8 (1966), 295–306. MR 196912, DOI 10.1007/BF02162565
Richard H. Bartels and Gene H. Golub, Stable numerical methods for obtaining the Chebyshev solution to an overdetermined system of equations, Comm. ACM 11 (1968), 401–406. MR 0240957, DOI 10.1145/363347.363364
Paul T. Boggs, The solution of nonlinear systems of equations by $A$-stable integration techniques, SIAM J. Numer. Anal. 8 (1971), 767–785. MR 297121, DOI 10.1137/0708071
Peter Businger and Gene H. Golub, Handbook series linear algebra. Linear least squares solutions by Householder transformations, Numer. Math. 7 (1965), 269–276. MR 176590, DOI 10.1007/BF01436084
E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
E. W. Cheney and A. A. Goldstein, Newton’s method for convex programming and Tchebycheff approximation, Numer. Math. 1 (1959), 253–268. MR 109430, DOI 10.1007/BF01386389
George B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, N.J., 1963. MR 0201189

Proceedings

ACM National Conference

An Algorithm for Solving Overdetermined Linear Equations in the

Sense

C. S. Duris and V. P. Sreedharan, Chebyshev and $l^{1}$-solutions of linear equations using least squares solutions, SIAM J. Numer. Anal. 5 (1968), 491–505. MR 235708, DOI 10.1137/0705040
George E. Forsythe and Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223
Allen A. Goldstein, Norman Levine, and James B. Herreshoff, On the “best” and “least $q$th” approximation of an overdetermined system of linear equations, J. Assoc. Comput. Mach. 4 (1957), 341–347. MR 93897, DOI 10.1145/320881.320890
G. Hadley, Linear programming, Addison-Wesley Series in Industrial Management, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1962. MR 0135622
L. A. Karlovitz, Construction of nearest points in the $L^{p}$, $p$ even, and $L^{\infty }$ norms. I, J. Approximation Theory 3 (1970), 123–127. MR 265829, DOI 10.1016/0021-9045(70)90019-5
Gunter H. Meyer, On solving nonlinear equations with a one-parameter operator imbedding, SIAM J. Numer. Anal. 5 (1968), 739–752. MR 242366, DOI 10.1137/0705057
J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
M. R. Osborne and G. A. Watson, On the best linear Chebyshev approximation, Comput. J. 10 (1967), 172–177. MR 218808, DOI 10.1093/comjnl/10.2.172
V. P. Sreedharan, Least squares algorithms for finding solutions of overdetermined linear equations which minimize error in an abstract norm, Numer. Math. 17 (1971), 387–401. MR 293823, DOI 10.1007/BF01436088
E. Stiefel, Über diskrete und lineare Tschebyscheff-Approximationen, numer. Math. 1 (1959), 1–28 (German). MR 0107960, DOI 10.1007/BF01386369
E. Stiefel, Note on Jordan elimination, linear programming and Tchebycheff approximation, Numer. Math. 2 (1960), 1–17. MR 111124, DOI 10.1007/BF01386203