cpp_boy 100 Report post Posted June 29, 2005 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] 0 Share this post Link to post Share on other sites
moucoulin 144 Report post Posted June 29, 2005 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... 0 Share this post Link to post Share on other sites
cpp_boy 100 Report post Posted June 29, 2005 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 1x2^2 x2 1x3^2 x3 1 0 Share this post Link to post Share on other sites
moucoulin 144 Report post Posted June 29, 2005 |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. 0 Share this post Link to post Share on other sites
cpp_boy 100 Report post Posted June 29, 2005 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). 0 Share this post Link to post Share on other sites
moucoulin 144 Report post Posted June 29, 2005 1000*1000A gauss jordan should still do. It all depends.What is the context of the problem? 0 Share this post Link to post Share on other sites
lonesock 807 Report post Posted June 29, 2005 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 0 Share this post Link to post Share on other sites
moucoulin 144 Report post Posted June 29, 2005 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. 0 Share this post Link to post Share on other sites
cpp_boy 100 Report post Posted June 29, 2005 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 :( 0 Share this post Link to post Share on other sites
cpp_boy 100 Report post Posted June 29, 2005 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 ? 0 Share this post Link to post Share on other sites
lonesock 807 Report post Posted June 29, 2005 maybe look into cubic splines? 0 Share this post Link to post Share on other sites
cpp_boy 100 Report post Posted June 30, 2005 Quote:Original post by lonesockmaybe 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" ;) 0 Share this post Link to post Share on other sites