HyperAI
HomeNewsLatest PapersTutorialsDatasetsWikiSOTALLM ModelsGPU LeaderboardEvents
Search
About
HyperAI

Polynomial Interopolation

Interpolation is also called "interpolation method". It uses the function values of function f(x) at several known points in a certain interval to make an appropriate specific function, and uses the value of this specific function as the approximate value of function f(x) at other points in the interval. This method is called interpolation. If this specific function is a polynomial, it is called polynomial interpolation. Several commonly used polynomial interpolation methods are: direct method, Lagrange interpolation method and Newton interpolation method.

definition

Data points (xi,yi), any two of which xi They are all different, and you need to find a satisfying

P(xi）=yi, i=0,…, n

A polynomial of order p that is no greater than order n. The uniqueness theorem states that there is one and only one such polynomial of order p.

In more complex terms, this polynomial can be expressed as follows: for n+1 interpolation points (xi), polynomial interpolation defines a linear bijection

{\displaystyle L_{n}:\mathbb {K} ^{n+1}\to \Pi _{n}}

in {\displaystyle \Pi _{n}} is less than or equal to n The vector space of polynomials.

In practical applications, these interpolation points may come from data obtained from an experimental measurement, or from the value of a complex function y=f(x). By calculating the interpolation polynomial, we can find the rules between these experimental data, or use a simple polynomial function y=P(z) to approximate a complex function y=f(x).

Constructing a polynomial interpolant

Assume that the interpolation polynomial is of the form

{\displaystyle p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}.\qquad (1)}

p Interpolating data points means

{\displaystyle p(x_{i})=y_{i}\qquad {\mbox{for all }}i\in \left\{0,1,\dots ,n\right\}.}

If we substitute into equation (1), we get the coefficients {\displaystyle a_{k}} The linear equation system of{\displaystyle {\begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&x_{0}^{n-2}&\ldots &x_{0}&1\\x_{1}^{n}&x_{1}^{n-1}&x_{1}^{n-2}&\ldots &x_{1}&1\\\vdots &\vdots &\vdots &&\vdots &\vdots \\x_{n}^{n}&x_{n}^{n-1}&x_{n}^{n-2}&\ldots &x_{n}&1\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.}

To construct the interpolation polynomial {\displaystyle p(x)}, to solve this system calculate the coefficients {\displaystyle a_{k}}.

The matrix on the left is usually called the Vandermonde matrix, and its determinant is not zero, which proves the uniqueness theorem: there is only one interpolating polynomial.

Applications of Polynomial Interpolation

Polynomials can be used to approximate complex curves, such as text in typography, from a few given data points. A related application is the estimation of the natural logarithm and trigonometric functions: select a few known data points, build a lookup table, and then interpolate between these data points. This allows very fast calculations. Polynomial interpolation is also the basis of algorithms in numerical integration and numerical ordinary differential equations.

Polynomial interpolation is also critical in sub-quadratic multiplication and squaring operations. For example, a = f(x) = a0x0 + a1x1 + … and b = g(x) = b0x0 + b1x1 + … then the product ab equal W(x) = f(x)g(x). Interpolation based on these points will give W(x) and the product ab For Karatchuba multiplication, this technique is faster than quadratic multiplication for ordinary numbers of inputs, especially when implemented in parallel hardware.

References

【1】https://zh.wikipedia.org/wiki/