Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A new algorithm for the Chebyshev solution of overdetermined linear systems

Author: Paul T. Boggs
Journal: Math. Comp. 28 (1974), 203-217
MSC: Primary 65F20
MathSciNet review: 0334482
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Ian Barrodale and Andrew Young, Algorithms for best 𝐿₁ and 𝐿_{∞} linear approximations on a discrete set, Numer. Math. 8 (1966), 295–306. MR 0196912
  • [2] 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
  • [3] Paul T. Boggs, The solution of nonlinear systems of equations by 𝐴-stable integration techniques, SIAM J. Numer. Anal. 8 (1971), 767–785. MR 0297121
  • [4] Paul T. Boggs & J. E. Dennis, "Error bounds for the discretized steepest descent and the discretized Levenberg-Marquardt algorithms" (In preparation).
  • [5] Peter Businger and Gene H. Golub, Handbook series linear algebra. Linear least squares solutions by Householder transformations, Numer. Math. 7 (1965), 269–276. MR 0176590
  • [6] E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
  • [7] E. W. Cheney and A. A. Goldstein, Newton’s method for convex programming and Tchebycheff approximation., Numer. Math. 1 (1959), 253–268. MR 0109430
  • [8] George B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, N.J., 1963. MR 0201189
  • [9] 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.
  • [10] C. Duris, An Algorithm for Solving Overdetermined Linear Equations in the $ {l^p}$ Sense, Math. Report No. 70-10, Drexel University, 1970.
  • [11] C. S. Duris and V. P. Sreedharan, Chebyshev and 𝑙¹-solutions of linear equations using least squares solutions, SIAM J. Numer. Anal. 5 (1968), 491–505. MR 0235708
  • [12] George E. Forsythe and Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223
  • [13] Allen A. Goldstein, Norman Levine, and James B. Herreshoff, On the “best” and “least 𝑞th” approximation of an overdetermined system of linear equations, J. Assoc. Comput. Mach. 4 (1957), 341–347. MR 0093897
  • [14] G. Hadley, Linear programming, Addison-Wesley Series in Industrial Management, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1962. MR 0135622
  • [15] L. A. Karlovitz, Construction of nearest points in the 𝐿^{𝑝}, 𝑝 even, and 𝐿^{∞} norms. I, J. Approximation Theory 3 (1970), 123–127. MR 0265829
  • [16] L. Karlovitz, Private communication.
  • [17] Gunter H. Meyer, On solving nonlinear equations with a one-parameter operator imbedding., SIAM J. Numer. Anal. 5 (1968), 739–752. MR 0242366
  • [18] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
  • [19] M. R. Osborne and G. A. Watson, On the best linear Chebyshev approximation, Comput. J. 10 (1967), 172–177. MR 0218808
  • [20] 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 0293823
  • [21] E. Stiefel, Über diskrete und lineare Tschebyscheff-Approximationen, numer. Math. 1 (1959), 1–28 (German). MR 0107960
  • [22] E. Stiefel, Note on Jordan elimination, linear programming and Tchebycheff approximation, Numer. Math. 2 (1960), 1–17. MR 0111124

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F20

Retrieve articles in all journals with MSC: 65F20

Additional Information

Keywords: Pólya algorithm, $ {l_p}$ solutions, differential equation for $ {l_p}$ solutions, stable integration techniques
Article copyright: © Copyright 1974 American Mathematical Society