Polynomial interpolation
In computer graphics, polynomials can be used to approximate complicated plane curves given a few specified points, for example the shapes of letters in typography.
This is usually done with Bézier curves, which are a simple generalization of interpolation polynomials (having specified tangents as well as specified points).
from above equation in matrix form: The coefficients are derived as where is the notation for divided differences.
The form of n-th coefficient is assumed for proof by mathematical induction.
Hence these paths can be morphed to start from the leftmost corner and end in a common point.
consecutively arranged points, equivalent to Newton's forward interpolation formula:
consecutively arranged points, equivalent to Newton's backward interpolation formula:
Several authors have therefore proposed algorithms which exploit the structure of the Vandermonde matrix to compute numerically stable solutions in O(n2) operations instead of the O(n3) required by Gaussian elimination.
[7][8][9] These methods rely on constructing first a Newton interpolation of the polynomial and then converting it to a monomial form.
To find the interpolation polynomial p(x) in the vector space P(n) of polynomials of degree n, we may use the usual monomial basis for P(n) and invert the Vandermonde matrix by Gaussian elimination, giving a computational cost of O(n3) operations.
Another method is preferred when the aim is not to compute the coefficients of p(x), but only a single value p(a) at a point x = a not in the original data set.
, we can use the same coefficients to find the interpolating polynomial for a second set of data points
The case of equally spaced points can also be treated by the method of finite differences.
of degree d defines a sequence of values at positive integer points,
.Furthermore, there is a Lagrange remainder form of the error, for a function f which is n + 1 times continuously differentiable on a closed interval
This error bound suggests choosing the interpolation points xi to minimize the product
This parallels the reasoning behind the Lagrange remainder term in the Taylor theorem; in fact, the Taylor remainder is a special case of interpolation error when all interpolation nodes xi are identical.
Thus, the maximum error will occur at some point in the interval between two successive nodes.
Convergence may be understood in different ways, e.g. pointwise, uniform or in some integral norm.
The situation is rather bad for equidistant nodes, in that uniform convergence is not even guaranteed for infinitely differentiable functions.
Another example is the function f(x) = |x| on the interval [−1, 1], for which the interpolating polynomials do not even converge pointwise except at the three points x = ±1, 0.
The following result seems to give a rather encouraging answer: Theorem — For any function f(x) continuous on an interval [a,b] there exists a table of nodes for which the sequence of interpolating polynomials
But this is true due to a special property of polynomials of best approximation known from the equioscillation theorem.
The defect of this method, however, is that interpolation nodes should be calculated anew for each new function f(x), but the algorithm is hard to be implemented numerically.
Does there exist a single table of nodes for which the sequence of interpolating polynomials converge to any continuous function f(x)?
The answer is unfortunately negative: Theorem — For any table of nodes there is a continuous function f(x) on an interval [a, b] for which the sequence of interpolating polynomials diverges on [a,b].
For better Chebyshev nodes, however, such an example is much harder to find due to the following result: Theorem — For every absolutely continuous function on [−1, 1] the sequence of interpolating polynomials constructed on Chebyshev nodes converges to f(x) uniformly.
[15] Runge's phenomenon shows that for high values of n, the interpolation polynomial may oscillate wildly between the data points.
Hermite interpolation problems are those where not only the values of the polynomial p at the nodes are given, but also all derivatives up to a given order.
Birkhoff interpolation is a further generalization where only derivatives of some orders are prescribed, not necessarily all orders from 0 to a k. Collocation methods for the solution of differential and integral equations are based on polynomial interpolation.
