Fitting a \(C^m\)-smooth function to data. I. (Q2389140)

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.