In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points in the dataset. Given a set of n + 1 data points ( x 0 , y 0 ) , … , ( x n , y n ) {\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})} , with no two x j {\displaystyle x_{j}} the same, a polynomial function p ( x ) = a 0 + a 1 x + ⋯ + a n x n {\displaystyle p(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}} is said to interpolate the data if p ( x j ) = y j {\displaystyle p(x_{j})=y_{j}} for each j ∈ { 0 , 1 , … , n } {\displaystyle j\in \{0,1,\dotsc ,n\}} . There is always a unique such polynomial, commonly given by two explicit formulas, the Lagrange polynomials and Newton polynomials.
Applications The original use of interpolation polynomials was to approximate values of important transcendental functions such as natural logarithm and trigonometric functions. Starting with a few accurately computed data points, the corresponding interpolation polynomial will approximate the function at an arbitrary nearby point. Polynomial interpolation also forms the basis for algorithms in numerical quadrature (Simpson's rule) and numerical ordinary differential equations (multigrid methods). 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). In numerical analysis, polynomial interpolation is essential to perform sub-quadratic multiplication and squaring, such as Karatsuba multiplication and Toom–Cook multiplication, where interpolation through points on a product polynomial yields the specific product required. For example, given a = f(x) = a0x0 + a1x1 + ··· and b = g(x) = b0x0 + b1x1 + ···, the product ab is a specific value of W(x) = f(x)g(x). One may easily find points along W(x) at small values of x, and interpolation based on those points will yield the terms of W(x) and the specific product ab. As fomulated in Karatsuba multiplication, this technique is substantially faster than quadratic multiplication, even for modest-sized inputs, especially on parallel hardware. In computer science, polynomial interpolation also leads to algorithms for secure multi party computation and secret sharing.
Interpolation theorem For any n + 1 {\displaystyle n+1} bivariate data points ( x 0 , y 0 ) , … , ( x n , y n ) ∈ R 2 {\displaystyle (x_{0},y_{0}),\dotsc ,(x_{n},y_{n})\in \mathbb {R} ^{2}} , where no two x j {\displaystyle x_{j}} are the same, there exists a unique polynomial p ( x ) {\displaystyle p(x)} of degree at most n {\displaystyle n} that interpolates these points, i.e. p ( x 0 ) = y 0 , … , p ( x n ) = y n {\displaystyle p(x_{0})=y_{0},\ldots ,p(x_{n})=y_{n}} . Equivalently, for a fixed choice of interpolation nodes x j {\displaystyle x_{j}} , polynomial interpolation defines a linear bijection L n {\displaystyle L_{n}} between the (n+1)-tuples of real-number values ( y 0 , … , y n ) ∈ R n + 1 {\displaystyle (y_{0},\ldots ,y_{n})\in \mathbb {R} ^{n+1}} and the vector space P ( n ) {\displaystyle P(n)} of real polynomials of degree at most n:
… excerpt ends here. Continue reading the full article.
