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 be the point which minimizes the residual of a linear system in the norm. It is known that under certain conditions , the Chebyshev or solution, as . A differential equation describing is derived from which an iterative scheme is devised. A convergence analysis is given and numerical results are presented.

**[1]**I. Barrodale & A. Young, "Algorithms for best and 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**Sense*, Math. Report No. 70-10, Drexel University, 1970.**[11]**C. Duris & V. P. Sreeduaran, "Chebyshev and -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*q*th' 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 ,*p*even, and 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)**

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,
solutions,
differential equation for solutions,
stable integration techniques

Article copyright:
© Copyright 1974
American Mathematical Society