0
$\begingroup$

I am trying to apply a polynomial interpolation to 340 points in a 4D space, i.e.,

$$f(x,y,z)=k\, .$$

What I would like to understand is this: if I use a 6th order polynomial I will end up with 343 degrees of freedom [(order+1)^(dimensions)] for my polynomial, which is a number greater than the actual available number of points. Is the problem underdetermined? Can I state that I cannot use such order for the interpolation?

Then, if I use a 5th order polynomial, this has 216 degrees of freedom, that is a number smaller than my number of points. Is the problem overdetermined? Can I anyway use this order to interpolate my data without problems?

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ What do you mean by "apply a polynomial interpolation to 340 points"? What is commonly done with interpolation is to use a set of points to approximate your function over a domain, and then use those points to interpolate on points different from the original ones. $\endgroup$ – nicoguaro♦ Jun 16 '17 at 0:21
0
$\begingroup$

I'm assuming you're doing your interpolation something like the following way: Given a set of $(x,y,z)$ coordinates $(x_i,y_i,z_i)$ and corresponding value $f_i$ for $i=1,2,...,N$, find the coefficients $c_j$ of the multivariate polynomial

$f(x,y,z) = \sum_{j=1}^M c_j x^{\alpha_j} y^{\beta_j} z^{\gamma_j}$

such that

$f(x_i, y_i, z_i) = f_i$

Here $\alpha_j$, $\beta_j$, and $\gamma_j$ define the orders of each monomial term.

This yields a matrix equation of the following form

$A c = f$

where $A_{ij} = x_i^{\alpha_j} y_i^{\beta_j} z_i^{\gamma_j}$. This is a multivariate version of the Vandermonde matrix. If $A$ is square, then solving for $c$ gives your solution. Obviously, if there are multiple coordinates at the same location, $A$ is singular. I think there are other requirements to guarantee non-singular $A$.

If you have more unknowns ($M$) than constraints ($N$) then your system is underdetermined, which means that there are an infinite number of solutions that satisfy your constraints. It's not that you can't use this polynomial order, it's just that you can't find a unique solution.

If you have more constraints ($N$) than unknowns ($M$) then your system is overdetermined, so there is in general no solution which satisfies all of the constraints. You could solve for $c$ in the least-squares sense, by solving

$c = (A^T A)^{-1} A^T f$

If you need to guarantee that $f(x_i,y_i,z_i)=f_i$ exactly, then this won't work for you. But if you just need it to be close, then this could be the ticket.

You could also start with the underdetermined case and pick some of the highest order terms to remove until $M=N$. Then (assuming $A$ isn't singular) your solution is unique and your constraints are exactly satisfied.

Some nitpicking:

You say this is interpolation in "4D space". I suppose you're considering $f$ to be the fourth dimension, but that's confusing. It's really interpolation of a field $f$ in 3D $(x,y,z)$ space.

You say that a 6th order multivariate polynomial in 3 dimensions has 343 degrees of freedom. Technically, a $p^{th}$ other polynomial contains no terms with order higher than $p$, or in other words $\alpha_j+\beta_j+\gamma_j \le p$ for all $j$. There are ${p+d \choose d}$ degrees-of-freedom, which for $d=3$ is $\frac{(p+3)(p+2)(p+1)}{6}$, and for $p=6,d=3$ is 84.

What you're talking about is something akin to trilinear or tricubic functions, but for higher order. I don't know what you would actually call them, and I also don't really know why you would use them over the normal multivariate polynomial complete functions.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thanks a lot @led23head, very precise and helpful. Anyway, I am trying to implement this in Python. About the last part (nitpicking): I create the Vandermonde matrix and this should be a matrix with (number_of_points, degrees_of_freedom). With a 6th order polynomial I technically have 343 degrees of freedom since I have 'x^0*y^0*z^0 + x^0*y^0*z^1+...+x^6+y^6+z^6'. Am I wrong stating this? Because what I understand from what you are saying is that I can't have polynomial terms like 'x^6*y^6*z^6' since 6+6+6>p=6. Should I fix the code and impose the constraint to the polynomial 'a+b+c<p'? $\endgroup$ – federico Jun 16 '17 at 10:30
  • $\begingroup$ @federico There's nothing wrong with including those terms. I was mostly nitpicking about what "nth order multivariate polynomial" means. The function space you choose for your interpolation depends on your application. That said, I could imagine that 18th order terms are unnecessary. $\endgroup$ – LedHead Jun 16 '17 at 10:57
  • $\begingroup$ So I can reduce the Vandermonde matrix to terms that respects 'a+b+c<p' and obtain a better results? Sorry for the likely trivial questions, but I do not know well this subject, and you are giving me precious advices. Thanks $\endgroup$ – federico Jun 16 '17 at 12:02
  • $\begingroup$ @federico I don't think removing terms will give you a better answer, but it might not make it worse. That of course depends on what you mean precisely by "better". Further questions about polynomial approximation theory should probably be asked in a new question. $\endgroup$ – LedHead Jun 16 '17 at 13:13
  • $\begingroup$ sorry led, could you give me the reference (or some references) from which you extracted what you reported me? Thanks $\endgroup$ – federico Jun 18 '17 at 17:49

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.