Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is possible to construct infinitely differentiable functions that interpolate through arbitrary points, the way polynomial splines do? If so, do they have a name and is there an algorithm for constructing the curves.

I suppose a infinite degree polynomial spline might qualify but I was hoping there might be something more like a bump function.

I definitely am a novice when it comes to this stuff, so please do not hesitate to correct me if I misusing any terminology.

share|improve this question
1  
+1 I'm pretty certain you can easily construct an infinite number of infinitely differentiable functions that pass through a given finite set of arbitrary points. Finding one for which interpolated values are reasonable -- ie, without implausible fluctuations in between the known points -- may be another matter, though. I'll be interested to see what the gurus come up with... –  walkytalky Aug 11 '10 at 12:33
    
The method I sketch below produces a graph that looks like a smoothed step function. –  Carl Mummert Aug 11 '10 at 12:40
    
walkytalky: the word you seem to be grasping for is "monotonicity". That being said, it's actually a nontrivial problem to have an approximant that is sufficiently smooth (differentiable) and is monotonic as well, free of spurious wiggles. The best solution really is dependent on the geometry of the data points given. –  J. M. Aug 11 '10 at 14:34
    
@J. Possibly "monotonicity" has a more specific meaning in this context that I am not aware of, but it seems to me that a reasonable interpolant is not necessarily monotonic (in the general sense) between known points. In some cases having an extremum between some adjacent samples may look more plausible. –  walkytalky Aug 11 '10 at 18:11
    
As mentioned, the best solution is dependent on the configuration of your given points. Obviously if your point-set seems to be coming from an oscillatory function, a monotonic method would be unsuitable. The usual constraint I keep seeing in practice is that the local extrema in your interpolant should either be in the same place as the extrema of your data, or that the new extremum (e.g. for an interpolant between two points with near-identical ordinates) be of the same order of magnitude as the points in the neighborhood, viz. "locally monotonic". –  J. M. Aug 12 '10 at 3:12

4 Answers 4

up vote 3 down vote accepted

For n data points, there is a unique polynomial of degree n−1 that passes through the points; one way to get it is the Lagrange polynomial.

Another class of interpolating functions is the thin plate spline, which is typically used for 2D image warping, but can easily be applied to 1D interpolation as well, which is a strictly simpler problem. The Wikipedia article on polyharmonic splines, of which the thin plate spline is a special case, has examples of other infinitely differentiable splines.

I believe that in principle, you can choose any basis function whose translations are linearly independent, and find an interpolating function as a sum of translations and scalings of the basis. The above are essentially examples of particular basis functions people have used because of their other nice properties.

Edit: Sorry, thin plate splines and other examples in the article, apart from the Gaussian, are infinitely differentiable almost everywhere. However, if you really want infinite differentiability everywhere, you can use any infinitely differentiable function as basis instead, such as the Gaussian, or $x^2/\sqrt{x^2+1}$.

share|improve this answer

Yes - if you have a finite list of points on the plane that pass the vertical line test, you can make a smooth (infinitely differentiable) function that goes through all of them.

This can actually be done somewhat explicitly, using the formulas at [1]. Define:

$$ f(x) = \begin{cases} 0 & x \leq 0 \\ e^{-1/x}& x > 0 \\ \end{cases}. $$

It can be proved that this is a smooth function. Then define

$$ g(x) = \frac{f(x)}{f(x)+f(1-x)}. $$

The function $g(x)$ is smooth, defined for all real $x$, and has the property that $g(x) = 0$ for all $x \leq 0$ while $g(x) = 1$ for all $x \geq 1$. By adding together shifted and scaled copies of $g(x)$, you can make a smooth function that goes through any finite list of points that pass the vertical line test.

1: http://en.wikipedia.org/wiki/Non-analytic_smooth_function

share|improve this answer
    
I can't make the definition by cases display correctly. If anyone else can, please feel free to edit my answer or leave a comment here. Thanks - –  Carl Mummert Aug 11 '10 at 12:39
    
Try three consecutive backslashes at the end of the first line, instead of 2. –  ShreevatsaR Aug 11 '10 at 14:09
    
One can always interpolate a set of points with parametric equations if need be. –  J. M. Aug 11 '10 at 14:24
    
@Carl: I've adjusted your TeX. @ShreevatsaR has the right idea. Markdown treats \ as a special character, so you need to type two slashes wherever TeX would expect one. So to get a \\ type \\\\. –  Larry Wang Aug 11 '10 at 14:28
    
@Kaestur Hakarl: Actually, I was going to suggest 4 backslashes, but I tried with 3 slashes and it works. Of course, ≥4 also works. –  ShreevatsaR Aug 11 '10 at 15:02

It's a bit disingenuous to say polynomial splines are infinitely differentiable; a spline with nth order pieces can only have at most C^{n-1} continuity. That being said, a different basis set (e.g. the Fourier basis or rational functions) would in principle be infinitely differentiable, but might be a very "wiggly" way to "connect the dots" so to speak. Polynomial interpolation, whatever method you use, will also suffer from this "wiggliness".

Why would you need your approximant to be infinitely differentiable anyway? Unless you're going to be doing something special I don't see it being a necessity.

share|improve this answer
1  
+1 for the last point, but it's an interesting question in the abstract. –  walkytalky Aug 11 '10 at 18:13
1  
I agree that saying a infinite degree polynomial is disingenuous, that is why I was trying to prevent that type of answer. I have no application for this, I was just curious if you could construct meaningful interpolation that looked like polynomial splines but was smooth. –  Jonathan Fischoff Aug 11 '10 at 19:43
1  
An approximant based on sines and cosines (i.e. the Fourier basis) would in principle be infinitely differentiable, but again this is not always appropriate. For most physical applications anyway one is usually content with C^2 (to use a physical example, the usual quantities of interest are position, velocity, and acceleration; "jerk" not so much.); people who solve boundary-value problems might sometimes want a C^4 approximant (quintic splines are the usual basis), but SFAIK nobody bothers with higher orders of continuity in practice. –  J. M. Aug 12 '10 at 3:18

You could build a generalized interpolating spline of any required degree of smoothness which passes through the n data points. Details are described in articles:

J. Duchon."Splines minimizing rotation-invariant semi-norms in Sobolev spaces" // Constructive Theory of Functions of Several Variables.Lecture Notes in Mathematics Volume 571, 1977, pp 85-100

В.К. Горбунов, В. В. Петрищев. "Развитие метода нормальной сплайн-коллокации для линейных дифференциальных уравнений" // Ж. вычисл. матем. и матем. физ., 2003, том 43, номер 8, страницы 1150–1159 (http://www.mathnet.ru/php/getFT.phtml?jrnid=zvmmf&paperid=974&what=fullt&option_lang=rus)

V.K. Gorbunov "The method of normal spline collocation" // USSR Computational Mathematics and Mathematical Physics, Volume 29, Issue 1, 1989, Pages 145–154

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.