Omnimaga
General Discussion => Other Discussions => Math and Science => Topic started by: Xeda112358 on October 28, 2018, 10:32:12 pm
-
Hi folks, I wanted to share a technique I came up with for evaluating sequential points of a polynomial, which is especially useful when you are drawing them. A naive approach would be evaluate the whole polynomial at each point, but the method I'll show you allows you to evaluate at a few points, and then for each subsequent point just use additions.
The basic premise is to use ##f(x)## as a starting point to get to ##f(x+1)##. For example, take ##f(x)=3+2x##. To get to ##f(x+1)##, all you have to do is add 2. Things get more complicated as you go to higher degree polynomials. For example, take ##f(x)=3+2x-3x^{2}+x^{3}##. Then to get to ##f(x+1)##, you need to add ##3x^{2}-3x##. However, you can go even further by finding how to get from ##3x^{2}-3x## to ##3(x+1)^{2}-3(x+1)##.
Now comes the theory.
Take ##f_{1}(x)=f(x+1)-f(x)## and ##f_{n+1}(x)=f_{n}(x+1)-f_{n}(x)##.
Then ##f(x+1)=f(x)+f_{1}(x)## and ##f_{n}(x+1)=f_{n}(x)+f_{n+1}(x)##.
##\begin{aligned}
f_{2}(x) &=f_{1}(x+1)-f_{1}(x),\\
&=(f(x+2)-f(x+1))-(f(x+1)-f(x)),\\
&=f(x+2)-2f(x+1)+f(x).
\end{aligned}##
##\begin{aligned}
f_{3}(x)&=f_{2}(x+1)-f_{2}(x),\\
&=(f(x+3)-2f(x+2)+f(x+1))-(f(x+2)-2f(x+1)+f(x)),\\
&=f(x+3)-3f(x+2)+3f(x+1))-f(x).
\end{aligned}##
And in general,
##f_{n}(x)=\sum_{k=0}^{n}{{n\choose k}(-1)^{k}f(x+n-k)}##
If you set ##x=0##:
##f_{n}(0)=\sum_{k=0}^{n}{{n\choose k}(-1)^{k}f(n-k)}##
So now let's take again, ##f(x)=3+2x-3x^{2}+x^{3}##.
##\begin{aligned}
f(0)&=3,\\
f_{1}(0)&=f(1)-f(0)&=0,\\
f_{2}(0)&=f(2)-2f(1)+f(0)&=0,\\
f_{3}(0)&=f(3)-3f(2)+3f(1)-f(0)&=6,\\
f_{k>3}(0)&=0.\\
\end{aligned}##
So what these values allow us to do, ##{3,0,0,6}##, is use a chain of additions to get the next value, instead of evaluating the cubic polynomial at each x:
##\begin{array}{rrrr}
[&3,&0,&0,&6]\\
[&3,&0,&6,&6]\\
[&3,&6,&12,&6]\\
[&9,&18,&18,&6]\\
[&27,&36,&24,&6]\\
[&63,&60,&30,&6]\\
[&123,&90,&36,&6]\\
[&213,&126,&42,&6]\\
...
\end{array}##
Basically, add the second element to the first, third element to the second, and fourth element to the third. The new value is the first. Repeat. So the next iteration would yield [213+126,126+42,42+6,6]=[339,168,48,6], and indeed, f(8)=339.
I'd like to apologise for how garbled this is, I'm really tired.
Also, you should note that for an n-th degree polynomial, you need to compute up to ##f_{n}(x)##, but everything after that is 0.
-
Dang. I’m gonna use this in my graphing program I think if i can get a handle on it.
-
For what it's worth, I did get it to work in TI-BASIC. My program only worked up to degree 8 polynomials (I could extend it; it was just a convenient size).
I'm on mobile atm and AFC, so I'll try to describe my code:
What I did is I computed Y1(Xmin+K∆X), for k from 0 to 8, storing them to a list, then I recombined starting from the end (the last element is a function of all previous elements and itself) applying that sum.
Then for efficiency, I clipped off any trailing zeros in L1.
I started plotting from Xmin to Xmax with step of ∆X:
For(X,Xmin,Xmax,∆X
Pt-On(X,L1(1
For(K,1,N-1
L1(K)+L1(K+1→L1(K
End
End
Note that it doesn't work well for non-polynomials like sine and cosine, but it can do rough estimates. I'm also sure it would fail at poles.
-
Nice. I hope that I will have the patience to write an equivalent in ICE for my grapher. Also, for what it's worth, I think in your example it was supposed to be :
f (x) = f (x+1) 3x2 + 3x
-
It is basically 3+2(x+1)-3(x+1)2+(x+1)3-(3+2x-3x2+x3) which should be 3x^2-3x (I hope).
-
f (x + 1) = 3 + 2(x + 1) - 3(x + 1)2 + (x + 1)3
f (x + 1) = 3 + 2x + 2 - 3(x2 + 2x + 1) + (x3 + 2x2 + x + x2 + 2x + 1)
f (x + 1) = (x3) + (-3x2 + 2x2 + x2) + (2x - 6x + x + 2x) + (3 + 2 - 3 + 1)
f (x + 1) = x3 - x + 3
it leaves -x, which + 3x = 2x.
I could be completely misunderstanding this though...
-
Your computation of f(x+1) is correct, but then you need to subtract f(x), so:
##
\begin{aligned}
f(x+1)-f(x)&=(x^{3}-x+3)-(x^{3}-3x^{2}+2x+3),\\
&=x^{3}-x+3-x^{3}+3x^{2}-2x-3,\\
&=-3x+3x^{2},\\
&=3x^{2}-3x.\\
\end{aligned}
##
-
Ah yes, I see now