Fitting a \(C^m\)-smooth function to data. I. (English) Zbl 1175.41001

This article continues the authors’ work on extension theorems. This time the question of interpolating or almost interpolating to finitely many given data is discussed. In this way, the finitely many data are extended to the whole space on which we work. Specifically, a function \(F\) defined on \(n\)-dimensional space is sought that matches the finitely many data exactly (or matches them “almost” in a precisely defined way) and satisfies a least upper bound \(M\) in a norm on the space of \(m\)-times continuously differentiate functions. The first problem which is solved in the paper is the question of the order of magnitude of this least \(M\). Also algorithms are stated, one of which computes the solution \(F\) of a slightly modified question in \(O(N\log N)\) operations, where \(N\) is the number of data. This slight modification means that the computed function only has to have the same order of magnitude in norm as the optimal solution. More than one algorithm is stated, because in order to explain the solution more clearly, initially an algorithm of quadratic order \(O(N^2)\) is established which is then modified to the improved order.


41A05 Interpolation in approximation theory
65D15 Algorithms for approximation of functions
Full Text: DOI Link