Browse Search Popular Register Upload Rules User list Login:
Search:
Polynomic Interpolation

Image:
screenshot of the scene

Author: FRA32

Group: Technical

Filesize: 44.44 kB

Date added: 2016-02-24

Rating: 6.3

Downloads: 1023

Views: 446

Comments: 8

Ratings: 4

Times favored: 0

Made with: Algodoo v2.1.0

Tags:

Scene tag

This scene shows a mathematic method I am currently working with in Real Life, the Interpolation.
Interpolation is a mathematic way of generating a function between a set of given points in order to find the inbetween points. This scene shows a primitive version of the interpolation, the Polynomic interpolation. What it does is basically taking all given points(in this case 10) and connecting them with 1 single polynom of grade n-1(in this case 10-1, or 9). This, in other words, is a formula that looks roughly like this: p(x)=a*x^9+b*x^8+c*x^7+d*x^6+e*x^5+f*x^4+g*x^3+h*x^2+i*x^1+j-
.
To calculate this formula, a placeholder formula is used, the interpolation equation. It looks like this:
p(x)=sum{i=0 to n}(prod{j=0 to n | j != i}((x-xj)/(xi-xj)) * yi)
the sum is the typical sigma sign, and prod is Capital Pi, a counterpart of sigma that multiplies all values instead of summing them. The equations core is the (x-xj)/(xi-xj) equation. It's a chain part of a polynom(hence the prod sign), with the special attribute that:
if x = xj, then the whole product equation turns 0 since (xj-xj)/(xi-xj) = 0/(xi-xj)=0 and 0*x*y*z = 0
if x = xi, then the whole product equation turns 1 since (xi-xj)/(xi-xj) = (a+b)/(a+b) = k/k = 1 and 1*1*1*1 = 1
if x lies inbetween all points, the product equation will calculate different multiples of x and multiply them with each other, resulting in a x*x*x fashion.

The interpolated function is graphed in this scene, and you can place the points as you like, as long as they are not on the same x coordinate and stay in 10m distance to the scenes origin (the scene only graphes from -15<x<15)
Last edited at 2016/07/03 21:47:36 by FRA32
Please log in to rate this scene
edit
Similar scenes
Title: Moving Average, Average and List Interpolation Scripts!
Rating: 5.25
Filesize: 27.7 kB
Downloads: 237
Comments: 3
Ratings: 2
Date added: 2024/04/08 15:59:11
Made with: Algodoo v2.1.0
Rating: rated 5.3
download
Title: Beziércurve-Drawer
Rating: 5
Filesize: 6.8 kB
Downloads: 317
Comments: 4
Ratings: 1
Date added: 2015/12/12 18:58:25
Made with: Algodoo v2.1.0
Rating: rated 5
download
Title: Cubic Spline Curve Calculator
Rating: 7.0834
Filesize: 82.66 kB
Downloads: 3608
Comments: 9
Ratings: 6
Date added: 2022/07/17 19:00:16
Made with: Algodoo v2.1.0
Rating: rated 7.1
download
nope, still doesn't work
Oh yes it does! It has a delay but at least it doesn't start from the 9th point lmao
Last edited at 2016/02/24 19:08:54 by The Linkage
huh, should work. Wait, I think it's this cursed algodoo configuration glitch.
Some scene messed your configurations, making your algodoo unable to read for(x,(i)=>{}) functions. That may be why it wont work, since it does work for me
Ah lol, alrighty then. It takes a while since the point interpolates, starting from -15, and needs to reach the first point before anything becomes visible xD
Is there any way to make it stop after it reaches the last point? it gets very hign and then resets itself
sure. Open the script menu of the little red blurry ball, and then, replace the whole _x> 15 ? {}: {} with:
_x > _px(10)+0.5 ? {sim.running = false} : {}
Last edited at 2016/02/24 19:14:36 by FRA32
Please correct me if I am wrong, but in a "linear" interpolation, you basically connect-the-dots with interpolated points. But in a polynomial interpolation, the interpolated points still connect-the-dots, but not with straight lines. The new data points scribe either a sin or cos pattern, but they should "hug" the original data points rather closely. I noticed in this scene that the new data scribes a sinusoidal curve that swings quite far above and below the original data points, which, to me, doesn't seem quite right. Please explain.....

BTW - As I've mentioned many times in the past, although I love math and the things that can be accomplished with it, my math skills are rather weak. So, if I said anything above which sounds "dumb" or doesn't make sense mathematically, please excuse my ignorance. :lol:
Last edited at 2017/03/04 16:04:27 by Xray
The reason why the graph of this interpolation oszillates so irregularely, compared to a sine wave, is because this is'nt actually a sine or cosine function. Rather, this is a polynome (hence the name Polynomic interpolation). A polynome is any function made from powers of X, i.e: Y=2X+(3-X)*(X+1)+(X^3)/4...
The most common polynome is Y=X^2, aka. the parabola. This interpolation however forms a polynome of 9th grade, meaning the hightest power of X is the 9th power. It is constructed by puzzling together multiple polynomes of the same grade, which all hit only 1 point and hit 0 on all others instead, thus meaning that for each point, exactly 1 part polynome hits it, thus when adding all together, the complete interpolation graph hits all points. The way the parts only hit only 1 point is quite simple if one can decipher the variable conjunctions, which often takes a while on the first to third time:
Given you want to calculate the part polynome that hits the 3rd Points, P3. To construct it, use this chain of operations:
Py*(P1x-X)/(P1x-P3x)*(P2x-X)/(P2x-P3x)­*(P4x-X)/(P4x-P3x)*(P5x-X)/(P5x-P3X)...
What this basically does is, whenever X is the same as one of the Px's, for example x=P1x, the paranthesis containing (P1x-x) turn 0, thus multiplying the rest of the function with 0, and thus hitting 0 on that X value. Should you however have x=P3x, then we will hit 1*Py, since we dont have an element stating (P3x-x) which would turn all into 0. Instead all parantheses before the / are identical to each paranthesis after the /, causing every element to return 1. Multiply by Py, and you hit Py at Px, meaning you just hit that point.
All that remains is doing the same for the other 9 points and adding all parts. Since we dont multiply them with each other, the grade always remains 9(Not 10 since the paranthesis element of the hit point is missing). This also means that, just like in linear interpolation, the function perfectly hits each point, instead of just "hugging" it.:lol: