Nonlinear curvefitting in the and norms
Authors:
Richard L. Shrager and Edward Hill
Journal:
Math. Comp. 34 (1980), 529541
MSC:
Primary 41A45; Secondary 41A50, 65D10
MathSciNet review:
559201
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In extending the LevenbergMarquardt method for nonlinear curvefitting to the and norms, the following problems arise, but are dealt with successfully: (1) Trial parameters are generated by linear programming, which can be timeconsuming. (2) Trial parameters are not uniquely specified in some cases. (3) There are intervals of the search parameter for which the trial parameters remain constant. (4) In , the trial parameters are discontinuous with respect to the search parameter. It is shown that linear constraints on the parameters are easily included in the computations. Finally, some numerical results are presented.
 [1]
D.
H. Anderson and M.
R. Osborne, Discrete, nonlinear approximation problems in
polyhedral norms, Numer. Math. 28 (1977), no. 2,
143–156. MR 0448807
(56 #7112)
 [2]
D.
H. Anderson and M.
R. Osborne, Discrete, nonlinear approximation problems in
polyhedral norms. A Levenberglike algorithm, Numer. Math.
28 (1977), no. 2, 157–170. MR 0445788
(56 #4122)
 [3]
I.
Barrodale and F.
D. K. Roberts, An improved algorithm for discrete 𝑙₁
linear approximation, SIAM J. Numer. Anal. 10 (1973),
839–848. MR 0339449
(49 #4208)
 [4]
I. BARRODALE & F. D. K. ROBERTS, ``Solution of an overdetermined system of equations in the norm,'' Comm. ACM, v. 17, 1974, pp. 319320.
 [5]
I.
Barrodale and C.
Phillips, An improved algorithm for discrete Chebyshev linear
approximation, Proceedings of the Fourth Manitoba Conference on
Numerical Mathematics (Winnipeg, Man., 1974) Utilitas Math., Winnipeg,
Man., 1975, pp. 177–190. Congr. Numer., No. XII. MR 0373585
(51 #9785)
 [6]
I. BARRODALE & F. D. K. ROBERTS, An Efficient Algorithm for Discrete Linear Approximation with Linear Constraints, Tech. Dept. DM103IR, Dept. of Math., Univ. of Victoria Victoria, B. C., Canada, July 1977.
 [7]
I. BARRODALE & F. D. K. ROBERTS, Solution of the Constrained Linear Approximation Problem, Tech. Dept. DM104IR, Dept. of Math., Univ. of Victoria, Victoria, B. C., Canada, July 1977.
 [8]
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)
 [9]
Richard
H. Bartels, Andrew
R. Conn, and James
W. Sinclair, Minimization techniques for piecewise differentiable
functions: the 𝑙₁ solution to an overdetermined linear
system, SIAM J. Numer. Anal. 15 (1978), no. 2,
224–241. MR 0501831
(58 #19079)
 [10]
Richard
H. Bartels, Andrew
R. Conn, and Christakis
Charalambous, On Cline’s direct method for solving
overdetermined linear systems in the 𝑙_{∞} sense, SIAM
J. Numer. Anal. 15 (1978), no. 2, 255–270. MR 0501832
(58 #19080)
 [11]
E.
W. Cheney, Introduction to approximation theory, McGrawHill
Book Co., New YorkToronto, Ont.London, 1966. MR 0222517
(36 #5568)
 [12]
Saul
I. Gass, Linear programming, 4th ed., McGrawHill Book Co.,
New YorkAucklandDüsseldorf, 1975. Methods and applications. MR 0373586
(51 #9786)
 [13]
P.
LaFata and J.
B. Rosen, An interactive display for approximation by linear
programming, Comm. ACM 13 (1970), 651–659. MR 0267810
(42 #2712)
 [14]
Kenneth
Levenberg, A method for the solution of certain nonlinear problems
in least squares, Quart. Appl. Math. 2 (1944),
164–168. MR 0010666
(6,52a)
 [15]
Donald
W. Marquardt, An algorithm for leastsquares estimation of
nonlinear parameters, J. Soc. Indust. Appl. Math. 11
(1963), 431–441. MR 0153071
(27 #3040)
 [16]
G.
F. McCormick and V.
A. Sposito, Using the 𝐿₂estimator in
𝐿₁estimation, SIAM J. Numer. Anal. 13
(1976), no. 3, 337–343. MR 0448808
(56 #7113)
 [17]
Duane
A. Meeter, On a theorem used in nonlinear least squares, SIAM
J. Appl. Math. 14 (1966), 1176–1179. MR 0207094
(34 #6910)
 [18]
D. D. MORRISON, Methods for NonLinear Least Squares Problems and Convergence Proofs. Tracking Programs and Orbit Determination, Proc. Jet Propulsion Lab. Seminar, 1970, pp. 19.
 [19]
M.
R. Osborne and G.
A. Watson, An algorithm for minimax approximation in the nonlinear
case, Comput. J. 12 (1969/1970), 63–68. MR 0245314
(39 #6625)
 [20]
M.
R. Osborne and G.
A. Watson, On an algorithm for discrete nonlinear 𝐿₁
approximation, Comput. J. 14 (1971), 184–188.
MR
0278491 (43 #4221)
 [21]
M.
R. Osborne and G.
A. Watson, Nonlinear approximation problems in vector norms,
Numerical analysis (Proc. 7th Biennial Conf., Univ. Dundee, Dundee, 1977),
Lecture Notes in Pure and Appl. Math., vol. 36, Dekker, New York,
1978, pp. 117–132. MR 492763
(81e:65027)
 [22]
John
R. Rice, The approximation of functions. Vol. I: Linear
theory, AddisonWesley Publishing Co., Reading, Mass.London, 1964. MR 0166520
(29 #3795)
 [23]
S.
R. Searle, Linear models, John Wiley & Sons, Inc., New
YorkLondonSydney, 1971. MR 0293792
(45 #2868)
 [24]
Richard
I. Shrager, Nonlinear regression with linear constraints: An
extension of the magnified diagonal method, J. Assoc. Comput. Mach.
17 (1970), 446–452. MR 0278742
(43 #4471)
 [25]
R. I. SHRAGER, ``Quadratic programming for nonlinear regression,'' Comm. ACM, v. 15, 1972, pp. 4145.
 [26]
R. I. SHRAGER & E. HILL, ``Some properties of the Levenberg method in the and norms,'' 1979. Available from the authors.
 [27]
G.
A. Watson, A method for calculating best nonlinear Chebyshev
approximations, J. Inst. Math. Appl. 18 (1976),
no. 3, 351–360. MR 0454480
(56 #12731)
 [1]
 D. H. ANDERSON & M. R. OSBORNE, ``Discrete, nonlinear approximation problems in polyhedral norms,'' Numer. Math., v. 28, 1977, pp. 143156. MR 0448807 (56:7112)
 [2]
 D. H. ANDERSON & M. R. OSBORNE, ``Discrete, nonlinear approximation problems in polyhedral normsa Levenberglike algorithm,'' Numer. Math., v. 28, 1977, pp. 157170. MR 0445788 (56:4122)
 [3]
 I. BARRODALE & F. D. K. ROBERTS, ``An improved algorithm for linear approximation,'' SIAM J. Numer. Anal., v. 10, 1973, pp. 839848. MR 0339449 (49:4208)
 [4]
 I. BARRODALE & F. D. K. ROBERTS, ``Solution of an overdetermined system of equations in the norm,'' Comm. ACM, v. 17, 1974, pp. 319320.
 [5]
 I. BARRODALE & C. PHILLIPS, ``Algorithm 495: Solution of an overdetermined system of linear equations in the Chebyshev norm,'' ACM Trans. Math. Software, v. 1, 1975, pp. 264270. MR 0373585 (51:9785)
 [6]
 I. BARRODALE & F. D. K. ROBERTS, An Efficient Algorithm for Discrete Linear Approximation with Linear Constraints, Tech. Dept. DM103IR, Dept. of Math., Univ. of Victoria Victoria, B. C., Canada, July 1977.
 [7]
 I. BARRODALE & F. D. K. ROBERTS, Solution of the Constrained Linear Approximation Problem, Tech. Dept. DM104IR, Dept. of Math., Univ. of Victoria, Victoria, B. C., Canada, July 1977.
 [8]
 R. H. BARTELS & G. H. GOLUB, ``Algorithm 328,'' Comm. ACM, v. 11, 1968, pp. 428430. MR 0240957 (39:2302)
 [9]
 R. H. BARTELS, A. R. CONN & J. W. SINCLAIR, ``Minimization techniques for piecewise differentiable functions: the solution to an overdetermined linear system,'' SIAM J. Numer. Anal., v. 15, 1978, pp. 224241. MR 0501831 (58:19079)
 [10]
 R. H. BARTELS, A. R. CONN & C. CHARALAMBOUS, ``On Cline's direct method for solving overdetermined linear systems in the sense,'' SIAM J. Numer. Anal., v. 15, 1978, pp. 255270. MR 0501832 (58:19080)
 [11]
 E. W. CHENEY, Introduction to Approximation Theory, McGrawHill, New York, 1966. MR 0222517 (36:5568)
 [12]
 S. I. GASS, Linear Programming, McGrawHill, New York, 1969. MR 0373586 (51:9786)
 [13]
 P. LaFATA & J. B. ROSEN, ``An interactive display for approximation by linear programming,'' Comm. ACM, v. 13, 1970, pp. 651659. MR 0267810 (42:2712)
 [14]
 K. LEVENBERG, ``A method for the solution of certain nonlinear problems in least squares,'' Quart. Appl. Math., v. 2, 1944, pp. 164168. MR 0010666 (6:52a)
 [15]
 D. W. MARQUARDT, ``An algorithm for leastsquares determination of nonlinear parameters,'' SIAM J. Appl. Math., v. 11, 1963, pp. 431441. MR 0153071 (27:3040)
 [16]
 G. F. McCORMICK & V. A. SPOSITO, ``Using the estimator in estimation,'' SIAM J. Numer. Anal., v. 13, 1976, pp. 337343. MR 0448808 (56:7113)
 [17]
 D. A. MEETER, ``On a theorem used in nonlinear least squares,'' SIAM J. Appl. Math., v. 14, 1966, pp. 11761179. MR 0207094 (34:6910)
 [18]
 D. D. MORRISON, Methods for NonLinear Least Squares Problems and Convergence Proofs. Tracking Programs and Orbit Determination, Proc. Jet Propulsion Lab. Seminar, 1970, pp. 19.
 [19]
 M. R. OSBORNE & G. A. WATSON, ``An algorithm for minimax approximation in the nonlinear case,'' Comput. J., v. 12, 1969, pp. 6368. MR 0245314 (39:6625)
 [20]
 M. R. OSBORNE & G. A. WATSON, ``On an algorithm for discrete nonlinear approximation,'' Comput. J., v. 14, 1971, pp. 184188. MR 0278491 (43:4221)
 [21]
 M. R. OSBORNE & G. A. WATSON, Nonlinear Approximation Problems in Vector Norms (G. A. Watson, Ed.), Lecture Notes in Math., Vol. 630, SpringerVerlag, Berlin, 1978. MR 492763 (81e:65027)
 [22]
 J. R. RICE, The Approximation of Functions, AddisonWesley, Reading, Mass., 1964. MR 0166520 (29:3795)
 [23]
 S. R. SEARLE, Linear Models, Wiley, New York, 1971. MR 0293792 (45:2868)
 [24]
 R. I. SHRAGER, ``Nonlinear regression with linear constraints: an extension of the magnified diagonal method,'' J. AMC, v. 17, 1970, pp. 446452. MR 0278742 (43:4471)
 [25]
 R. I. SHRAGER, ``Quadratic programming for nonlinear regression,'' Comm. ACM, v. 15, 1972, pp. 4145.
 [26]
 R. I. SHRAGER & E. HILL, ``Some properties of the Levenberg method in the and norms,'' 1979. Available from the authors.
 [27]
 G. A. WATSON, ``A method for calculating best nonlinear Chebyshev approximations,'' J. Inst. Math. Appl., v. 18, 1976, pp. 351360. MR 0454480 (56:12731)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
41A45,
41A50,
65D10
Retrieve articles in all journals
with MSC:
41A45,
41A50,
65D10
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571819800559201X
PII:
S 00255718(1980)0559201X
Article copyright:
© Copyright 1980
American Mathematical Society
