Good knots for given data sites

If the data sites are to be chosen for a given spline space, then a good choice is readily available, namely the extreme points of the Chebyshev spline for the spline space. This is the unique maximally equioscillating element of the space, normalized to have its rightmost local maximum equal to 1. While there is in general no explicit formula for the Chebyshev spline or its extreme points (as there is in the special case of the Bernstein knot sequence $1 = t_1=\cdots=t_k < t_{k+1} = \cdots = t_{2k} = 1$), both are easily computed since the knot averages $t_j^*:= (t_{j+1} + \cdots + t_{j+k-1})/(k-1)$, $j=1{:}n$ (also known as Greville absciss\ae) provide a very good initial guess for the extreme points in a Newton iteration for the solution of their characterizing equation (as the points at which the spline takes on alternately the value $\pm1$ while its derivative vanishes at every such point interior to the basic interval of the spline space). Use of these `Chebyshev points' leads to a spline interpolation projector of minimal norm (as a linear map on $C$), as was first pointed out in Demko77?? (Demko85??). This is equivalent to the fact that the inverse of the B-spline collocation matrix has minimal norm for this choice of points (for the given knot sequence). The complementary question, of choosing a satisfactory knot sequence $(t_i: i=1:n+k)$ for a given sequence $\tau_1< \cdots < \tau_n$ of data sites, has not yet been answered satisfactorily. It seems reasonable to try to keep the norm of the inverse of the B-spline collocation matrix small, but I know of no numerical scheme for achieving this. Also, according to Boor75a, this norm is bound to go to infinity as two data sites coalesce unless the knot sequence changes correspondingly in such a way that, in the limit, the limiting double data site is a knot of multiplicity $k$ for the spline space (thus preventing the splines from being differentiable at that point). This is exactly the situation with broken line interpolation, and is what happens more generally when two neighboring Greville points of any order $k$ coalesce. Malcolm Sabin mentioned (in sep96) that he has a satisfactory scheme, but I do not (yet) know details. Since the optimal knots, of GaffneyPowell76 and MicchelliRivlinWinograd76, stay simple even when data sites coalesce, they are, in particular, not good knots in the sense of keeping the norm of the inverse of the B-spline collocation matrix small.