A new algorithm for the Chebyshev solution of overdetermined linear systems
Author:
Paul T. Boggs
Journal:
Math. Comp. 28 (1974), 203217
MSC:
Primary 65F20
MathSciNet review:
0334482
Fulltext 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]
Ian
Barrodale and Andrew
Young, Algorithms for best 𝐿₁ and
𝐿_{∞} linear approximations on a discrete set, Numer.
Math. 8 (1966), 295–306. MR 0196912
(33 #5096)
 [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
(39 #2302)
 [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
(45 #6179)
 [4]
Paul T. Boggs & J. E. Dennis, "Error bounds for the discretized steepest descent and the discretized LevenbergMarquardt 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
(31 #862)
 [6]
E.
W. Cheney, Introduction to approximation theory, McGrawHill
Book Co., New YorkToronto, Ont.London, 1966. MR 0222517
(36 #5568)
 [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
(22 #316)
 [8]
George
B. Dantzig, Linear programming and extensions, Princeton
University Press, Princeton, N.J., 1963. MR 0201189
(34 #1073)
 [9]
C. Duris, "An exchange method for solving Haar or nonHaar overdetermined linear equations in the sense of Chebyshev," in Proceedings1968 ACM National Conference, 1968, pp. 6166.
 [10]
C. Duris, An Algorithm for Solving Overdetermined Linear Equations in the Sense, Math. Report No. 7010, 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
(38 #4011)
 [12]
George
E. Forsythe and Cleve
B. Moler, Computer solution of linear algebraic systems,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223
(36 #2306)
 [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
(20 #417)
 [14]
G.
Hadley, Linear programming, AddisonWesley Series in
Industrial Management, AddisonWesley Publishing Co., Inc., Reading,
Mass.London, 1962. MR 0135622
(24 #B1669)
 [15]
L.
A. Karlovitz, Construction of nearest points in the
𝐿^{𝑝}, 𝑝 even, and 𝐿^{∞} norms.
I, J. Approximation Theory 3 (1970), 123–127.
MR
0265829 (42 #738)
 [16]
L. Karlovitz, Private communication.
 [17]
Gunter
H. Meyer, On solving nonlinear equations with a oneparameter
operator imbedding., SIAM J. Numer. Anal. 5 (1968),
739–752. MR 0242366
(39 #3697)
 [18]
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 1970. MR 0273810
(42 #8686)
 [19]
M.
R. Osborne and G.
A. Watson, On the best linear Chebyshev approximation, Comput.
J. 10 (1967), 172–177. MR 0218808
(36 #1892)
 [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
(45 #2899)
 [21]
E.
Stiefel, Über diskrete und lineare
TschebyscheffApproximationen, numer. Math. 1 (1959),
1–28 (German). MR 0107960
(21 #6681)
 [22]
E.
Stiefel, Note on Jordan elimination, linear programming and
Tchebycheff approximation, Numer. Math. 2 (1960),
1–17. MR
0111124 (22 #1988)
 [1]
 I. Barrodale & A. Young, "Algorithms for best and linear approximation on a discrete set," Numer. Math., v. 8, 1966, pp. 295306. 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. 401406. MR 39 #2302. MR 0240957 (39:2302)
 [3]
 Paul T. Boggs, "The solution of nonlinear systems of equations by Astable integration techniques," SIAM J. Numer. Anal. v. 8, 1971, pp. 767785. MR 45 #6179. MR 0297121 (45:6179)
 [4]
 Paul T. Boggs & J. E. Dennis, "Error bounds for the discretized steepest descent and the discretized LevenbergMarquardt 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. 269276. MR 31 #862. MR 0176590 (31:862)
 [6]
 E. W. Cheney, Introduction to Approximation Theory, McGrawHill, 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. 253268. 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 nonHaar overdetermined linear equations in the sense of Chebyshev," in Proceedings1968 ACM National Conference, 1968, pp. 6166.
 [10]
 C. Duris, An Algorithm for Solving Overdetermined Linear Equations in the Sense, Math. Report No. 7010, 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. 491505. MR 38 #4011. MR 0235708 (38:4011)
 [12]
 G. Forsythe & C. B. Moler, Computer Solution of Linear Algebraic Systems, PrenticeHall, 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. 341347. MR 20 #417. MR 0093897 (20:417)
 [14]
 G. Hadley, Linear Programming, AddisonWesley Series in Industrial Management, AddisonWesley, 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. 123127. MR 42 #738. MR 0265829 (42:738)
 [16]
 L. Karlovitz, Private communication.
 [17]
 G. Meyer, "On solving nonlinear equations with a oneparameter operator imbedding," SIAM J. Numer. Anal., v. 5, 1968, pp. 739752. 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. 172177. 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. 387401. MR 45 #2899. MR 0293823 (45:2899)
 [21]
 E. Stiefel, "Über diskrete und lineare TschebyscheffApproximationen," Numer. Math., v. 1, 1959, pp. 128. 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. 117. 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:
http://dx.doi.org/10.1090/S00255718197403344823
PII:
S 00255718(1974)03344823
Keywords:
Pólya algorithm,
solutions,
differential equation for solutions,
stable integration techniques
Article copyright:
© Copyright 1974
American Mathematical Society
