I was wondering how I could fit a polynomial surface through a set of points in two variables. When I look up this problem in the literature, I usually see two options:

  • Use a tensor product, but this only seems to work in the case the points are evaluated in a grid
  • Use some special point layouts, like Padua or Chebyshev points.

Neither options seems feasible for pseudo-random point sets. Does anyone have an idea? (I guess I could use the standard Lagrange formula in two variables, but that doesn't seem like a numerically stable solution.)

  • 2
    $\begingroup$ A curve, or a surface? $\endgroup$ – J. M. isn't a mathematician Nov 6 '11 at 15:49
  • $\begingroup$ A surface; sorry. $\endgroup$ – Howard Nov 6 '11 at 16:49

You can do a multidimensional function minimization. Write your polynomial as $\sum a_{ij}x^iy^j$ over whatever range of $i,j$ you like (hope you have less terms than data points). Then calculate the polynomial at each point, square the errors and sum. Feed it to a minimizer taking the $a_{ij}$ as the parameters and minimize. Sections 10.4 through 10.7 of Numerical Recipes deal with this, as will any numerical analysis text.

| cite | improve this answer | |
  • $\begingroup$ As far as I knew, sum-of-squares methods do not guarantee that the polynomial will contain the interpolated points, it will try to fit a curve that minimizes the error? $\endgroup$ – Howard Nov 6 '11 at 16:48
  • $\begingroup$ @Howard: true. You should add it as a characteristic of the problem exposition in your question, whether the points should be matched or whether you are fine with a least-squares-solution. $\endgroup$ – Gottfried Helms Nov 6 '11 at 17:23
  • 1
    $\begingroup$ @Howard: it will not. In theory, if you have as many polynomials as points, it should be able to fit them exactly (within numerical error). Usually the point of least squares is to smooth the data and you don't want it hitting the points exactly. If you want the polynomials to fit exactly, you need as many as you have data points and then you have a simultaneous equations problem. $\endgroup$ – Ross Millikan Nov 6 '11 at 17:52

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.