Given two points, it is easy to find the equation of a line between them. But how difficult is it to fit a parabola to three arbitrary points, or a cubic to four, etc.?
First I’ll consider a cold-blooded way to do this, then a recursive method.
Suppose you want to fit an -degree polynomial perfectly through points,
You know the polynomial will have the form
Plugging in the values of the and coordinates, we get linear equations in the variables .
which we can write in matrix form as
We can solve the matrix equation using Gaussian elimination. This takes arithmetic operations1.
For the next method, begin by considering three points to be fit by a quadratic. This would be quite simple if you knew the zeroes of the quadratic. Any quadratic with zeroes at and is of the form
The freedom in lets us fit an arbitrary third point by setting
So the full quadratic is
But this only works for special sets of points in which two coordinates are zero. However, we can use it as a starting point to fit a curve through any three points. The idea is to find the line that goes through the first two points. Subtract that from all three coordinates, and now you’ve reduced it too the previously-solved problem, with two points zero.
and plugging into the solution to the quadratic with zeroes gives
We can use the result to solve an arbitrary cubic in the same way. First, find the solution when three of four points are zeroes. Then go back to the four arbitrary points and fit a quadratic through the first three. Subtract that quadratic from all four points. You’ve got three zeroes and a fourth arbitrary point. Fit that with the solution from the first step, and add the quadratic back in to complete the solution.
Similarly, we could extend the method to fit points with an degree polynomial.
Let’s count the number of operations to implement this method. The first step, in which we solve the specialized problem with a bunch of zeroes, involves multiplying numbers and doing one division, because
The second step, fitting the first points to a degree polynomial, takes an unknown number of operations, since we aren’t done our count yet.
The third step, subtracting the degree polynomial from each of the points, takes operations.
The fourth step, substituting the modified points into the formula from step 1, takes operations, too.
That’s it – then we’re done. So overall, fitting with a degree polynomial takes more steps than fitting with a degree polynomial. That implies that the overall procedure, including recursion, is , an improvement over Gaussian elimination.
1) Strang, Gilbert Linear Algebra and Its Applications, 2nd ed.
pp. 4-5 explains the count for Gaussian elimination.