tags:

views:

453

answers:

3

I've three sets of data such as:

x   y
4   0
6   60
8   0

Does anyone know any (efficient) Java codes that can give me back the values of a, b, and c (the coefficients)?

+1  A: 

It depends on exactly what you are looking for: Are you looking for the unique polynomial which is defined by those three points, or are you looking for a library which will generate a polynomial which passes through all points?

If you are looking at the first, the best technique is to construct the coefficient matrix(That is, the set of three linear equations which uniquely constrain this quadratic equation)and apply Gaussian Elimination to get your result. This can be done by hand the most efficiently, but you can also use The Apache Commons Math Library's Real Matrix solve methods. (EDIT Thanks for the correction--I speak before I think sometimes ;)

If you are looking at the second, this is specific case of a general class of problems called Interpolation by Polynomials, and there are several ways of solving--Splines are my personal favorite, but all have their strengths and weaknesses. Luckily, Apache Commons Math implements several such methods. I would look at the SplineInterpolator class. Splines use cubics instead of quadratics, but they tend to be very good approximations. They also don't fail if one point is a linear multiple of another.

For just three points, both methods should be about equal in performance characteristics. If you are doing more than three points, however, I would strongly recommend using interpolation, as using Guassian Elimination scales incredibly poorly( O(n^3)), and Splines(Or another interpolation technique) are less likely to fail.

Scott Fines
The only way a set of 3 points can't have a unique quadratic is if one of the x values is repeated in your list (providing you allow linear and constant polynomials as degenerate forms of quadratics).
Simon Nickerson
+5  A: 

I assume you want the formula in this form:

y = a * x^2 + b*x + c

If you have only three points you can describe the quadratic curve that goes through all three points with the formula:

y = (x-x2)(x-x3) / (x1-x2)(x1-x3) * y1 +
    (x-x1)(x-x3) / (x2-x1)(x2-x3) * y2 +
    (x-x1)(x-x2) / (x3-x1)(x3-x2) * y3

In your example:

x1 = 4, y1 = 0, x2 = 6, y2 = 60, x3 = 8, y3 = 0

To get the coefficients a, b, c in terms of x1, x2, x3, y1, y2 and y3 you just need to multiply the formula out and then collect the terms. It's not difficult, and it will run very fast but it will be quite a lot of code to type in. It would probably be better to look for a package that already does this for you, but if you want to do it yourself, this is how you could do it.

The fact that two of the y terms are zero in your example makes the formula a lot simpler, and you might be able to take advantage of that. But if that was just a coincidence and not a general rule, then you need the full formula.

Mark Byers
+1: This is known as the Lagrange interpolating polynomial (http://en.wikipedia.org/wiki/Lagrange_polynomial)
Simon Nickerson
Awesome! That's what I was looking for. I knew the formula but couldn't come to a general form. This works perfectly for me. Also, the pattern looks similar, I always have two 0 values on either side i.e. y0 = y2 = 0
chown
+2  A: 

The LaGrange interpolation is probably the most 'efficient' (how do you measure that?) solution you are going to find. So I'll suggest a completely general code. You did want code, right? This code can go linear, quadratic, cubic, .... for any number of points.

I didn't actually try to compile it, so I don't if the source code is up to date. You know how online demos go. Yet the applet from the associated web page is fully functional. The jar file will run standalone. With a resizable window, you really don't need to customize it.

gary