So a few weeks ago I wrote about an algorithm for finding a polynomial that hit 3-points. But the mathematician in me inevitably asked “what about more points?” To do this, we just need to expand the algorithm. Instead of having 3 equations and 3 unknowns, we have n equations and n unknowns—just more linear algebra.
We start with the 3-point equation. Here we have three known points . From this we get the following matrix in order to get a 2nd degree polynomial:
through are the coefficients for the polynomial. The pattern is such that we can rewrite this expression like this:
From there, we can derive the n-point equation by following the pattern:
Again, to solve this equation we can use Cramer's rule and the determinant function I wrote.
Below is the result. You can click and drag any of the black circle points to move it. The graph will update and find a polynomial that will hit all of these points.
The guts of the system is the coefficient calculation function. Note that there isn't much needed. A base matrix is constructed, and the base serves to construct the replaced column matrices. The determinant of each of these matrices is taken and the coefficients calculated.
The script is limited to 7 points although more are possible. The number of multiplications when adding an extra point grows at a rate of . For 3 points, that's 60 multiplications; and 4 points, 260; and at 7 point, 80,696. By 9 points, over a 7 million multiplications are needed, and by 12, over 12 billion. Note that these are all floating-point multiplications and done in with a scripting language. PHP isn't a bad language, nor is the Micro Dragon a bad web server, but asking the setup for a heavy-duty workload of more then 7 points is a bit much.