Remote Access Mathematics of Computation
Green Open Access

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
DOI: https://doi.org/10.1090/S0025-5718-1974-0334482-3
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] I. Barrodale & A. Young, "Algorithms for best $ {L_1}$ and $ {L_\infty }$ linear approximation on a discrete set," Numer. Math., v. 8, 1966, pp. 295-306. MR 33 #5096. MR 0196912 (33:5096)
  • [2] R. Bartels & G. Golub, "Stable numerical methods for obtaining the Chebyshev solution to an overdetermined system of equations," Comm. ACM, v. 11, 1968, pp. 401-406. MR 39 #2302. MR 0240957 (39:2302)
  • [3] Paul T. Boggs, "The solution of nonlinear systems of equations by A-stable integration techniques," SIAM J. Numer. Anal. v. 8, 1971, pp. 767-785. MR 45 #6179. MR 0297121 (45:6179)
  • [4] Paul T. Boggs & J. E. Dennis, "Error bounds for the discretized steepest descent and the discretized Levenberg-Marquardt algorithms" (In preparation).
  • [5] P. Businger & G. H. Golub, "Handbook series linear algebra. Linear least squares solutions by Householder transformations," Numer. Math., v. 7, 1965, pp. 269-276. MR 31 #862. MR 0176590 (31:862)
  • [6] E. W. Cheney, Introduction to Approximation Theory, McGraw-Hill, New York, 1966. MR 36 #5568. MR 0222517 (36:5568)
  • [7] E. W. Cheney & A. A. Goldstein, "Newton's method for convex programming and Tchebyscheff approximation," Numer. Math., v. 1, 1959, pp. 253-268. MR 22 #316. MR 0109430 (22:316)
  • [8] G. B. Dantzig, Linear Programming and Extensions, Princeton Univ. Press, Princeton, N.J., 1963. MR 34 #1073. MR 0201189 (34:1073)
  • [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. Duris & V. P. Sreeduaran, "Chebyshev and $ {l^1}$-solutions of linear equations using least squares solutions," SIAM J. Numer. Anal., v. 5, 1968, pp. 491-505. MR 38 #4011. MR 0235708 (38:4011)
  • [12] G. Forsythe & C. B. Moler, Computer Solution of Linear Algebraic Systems, Prentice-Hall, Englewood Cliffs, N.J., 1967. MR 36 #2306. MR 0219223 (36:2306)
  • [13] A. A. Goldstein, N. Levine & J. B. Hereshoff, "On the 'best' and 'least qth' approximation of an overdetermined system of linear equations," J. Assoc. Comput. Mach., v. 4, 1957, pp. 341-347. MR 20 #417. MR 0093897 (20:417)
  • [14] G. Hadley, Linear Programming, Addison-Wesley Series in Industrial Management, Addison-Wesley, Reading, Mass., 1962. MR 24 #B1669. MR 0135622 (24:B1669)
  • [15] L. Karlovitz, "Construction of nearest points in the $ {L^p}$, p even, and $ {L^\infty }$ norms. I," J. Approximation Theory, v. 3, 1970, pp. 123-127. MR 42 #738. MR 0265829 (42:738)
  • [16] L. Karlovitz, Private communication.
  • [17] G. Meyer, "On solving nonlinear equations with a one-parameter operator imbedding," SIAM J. Numer. Anal., v. 5, 1968, pp. 739-752. MR 39 #3697. MR 0242366 (39:3697)
  • [18] J. Ortega & W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. MR 42 #8686. MR 0273810 (42:8686)
  • [19] M. Osborne & G. Watson, "On the best linear Chebyshev approximation," Comput. J., v. 10, 1967, pp. 172-177. MR 36 #1892. MR 0218808 (36:1892)
  • [20] V. P. Sreedharan, "Least squares algorithms for finding solutions of overdetermined linear systems which minimize error in an abstract norm," Numer. Math., v. 17, 1971, pp. 387-401. MR 45 #2899. MR 0293823 (45:2899)
  • [21] E. Stiefel, "Über diskrete und lineare Tschebyscheff-Approximationen," Numer. Math., v. 1, 1959, pp. 1-28. MR 21 #6681. MR 0107960 (21:6681)
  • [22] E. Stiefel, "Note on Jordan elimination, linear programming, and Tschebyscheff approximation," Numer. Math., v. 2, 1960, pp. 1-17. MR 22 #1988. MR 0111124 (22:1988)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F20

Retrieve articles in all journals with MSC: 65F20


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1974-0334482-3
Keywords: Pólya algorithm, $ {l_p}$ solutions, differential equation for $ {l_p}$ solutions, stable integration techniques
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society