I have an expensive scalar-valued function $f$. If needed, you can assume it's single-variate.
I want to approximate the function on the interval $[0,1]$, so I evaluate it at several points $x^n \triangleq x_1,\ldots,x_n$, and then interpolate through those. My question is how should I choose these interpolation points? Assume I won't be using polynomial interpolation (I'll be using either splines, kriging, or radial-basis functions).
Obviously, there's equal-spacing, there's Latin Hypercube Sampling (LHS), and there's purely random sampling. But my intuition is there's a dynamic sampling method which tries to sample more wherever the function is especially volatile or hairy and less where the function is quite smooth.
Could anyone give me at least a heuristic answer for this? If necessary, you can use evaluations of the gradient or even the Hessian, but that's much less than ideal.
For polynomial interpolation (which you said you're not using) you should interpolate at Chebyshev zeros or Chebyshev extrema. Though, actually, any sites that are more densely clustered near the ends of your interval will work adequately. There's a book entitled "Approximation Theory and Practice" by Trefethen that has lots of details about this topic.
There are similar results for spline interpolation. The analogous sites are the Chebyshev-Demko sites. The process is discussed in de Boor's book "A Practical Guide to Splines".