Polynomial Interpolation and Least Square Approximation
For a list of points (xi, yi), a polynomial is determined that is defined by these points.
n+1 points, each with different x coordinates, uniquely determine an interpolation polynomial of degree n.
So you first have to determine the number of support points. You can also specify the desired polynomial degree.
If no polynomial degree is specified, a polynomial is determined according to the number of points by interpolation.
If the specified polynomial degree at n points is smaller than n-1, a balancing polynomial in the sense of the least squares method is determined by approximation.
Unlike interpolation, not all points have to have different x coordinates. It is sufficient if at least g+1 points have different x coordinates at polynomial degree g.
The points (xi, yi) can be manipulated using the table or by clicking and dragging with the mouse.
Interpolation
To determine the coefficients of a polynomial of degree n of the form
anxn + an-1xn-1 + ... + a2x2 + a1x + a0
n+1 equations are needed.
For a system of n points Pi(xi/yi), n equations can be created:
an-1x1n-1 + ... + a2x12 + a1x1 + a0 = y1
an-1x2n-1 + ... + a2x22 + a1x2 + a0 = y2
...
an-1xnn-1 + ... + a2xn2 + a1xn + a0 = yn
or in matrix notation:
X a = y
The n×n matrix X contains the different x-coordinates in all powers from 0 to n-1.
The vector a contains the desired coefficients ai.
If the x-coordinates of all n points are all distinct, the matrix X is regular and the system of equations can be uniquely solved.
The solution vector a then contains the coefficients of the interpolation polynomial of degree n-1.
Example:
The following three points are given: P1(-1/3), P2(0/1) and P3(1/3).
The system of equations is then:
1·a2 - 1·a1 + 1·a0 = 3
0·a2 + 0·a1 + 1·a0 = 1
1·a2 + 1·a1 + 1·a0 = 3
with the solution:
a2 = 2, a1 = 0, a0 = 1
The interpolation polynomial is therefore:
2·x2 + 1
Approximation
If you have more points available than you need for interpolating a polynomial,
you can proceed formally analogously when setting up the equations.
However, the matrix X is then no longer square. It has more rows than columns.
The system of equations is overdetermined.
To determine the solution, you multiply both sides of the system of equations from the left by XT. This gives:
XTX a = XTy.
The resulting coefficient matrix XTX is now symmetric and regular if the points used
have at least as many different x-coordinate as there are unknown polynomial coefficients to be determined in a.
The solution to the system of equations then yields coefficients of a polynomial that approximately follows the path of the points.
Example:
Given the three points P1(0/0), P2(1/1) and P3(2/4).
We are looking for a straight line that can be approximately determined by these points.
This initially yields the following 3 equations:
0·a1 + 1·a0 = 0
1·a1 + 1·a0 = 1
2·a1 + 1·a0 = 4
The system of equations is then:
5·a1 + 3·a0 = 9
3·a1 + 3·a0 = 5
with solution:
a1 = 2, a0 = -1/3
The approximation polynomial is therefore:
2·x - 1/3.
more JavaScript applications