This thread brought back some old memories of when I discovered my own interpolation formulas that generate polynomials and exponential equations for sets of points. Since the topic is about finding a polynomial for a given set of points, I'll share with you all the methods that I discovered myself along with the methods that I later learned as a result of researching my own. Interpolating [math]F(x)[/math] for a Set of Points First, we need to define the function [math]S(i,j)[/math] that gives us the subscripts for [math]x[/math] and [math]y[/math] that is used by the interpolating formula to derive the polynomial. You'll notice that this function has two inputs, [math]i[/math] and [math]j[/math]. These represent the summation and product indices used by [math]\Sigma[/math] and [math]\Pi[/math]. [math]S(i,j)=j-\frac{1}{2}\left((-1)^{\frac{\left\vert j-i \right\vert+j-i}{2}}+(-1)^{\frac{\left\vert j-i+1 \right\vert+j-i+1}{2}}\right)+1[/math] When we examine the outputs of [math]S[/math] by holding [math]i[/math] constant allowing [math]j[/math] to be the variable, we see that [math]S[/math] produces a linear sequence that skips [math]i[/math] in the sequence. [math]i=1,\ j\Rightarrow \{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...\}[/math] [math]i=2,\ j\Rightarrow \{1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...\}[/math] [math]i=3,\ j\Rightarrow \{1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...\}[/math] [math]i=4,\ j\Rightarrow \{1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...\}[/math] [math]i=5,\ j\Rightarrow \{1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...\}[/math] I discovered this equation back in 1999 right after I graduated high school and was attending OU. I was interested in interpolation because when I was in high school, I discovered Newton's interpolation formula on my own and extended it to account for increasing summations of f(x). I used the knowledge gained from working that problem to create an exponential interpolation formula that works like the polynomial version except it produces an exponential equation and accounts for increasing products of the interpolated function.
However, these formulas didn't work for any set of points. They had to be ordered. So, I started working the numbers and discovered the equation that interpolates any given set of points. [math]S(i,j)=j-\frac{1}{2}\left((-1)^{\frac{\left\vert j-i \right\vert+j-i}{2}}+(-1)^{\frac{\left\vert j-i+1 \right\vert+j-i+1}{2}}\right)+1[/math] [math]\mathcal{D}(x)=\sum_{i=1}^n \left(y_i(x_i-x+1)\prod_{j=1}^{n-1} \left(\frac{x-x_{S(i,j)}}{x_i-x_{S(i,j)}}\right)\right)[/math] The resulting polynomials always have a degree that is equal to the number of points in the set. So, my equation does not produce the lowest degree polynomial that interpolates the set of points. However, a few years later while taking Numerical Analysis at OU, I learned that my equation was actually a variation of an already known interpolation formula called Lagrange interpolation that produces the polynomial of least degree that interpolates the set of points. Interpolating [math]F(x)[/math] for a Set of Points using Lagrange Interpolation My equation was so close to Lagrange Interpolation that I only had to remove a single factor, [math](x_i-x+1)[/math], to make my equation equal to his. [math]\mathcal{L}(x)=\sum_{i=1}^n \left(y_i\prod_{j=1}^{n-1} \left(\frac{x-x_{S(i,j)}}{x_i-x_{S(i,j)}}\right)\right)[/math]
You can only imagine my amazement when I seen my equation staring back at me and was not only simplified, but also did something unique by producing the polynomial of least degree that interpolates the set of points. Well, I amazed myself once again when I discovered that the method I used to extend Newton's interpolation formula to exponential equations also works for Lagrange interpolation! I love mathematics!!!
Extending Lagrange Interpolation to Exponential Functions for a Set of Points
The work I did in high school to extend Newton interpolation to exponential functions also works for Lagrange interpolation. If we think of polynomials as summing the terms [math]F_{\sigma}(x)[/math] and exponentials as multiplying the terms [math]F_{\pi}(x)[/math], then we can easily extend interpolation formulas from polynomials to exponential functions.
Polynomial / Summation
[math]\mathcal{L}_{\sigma}(x)=\sum_{i=1}^n \left(y_i\prod_{j=1}^{n-1} \left(\frac{x-x_{S(i,j)}}{x_i-x_{S(i,j)}}\right)\right)[/math]
Exponential / Multiplication
[math]\mathcal{L}_{\pi}(x)=\prod_{i=1}^n \left(y_{i}^{\prod_{j=1}^{n-1} \left(\frac{x-x_{S(i,j)}}{x_i-x_{S(i,j)}}\right)}\right)[/math]
As we can see, sigma [math]\Sigma[/math] is replaced with [math]\Pi[/math] to multiply the terms. Then, instead of multiplying [math]y_i[/math] by the product series, we apply the exponent operation.
Using Mathematica to Explore my Method and Lagrange's
If you made it all the way to the end of this post, I have attached a Mathematica 7 file so you can play around with my method and Lagrange's. Enjoy!!!
Interpolation.zip