2
$\begingroup$

I'd need any (real-valued) function (whatever meets the following description at least approximately) continuous and thrice differentiable everywhere (or twice if 3 not possible), with the following features.

Seen "by far, it would be resembling the floor function $\lfloor x \rfloor $, exactly equal to $j$ at each positive integer $j$, but then slightly increasing on the "horizontal" part and finally more suddenly raise to the next integer, so approximately doing as follows. Let $\epsilon$ and $\alpha$ two arbitrarily small positive numbers given by the user. The function should be:

$j$ at any integer $j$ (I need only $j$ > 2, no need to consider negative integers)

increasing from $j$ to $j +\alpha$ near the the "horizontal part" of the floor, say approximately over $(j, j + 1 - \epsilon$].

suddenly increasing (or non-decreasing), from $j + \alpha$ to $(j + 1)$, "near the step" of a floor function [say approximately over $[j + 1 - \epsilon, j+1$).

These pieces should be "joined" in such a way that the function is continuous and differentiable. (Any function with the above characteristics will do: of course, the simpler the better: I need it for an iterative program)

PS. added later

If useful, I found this paper: http://math.arizona.edu/~shankar/projects/TermPaper_Yilu.pdf

which has something which perhaps may come close (see pag. 10/11). But it is missing the increasing "horizontal" part.

$\endgroup$
  • 1
    $\begingroup$ What is the domain of your function? All $x\in\mathbb{R}$? $\endgroup$ – barak manos Aug 25 '14 at 11:56
  • 1
    $\begingroup$ I could give you a Spline if $x$ was limited between some minimum and maximum values. $\endgroup$ – barak manos Aug 25 '14 at 11:58
  • 1
    $\begingroup$ So would a C / C++ / Python code do then (and if yes, which one)? $\endgroup$ – barak manos Aug 25 '14 at 12:00
  • 1
    $\begingroup$ Well, the code will also print the function for you if that's what you want (you'll have to input your $M$ of course). $\endgroup$ – barak manos Aug 25 '14 at 12:02
  • 1
    $\begingroup$ Second thought, for your requirement, the traditional Spline algorithm will yield a straight line, i.e., $f(x)=x$... So you'll also need to define a "midpoint" between every two integers in your domain. For example: $f(3.5)=3.1,f(4.5)=4.1,f(5.5)=5.1\dots$ $\endgroup$ – barak manos Aug 25 '14 at 12:11
2
$\begingroup$

You can build the function you need from an alternating sequence of linear pieces and polynomial pieces.

Over the interval $(j-1, j - \epsilon]$, you just use a straight line that increases from $j-1$ to $j -1+\alpha$. Call it's slope $m$, which we can calculate from $\epsilon$ and $\alpha$. In fact, $m = \alpha/(1-\epsilon$.

Similarly, over the interval $(j, j +1 - \epsilon]$, you just use a straight line that increases from $j$ to $j +\alpha$.

Now we need to fit in a polynomial piece $p$ that provides a steep upwards ramp over the interval $(j - \epsilon, j]$. The requirements are: $$p(j - \epsilon) = j-1+\alpha \quad ; \quad p(j) = j$$ $$p'(j - \epsilon) = m \quad ; \quad p'(j) = m$$ A cubic polynomial has four coefficients, so you will be able to satisfy these four conditions. You could just assume $p(x) = ax^3 + bx^2 + cx + d$, write down the four equations arising from the four conditions, and solve for $a$, $b$, $c$, $d$. This is the brute force approach; there are cleverer approaches using Hermite interpolation techniques, which give you the required curve immediately, without the need to solve a system of linear equations. See this article, for example. Applying the Hermite cubic formulae, we get $$ p(t) = (m - \epsilon)(2t^3 - 3t^2) + mt + j - \epsilon \qquad (0 \le t \le 1) $$ where $t = (x - j + \epsilon)/\epsilon$. You only have to do this once. Thereafter, you can get other polynomial filler pieces just by shifting this basic one to the left or right.

The curve constructed this way will be only once differentiable -- there will be discontinuities in the second derivative at all the joints. If you want a curve that's twice differentiable, you let $p$ be a quintic polynomial, and you add two more conditions that force it to mate nicely with the adjacent linear pieces: $$ p''(j - \epsilon) = 0 \quad ; \quad p''(j) = 0 $$ To get a curve that's thrice differentiable, use a polynomial of degree 7, and so on.

