Nonlinear curve-fitting in the 𝐿₁ and 𝐿_{∞} norms

Shrager, Richard L.; Hill, Edward

doi:10.1090/S0025-5718-1980-0559201-X

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 Free Access

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.

[1] D. H. Anderson and M. R. Osborne, Discrete, nonlinear approximation problems in polyhedral norms, Numer. Math. 28 (1977), no. 2, 143–156. MR 448807, https://doi.org/10.1007/BF01394449
[2] D. H. Anderson and M. R. Osborne, Discrete, nonlinear approximation problems in polyhedral norms. A Levenberg-like algorithm, Numer. Math. 28 (1977), no. 2, 157–170. MR 445788, https://doi.org/10.1007/BF01394450
[3] I. Barrodale and F. D. K. Roberts, An improved algorithm for discrete 𝑙₁ linear approximation, SIAM J. Numer. Anal. 10 (1973), 839–848. MR 339449, https://doi.org/10.1137/0710069
[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 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
[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] 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
[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 501831, https://doi.org/10.1137/0715015
[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 501832, https://doi.org/10.1137/0715017
[11] E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
[12] Saul I. Gass, Linear programming, 4th ed., McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1975. Methods and applications. MR 0373586
[13] P. LaFata and J. B. Rosen, An interactive display for approximation by linear programming, Comm. ACM 13 (1970), 651–659. MR 0267810, https://doi.org/10.1145/362790.362793
[14] Kenneth Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math. 2 (1944), 164–168. MR 0010666, https://doi.org/10.1090/S0033-569X-1944-10666-0
[15] Donald W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math. 11 (1963), 431–441. MR 153071
[16] G. F. McCormick and V. A. Sposito, Using the 𝐿₂-estimator in 𝐿₁-estimation, SIAM J. Numer. Anal. 13 (1976), no. 3, 337–343. MR 448808, https://doi.org/10.1137/0713030
[17] Duane A. Meeter, On a theorem used in nonlinear least squares, SIAM J. Appl. Math. 14 (1966), 1176–1179. MR 207094, https://doi.org/10.1137/0114094
[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 and G. A. Watson, An algorithm for minimax approximation in the nonlinear case, Comput. J. 12 (1969/70), 63–68. MR 245314, https://doi.org/10.1093/comjnl/12.1.63
[20] M. R. Osborne and G. A. Watson, On an algorithm for discrete nonlinear 𝐿₁ approximation, Comput. J. 14 (1971), 184–188. MR 278491, https://doi.org/10.1093/comjnl/14.2.184
[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
[22] John R. Rice, The approximation of functions. Vol. I: Linear theory, Addison-Wesley Publishing Co., Reading, Mass.-London, 1964. MR 0166520
[23] S. R. Searle, Linear models, John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0293792
[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 278742, https://doi.org/10.1145/321592.321597
[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. 18 (1976), no. 3, 351–360. MR 454480