Today I mentioned something about interpolation but breezed over some of the algebra intensive parts because I know that for the most part you're not all enthusiastic about Euclid (that alliteration is intentional, I also considered "giddy about Gauss" and "pleased with Pythagoras") I feel I've done the world a disservice, so here's a post pretty much no one will read.
This is called Lagrangian Interpolation, named after some guy Lagrange. Given any number of points, you can create (find?) a polynomial that describes it. For the sake of simplicity, I'll use just three points, but it'll be really obvious how you can expand to any n+1 number of points.
Consider three points, for the sake of avoiding subscript we'll call them (a,A),(b,B) and (c,C). This is just like your high school algebra class, the first number (the lowercase letter) tells you how far over in the x (horizontal) direction and the second (capital) tells you how far up in the y (vertical). It's like Battleship. So if (a,A) = (3,4) you'd go over three and up four (grab some graph paper and play along).
Now here's the formula you've all been waiting for:
(I’m going through formatting hell right now, so please bear with me).
With this equation, if x = a, both the second and third terms reduce to zero, and the first term reduces to A:
So the curve passes through the point (a,A) (and (b,B) and (c,C)). I feel like it might be a little confusing at this point, but it’s difficult to explain without a white board, so deal with it.
Stop! Example time. (like Hammer time, but without baggy pants). Consider the points (1,1), (2,3) and (5,8). Ultimately our goal is to find the equation for a curve that passes though all of these points. We can use Lagrange interpolation to find the equation:
And if we really wanted to (and we really do) we could reduce it even further:
Which actually isn’t too intimidating. Hooray for algebra.
This connects directly to the complexity stuff we were talking about quite nicely. You can see how lengthy the equation is for just three points, and it just gets obnoxiously bigger as you add more and more points.
For 7 points: (1,1),(2,8),(3,2),(4,7),(5,0),(6,6),(7,0) we get this crazy graph.
This can be described by the offensive equation:
-0.2681x6 + 6.4208x5 - 60.743x4 + 287.9x3 - 712.49x2 + 858.18x – 378
The more and more “random” points we add, the worse and worse our descriptive formula gets. At this point, it’s obvious (I hope) that the descriptive equation for random points is just as complex as the bunch of points themselves.
If you’ve gotten this far, leave a comment or something so I can get a feel for whether or not there’s a call for something like this.
-Nick
Nick,
ReplyDeleteyou are quite good at making this understandable. I was a little lost at the beginning, but by the end it made total sense. It is helpful to me to learn the algebra behind some of the things we discuss, both because I am lacking in that field and because it gives me another way to think about them. Keep posting math!
Thank you for posting this I like it.
ReplyDeletePerhaps my algebra is wrong but I got a different result when I tried to reduce the example equation.
here's what I got: (-x²+27x-14)/12
what did I do wrong?
Yeah, you're right.
ReplyDeleteI actually just cheated and make Excel do the actual math. Yeah, I know I suck. I figured the theory was actually more important than the process. When I copied it down, I copied it down wrong.
Nice catch, I'll go about fixing it now.