LIPMA: A Fortran 77 package for best L-1 piecewise monotonic data smoothing
Fortran 77 software is presented for the calculation of a best L-1 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 L-1 monotonic calculation. The most distinctive feature of the algorithm is that it terminates at a global minimum in at most n(3) + O(kn(2)) computer operations, although this calculation can exhibit O(n(k)) 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 L-1 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. (C) 2002 Elsevier Science B.V. All rights reserved.
piecewise monotonicity smoothing approximation divided difference dynamic programming turning point median absolute value data fitting l-1 norm noise peak