# Lagrange interpolation ?

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

## 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 on other sites
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...)

##### Share on other sites
Quote:
 Original post by moucoulinI'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 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 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 on other sites
1000*1000

A gauss jordan should still do. It all depends.

What is the context of the problem?

##### 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 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 on other sites
Quote:
 Original post by moucoulin1000*1000A 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 on other sites
Quote:
 Original post by moucoulinBy 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 ?

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 15
• 14
• 46
• ### Forum Statistics

• Total Topics
634061
• Total Posts
3015301
×