L1PMA: A Fortran 77 package for best L1 piecewise monotonic data smoothing Original Research Article

Fortran 77 software is presented for the calculation of a best L1 approximation to n measurements that include random errors by requiring k−1 sign changes in the first divided differences of the approximation or equivalently k monotonic sections, alternately increasing and decreasing. A dynamic programming algorithm separates the measurements into optimal disjoint sections of adjacent data and applies to each section a single L1 monotonic calculation. The most distinctive feature of the algorithm is that it terminates at a global minimum in at most n3+O(kn2) computer operations, although this calculation can exhibit O(nk) local minima, because the optimal positions of the turning points are also unknowns of the optimization process. The arithmetic operations involved in this calculation are comparisons mainly spent in finding the medians of subranges of data during the monotonic calculations. The package employs techniques for median and for best L1 monotonic approximation, while full details of these techniques are specified. The package has been applied and tested on a variety of data that have substantial differences and showed quadratic behaviour in n. Some numerical results demonstrate the performance of the method. Further, there is a commentary on the division of the code into subroutines. Driver programs and numerical examples with output are provided to help new users of the method. Besides that piecewise monotonicity is a property of a wide range of functions, an important application of the method is in estimating turning points of a function from some noisy measurements of its values.