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

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]**Ian Barrodale and Andrew Young,*Algorithms for best 𝐿₁ and 𝐿_{∞} linear approximations on a discrete set*, Numer. Math.**8**(1966), 295–306. MR**0196912**, https://doi.org/10.1007/BF02162565**[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**, https://doi.org/10.1145/363347.363364**[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**, https://doi.org/10.1137/0708071**[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**, https://doi.org/10.1007/BF01436084**[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**, https://doi.org/10.1007/BF01386389**[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**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**, https://doi.org/10.1137/0705040**[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**, https://doi.org/10.1145/320881.320890**[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**, https://doi.org/10.1137/0705057**[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**, https://doi.org/10.1093/comjnl/10.2.172**[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**, https://doi.org/10.1007/BF01436088**[21]**E. Stiefel,*Über diskrete und lineare Tschebyscheff-Approximationen*, numer. Math.**1**(1959), 1–28 (German). MR**0107960**, https://doi.org/10.1007/BF01386369**[22]**E. Stiefel,*Note on Jordan elimination, linear programming and Tchebycheff approximation*, Numer. Math.**2**(1960), 1–17. MR**0111124**, https://doi.org/10.1007/BF01386203

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