On the Best Least Squares Approximation of Continuous Functions using Linear Splines with Free Knots

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