# Polynomial interpolation on scattered points

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.)

• A curve, or a surface? – J. M. isn't a mathematician Nov 6 '11 at 15:49
• A surface; sorry. – 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.