Algorithm 742: L2CXFT: a Fortran subroutine for least-squares data fitting with nonnegative second divided differences

ABSTRACT

A Fortran subroutine applies the method of Demetriou and Powell [1991] to restore convexity in n measurements of a convex function contaminated by random errors. The method minimizes the sum of the squares of the errors, subject to nonnegativity of second divided differences, in two phases. First, an approximation close to the optimum is derived in O(n) operations. Then, this approximation is used as the starting point of a dual-feasible quadratic programming algorithm that completes the calculation of the optimum. The constraints allow B-splines to be used, which reduce the problem to an equivalent one with fewer variables where the knots of the splines are determined automatically from the data points due to the constraint equations. The subroutine benefits from this reduction, since common submatrices that occur during the calculation are updated suitably. Iterative refinement improves the accuracy of some calculations when round-off errors accumulate. The subroutine has been applied to a variety of data having substantial differences and has performed fast and stably even for small data spacing, large n, and single-precision arithmetic. Driver programs and examples with output are provided to demonstrate the use of the subroutine.

REFERENCES

• 1: DE BOOR, C. 1978. A Practical Guide to Splines. SpringerWerlag, New York.
• 2: DEMETRIOU, I. C. 1985. Data smoothing by piecewise monotonic divided differences. Ph.D. dissertation, Dept. of Applied Mathematics and Theoretical Physics, Univ. of Cambridge, Cambridge, U.K.
• 3: DEMETRIOU, I. C. AND POWELL, M. J. D. 1991. The minimum sum of squares change to univariate data that gives convexity. IMA J. Numer. Anal. 11, 3, 433-448.
• 4: GOLDFARB, D. AND IDNANI, G. 1983. A numerically stable dual method for solving strictly convex quadratic programs. Math. Program. 27, 1, 1-33.
• 5: HANSON, D. L. AND PLEDGER, G. 1976. Consistency in concave regression. Ann. Stat. 4, 6, 1038-1050.
• 6: LAWSON, C. L. AND HANSON, R. J. 1974. Solving Least Squares Problems. Prentice-Hall, Englewood Cliffs, N.J.
• 7: POWELL, M. J. D. 1981. Approximation Theory and Methods. Cambridge University Press, Cambridge, U.K.
• 8: POWELL, M. J.D. 1989. TOLMIN: A Fortran package for linearly constrained optimization calculations. Rep. DAMTP 1989/NA2, Dept. of Applied Mathematics and Theoretical Physics, Univ. of Cambridge, Cambridge, U.K.
• 9: POWELL, M. J.D. 1983. ZQPCVX: A Fortran subroutine for convex quadratic programming. Rep. DAMTP 1983/NA17, Dept. of Applied Mathematics and Theoretical Physics, Univ. of Cambridge, Cambridge, U.K.
• 10: SCHUMAKER, L.L. 1981. Spline Functions: Basic Theory. Wiley, New York.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Least squares approximation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms

Keywords:
B-splines, convex approximation, data fitting, divided difference