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 Paul T. Boggs & J. E. Dennis, "Error bounds for the discretized steepest descent and the discretized Levenberg-Marquardt algorithms" (In preparation).
- 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 C. Duris, "An exchange method for solving Haar or non-Haar overdetermined linear equations in the sense of Chebyshev," in Proceedings-1968 ACM National Conference, 1968, pp. 61-66. C. Duris, An Algorithm for Solving Overdetermined Linear Equations in the ${l^p}$ Sense, Math. Report No. 70-10, Drexel University, 1970.
- 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 L. Karlovitz, Private communication.
- 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
Additional Information
- © Copyright 1974 American Mathematical Society
- Journal: Math. Comp. 28 (1974), 203-217
- MSC: Primary 65F20
- DOI: https://doi.org/10.1090/S0025-5718-1974-0334482-3
- MathSciNet review: 0334482