Porabola From 3 Points

[BigMoosie]

If I am given 3 points I am sure (but cannot prove) that there will be only 1 porabola that can satisfy all 3 of them. What formula would allow me to solve this porabola? The same applies for 4 points and a cubic (or more generally, n points and a polynomial of n-1 degree).

 

Of course, no two points can share a y-value and not all the points can be in a straight line.

 

I solved this problem for a circle given 3 points, althought the porabola has proven far more difficult. Could you please help?

[cosine]

If I am given 3 points I am sure (but cannot prove) that there will be only 1 porabola that can satisfy all 3 of them. What formula would allow me to solve this porabola? The same applies for 4 points and a cubic (or more generally' date=' n points and a polynomial of n-1 degree).

 

Of course, no two points can share a y-value and not all the points can be in a straight line.

 

I solved this problem for a circle given 3 points, althought the porabola has proven far more difficult. Could you please help?[/quote']

 

Analytically you could give a proof saying that a parabola is of the form [math]y = ax^{2} + bx + c[/math], so that with 3 points you can solve for the 3 coefficients.

 

Hope this helps, can't really think of a synthetic proof, sorry.

[BigMoosie]

Well, here is a proof, but it isnt really my goal to find one:

 

Given two porabolas:

 

[math]y=ax^2+bx+c[/math] and [math]y=Ax^2+Bx+C[/math]

 

Equating to find intersections:

 

[math]ax^2+bx+c = Ax^2+Bx+C[/math]

 

[math](a-A)x^2+(b-B)x+(c-C) = 0[/math]

 

The quadratic can have at most 2 distinct solutions, therefore with three points there can be no ambiguity.

[cosine]

Well' date=' here is a proof, but it isnt really my goal to find one:

 

Given two porabolas:

 

[math']y=ax^2+bx+c[/math] and [math]y=Ax^2+Bx+C[/math]

 

Equating to find intersections:

 

[math]ax^2+bx+c = Ax^2+Bx+C[/math]

 

[math](a-A)x^2+(b-B)x+(c-C) = 0[/math]

 

The quadratic can have at most 2 distinct solutions, therefore with three points there can be no ambiguity.

 

Well hey, nice proof!

 

Btw, what was your goal?

[BigMoosie]

To find the porabola that passes through the three given points.

[jcarlson]

sorry double post

[jcarlson]

The general form of a quadratic function is given by:

 

[math]y(x)=Ax^{2}+Bx+C[/math]

 

where A, B, and C are constants.

 

We are given three points, [math]\{(x_1,y_1),(x_2,y_2),(x_3,y_3)\}[/math]. Our goal is to find A, B, and C in terms of [math]x_1, x_2, x_3, y_1, y_2,[/math] and [math]y_3[/math]. This will allow us to find a particular quadratic function that lies on all 3 points.

 

We begin by substituting the first point, [math](x_1,y_1)[/math], into the general equation for a quadratic function, and solving for A.

 

[math]

y_1=Ax_{1}^{2}+Bx_1+C

[/math]

 

[math]

Ax_{1}^{2}=Bx_1+C-y_1

[/math]

 

[math]

A=\frac{Bx_1+C-y_1}{x_{1}^{2}}

[/math]

 

Now we substitute [math](x_2,y_2)[/math], this time solving for B.

 

[math]

y_2=Ax_{2}^{2}+Bx_2+C

[/math]

 

[math]

Bx_2=y_2-Ax_{2}^{2}-C

[/math]

 

[math]

B=\frac{y_2-Ax_{2}^{2}-C}{x_2}

[/math]

 

Last, we substitute [math](x_3,y_3)[/math], and solve for C.

 

[math]

y_3=Ax_{3}^{2}+Bx_3+C

[/math]

 

[math]

C=y_3-Ax_{3}^{2}-Bx_3

[/math]

 

Now we substitute the equation for C into the equation for B.

 

[math]

B=\frac{y_2-Ax_{2}^{2}-y_3+Ax_{3}^{2}+Bx_3}{x_2}

[/math]

 

[math]

B=\frac{y_2-y_3+A(x_{3}^{2}-x_{2}^{2})+Bx_3}{x_2}

[/math]

 

[math]

Bx_2-Bx_3=y_2-y_3+A(x_{3}^{2}-x_{2}^{2})

[/math]

 

[math]

B=\frac{y_2-y_3+A(x_{3}^{2}-x_{2}^{2})}{x_2-x_3}

[/math]

 

Now substitute the equation for C into A.

 

[math]

A=\frac{Bx_1+y_3-Ax_{3}^{2}-Bx_3-y_1}{x_{1}^{2}}

[/math]

 

[math]

Ax_{1}^{2}+Ax_{3}^{2}=B(x_1-x_3)+y_3-y_1

[/math]

 

[math]

A=\frac{B(x_1-x_3)+y_3-y_1}{x_{1}^{2}+x_{3}^{2}}

[/math]

 

Now B into A...

 

[math]

A=\frac{\frac{y_2-y_3+A(x_{3}^{2}-x_{2}^{2})}{x_2-x_3}(x_1-x_3)+y_3-y_1}{x_{1}^{2}+x_{3}^{2}}

[/math]

 

Simplifying:

 

[math]

A=\frac{(y_2-y_3)(x_1-x_3)+(y_3-y_1)(x_2-x_3)}{(x_1^2+x_2^2)(x_2-x_3)-(x_3^2-x_2^2)(x_1-x_2)}

[/math]

 

To find B, substitute the equation for A into the equation for B

 

[math]

B=\frac{y_2-y_3+\frac{(y_2-y_3)(x_1-x_3)+(y_3-y_1)(x_2-x_3)}{(x_1^2+x_2^2)(x_2-x_3)-(x_3^2-x_2^2)(x_1-x_2)}(x_{3}^{2}-x_{2}^{2})}{x_2-x_3}

[/math]

 

[math]

B=\frac{y_2-y_3}{x_2-x_3}-\frac{(x_3+x_2)(y_2-y_3)(x_1-x_3)+(x_3+x_2)(y_3-y_1)(x_2-x_3)}{(x_1^2+x_2^2)(x_2-x_3)-(x_3^2-x_2^2)(x_1-x_2)}

[/math]

 

Finally, to find C, substitute A and B into the equation for C.

 

[math]

C=y_3-\frac{y_2-y_3}{x_2-x_3}-[/math] [math][x_3^2(y_2-y_3)(x_1-x_3)+x_3^2(y_3-y_1)(x_2-x_3)[/math] [math]+x_3(x_3+x_2)(y_2-y_3)(x_1-x_3)+x_3(x_3+x_2)(y_3-y_1)(x_2-x_3)][/math] [math]/ [(x_1^2+x_2^2)(x_2-x_3)-(x_3^2-x_2^2)(x_1-x_2)][/math]

 

Now you have your 3 coefficients in terms of the 3 points given, and you should be able to find the equation of your parabola.

 

Also I'm pretty sure it will work with 3 points in a straight line as well. The coefficient A will turn out to be 0 and the function will reduce to [math]y(x)=Bx+C[/math]

[Algebracus]

The formula [math]y = ax^2 + bx + c[/math] is not a general formula for a parabola. Another formula is for instance [math]x = ay^2 + by + c[/math], and I will use these two formulas to show that given three points [math](x_0, y_0), (x_1, y_1), (x_2, y_2)[/math], there may be more than two parabolas which satisfy the points:

 

Let the points be (0,0), (-1,1) and (1,2).

 

y(x) = ax^2 + bx + c

y(0) = c = 0

y(1) = a + b + c = a + b = 2

y(-1) = a - b + c = a - b = 1

 

That is, [math]y = 1.5x^2 + 0.5x[/math]

 

x(y) = ay^2 + by + y

x(0) = c = 0

x(2) = 4a + 2b = 1 = 2(a + b) + 2a = -2 + 2a

x(1) = a + b = -1

 

That is, [math]x = 1.5y^2 - 2.5y[/math].

 

Needless to say, there may be even more parabolas satisfying these three points, that is, som skew parabolas.

[Algebracus]

The natural question to ask is: What is the smallest number [math]n[/math] so that given [math]n[/math] points in the plane, there is at most one parabola which satisfy the points?

 

Name this smallest number [math]N[/math]. I have already shown that [math] N > 3[/math], and it doesn't take much effort to show that [math]N > 4[/math]:

 

The two parabolas [math]y = x^2[/math] and [math]x = (y - 2)^2 - 2 = y^2 - 4y + 2[/math] have four points in common. This follows because the equation [math]x^4 - 4x^2 - x + 2 = 0 = (x + 1)(x - 2)(x^2 + x - 1)[/math] has four real solutions.

[Algebracus]

Now, I am going to show that [math]N = 5[/math]

 

Let some arbitrary parabola be given. We use a coordinate system having the y-axis as the symmetric axis of the parabola and origo as the intersection point of the y-axis and the parabola; the formula for the parabola can now be settled as [math]y = ax^2[/math]. The general formula for a parabola is [math]Ax^2 + By^2 + Cxy + Dx + Ey + F = 0[/math] , with some restrictions that is not problematic here. We are going to show that such a parabola can not have more than four points in common with the given parabola.

 

Points satisfying both parabolas are points satisfying the equation as follows: [math]Ax^2 + Ba^2x^4 + Cax^3 + Dx + Eax^2 + F = 0[/math]. This is a polynomial equation of degree 4, and it has at most 4 different real solutions, that is, the two parabolas have at most 4 points in common; [math]N \leq 5[/math]. Since [math]N > 4[/math], [math]N = 5[/math].

 

I think a modified procedure can be used to prove that [math]N \leq 9[/math] for all conics. Then, we can show by a simple example that [math]N = 9[/math] for hyperbolas, and it is also easily proved that [math]N = 3[/math] for circles, [math]N = 2[/math] for lines and [math]N = 1[/math] for points. I think [math]N = 5[/math] for ellipses, but have not proved it yet. The proof is probably rather trivial.

[BigMoosie]

jcarlson, thankyou for that, it is exactly what I was after. I managed to simplify the formulas to this:

 

[math]a = \frac{\frac{y_0-y_1}{x_1-x_0}+\frac{y_1-y_2}{x_1-x_2}}{x_2-x_0}[/math]

 

[math]b = \frac{y_0-y_1}{x_0-x_1} - a(x_0+x_1)[/math]

 

[math]c = y_0 - x_0(ax_0+b)[/math]

 

I will solve for a quartic and see if I can make a general procedure for any polygon.

 

If you have Firefox 1.5 or Safari 1.3 you can see a little interactive example I made: http://www.random.abrahamjoffe.com.au/public/JavaScripts/quadratic.htm

 

Algebracus, that is very interesting though unfortunately does not relate to my problem as I am only after functions of x,

[BigMoosie]

It seems Newton beat me to it (is there anything that guy didnt do?). Here is an article explaining his method: http://en.wikipedia.org/wiki/Newton_polynomial. I have created an example similar to the one above but for any polynomial (once again, only Firefox 1.5 or Safari 1.3): http://www.random.abrahamjoffe.com.au/public/JavaScripts/canvas/interpolation.htm

[Algebracus]

I don't agree with you when you are saying that my replies don't relate to your problem the way you formulated it firstly. Just look at your first post in the thread:

 

If I am given 3 points I am sure (but cannot prove) that there will be only 1 porabola that can satisfy all 3 of them.

 

I have shown that you were wrong and that the actual number is 5, not 3. Since the result is wrong, your problem is not interesting, unless you are talking about representing parabolas as functions of x. If you assumed this restriction, you should have mentioned it in your first post! On the other hand, circles doesn't satisfy this assumption; they can't be represented by a single function f(x). A parabola satisfying [math]y^2 = x[/math] isn't worse than a circle satisfying [math]y^2 = 1 - x^2[/math]. So, why did you mention circles in your first post?

[BigMoosie]

I appologise for misleading you Algebebracus, it was not my intention. You are absolutely correct that I was not specific enough and your solution is accurate for the interperated problem. Now that you mention it I do see that mentioning circles was pretty pointless too and only made the confusion worse. I normally view polynomials as unvaried and didnt see the ambiguity.

[woelen]

jcarlson' date=' thankyou for that, it is exactly what I was after. I managed to simplify the formulas to this:

 

[math']a = \frac{\frac{y_0-y_1}{x_1-x_0}+\frac{y_1-y_2}{x_1-x_2}}{x_2-x_0}[/math]

 

[math]b = \frac{y_0-y_1}{x_0-x_1} - a(x_0+x_1)[/math]

 

[math]c = y_0 - x_0(ax_0+b)[/math]

 

I will solve for a quartic and see if I can make a general procedure for any polygon.

Polygon? Or do you mean univariate polynomial y = P(x)?

 

It simply boils down to solving a non-homogeneous set of linear equations Ac=b. Here the vector c is the vector of polynomial coefficients, the matrix A is built up of all powers of x and the vector b is built up of all values of y.

 

Keep in mind though, that in general the matrix A can become very ill-conditioned for a large real set of points i from 1 to N, {(xi, yi)}. In numerical solving this may give big troubles, even for moderate degrees of the polynomial (e.g. degree equal to 20 is at the border for standard IEEE 64 bit precision, C's double).

[BigMoosie]

Yes polynomial, thanks for fixing the typo.

I'm sorry but I do not know anything about matrixes yet, what would be a good starting point to learn?

[woelen]

Yes polynomial' date=' thanks for fixing the typo.

I'm sorry but I do not know anything about matrixes yet, what would be a good starting point to learn?[/quote']

A nice introductory text, easy to understand, is the following:

 

http://joshua.smcvt.edu/linearalgebra/

 

It really is worth the effort. If you understand linear algebra and matrix theory, then your problem of polynomial curve fitting becomes really trivial (except possibly from the numerical point of view due to round-off noise, but that is another matter). You will see that many problems can be formulated and solved easily and elegantly with the theory of linear algebra at hand.