Sign in to follow this  
cpp_boy

Lagrange interpolation ?

Recommended Posts

cpp_boy    100
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
moucoulin    144
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
cpp_boy    100
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
moucoulin    144
|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
cpp_boy    100
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
lonesock    807
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
moucoulin    144
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
cpp_boy    100
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
cpp_boy    100
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
cpp_boy    100
Quote:
Original post by lonesock
maybe look into cubic splines?



I'm aware of cubic splines. Those will be to hard to program. I almost complited my lagrange, so I'm to lazy to switch to something else.

Thanks a lot everybody, you were VERY usefull ;)
I rated you all as "Extrimly usefull" ;)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this