Interpolation by algebraic polynomials

Interpolation by the algebraic polynomials of the function f (x) on the interval [a, b] —constructs the polynomial P _n (x) of degree less _than or equal to n , taking f (x _i ):

$P_{n}(x_{i})=f(x_{i}),\quad i=0,1,...,n$ ${\ displaystyle P_ {n} (x_ {i}) = f (x_ {i}), \ quad i = 0,1, ..., n}$ ${\ displaystyle P_ {n} (x_ {i}) = f (x_ {i}), \ quad i = 0,1, ..., n}$

The system of equations determining the coefficients of such a polynomial has the form

$P_{n}(x_{i})=a_{0}+a_{1}x_{i}+a_{2}x_{i}^{2}+\ldots +a_{n}x_{i}^{n}=f(x_{i}),\quad i=0,1,...,n$ ${\ displaystyle P_ {n} (x_ {i}) = a_ {0} + a_ {1} x_ {i} + a_ {2} x_ {i} ^ {2} + \ ldots + a_ {n} x_ { i} ^ {n} = f (x_ {i}), \ quad i = 0,1, ..., n}$ ${\ displaystyle P_ {n} (x_ {i}) = a_ {0} + a_ {1} x_ {i} + a_ {2} x_ {i} ^ {2} + \ ldots + a_ {n} x_ { i} ^ {n} = f (x_ {i}), \ quad i = 0,1, ..., n}$

Its determinant is the determinant of Vandermonde .

$\triangle ={\begin{vmatrix}1&x_{0}&x_{0}^{2}&...&x_{0}^{n}\\1&x_{1}&x_{1}^{2}&...&x_{1}^{n}\\.......\\1&x_{n}&x_{n}^{2}&...&x_{n}^{n}\end{vmatrix}}=\prod _{i,j=0 \atop i>j}^{n}(x_{i}-x_{j})$ ${\ displaystyle \ triangle = {\ begin {vmatrix} 1 & x_ {0} & x_ {0} ^ {2} & ... & x_ {0} ^ {n} \\ 1 & x_ {1} & x_ {1} ^ {2} & ... & x_ {1} ^ {n} \\ ....... \\ 1 & x_ {n} & x_ {n} ^ {2} & ... & x_ {n} ^ {n} \ end { vmatrix}} = \ prod _ {i, j = 0 \ atop i> j} ^ {n} (x_ {i} -x_ {j})}$ ${\ displaystyle \ triangle = {\ begin {vmatrix} 1 & x_ {0} & x_ {0} ^ {2} & ... & x_ {0} ^ {n} \\ 1 & x_ {1} & x_ {1} ^ {2} & ... & x_ {1} ^ {n} \\ ....... \\ 1 & x_ {n} & x_ {n} ^ {2} & ... & x_ {n} ^ {n} \ end { vmatrix}} = \ prod _ {i, j = 0 \ atop i> j} ^ {n} (x_ {i} -x_ {j})}$

It is nonzero for any pairwise different values of x _i , and interpolation of the function f from its values at nodes x _i using the polynomial P _n (x) is always possible and unique.

Content

Application

The resulting interpolation formula $f(x)\approx P_{n}(x)$ ${\ displaystyle f (x) \ approx P_ {n} (x)}$ they are often used for approximate calculation of the values of the function f for the values of the argument x other than the interpolation nodes. In this case, interpolation is distinguished in the narrow sense, when $x\in \left[x_{0},x_{n}\right]$ ${\ displaystyle x \ in \ left [x_ {0}, x_ {n} \ right]}$ and extrapolation when $x\in \left[a,b\right]$ ${\ displaystyle x \ in \ left [a, b \ right]}$ , $x\not \in \left[x_{0},x_{n}\right]$ ${\ displaystyle x \ not \ in \ left [x_ {0}, x_ {n} \ right]}$

Interpolation Problem

Let in space are given $n$ ${\ displaystyle n}$ points $P_{1},P_{2},\dots ,P_{n}$ ${\ displaystyle P_ {1}, P_ {2}, \ dots, P_ {n}}$ which in some coordinate system have radius vectors $\mathbf {r} _{1},\mathbf {r} _{2},\dots ,\mathbf {r} _{n}$ ${\ displaystyle \ mathbf {r} _ {1}, \ mathbf {r} _ {2}, \ dots, \ mathbf {r} _ {n}}$ .

The task of interpolation is to construct a curve passing through the indicated points in the indicated order.

Problem

An infinite number of curves can be drawn through a fixed set of points; therefore, the interpolation problem does not have a unique solution.

