Jump to content
  • Advertisement
Sign in to follow this  
cpp_boy

Lagrange interpolation ?

This topic is 4860 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello. I'm writing method for lagrange interpolation. The big problem is that I dont know how to get interpolating polynomial's coefficients (a, b, c ...). For example, when you have three points, and you want to pass through them lagrange interpolation, finally you get interpolant of the form : P(x) = ax^2 + bx +c . The question is, how do I get those a,b,c coefficients (or "n" coefficients for "n-1" degree interpolant). Thanks in advance. [Edited by - cpp_boy on June 29, 2005 2:41:34 PM]

Share this post


Link to post
Share on other sites
Advertisement
I'm a bit surprised by the forms of the lagrangian polynoms, usually looking more like a product of divided differences but whatsoever points coordinates are solutions of the polynomial equations so there is a linear system to solve.

For example, interpolation using second order simple polynoms, three points (x1,y1), (x2,y2) and (x3,y3)

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

y2= a *x2^2+b*x2+c


y3= a *x3^2+b*x3+c



(a,b,c) is the vector of unknowns.


(a,b,c)= M^(-1) *(y1,y2,y3)

M: matrix formed with (x1^2...)

If it is readable...

Share this post


Link to post
Share on other sites
Quote:
Original post by moucoulin
I'm a bit surprised by the forms of the lagrangian polynoms, usually looking more like a product of divided differences but whatsoever points coordinates are solutions of the polynomial equations so there is a linear system to solve.

For example, interpolation using second order simple polynoms, three points (x1,y1), (x2,y2) and (x3,y3)

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

y2= a *x2^2+b*x2+c


y3= a *x3^2+b*x3+c



(a,b,c) is the vector of unknowns.


(a,b,c)= M^(-1) *(y1,y2,y3)

M: matrix formed with (x1^2...)

If it is readable...


I"m interested only in your last 4 lines. Can you please be a little more detailed. I dont understand how M looks. Do you mean
x1^2 x1 1
x2^2 x2 1
x3^2 x3 1

Share this post


Link to post
Share on other sites
|y1| |x1^2 x1 1| |a|
|y2|=|x2^2 x2 1| |b|
|y3| |x3^2 x3 1| |c|


It might be clearer like that, knowing that (a, b,c) is the unknow vector.

Solve the system to get it.

Share this post


Link to post
Share on other sites
Quote:
Original post by moucoulin
|y1| |x1^2 x1 1| |a|
|y2|=|x2^2 x2 1| |b|
|y3| |x3^2 x3 1| |c|


It might be clearer like that, knowing that (a, b,c) is the unknow vector.

Solve the system to get it.


First of all, thanks a lot. The only thing I dont have here is numeric algorithm for finding inverse matrix of M. Can you name one that is ok for my problem (I'm working with very big polynomials, 1000 degree and more).

Share this post


Link to post
Share on other sites
MathWorld is a good resource. Basically, using Lagrange interpolation polynomials, you come up with one polynomial per control point:
y(x) = Y0*PolyX0(x) + Y1*PolyX1(x)...etc.

To reduce all that down to a single function of x would require lots of combining.

Just some observations:

- single variable polynomials above 6th order are rarely useful in finite-elements (which is the only place I've used them). They go through your control-points, but have to do some wicked gyrations over the rest of the range.

- for very large polynomials, evaluating them in the form:
(((a*x + b)*x + c) * x) + d ... etc.
will be faster than:
a*x*x*x + b*x*x + c*x + d

Share this post


Link to post
Share on other sites
By the way, it might be better to look for other kind of interpolation, real lagrangian, or something else to reduce the degrees and hence the size of the matrix.

Share this post


Link to post
Share on other sites
Quote:
Original post by moucoulin
1000*1000

A gauss jordan should still do. It all depends.

What is the context of the problem?


I'm coding some traffic simulation ( academic project in cooporetion with INTEL). I need those interpolants for functions like [number of accidents VS speed ],
[ sensor location VS percentege of prevented accidents ]

and tens of other function needed to be interpolated. Actualy, what I need is done exactly by "polyfit" function in MATLAB. But I must use only java, so I'm must do everything manually :(

Share this post


Link to post
Share on other sites
Quote:
Original post by moucoulin
By the way, it might be better to look for other kind of interpolation, real lagrangian, or something else to reduce the degrees and hence the size of the matrix.


I cannot reduce the degree because I must the polynimial to pass through all control points.

Of course, I can look at Bezier, Hermite or some other interpolations. As I see it, Lagrange is the simliest, and I dont need great accuracy. So lagrange is ok, right ?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!