This is Words and Buttons Online — a collection of interactive #tutorials, #demos, and #quizzes about #mathematics, #algorithms and #programming.
This is a minimal interpolating polynomial (in arctangent scale, yes). For k points, if has k-1 degree, and it, of course, runs through all the points by definition of interpolation.
↑ This plot is interactive
This polynomial can be obtained by several ways, and Lagrange interpolation is one of them. Lagrange polynomial is not a polynomial with some specific “Lagrangian” properties, it's only the way the interpolating function is calculated.
And this is the way.
| L(x) = | k | yi gi(x) |
| Σ | ||
| i = 1 |
The functions g(x) are the basis polynomials. They are defined for every i ∈ 1..k. Here they are.
| gi(x) = | k |
|
||
| Π | ||||
| j = 1, j ≠ i |
Ok, but this thing doesn't even look like a polynomial. And how come it's interpolating?
The interpolant is a sum of products of linear functions. Each function is:
| x - xj |
| xi - xj |
At first, it might look like a rational function but xi - xj is not a function of x, it's just a number. In other words:
| x - xj | = | x | - | xj | , where cij = xi - xj |
| xi - xj | cij | cij |
And this one is definitely linear.
When x = xj this linear function is 0 because xj - xj = 0.
And when x = xi, the function is 1 for every xj apart from when xj = xi since xi - xj = xi - xj.
The product of these linear functions is the basis polynomial. It is defined for every i, and for every i, it multiplies all the linear functions defined for every j except for when xj = xi.
So when we compute a basis polynomial determined for i in xi we get 1, since all the linear functions result in 1.
And when we compute the very same basis polynomial for every other xj we get 0 since one of the linear functions results in 0.
E. g., the basis polynomial for the last point from the plot looks like this.
We should only multiply it by yi to make it go through the point (xi, yi).
Now adding these basis polynomials together make them go through all the points since they don't mess up with each other. Every basis polynomial is 0 in all the xj except for xi so when you sum them up, there is no interference.
Ok but why is it a polynomial? Well, the linear function is a first-degree polynomial. You multiply k - 1 of them, you get k - 1 degree basis polynomial. And, of course, summing up a few basis polynomials of k - 1 degree can only result in a polynomial too.
Personally, I never used a Lagrange polynomial in practice. When I need an interpolating polynomial, I get one by solving a Vandermonde equation.
But Lagrange polynomial introduces a very important idea of a basis function. You can analyze your source function into basis functions, and you can synthesize a new function, with the properties you want, from that. Basis splines are built upon this idea.
With Lagrange polynomial, this idea is almost obscenely simple. It's all sums and products, ones and zeroes.
| Index #mathematics #tutorials | ← there's more. |
+ Github & RSS |