We will build the curves in the form $\mathbf {r} (t)$ ${\ displaystyle \ mathbf {r} (t)}$ where parameter $t$ ${\ displaystyle t}$ changes over a certain segment $[a,b]$ ${\ displaystyle [a, b]}$ : $a\leq t\leq b$ ${\ displaystyle a \ leq t \ leq b}$ . We introduce on the segment $[a,b]$ ${\ displaystyle [a, b]}$ the grid $\{t_{i}\}$ ${\ displaystyle \ {t_ {i} \}}$ of $n$ ${\ displaystyle n}$ points: $a=t_{1}<t_{2}<t_{3}<\dots <t_{n}=b$ ${\ displaystyle a = t_ {1} <t_ {2} <t_ {3} <\ dots <t_ {n} = b}$ and require that with the value of the parameter $t=t_{i}$ ${\ displaystyle t = t_ {i}}$ the curve passed through a point $P_{i}$ ${\ displaystyle P_ {i}}$ , so that $\mathbf {r} (t_{i})=\mathbf {r} _{i}$ ${\ displaystyle \ mathbf {r} (t_ {i}) = \ mathbf {r} _ {i}}$ .

The introduction of parameterization and grids can be done in various ways. Usually choose either a uniform grid, assuming $a=0$ ${\ displaystyle a = 0}$ , $b=n-1$ ${\ displaystyle b = n-1}$ , $t_{i}=i-1$ ${\ displaystyle t_ {i} = i-1}$ , or, more preferably, connect the points with segments and as the difference of the parameter values $t_{i+1}-t_{i}$ ${\ displaystyle t_ {i + 1} -t_ {i}}$ take the length of the segment $\mathbf {r} _{i+1}-\mathbf {r} _{i}$ ${\ displaystyle \ mathbf {r} _ {i + 1} - \ mathbf {r} _ {i}}$ .

One common interpolation technique is to use a polynomial curve from $t$ ${\ displaystyle t}$ degrees of $n-1$ ${\ displaystyle n-1}$ , i.e. as a function

$\mathbf {r} (t)=\mathbf {p} ^{(n-1)}(t)=\sum _{k=1}^{n}\mathbf {a} _{k}t^{n-k}$ ${\ displaystyle \ mathbf {r} (t) = \ mathbf {p} ^ {(n-1)} (t) = \ sum _ {k = 1} ^ {n} \ mathbf {a} _ {k} t ^ {nk}}$

Polynomial has $n$ ${\ displaystyle n}$ coefficients $\mathbf {a} _{k}$ ${\ displaystyle \ mathbf {a} _ {k}}$ which can be found from the conditions $\mathbf {r} (t_{i})=\mathbf {r} _{i}$ ${\ displaystyle \ mathbf {r} (t_ {i}) = \ mathbf {r} _ {i}}$ .

These conditions lead to a system of linear equations for the coefficients $\mathbf {a} _{k}$ ${\ displaystyle \ mathbf {a} _ {k}}$

${\begin{pmatrix}1&t_{1}&t_{1}^{2}&\ldots &t_{1}^{n-1}\\1&t_{2}&t_{2}^{2}&\ldots &t_{2}^{n-1}\\\vdots &\vdots &\vdots &&\vdots \\1&t_{n}&t_{n}^{2}&\ldots &t_{n}^{n-1}\end{pmatrix}}{\begin{pmatrix}\mathbf {a} _{n}\\\mathbf {a} _{n-1}\\\vdots \\\mathbf {a} _{1}\end{pmatrix}}={\begin{pmatrix}\mathbf {r} _{1}\\\mathbf {r} _{2}\\\vdots \\\mathbf {r} _{n}\end{pmatrix}}$ ${\ displaystyle {\ begin {pmatrix} 1 & t_ {1} & t_ {1} ^ {2} & \ ldots & t_ {1} ^ {n-1} \\ 1 & t_ {2} & t_ {2} ^ {2} & \ ldots & t_ {2} ^ {n-1} \\\ vdots & \ vdots & \ vdots && \ vdots \\ 1 & t_ {n} & t_ {n} ^ {2} & \ ldots & t_ {n} ^ {n-1 } \ end {pmatrix}} {\ begin {pmatrix} \ mathbf {a} _ {n} \\\ mathbf {a} _ {n-1} \\\ vdots \\\ mathbf {a} _ {1} \ end {pmatrix}} = {\ begin {pmatrix} \ mathbf {r} _ {1} \\\ mathbf {r} _ {2} \\\ vdots \\\ mathbf {r} _ {n} \ end {pmatrix}}}$

