I need help with approximation (math).

First off, this is not homework.

I am OK at math, but not nearly as good as people I have seen on this board. The problem I have now totally stumps me and I don’t know if what I want to do is even possible. OK, here is the question: Can I approximate a two dimensional function with a polynomial, and if so, how?

In one dimension I know how to do this. I know about Taylor approximations, minimax approximations, least squares and orthogonal polynomials. I know how to bound my error using the de la Valle-Pousin theorem. I even can create minimax approximations using Chebyshev polynomials.

But I don’t know how to do this in 2 dimensions.

Explicitly: for an unknown function f(x,y), I have a set of points, (x0,y0), (x1,y1),… (actually a grid of points) where I know the value of the function. Using these values, can I create a polynomial, P(x,y), that approximates the unknown function f(x,y)?

You just need a two dimensional polynomial. In addition to the standard
1-D terms, there may also be cross-product terms.

f(x,y) = a + b x + c y + d x^2 + e y^2 + f xy + …
I often use the solver in Excel to determine the coefficents.

Yes. It’s called “curve-fitting” or “polynomial regression”. Most probability textbooks will have a chapter on it. Mine’s in storage right now so I can’t help you. But it might be worth it to do a Google search to see if there’s any online regression programs.

Damn. How do I do it though?

I know how to do curve fitting with one variable or with a serparble function, but it is those cross terms that kill me. Typically when I do this I use Chebyshev or Legendre polynomials and use Gram-Schmidt method to do the regression. I have also been known to use Least Squares even though it is unstable.

sishoch, How do you determine the coefficients in excel? Can you post an algorithm?

Thanks for the replies.

Separable :smack:

Please ignore that and any other spelling/grammer errors you find. My blood is somewhat up with this problem.

Excel is the wrong software to do this in. For some reason, people seem to think it’s a decent stat package, but it’s really bare-bones.

Regression can get pretty complicated pretty quickly, and the formulas are not your friends if you’re not very comfortable with matrix algebra. I’d offer to do it myself, but I don’t have the software for it.

I looked through Excels help files and it looks like they are just doing linear regression except when using trendlines (a one-D case). As far as linear regression, I could probably figure out how to fit a plane to my data using a minimax-type approximation, but I would prefer something of a higher degree (with a smaller maximum error).

As far as matrix algebra, I feel very comfortable with it. As far as software, I have MATLAB and Mathematica. I went through the Mathematica help files and could not find anything that helped me. I have yet to poke around the MATLAB help files, though I just remembered I have the statistical toolbox for MATLAB, so maybe I do have something.

Still though, I would prefer to know what MATLAB (or whatever) is doing before I use it. Can anybody post a link or a reference of methods for fitting 2-d data using non-seperable polynomials?

You know, I should not try to do work after dinner (with the 2 glasss of wine I had) or even at the end of a long day. I just can’t think clearly.

What I really want to do is interpolate between the points I have using splines or hermite polynomials or something. This I can do.

Thanks for the help everyone.

You said you knew Taylor expansions. If you know how to get from Taylor to a polynomial with specified valuesin one dimension you should know how in n dimensions.

Do you want to do it in general or for this particular set of points? If it’s a one-time thing, send me the data (either in a post or via email) and I’ll see what I can do. I’ll explain how I did it after I’ve looked to see what the best approach will be. Also some information on tolerance and the errors (if any) on the data would be helpful.

About 8-9 years ago I wrote a MATLAB routine that pretty much does this. I can’t even remember why, but I do have it handy.

Basically, I adapted the native MATLAB routines polyfit.m and polyval.m to two dimensions. It does a least-squares approximation, using the same algorithm. The user specifies what degree of polynomial to use.

Feel free to send me an email (available through my profile) - I’d be happy to send you the routines if you’d like.

Yes, but I have an unknown function so it is difficult for me to take deriavtives. I was not thinking clearly last night when I posted the OP. It was ~9:00 pm, after dinner, after wine, and after a 10 hour work day with only a short break for dinner.

What I needed to do was interpolate between the values of the function I know, not approximate the function. I have done that using a crude Lagrange piecewise polynomial of order 3. This is a brute force calculation and I can not think of a way to extend it to a global interpolation (splines) though I sure it is doable. What I have seems to work relativly well even though the interpolation is discontinuous in slope at the subinterval boundaries. It is good enough.

Thank you all for your help.

FWIW, I’ve never actually done this sort of regression before, but here’s my educated guess on how it works.

You’ve got two vectors x and y of coordinates, and a vector v of values. You want a function f(x, y) = (ax + by + c)[sup]n[/sup] such that the sum of the quantity (f(x[sub]i[/sub], y[sub]i[/sub]) - v[sub]i[/sub])[sup]2[/sup] is minimized for a constant n. Finding the minimum is a matter of matrix calculus and some algebra, and that can get tricky. If you have MATLAB and Mathematica, you should be good to go.

The reason you want to hold n constant is because for a suitably large value of n (equal to the number of points you have), you’re finding the polynomial that fits exactly those points. If you get a new data point that doesn’t fit that polynomial, it’s no good.

Generally, you’d start with n = 1 and figure out how good the model is using appropriate techniques (that I don’t know). Then go up to n = 2, then n = 3, and so on and so forth. The last value of n that gives you a significant increase in the goodness of fit is probably the best one to use. Significant here is a very subjective term.