A polynomial algorithm on computing LAD splines. (English) Zbl 0748.65012

Summary: The authors prove that least absolute deviations (LAD) splines can be calculated by solving a specific convex quadratic programming problem. A polynomial time algorithm, which requires no more than \(O(n^ 3L)\) arithmetic operations, is designed to solve this programming problem. The algorithm is taken into practice successfully on an IBM personal computer with Turbo Pascal. By comparing with least squares deviations splines, the paper shows that the method of smoothing statistical data with LAD splines is more robust and effective.


65D07 Numerical computation using splines
65K05 Numerical mathematical programming methods
65D10 Numerical smoothing, curve fitting
65C99 Probabilistic methods, stochastic differential equations
90C20 Quadratic programming
90C25 Convex programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
90C90 Applications of mathematical programming


Turbo Pascal
Full Text: DOI