ON THE BEST LEAST-SQUARES APPROXIMATION OF CONTINUOUS-FUNCTIONS USING LINEAR SPLINES WITH FREE KNOTS

Approximations to continuous functions by linear splines can generally be greatly improved if the knot points are free variables. In this paper we address the problem of computing a best linear spline L2-approximant to a given continuous function on a given closed real interval with a fixed number of free knots. We describe an alogrithm that is currently available and establish the theoretical basis for two new algorithms that we have developed and tested. We show that one of these new algorithms had good local convergence properties by comparison with the other techniques, though its convergence is quite slow. The second new algorithm is not so robust but is quicker and so is used to aid efficiency. A starting procedure based on a dynamic programming approach is introduced to give more reliable global convergence properties. We thus propose a hybrid algorithm which is both robust and reasonably efficient for this problem.