Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


#ActualEzbez

Posted 04 September 2013 - 01:49 PM

We are trying to solve for the constants a,b,c so that the polynomial a+bx+cx^2 gives the appropriate points. Suppose those points are (x1,y1), (x2, y2), (x3,y3).

 

The typical way to solve this is by using some linear algebra (I know! linear algebra lets you solve quadratics? It's somewhat surprising but we actually know x here and so we don't need to worry about any quadratic behavior. The things were solving for are a, b, and c which are only used linearly in this equation.). If you aren't familiar with this then you'll have to solve it out entirely (and may want to either way if you're not already using a linear algebra library). What this means is that we can plug each point (x,y) into the polynomial and this gives us a constraint on the possible values of a,b,c. So we get:

 

a + b*x1 + c*x1^2 = y1

a + b*x2 + c*x2^2 = y2
a + b*x3 + c*x3^2 = y3
 
These are three equations and we have three unknowns a,b,c so it should be solvable, at least so long as the three points permit a unique solution (almost all such points do). You can now solve these three equations for a,b,c.
 
If you know linear algebra, then this is just solving the matrix-vector equation:
 
The matrix M = 
| 1 x1 x1^2 |
| 2 x2 x2^2 |
| 3 x3 x3^2 |
The vector Y = {y1, y2, y3} (a column vector)
The vector X = {a,b,c} (also a column vector).
Solve M * X = Y, or X = M \ Y if you're in a language or package that support matrix math directly. Most such languages will also have built-in functions to do this sort of thing. Look for polynomial fitting or least squares (though least squares would technically be overkill).
 
Or, like I said, you can solve this any other way that you want, such as substitution that most people learn by
highschool algebra.
 
Edit:
Actually, I feel like doing that substitution out right now. Starting with the last equation:
a + b x3 + c x3^2 = y3, so a = y3 - bx3 - cx3^2
Substitute into the second equation for a:
(y3 - bx3 - cx3^2) + bx2 + cx2^2 = y2
Solve for b:
b = [ y2 - y3+ c (x3^2 - x2^2) ] / (x2 - x3)
Substitute into the first equation for b and a:
(y3 - [y2 - y3 + c ( x3^2 - x2^2) ] / (x2 - x2) - cx3^2) - [y2 - y3 + c (x3^2 - x2^2)] / (x2 - x3) x1 - cx1^2 = y1
Solve for c:
c = oh gosh I don't really feel like doing the rest of this I guess, but you get the idea. It's pretty long! So I decided to cheat and use Wolfram|Alpha to solve it for me.
 
This gives us some beautiful solutions:
Let C = 1/ [ (x1-x2) * (x2 - x3) * (x1 - x3) ].
a = C * [ x1*x2 * (x2-x3) * y1 - x1*x3 * (x1-x3) * y2 + x1*x2 * (x1-x2) * y3]
b = C * [-(x2 + x3) * (x2-x3) * y1 + (x1 + x3)* (x1-x3) * y2 + (x1 + x2) * (x1 - x2) * y3]
c = C * [ (x2 - x3) * y1 - (x1 - x3) * y2 + (x1 - x2) * y3 ]
Gives us the coefficients!

#2Ezbez

Posted 04 September 2013 - 01:49 PM

We are trying to solve for the constants a,b,c so that the polynomial a+bx+cx^2 gives the appropriate points. Suppose those points are (x1,y1), (x2, y2), (x3,y3).

 

The typical way to solve this is by using some linear algebra (I know! linear algebra lets you solve quadratics? It's somewhat surprising but we actually know x here and so we don't need to worry about any quadratic behavior. The things were solving for are a, b, and c which are only used linearly in this equation.). If you aren't familiar with this then you'll have to solve it out entirely (and may want to either way if you're not already using a linear algebra library). What this means is that we can plug each point (x,y) into the polynomial and this gives us a constraint on the possible values of a,b,c. So we get:

 

a + b*x1 + c*x1^2 = y1

a + b*x2 + c*x2^2 = y2
a + b*x3 + c*x3^2 = y3
 
These are three equations and we have three unknowns a,b,c so it should be solvable, at least so long as the three points permit a unique solution (almost all such points do). You can now solve these three equations for a,b,c.
 
If you know linear algebra, then this is just solving the matrix-vector equation:
 
The matrix M = 
| 1 x1 x1^2 |
| 2 x2 x2^2 |
| 3 x3 x3^2 |
The vector Y = {y1, y2, y3} (a column vector)
The vector X = {a,b,c} (also a column vector).
Solve M * X = Y, or X = M \ Y if you're in a language or package that support matrix math directly. Most such languages will also have built-in functions to do this sort of thing. Look for polynomial fitting or least squares (though least squares would technically be overkill).
 
Or, like I said, you can solve this any other way that you want, such as substitution that most people learn by highschool algebra.
 
Actually, I feel like doing that substitution out right now. Starting with the last equation:
a + b x3 + c x3^2 = y3, so a = y3 - bx3 - cx3^2
Substitute into the second equation for a:
(y3 - bx3 - cx3^2) + bx2 + cx2^2 = y2
Solve for b:
b = [ y2 - y3+ c (x3^2 - x2^2) ] / (x2 - x3)
Substitute into the first equation for b and a:
(y3 - [y2 - y3 + c ( x3^2 - x2^2) ] / (x2 - x2) - cx3^2) - [y2 - y3 + c (x3^2 - x2^2)] / (x2 - x3) x1 - cx1^2 = y1
Solve for c:
c = oh gosh I don't really feel like doing the rest of this I guess, but you get the idea. It's pretty long! So I decided to cheat and use Wolfram|Alpha to solve it for me.
 
This gives us some beautiful solutions:
Let C = 1/ [ (x1-x2) * (x2 - x3) * (x1 - x3) ].
a = C * [ x1*x2 * (x2-x3) * y1 - x1*x3 * (x1-x3) * y2 + x1*x2 * (x1-x2) * y3]
b = C * [-(x2 + x3) * (x2-x3) * y1 + (x1 + x3)* (x1-x3) * y2 + (x1 + x2) * (x1 - x2) * y3]
c = C * [ (x2 - x3) * y1 - (x1 - x3) * y2 + (x1 - x2) * y3 ]
Gives us the coefficients!

#1Ezbez

Posted 04 September 2013 - 01:33 PM

We are trying to solve for the constants a,b,c so that the polynomial a+bx+cx^2 gives the appropriate points. Suppose those points are (x1,y1), (x2, y2), (x3,y3).

 

The typical way to solve this is by using some linear algebra (I know! linear algebra lets you solve quadratics? It's somewhat surprising but we actually know x here and so we don't need to worry about any quadratic behavior. The things were solving for are a, b, and c which are only used linearly in this equation.). If you aren't familiar with this then you'll have to solve it out entirely (and may want to either way if you're not already using a linear algebra library). What this means is that we can plug each point (x,y) into the polynomial and this gives us a constraint on the possible values of a,b,c. So we get:

 

a + b*x1 + c*x1^2 = y1

a + b*x2 + c*x2^2 = y2
a + b*x3 + c*x3^2 = y3
 
These are three equations and we have three unknowns a,b,c so it should be solvable, at least so long as the three points permit a unique solution (almost all such points do). You can now solve these three equations for a,b,c.
 
If you know linear algebra, then this is just solving the matrix-vector equation:
 
The matrix M = 
| 1 x1 x1^2 |
| 2 x2 x2^2 |
| 3 x3 x3^2 |
The vector Y = {y1, y2, y3} (a column vector)
The vector X = {a,b,c} (also a column vector).
Solve M * X = Y, or X = M \ Y if you're in a language or package that support matrix math directly. Most such languages will also have built-in functions to do this sort of thing. Look for polynomial fitting or least squares (though least squares would technically be overkill).
 
Or, like I said, you can solve this any other way that you want, such as substitution that most people learn by highschool algebra.

PARTNERS