$\endgroup$
  • $\begingroup$ That is, I think, exactly what I had in mind. The problem, I guess, is for me to actually put together the final expression for the thrice differentiable version and obtain the formal expression of it on the interval ($j$, $j+1$] $\endgroup$ – Pam Aug 25 '14 at 13:06
  • 1
    $\begingroup$ OK. So decide what slopes you want to use at all the "joint" places, and then do the polynomial fitting on every segment, instead of alternating with linear pieces. $\endgroup$ – bubba Aug 25 '14 at 13:24
  • 1
    $\begingroup$ See my edit. I added a link that gives an immediate explicit solution for the cubic case. $\endgroup$ – bubba Aug 25 '14 at 13:37
  • 1
    $\begingroup$ Added explicit formula for the Hermite cubic case. $\endgroup$ – bubba Aug 25 '14 at 14:07
  • 1
    $\begingroup$ The only reason I answered the question is because you used the word "thrice". It's nice to see some literacy on this site. The more typical butchery of my language is depressing. $\endgroup$ – bubba Aug 25 '14 at 14:33
1
$\begingroup$

For your requirement, the traditional spline-computing algorithm will yield $f(x)=x$.

So you'll also need to define a "midpoint" between every two integers in your domain.

For example: $f(2)=2,f(2.5)=2.1,f(3)=3,f(3.5)=3.1,f(4)=4,f(4.5)=4.1$.

Here is a piece of Python code for any given number of points $(x_0,y_0),(x_1,y_1),...,(x_N,y_N)$:

class Point:
    def __init__(self,x,y):
        self.x = 1.0*x
        self.y = 1.0*y

def Spline(points):
    N   = len(points)-1
    w   =     [(points[i+1].x-points[i].x)      for i in range(0,N)]
    h   =     [(points[i+1].y-points[i].y)/w[i] for i in range(0,N)]
    ftt = [0]+[3*(h[i+1]-h[i])/(w[i+1]+w[i])    for i in range(0,N-1)]+[0]
    A   =     [(ftt[i+1]-ftt[i])/(6*w[i])       for i in range(0,N)]
    B   =     [ftt[i]/2                         for i in range(0,N)]
    C   =     [h[i]-w[i]*(ftt[i+1]+2*ftt[i])/6  for i in range(0,N)]
    D   =     [points[i].y                      for i in range(0,N)]
    return A,B,C,D

def PrintSpline(points,A,B,C,D):
    for i in range(0,len(points)-1):
        func = str(points[i].x)+' <= x <= '+str(points[i+1].x)+' : f(x) = '
        components = []
        if A[i]:
            components.append(str(A[i])+'(x-'+str(points[i].x)+')^3')
        if B[i]:
            components.append(str(B[i])+'(x-'+str(points[i].x)+')^2')
        if C[i]:
            components.append(str(C[i])+'(x-'+str(points[i].x)+')')
        if D[i]:
            components.append(str(D[i]))
        if components:
            func += components[0]
            for i in range (1,len(components)):
                if components[i][0] == '-':
                    func += ' - '+components[i][1:]
                else:
                    func += ' + '+components[i]
            print func
        else:
            print func+'0'

Here is how you can print the Spline function of the $6$ points in the example above:

points = [
    Point(2,2),Point(2.5,2.1),
    Point(3,3),Point(3.5,3.1),
    Point(4,4),Point(4.5,4.1),
]
A,B,C,D = Spline(points)
PrintSpline(points,A,B,C,D)

Here is Wolfram's graphic illustration (sorry about the missing piece $4\leq{x}\leq4.5$):

enter image description here

You can change the characteristics of the "horizontal" parts by "playing" with the midpoint values.

$\endgroup$
  • $\begingroup$ Hmmm. That is interesting, but I would need a formal expression, mathematically manipulable, from which I can compute the derivatives, as other formal expressions. For an example of what I mean, see for instance the link I added in my question math.arizona.edu/~shankar/projects/TermPaper_Yilu.pdf (pag. 10) $\endgroup$ – Pam Aug 25 '14 at 12:24
  • 1
    $\begingroup$ @Pam: Added a graphic illustration. $\endgroup$ – barak manos Aug 25 '14 at 12:43
  • $\begingroup$ Hmm. Well, while interesting, I am not sure this is something I can use or I can derive from. I would need something that has a formal expression whose formal "structure" does not vary with the integer $j$. It should entirely be defined in term of $x$ and the constants $\epsilon$, $\alpha$ (or few more if necessary), but not "structurally" dependent on $j$. $\endgroup$ – Pam Aug 25 '14 at 12:51
  • $\begingroup$ @Pam: Well, from the look of it, I think it's fair to say that it does not depend on the value of $j$, as you have the same coefficients for every piece of the function in the range ${K}\leq{x}\leq{k+0.5}$ and the same coefficients for every piece of the function in the range ${K+0.5}\leq{x}\leq{k+1}$ You can observe that in the example given at the bottom of the answer. $\endgroup$ – barak manos Aug 25 '14 at 13:06
  • $\begingroup$ @barakmanos -- Is this curve monotone increasing? $\endgroup$ – bubba Aug 25 '14 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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