ALGORITHM-742 - L2CXFT - A FORTRAN SUBROUTINE FOR LEAST-SQUARES DATA FITTING WITH NONNEGATIVE 2ND DIVIDED DIFFERENCES

Fortran subroutine applies the method of Demetriou and Powell [1991] t o restore convexity in n measurements of a convex function contaminate d by random errors. The method minimizes the sum of the squares of the errors, subject to nonnegativity of second divided differences, in tw o 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 use d, which reduce the problem to an equivalent one with fewer variables where the knots of the splines are determined automatically from the d ata points due to the constraint equations. The subroutine benefits fr om this reduction, since common submatrices that occur during the calc ulation are updated suitably. iterative refinement improves the accura cy of some calculations when round-off errors accumulate. The subrouti ne has been applied to a variety of data having substantial difference s 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.