Note that three systems of equations need to be solved: for $x$ ${\ displaystyle x}$ , $y$ ${\ displaystyle y}$ and $z$ ${\ displaystyle z}$ coordinates. All of them have one matrix of coefficients, reversing which, according to the values of radius vectors $\mathbf {r} _{i}$ ${\ displaystyle \ mathbf {r} _ {i}}$ points are calculated vectors $\mathbf {a} _{k}$ ${\ displaystyle \ mathbf {a} _ {k}}$ polynomial coefficients. Matrix determinant

$W(t_{1},t_{2},\ldots ,t_{n})={\begin{vmatrix}1&t_{1}&t_{1}^{2}&\ldots &t_{1}^{n-1}\\1&t_{2}&t_{2}^{2}&\ldots &t_{2}^{n-1}\\\vdots &\vdots &\vdots &&\vdots \\1&t_{n}&t_{n}^{2}&\ldots &t_{n}^{n-1}\end{vmatrix}}=\prod _{i,j,i>j}(t_{i}-t_{j})$ ${\ displaystyle W (t_ {1}, t_ {2}, \ ldots, t_ {n}) = {\ begin {vmatrix} 1 & t_ {1} & t_ {1} ^ {2} & \ ldots & t_ {1} ^ {n-1} \\ 1 & t_ {2} & t_ {2} ^ {2} & \ ldots & t_ {2} ^ {n-1} \\\ vdots & \ vdots & \ vdots && \ vdots \\ 1 & t_ {n } & t_ {n} ^ {2} & \ ldots & t_ {n} ^ {n-1} \ end {vmatrix}} = \ prod _ {i, j, i> j} (t_ {i} -t_ {j })}$

called the determinant of Vandermond . If the grid nodes do not match, it is nonzero, so the system of equations has a solution.

In addition to direct matrix inversion, there are several other ways to calculate the interpolation polynomial. Due to the uniqueness of the polynomial, we are talking about various forms of its notation.

Benefits

For a given set of points and parameter grid, the curve is constructed uniquely.
The curve is interpolation, that is, it passes through all given points.
The curve has continuous derivatives of any order.

Weaknesses

As the number of points increases, the order of the polynomial increases, and with it, the number of operations that must be performed to calculate the point on the curve increases.
As the number of points increases, oscillations can occur in the interpolation curve (see example below).

Example

Interpolation on a sequence of grids. Runge example.

A classic example ( Runge ) showing the appearance of oscillations in an interpolation polynomial is interpolation on a uniform grid of function values

$f(x)={\frac {1}{1+x^{2}}}$ ${\ displaystyle f (x) = {\ frac {1} {1 + x ^ {2}}}}$

We introduce on the segment $[-5,5]$ ${\ displaystyle [-5.5]}$ uniform grid $x_{i}=-5+(i-1)h$ ${\ displaystyle x_ {i} = - 5+ (i-1) h}$ , $h=10/(n-1)$ ${\ displaystyle h = 10 / (n-1)}$ , $1\leq i\leq n$ ${\ displaystyle 1 \ leq i \ leq n}$ and consider the behavior of the polynomial

$y(x)=\sum _{i=1}^{n}a_{i}x^{n-i}$ ${\ displaystyle y (x) = \ sum _ {i = 1} ^ {n} a_ {i} x ^ {ni}}$

which at points $x_{i}$ ${\ displaystyle x_ {i}}$ takes values $y_{i}=1/(1+x_{i}^{2})$ ${\ displaystyle y_ {i} = 1 / (1 + x_ {i} ^ {2})}$ . The figure shows graphs of the function itself (dash-dotted line) and three interpolation curves for $n=3,5,9$ ${\ displaystyle n = 3,5,9}$ :

grid interpolation $x_{1}=-5,x_{2}=0,x_{3}=5$ ${\ displaystyle x_ {1} = - 5, x_ {2} = 0, x_ {3} = 5}$ - quadratic parabola;
grid interpolation $x_{1}=-5,x_{2}=-2.5,x_{3}=0,x_{4}=2.5,x_{5}=5$ ${\ displaystyle x_ {1} = - 5, x_ {2} = - 2.5, x_ {3} = 0, x_ {4} = 2.5, x_ {5} = 5}$ - polynomial of the fourth degree;
grid interpolation $x_{1}=-5,x_{2}=-3.75,x_{3}=-2.5,x_{4}=-1.25,x_{5}=0,x_{6}=1.25,x_{7}=2.5,x_{8}=3.75,x_{9}=5$ ${\ displaystyle x_ {1} = - 5, x_ {2} = - 3.75, x_ {3} = - 2.5, x_ {4} = - 1.25, x_ {5} = 0, x_ {6} = 1.25, x_ {7} = 2.5, x_ {8} = 3.75, x_ {9} = 5}$ - polynomial of the eighth degree.

The values of the interpolation polynomial even for smooth functions at intermediate points can strongly deviate from the values of the function itself.