Learn more about Spline Toolbox

optknt - Knot distribution "optimal" for interpolation

Syntax

knots = optknt(tau,k,maxiter) optknt(tau,k)

Description

knots = optknt(tau,k,maxiter) provides the knot sequence t that is best for interpolation from at the site sequence tau, with 10 the default for the optional input maxiter that bounds the number of iterations to be used in this effort. Here, best or optimal is used in the sense of References and References, and this means the following: For any recovery scheme that provides an interpolant that matches a given at the sites tau(1), ..., tau(n), we may determine the smallest constant for which for all smooth functions .

Here, . Then we may look for the optimal recovery scheme as the scheme for which is as small as possible. Micchelli/Rivlin/Winograd have shown this to be interpolation from , with t uniquely determined by the following conditions:

t(1) = ... = t(k) = tau(1);
t(n+1) = ... = t(n+k) = tau(n);
Any absolutely constant function with sign changes at the sites t(k+1), ..., t(n) and nowhere else satisfies

Gaffney/Powell called this interpolation scheme optimal since it provides the center function in the band formed by all interpolants to the given data that, in addition, have their th derivative between and (for large ).

optknt(tau,k) is the same as optknt(tau,k,10).

Examples

See the last part of the demo "Spline Interpolation" for an illustration. For the following highly nonuniform knot sequence

t = [0, .0012+[0, 1, 2+[0,.1], 4]*1e-5, .002, 1];

the command optknt(t,3) will fail, while the command optknt(t,3,20), using a high value for the optional parameter maxiter, will succeed.

Algorithm

This is the Fortran routine SPLOPT in PGS. It is based on an algorithm described in References, for the construction of that sign function mentioned above. It is essentially Newton's method for the solution of the resulting nonlinear system of equations, with aveknt(tau,k) providing the first guess for t(k+1), ...,t(n), and some damping used to maintain the Schoenberg-Whitney conditions .

References

[1]C. de Boor, "Computational aspects of optimal recovery", in Optimal Estimation in Approximation Theory, C.A. Micchelli & T.J. Rivlin eds., Plenum Publ., New York, 1977, 69-91.

[2]P.W. Gaffney & M.J.D. Powell, "Optimal interpolation", in Numerical Analysis, G.A. Watson ed., Lecture Notes in Mathematics, No. 506, Springer-Verlag, 1976, 90-99.

[3]C.A. Micchelli, T.J. Rivlin & S. Winograd, "The optimal recovery of smooth functions", Numer. Math. 80, (1974), 903-906.