1
$\begingroup$

I am currently working on 2D interpolation and I am using cubic splines.

In 1D given N points one would use N+2 splines and would have to apply additional constraints in order to achieve a square system. For example requiring that the interpolant, S, second derivative is equal to zero ,Sxx = 0, at the end points (Natural Spline conditions)

I was wondering how one would extend this to 2D? I believe it should be something like Sxx = Syy = 0 at the edge of your domain but I am not sure (if so I believe we would still be missing some equations). Any help would be appreciated.

I will provide an example in 2D: Consider the points 1:1:10 in the x component and 1:1:10 in the y component, thus N points in each direction. For cubic splines one need N+2 splines in each direction. In 1D interpolation we can add the constraint that the second derivative should be zero to arrive at (N+2) equations for (N+2) unknowns.

Thus to extend to 2D I will take the tensor product of these points I will have a 10x10 grid (100 pairs of points) and the tensor product of 12 splines in each direction (144 splines). Since I am using these for interpolation then I can retrieve 100 equations by setting up an equation for each point in my grid. I can retrieve an additional 40 equations by asking that S_{xx} = S_{yy} = 0 at the boundaries. 10 at $(x_0,y)$, $(x_N,y)$, $(x,y_0)$, $(x,y_N)$ Thus I would be missing 4 equations. This is where my confusion lies.

$\endgroup$
  • $\begingroup$ The attraction of cubic B-splines in 1D is their smoothness, continuous second derivatives even at the knots. In two-dimensions the goals of smoothness vs. compact support need to be matched with your grid. The phrase "square system" suggests you have equally spaced nodes in both coordinate directions. It would help if you clarified your post to explain your grid nodes more clearly. $\endgroup$ – hardmath Apr 27 '15 at 12:22
  • $\begingroup$ I believe square system means I am using the splines for interpolation. I added some more clarification as you requested. $\endgroup$ – user2785954 Apr 27 '15 at 13:01
2
$\begingroup$

There are two different ways to extent cubic splines to 2D.

The more official approach is the tensor product approach. On the boundaries where $x$ is constant, you require $S_{xx}=0=S_{xxy}$. On the boundaries where $y$ is constant, you require $S_{yy}=0=S_{xyy}$. The condition $S_{xxy}=0$ can be derived from $S_{xx}(x_0,y)=0\ \forall y$.

The less official approach is the hierarchical basis or sparse grid approach. Here you just require $S_{xx}=0$ on the boundary grid points where $x$ is constant, and $S_{yy}=0$ on the boundary grid points where $y$ is constant. Then you use 1D splines to determine the partial derivative in $x$- and $y$-direction in all grid points. On a cell, you now have 12 prescribed degrees of freedom: the value and two derivatives in each corner of the cell. Linear interpolation takes care of the values, hence all you need for the derivatives it a form function which is zero on the four corners, and has partial derivative 1 in one direction in one corners, and all other partial derivatives zero in the corners: $x^2(x-1)y$. The resulting function will be continuous everywhere, and smooth along the axis parallel lines through grid points. So you don't have the complete spline smoothness, but the expected convergence order (of the approximation) should already be achieved.

$\endgroup$
  • $\begingroup$ In the described official approach wouldn't you have an overdetermined system with the four conditions? $S_{xx}$=0=$S_{xxy}$, $S_{yy}$=0=$S_{yyx}$? As an example suppose you have 2 points in the x-component and 2 points in the y component. Then you need 4 splines in each of those components. Thus you need 16 equations. You can get 4 equations from the four points and each condition would then contribute another 4 (16 total) yielding a 20 x16 system? Or am I thinking about this wrong? $\endgroup$ – user2785954 Apr 27 '15 at 2:12
  • $\begingroup$ @user2785954 The condition $S_{xxy}=0$ only yields one equation per $x$-boundary edge, not one equation per $x$-boundary vertex. Similarly for the condition $S_{xyy}=0$. $\endgroup$ – Thomas Klimpel Apr 27 '15 at 5:58
  • $\begingroup$ I think I understand now, so when forming the linear equation for $S_{xxy}$, we can pick any y ? i.e.$ S_{xxy}(x_0,y_i) = 0$ . Thus we can get 4 linear equations? $S_{xxy}(x_0,y_i) = 0$ $S_{xxy}(x_N,y_i) = 0$ $S_{yyx}(x_i,y_0) = 0$ $S_{yyx}(x_i,y_N) = 0$ $\endgroup$ – user2785954 Apr 27 '15 at 6:17
  • $\begingroup$ @user2785954 I had both methods implemented at some points, and the final implementations both reduced the actual spline computations to 1D problems. For the tensor product approach, you need to compute $S_{xy}$ in the grid points in addition to $S_x$ and $S_y$. The tensor structure can be exploited for this. I just tried to express the actual boundary conditions satisfied by this tensor product approach. $\endgroup$ – Thomas Klimpel Apr 27 '15 at 13:37
  • 1
    $\begingroup$ @user2785954 I tried to hint that I didn't really work with equations. I rather followed a procedure like the one outlined in en.wikipedia.org/wiki/… in the section starting with "To find the cross derivative, ..." $\endgroup$ – Thomas Klimpel Apr 27 '15 at 14:35

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.