table_model constraints

I've been having a look at the numbers of equations and unknowns
for a 2-d interpolation, 2nd and 3rd order.

**** 2nd order splines

If one has a polynomial Cij x^i y^j for i=0..2, j=0..2, there are
9 coefficients per region.

If we assume a Cartesian grid, with M points in the x direction
and N points in the y direction, that gives (M-1)*(N-1) regions.

Thus, we have a total of 9MN-9M-9N+9 unknowns.

In each region, the polynomial must fit the data given for the four
corners. This is 4MN-4M-4N+4 equations/constraints.

The derivative df/dx must be continuous at the boundaries. I believe
we want the derivative to be continuous for all y along the edge,
not just at the corner points. df/dx will have terms that are
order y^0,y^1, and y^2; the coefficients of each power must be
equal on either side of the boundary, so this means we have 3
equations for each boundary. There are (M-2) boundaries per "row"
and (N-1) rows. This makes 3MN-3M-6N+6 equations.

The derivative df/dy gives us 3MN-6M-3N+6 for similar reasons.

Thus, we have a total of 10MN-13M-13N+16 equations, but only
9MN-9M-9N+9 unknowns. The system is *overconstrained* once we
get bigger than 7x7.

I don't see that a 2nd order spline is useful in 2d (or 3d),
since we have to give up some constraints, either fitting
the data or continuity of derivatives.

**** 3rd order splines

The book "Numerical Recipes in C" indicates that a bicubic spline can
be set up by specifying f, df/dx, df/dy, and d2f/dxdy on the Cartesian
grid. The interpolation function will have these specified derivatives
continuous across the region boundaries. Note that, even though it is
cubic, we don't necessarily get 2nd order derivatives continuous.
The bicubic spline is of the form
  (sum on i=0..3)(sum on j=0..3) Cij x^i y^j
which is 16 terms per region.

Since users generally will not have derivative information, let's see
how many constraints we need beyond the function values and the
continuity of derivatives.

The values provide 4 constraints per region.

The derivative df/dx will contain terms of order y^0, y^1, y^2, y^3,
and these must vanish independently; that means we have 4 equations
per boundary, and (M-2)*(N-1) boundaries. We get the same number of
constraints for df/dy.

It turns out that we do not get any further constraints by requiring
continuity of d2f/dxdy, because these constraints are linearly related
to the constraints enforced by the first derivatives.

So, we have 16MN-16M-16N+16 unknowns, and 12MN-16M-16N+20 equations,
so we are missing 4MN-4 constraints.

Anyone one want to take a stab at defining those constraints?

-Geoffrey
Received on Tue Aug 10 13:05:46 2004