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_{1}$ and $L_{\infty }$ norms
HTML articles powered by AMS MathViewer

by Richard L. Shrager and Edward Hill PDF

Math. Comp. 34 (1980), 529-541 Request permission

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

D. H. Anderson and M. R. Osborne, Discrete, nonlinear approximation problems in polyhedral norms, Numer. Math. 28 (1977), no. 2, 143–156. MR 448807, DOI 10.1007/BF01394449
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, DOI 10.1007/BF01394450
I. Barrodale and F. D. K. Roberts, An improved algorithm for discrete $l_{1}$ linear approximation, SIAM J. Numer. Anal. 10 (1973), 839–848. MR 339449, DOI 10.1137/0710069

Comm. ACM

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) Congr. Numer., No. XII, Utilitas Math., Winnipeg, Man., 1975, pp. 177–190. MR 0373585

An Efficient Algorithm for Discrete

Linear Approximation with Linear Constraints

Solution of the Constrained

Linear Approximation Problem

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, DOI 10.1145/363347.363364
Richard H. Bartels, Andrew R. Conn, and James W. Sinclair, Minimization techniques for piecewise differentiable functions: the $l_{1}$ solution to an overdetermined linear system, SIAM J. Numer. Anal. 15 (1978), no. 2, 224–241. MR 501831, DOI 10.1137/0715015
Richard H. Bartels, Andrew R. Conn, and Christakis Charalambous, On Cline’s direct method for solving overdetermined linear systems in the $l_{\infty }$ sense, SIAM J. Numer. Anal. 15 (1978), no. 2, 255–270. MR 501832, DOI 10.1137/0715017
E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
Saul I. Gass, Linear programming, 4th ed., McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1975. Methods and applications. MR 0373586
P. LaFata and J. B. Rosen, An interactive display for approximation by linear programming, Comm. ACM 13 (1970), 651–659. MR 0267810, DOI 10.1145/362790.362793
Kenneth Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math. 2 (1944), 164–168. MR 10666, DOI 10.1090/S0033-569X-1944-10666-0
Donald W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math. 11 (1963), 431–441. MR 153071, DOI 10.1137/0111030
G. F. McCormick and V. A. Sposito, Using the $L_{2}$-estimator in $L_{1}$-estimation, SIAM J. Numer. Anal. 13 (1976), no. 3, 337–343. MR 448808, DOI 10.1137/0713030
Duane A. Meeter, On a theorem used in nonlinear least squares, SIAM J. Appl. Math. 14 (1966), 1176–1179. MR 207094, DOI 10.1137/0114094

Methods for Non-Linear Least Squares Problems and Convergence Proofs. Tracking Programs and Orbit Determination

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, DOI 10.1093/comjnl/12.1.63
M. R. Osborne and G. A. Watson, On an algorithm for discrete nonlinear $L_{1}$ approximation, Comput. J. 14 (1971), 184–188. MR 278491, DOI 10.1093/comjnl/14.2.184
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
John R. Rice, The approximation of functions. Vol. I: Linear theory, Addison-Wesley Publishing Co., Reading, Mass.-London, 1964. MR 0166520
S. R. Searle, Linear models, John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0293792
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, DOI 10.1145/321592.321597

Comm. ACM

G. A. Watson, A method for calculating best non-linear Chebyshev approximations, J. Inst. Math. Appl. 18 (1976), no. 3, 351–360. MR 454480, DOI 10.1093/imamat/18.3.351