Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Nonlinear curve-fitting in the $ L\sb{1}$ and $ L\sb{\infty }$ norms


Authors: Richard L. Shrager and Edward Hill
Journal: Math. Comp. 34 (1980), 529-541
MSC: Primary 41A45; Secondary 41A50, 65D10
DOI: https://doi.org/10.1090/S0025-5718-1980-0559201-X
MathSciNet review: 559201
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In extending the Levenberg-Marquardt $ {L_2}$ method for nonlinear curve-fitting to the $ {L_1}$ and $ {L_\infty }$ norms, the following problems arise, but are dealt with successfully:

(1) Trial parameters are generated by linear programming, which can be time-consuming.

(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 $ {L_1}$, 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.


References [Enhancements On Off] (What's this?)

  • [1] D. H. ANDERSON & M. R. OSBORNE, ``Discrete, nonlinear approximation problems in polyhedral norms,'' Numer. Math., v. 28, 1977, pp. 143-156. MR 0448807 (56:7112)
  • [2] D. H. ANDERSON & M. R. OSBORNE, ``Discrete, nonlinear approximation problems in polyhedral norms--a Levenberg-like algorithm,'' Numer. Math., v. 28, 1977, pp. 157-170. MR 0445788 (56:4122)
  • [3] I. BARRODALE & F. D. K. ROBERTS, ``An improved algorithm for $ {L_1}$ linear approximation,'' SIAM J. Numer. Anal., v. 10, 1973, pp. 839-848. MR 0339449 (49:4208)
  • [4] I. BARRODALE & F. D. K. ROBERTS, ``Solution of an over-determined system of equations in the $ {L_1}$ norm,'' Comm. ACM, v. 17, 1974, pp. 319-320.
  • [5] I. BARRODALE & C. PHILLIPS, ``Algorithm 495: Solution of an over-determined system of linear equations in the Chebyshev norm,'' ACM Trans. Math. Software, v. 1, 1975, pp. 264-270. MR 0373585 (51:9785)
  • [6] I. BARRODALE & F. D. K. ROBERTS, An Efficient Algorithm for Discrete $ {L_1}$ Linear Approximation with Linear Constraints, Tech. Dept. DM-103-IR, Dept. of Math., Univ. of Victoria Victoria, B. C., Canada, July 1977.
  • [7] I. BARRODALE & F. D. K. ROBERTS, Solution of the Constrained $ {L_1}$ Linear Approximation Problem, Tech. Dept. DM-104-IR, 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. 428-430. MR 0240957 (39:2302)
  • [9] R. H. BARTELS, A. R. CONN & J. W. SINCLAIR, ``Minimization techniques for piecewise differentiable functions: the $ {L_1}$ solution to an overdetermined linear system,'' SIAM J. Numer. Anal., v. 15, 1978, pp. 224-241. 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 $ {L_\infty }$ sense,'' SIAM J. Numer. Anal., v. 15, 1978, pp. 255-270. MR 0501832 (58:19080)
  • [11] E. W. CHENEY, Introduction to Approximation Theory, McGraw-Hill, New York, 1966. MR 0222517 (36:5568)
  • [12] S. I. GASS, Linear Programming, McGraw-Hill, 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. 651-659. MR 0267810 (42:2712)
  • [14] K. LEVENBERG, ``A method for the solution of certain non-linear problems in least squares,'' Quart. Appl. Math., v. 2, 1944, pp. 164-168. MR 0010666 (6:52a)
  • [15] D. W. MARQUARDT, ``An algorithm for least-squares determination of nonlinear parameters,'' SIAM J. Appl. Math., v. 11, 1963, pp. 431-441. MR 0153071 (27:3040)
  • [16] G. F. McCORMICK & V. A. SPOSITO, ``Using the $ {L_2}$-estimator in $ {L_1}$-estimation,'' SIAM J. Numer. Anal., v. 13, 1976, pp. 337-343. MR 0448808 (56:7113)
  • [17] D. A. MEETER, ``On a theorem used in non-linear least squares,'' SIAM J. Appl. Math., v. 14, 1966, pp. 1176-1179. MR 0207094 (34:6910)
  • [18] D. D. MORRISON, Methods for Non-Linear Least Squares Problems and Convergence Proofs. Tracking Programs and Orbit Determination, Proc. Jet Propulsion Lab. Seminar, 1970, pp. 1-9.
  • [19] M. R. OSBORNE & G. A. WATSON, ``An algorithm for minimax approximation in the nonlinear case,'' Comput. J., v. 12, 1969, pp. 63-68. MR 0245314 (39:6625)
  • [20] M. R. OSBORNE & G. A. WATSON, ``On an algorithm for discrete nonlinear $ {L_1}$ approximation,'' Comput. J., v. 14, 1971, pp. 184-188. 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, Springer-Verlag, Berlin, 1978. MR 492763 (81e:65027)
  • [22] J. R. RICE, The Approximation of Functions, Addison-Wesley, 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. 446-452. MR 0278742 (43:4471)
  • [25] R. I. SHRAGER, ``Quadratic programming for nonlinear regression,'' Comm. ACM, v. 15, 1972, pp. 41-45.
  • [26] R. I. SHRAGER & E. HILL, ``Some properties of the Levenberg method in the $ {L_1}$ and $ {L_\infty }$ norms,'' 1979. Available from the authors.
  • [27] G. A. WATSON, ``A method for calculating best non-linear Chebyshev approximations,'' J. Inst. Math. Appl., v. 18, 1976, pp. 351-360. 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: https://doi.org/10.1090/S0025-5718-1980-0559201-X
Article copyright: © Copyright 1980 American Mathematical Society

American Mathematical Society