## Friday, December 21, 2012

### Inverse polynomial approximation

Consider the limiting process of using the Simpson's rule to approximate say e^x from x=0..5 using n rectangles:
n=2    165.11927912116
n=4    149.09326952253
n=6    147.77767796066
n=8    147.53254079859
n=10  147.46285985231

Intuitively you can imagine the graph going to a limit as n goes to infinity in this process, it will just get closer and closer from above to the real value of e^x over the interval.

But  if you try to model this process with polynomial interpolation it does very poorly.

See it actually tends towards infinity after the part where it is forced to match the values given instead of a limit.

I found that if you instead solve for what I'm calling an inverse polynomial, that is of the form:
you can get much closer. I'll go into detail how this is done in a minute but the polynomial you end up with using the data in the example I first mentioned is:
The graph of this looks like:
This looks a lot more like it models the process. In fact the next couple values of this inverse polynomial at x=10 and x=12 are:
147.4628599
147.4349611
so it is approaching something the actual limit of the process that is the integral of e^x for x=0..5 is:
147.4131591
So by modeling the algorithm and then looking ahead a few values we could "see" closer to the limit than actually running the algorithm for higher values of n. Which for a very difficult algorithm would be very handy.

Now the way I solve for this polynomial is consider this matrix where x, x+2, x+4, etc. are the given values of the function for a certain value of x:
In my case I evaluate the above matrix at x=2 and that gives this to solve:

Solving these 5 equations for the 5 variables gives the inverse polynomial coefficents.
Then these are plugged into:
to get:

I think this process should work well to model functions that tend towards a limit, for instance many algorithms.